0%

用到了 Bellman-Ford Shortist Path Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
using namespace std;
#define INF 1e9

struct edge{
int from,to,cost;
};

int d[505],c[505],n,m;
edge a[10050];

void shortistPath(){
while(1){
bool update=false;
for(int i=0;i<2*m;i++){
if(d[a[i].from]!=INF &&
d[a[i].to]>d[a[i].from]+a[i].cost+c[a[i].to]){
d[a[i].to]=d[a[i].from]+a[i].cost+c[a[i].to];
update=true;
}
}
if(!update) break;
}
}

int main(){
ios::sync_with_stdio(false);cin.tie(0);

cin>>n;
for(int i=1;i<=n;i++){
cin>>c[i];
d[i]=INF;
}
cin>>m;
for(int i=0;i<m;i++){
cin>>a[i].from>>a[i].to>>a[i].cost;
a[m+i].from=a[i].to;
a[m+i].to=a[i].from;
a[m+i].cost=a[i].cost;
}
d[1]=0;
shortistPath();
if(d[n]!=INF){
cout<<d[n];
}else{
cout<<"-1";
}
return 0;
}
閱讀全文 »

關於樹狀圖的應用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;

int w[2000010]={0},st[10010],child[2000010][2],n,m;

int dfs(int a){
if(a>=n) return w[a];
w[a]=dfs(child[a][0])+dfs(child[a][1]);
return w[a];
}

int findBox(int stw,int a){
if(a>=n){
return a;
}
if(w[child[a][0]]<=w[child[a][1]]){
w[child[a][0]]+=stw;
return findBox(stw,child[a][0]);
}
w[child[a][1]]+=stw;
return findBox(stw,child[a][1]);
}

int main(){
ios::sync_with_stdio(false);cin.tie(0);

cin>>n>>m;
for(int i=0;i<n;i++) cin>>w[n+i];

for(int i=0;i<m;i++) cin>>st[i];

for(int i=1;i<n;i++){
int p,s,t;cin>>p>>s>>t;
child[p][0]=s;child[p][1]=t;
}
int root=1;
w[1]=dfs(root);
for(int i=0;i<m;i++){
cout<<findBox(st[i],root)<<" ";
}

return 0;
}
閱讀全文 »

樹狀圖的結構以及 DFS ( 深度優先搜索 ) ,另外用了 height[] 來儲存高度以降低複雜度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<(b);i++)

long long n;
vector<long long> child[100010];
long long p[100010],height[100010];

void dfs(long long a){
height[a]=0;
for(long long v:child[a]){
dfs(v);
height[a]=max(height[a],height[v]+1);
}
return;
}

int main(){
cin>>n;
For(i,1,n+1){
long long chN;cin>>chN;
For(j,0,chN){
long long ch;cin>>ch;
child[i].push_back(ch);
p[ch]=i;
}
}
int root;
for(root=1;root<=n;root++){
if(p[root]==0) break;
}
dfs(root);
long long total=0;
for(int i=1;i<=n;i++) total+=height[i];
cout<<root<<"\n";
cout<<total<<"\n";
return 0;
}
閱讀全文 »

直接附上範例

1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>
using namespace std;

int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
for(int i=0;i<1e6;i++){
cout<<i;
}
}
閱讀全文 »

計算前綴和以及二分搜,以下為程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;

int main(){
ios::sync_with_stdio(false);

int n,m;cin>>n>>m;

int q,pSum[200010];
cin>>pSum[0];
for(int i=1;i<n;i++){
cin>>pSum[i];
pSum[i]=pSum[i]+pSum[i-1];
}
int pos=0;
for(int i=0;i<m;i++){
cin>>q;
if(pos!=0){
if(q>(pSum[n-1]-pSum[pos-1])){
q-=(pSum[n-1]-pSum[pos-1]);
q%=pSum[n-1];
pos=lower_bound(pSum,pSum+n,q)-pSum+1;
}else{
pos=lower_bound(pSum,pSum+n,q+pSum[pos-1])-pSum+1;
}
}else{
q%=pSum[n-1];
pos=lower_bound(pSum,pSum+n,q)-pSum+1;
}
pos%=n;
}
cout<<pos;
return 0;
}
閱讀全文 »

有意點點類似 BFS ,不過一次只會有一個分支,以下是程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<deque>

#define MAX 1000000
using namespace std;

struct step{
long long x,y;
};

int main(){
int n,m,min=MAX+1;
cin>>n>>m;
long long sum=0;
step best;
int mp[110][110]={MAX};

for(int i=0;i<110;i++){
for(int j=0;j<110;j++){
mp[i][j]=MAX;
}
}

for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
if(min>mp[i][j]){
min=mp[i][j];
best.x=j;best.y=i;sum=min;
}
}
}

deque<step> st;
st.push_front(best);
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

while(!st.empty()){
step now=st.back();
st.pop_back();

min=MAX;

mp[now.y][now.x]=MAX;
for(int i=0;i<4;i++){
step next;
next.x=now.x+dx[i];
next.y=now.y+dy[i];
if(mp[next.y][next.x]<min){
min=mp[next.y][next.x];
best.x=next.x;best.y=next.y;
}
}
if(min==MAX){
continue;
}else{
sum+=mp[best.y][best.x];
st.push_front(best);
}

}
cout<<sum;
return 0;
}
閱讀全文 »

題目連結:c292. APCS2017-0304-3數字龍捲風 - 高中生程式解題系統

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>

int map[101][101];
bool visit[101][101]={false};

int main(){
int n,r;
std::cin>>n>>r;

for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
std::cin>>map[i][j];
}
}

int row=n/2,col=n/2;
for(int i=0;i<n*n;i++){
visit[row][col]=true;
std::cout<<map[row][col];

switch(r){
case 0:
//left
col--;
if(!visit[row-1][col]){
r++;
}
break;
case 1:
//up
row--;
if(!visit[row][col+1]){
r++;
}
break;
case 2:
//right
col++;
if(!visit[row+1][col]){
r++;
}
break;
case 3:
//down
row++;
if(!visit[row][col-1]){
r=0;
}
break;
}
}
return 0;
}
閱讀全文 »