NOIP2014-5-10模拟赛

时间:2022-12-17 11:30:34

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:

直接模拟即可

NOIP2014-5-10模拟赛NOIP2014-5-10模拟赛
 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 }
Code1

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)

NOIP2014-5-10模拟赛NOIP2014-5-10模拟赛
 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 }
Code2

T3:

这题就是个最短路,稍微修改下即可

我第一次用dijk写的,结果T了6个点

NOIP2014-5-10模拟赛NOIP2014-5-10模拟赛
  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 }
Code3

后来改用SPFA,AC了

NOIP2014-5-10模拟赛NOIP2014-5-10模拟赛
  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 }
Code4

可见SPFA效率比dijk高很多啊。。。