Problem 1 机器人(robot.cpp/c/pas)
【题目描述】
早苗入手了最新的Gundam模型。最新款自然有着与以往不同的功能，那就是它能够自动行走，厉害吧。
早苗的新模型可以按照输入的命令进行移动，命令包括‘E’、‘S’、‘W’、‘N’四种，分别对应东南西北。执行某个命令时，它会向对应方向移动一个单位。作为新型机器人，它可以执行命令串。对于输入的命令串，每一秒它会按命令行动一次。执行完命令串的最后一个命令后，会自动从头开始循环。在0时刻时机器人位于（0,0）。求T秒后机器人所在位置坐标。
【输入格式】
第1行：一个字符串，表示早苗输入的命令串，保证至少有1个命令
第2行：一个正整数T
【输出格式】
2个整数，表示T秒时，机器人的坐标。
【样例输入】
NSWWNSNEEWN
12
【样例输出】
-1 3
【数据范围】
对于60%的数据 T<=500,000 且命令串长度<=5,000
对于100%的数据 T<=2,000,000,000 且命令串长度<=5,000
【注意】
向东移动，坐标改变改变为(X+1,Y);
向南移动，坐标改变改变为(X,Y-1);
向西移动，坐标改变改变为(X-1,Y);
向北移动，坐标改变改变为(X,Y+1);
Problem 2 数列(seq.cpp/c/pas)
【题目描述】
a[1]=a[2]=a[3]=1
a[x]=a[x-3]+a[x-1] (x>3)
求a数列的第n项对1000000007（10^9+7）取余的值。
【输入格式】
第一行一个整数T，表示询问个数。
以下T行，每行一个正整数n。
【输出格式】
每行输出一个非负整数表示答案。
【样例输入】
3
6
8
10
【样例输出】
4
9
19
【数据范围】
对于30%的数据 n<=100；
对于60%的数据 n<=2*10^7；
对于100%的数据 T<=100，n<=2*10^9；
Problem 3 虫洞(holes.cpp/c/pas)
【题目描述】
N个虫洞，M条单向跃迁路径。从一个虫洞沿跃迁路径到另一个虫洞需要消耗一定量的燃料和1单位时间。虫洞有白洞和黑洞之分。设一条跃迁路径两端的虫洞质量差为delta。
1.从白洞跃迁到黑洞，消耗的燃料值减少delta，若该条路径消耗的燃料值变为负数的话，取为0。
2.从黑洞跃迁到白洞，消耗的燃料值增加delta。
3.路径两端均为黑洞或白洞，消耗的燃料值不变化。
作为压轴题，自然不会是如此简单的最短路问题，所以每过1单位时间黑洞变为白洞，白洞变为黑洞。在飞行过程中，可以选择在一个虫洞停留1个单位时间，如果当前为白洞，则不消耗燃料，否则消耗s[i]的燃料。现在请你求出从虫洞1到N最少的燃料消耗，保证一定存在1到N的路线。
【输入格式】
第1行：2个正整数N,M
第2行：N个整数，第i个为0表示虫洞i开始时为白洞，1表示黑洞。
第3行：N个整数，第i个数表示虫洞i的质量w[i]。
第4行：N个整数，第i个数表示在虫洞i停留消耗的燃料s[i]。
第5..M+4行：每行3个整数，u,v,k，表示在没有影响的情况下，从虫洞u到虫洞v需要消耗燃料k。
【输出格式】
一个整数，表示最少的燃料消耗。
【样例输入】
4 5
1 0 1 0
10 10 100 10
5 20 15 10
1 2 30
2 3 40
1 3 20
1 4 200
3 4 200
【样例输出】
130
【数据范围】
对于30%的数据： 1<=N<=100,1<=M<=500
对于60%的数据： 1<=N<=1000,1<=M<=5000
对于100%的数据： 1<=N<=5000，1<=M<=30000
其中20%的数据为1<=N<=3000的链
1<=u,v<=N, 1<=k,w[i],s[i]<=200
【样例说明】
按照1->3->4的路线。
T1:
直接模拟即可
1 #include<cstdio> 2 #include<cstdlib> 3 #include<algorithm> 4 #include<cstring> 5 #define MAXN 5000 6 using namespace std; 7 int dx,dy; 8 int gx[4]={1,0,-1,0}; 9 int gy[4]={0,-1,0,1}; 10 //E S W N 11 int x,y; 12 int T; 13 char s[MAXN]; 14 15 int main() 16 { 17 scanf("%s",s+1); 18 scanf("%d",&T); 19 int len=strlen(s+1); 20 for(int i=1;i<=len;i++){ 21 if('E'==s[i]){ 22 dx+=gx[0]; 23 dy+=gy[0]; 24 } 25 else if('S'==s[i]){ 26 dx+=gx[1]; 27 dy+=gy[1]; 28 } 29 else if('W'==s[i]){ 30 dx+=gx[2]; 31 dy+=gy[2]; 32 } 33 else{ 34 dx+=gx[3]; 35 dy+=gy[3]; 36 } 37 } 38 int q=T/len; 39 int p=T%len; 40 x+=(dx*q),y+=(dy*q); 41 if(p){ 42 for(int i=1;i<=p;i++){ 43 if('E'==s[i]){ 44 x+=gx[0]; 45 y+=gy[0]; 46 } 47 else if('S'==s[i]){ 48 x+=gx[1]; 49 y+=gy[1]; 50 } 51 else if('W'==s[i]){ 52 x+=gx[2]; 53 y+=gy[2]; 54 } 55 else{ 56 x+=gx[3]; 57 y+=gy[3]; 58 } 59 } 60 } 61 printf("%d %d\n",x,y); 62 return 0; 63 }
T2:
用矩阵快速幂优化，得公式
f x 1 0 1 f 3
(f x-1)=(1 0 0) ^ (x-3) * (f 2)
f x-2 0 1 0 f 1
时间复杂度O(T*logn)
1 #include<cstdio> 2 #include<cstdlib> 3 #include<algorithm> 4 #include<cstring> 5 #define MOD 1000000007 6 #define ll long long 7 using namespace std; 8 struct Mat{ 9 ll s[3][3]; 10 Mat(){ 11 memset(s,0,sizeof(s)); 12 } 13 friend Mat operator * (const Mat &A,const Mat &B){ 14 Mat ret; 15 for(int i=0;i<3;i++){ 16 for(int j=0;j<3;j++){ 17 for(int k=0;k<3;k++){ 18 ret.s[i][j]=(ret.s[i][j]+(A.s[i][k]*B.s[k][j])%MOD)%MOD; 19 } 20 } 21 } 22 return ret; 23 } 24 Mat operator = (const Mat &A){ 25 for(int i=0;i<3;i++){ 26 for(int j=0;j<3;j++){ 27 s[i][j]=A.s[i][j]; 28 } 29 } 30 } 31 }; 32 int T; 33 Mat Power(Mat A,int p){ 34 if(1==p){ 35 return A; 36 } 37 if(p&1){ 38 return Power(A*A,p>>1)*A; 39 } 40 else{ 41 return Power(A*A,p>>1); 42 } 43 } 44 int main() 45 { 46 // freopen("data.in","r",stdin); 47 Mat A; 48 A.s[0][0]=1,A.s[0][1]=0,A.s[0][2]=1; 49 A.s[1][0]=1,A.s[1][1]=0,A.s[1][2]=0; 50 A.s[2][0]=0,A.s[2][1]=1,A.s[2][2]=0; 51 scanf("%d",&T); 52 for(int i=1;i<=T;i++){ 53 int n; 54 scanf("%d",&n); 55 if(1==n||2==n||3==n){ 56 printf("1\n"); 57 continue; 58 } 59 Mat t=Power(A,n-3); 60 ll ans=(t.s[0][0]+t.s[0][1])%MOD; 61 ans=(ans+t.s[0][2])%MOD; 62 printf("%lld\n",ans); 63 } 64 return 0; 65 }
T3:
这题就是个最短路，稍微修改下即可
我第一次用dijk写的，结果T了6个点
1 #include<cstdio> 2 #include<cstdlib> 3 #include<algorithm> 4 #include<cstring> 5 #include<queue> 6 #define MAXN 5005 7 #define MAXM 30005 8 #define INF 0x7f7f7f7f 9 using namespace std; 10 struct Node{ 11 int s,u; 12 int d; 13 Node(int ss,int uu,int dd){ 14 s=ss,u=uu,d=dd; 15 } 16 Node(){ 17 s=u=0; 18 d=INF; 19 } 20 friend bool operator < (const Node &p1,const Node &p2){ 21 return (p1.d<p2.d); 22 } 23 friend bool operator > (const Node &p1,const Node &p2){ 24 return !(p1.d<p2.d); 25 } 26 }; 27 priority_queue<Node> q; 28 int d[2][MAXN]; 29 int V,E; 30 int s[MAXN]; 31 int w[MAXN]; 32 int first[MAXN],Next[MAXM],to[MAXM],W[MAXM],cnt; 33 int p[2][MAXN]; 34 // 0 not change 1 change 35 int Abs(int x){ 36 return (x>0)?x:-x; 37 } 38 void Add(int x,int y,int w){ 39 Next[++cnt]=first[x]; first[x]=cnt; to[cnt]=y; W[cnt]=w; 40 //single edge 41 } 42 void dijk(){ 43 d[0][1]=0; 44 q.push(Node(0,1,0)); 45 while(!q.empty()){ 46 Node t=q.top(); q.pop(); 47 // now using t.s 48 int ds=(!t.s); 49 int x=t.u; 50 if(d[t.s][t.u]!=t.d){ 51 continue; 52 } 53 //stay 54 if(!p[t.s][x]){ 55 if(d[ds][x]>d[t.s][x]){ 56 d[ds][x]=d[t.s][x]; 57 q.push(Node(ds,x,d[ds][x])); 58 } 59 } 60 else{ 61 if(d[ds][x]>d[t.s][x]+s[x]){ 62 d[ds][x]=d[t.s][x]+s[x]; 63 q.push(Node(ds,x,d[ds][x])); 64 } 65 } 66 for(int e=first[x];e;e=Next[e]){ 67 int y=to[e]; 68 int dw=W[e]; 69 if(p[t.s][x]!=p[t.s][y]){ 70 //0 white 1 black 71 //0->1 w-=delta w=max(w,0) 72 //1->0 w+=delta 73 if(!p[t.s][x]){ 74 dw-=Abs(w[x]-w[y]); 75 dw=max(dw,0); 76 } 77 else{ 78 dw+=Abs(w[x]-w[y]); 79 } 80 } 81 if(d[ds][y]>d[t.s][x]+dw){ 82 d[ds][y]=d[t.s][x]+dw; 83 q.push(Node(ds,y,d[ds][y])); 84 } 85 } 86 } 87 } 88 int main() 89 { 90 // freopen("data.in","r",stdin); 91 memset(d,0x7f,sizeof(d)); 92 scanf("%d%d",&V,&E); 93 for(int i=1;i<=V;i++){ 94 scanf("%d",&p[0][i]); 95 p[1][i]=(!p[0][i]); 96 } 97 for(int i=1;i<=V;i++){ 98 scanf("%d",&w[i]); 99 } 100 for(int i=1;i<=V;i++){ 101 scanf("%d",&s[i]); 102 } 103 for(int i=1;i<=E;i++){ 104 int x,y,k; 105 scanf("%d%d%d",&x,&y,&k); 106 Add(x,y,k); 107 } 108 dijk(); 109 int ans=min(d[0][V],d[1][V]); 110 printf("%d\n",ans); 111 return 0; 112 }
后来改用SPFA，AC了
1 #include<cstdio> 2 #include<cstdlib> 3 #include<algorithm> 4 #include<cstring> 5 #include<queue> 6 #define MAXN 5005 7 #define MAXM 30005 8 #define INF 0x7f7f7f7f 9 using namespace std; 10 struct Node{ 11 int s,u; 12 int d; 13 Node(int ss,int uu,int dd){ 14 s=ss,u=uu,d=dd; 15 } 16 Node(){ 17 s=u=0; 18 d=INF; 19 } 20 }; 21 int d[2][MAXN]; 22 bool b[2][MAXN]; 23 queue<Node> q; 24 int V,E; 25 int s[MAXN]; 26 int w[MAXN]; 27 int first[MAXN],Next[MAXM],to[MAXM],W[MAXM],cnt; 28 int p[2][MAXN]; 29 // 0 not change 1 change 30 int Abs(int x){ 31 return (x>0)?x:-x; 32 } 33 void Add(int x,int y,int w){ 34 Next[++cnt]=first[x]; first[x]=cnt; to[cnt]=y; W[cnt]=w; 35 //single edge 36 } 37 void SPFA(){ 38 d[0][1]=0; 39 b[0][1]=1; 40 q.push(Node(0,1,0)); 41 while(!q.empty()){ 42 Node t=q.front(); q.pop(); 43 int S=t.s; 44 int ds=(!S); 45 int x=t.u; 46 b[S][x]=0; 47 // now using t.s 48 //stay 49 if(!p[S][x]){ 50 if(d[ds][x]>d[S][x]){ 51 d[ds][x]=d[S][x]; 52 if(!b[ds][x]){ 53 b[ds][x]=1; 54 q.push(Node(ds,x,d[ds][x])); 55 } 56 } 57 } 58 else{ 59 if(d[ds][x]>d[S][x]+s[x]){ 60 d[ds][x]=d[S][x]+s[x]; 61 if(!b[ds][x]){ 62 b[ds][x]=1; 63 q.push(Node(ds,x,d[ds][x])); 64 } 65 } 66 } 67 for(int e=first[x];e;e=Next[e]){ 68 int y=to[e]; 69 int dw=W[e]; 70 if(p[S][x]!=p[S][y]){ 71 //0 white 1 black 72 //0->1 w-=delta w=max(w,0) 73 //1->0 w+=delta 74 if(!p[S][x]){ 75 dw-=Abs(w[x]-w[y]); 76 dw=max(dw,0); 77 } 78 else{ 79 dw+=Abs(w[x]-w[y]); 80 } 81 } 82 if(d[ds][y]>d[S][x]+dw){ 83 d[ds][y]=d[S][x]+dw; 84 if(!b[ds][y]){ 85 b[ds][y]=1; 86 q.push(Node(ds,y,d[ds][y])); 87 } 88 } 89 } 90 } 91 } 92 int main() 93 { 94 // freopen("data.in","r",stdin); 95 memset(d,0x7f,sizeof(d)); 96 scanf("%d%d",&V,&E); 97 for(int i=1;i<=V;i++){ 98 scanf("%d",&p[0][i]); 99 p[1][i]=(!p[0][i]); 100 } 101 for(int i=1;i<=V;i++){ 102 scanf("%d",&w[i]); 103 } 104 for(int i=1;i<=V;i++){ 105 scanf("%d",&s[i]); 106 } 107 for(int i=1;i<=E;i++){ 108 int x,y,k; 109 scanf("%d%d%d",&x,&y,&k); 110 Add(x,y,k); 111 } 112 SPFA(); 113 int ans=min(d[0][V],d[1][V]); 114 printf("%d\n",ans); 115 return 0; 116 }
可见SPFA效率比dijk高很多啊。。。