NOIP2014-5-10模拟赛

Problem 1 机器人(robot.cpp/c/pas)

【题目描述】

早苗入手了最新的Gundam模型。最新款自然有着与以往不同的功能，那就是它能够自动行走，厉害吧。

早苗的新模型可以按照输入的命令进行移动，命令包括‘E’、‘S’、‘W’、‘N’四种，分别对应东南西北。执行某个命令时，它会向对应方向移动一个单位。作为新型机器人，它可以执行命令串。对于输入的命令串，每一秒它会按命令行动一次。执行完命令串的最后一个命令后，会自动从头开始循环。在0时刻时机器人位于（0,0）。求T秒后机器人所在位置坐标。

【输入格式】

第1行：一个字符串，表示早苗输入的命令串，保证至少有1个命令

第2行：一个正整数T

【输出格式】

2个整数，表示T秒时，机器人的坐标。

【样例输入】

NSWWNSNEEWN

【样例输出】

-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。

【输出格式】

每行输出一个非负整数表示答案。

【样例输入】

【样例输出】

【数据范围】

对于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:

直接模拟即可

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<cstring>

 #define MAXN 5000

 using namespace std;

 int dx,dy;

 int gx[]={,,-,};

 int gy[]={,-,,};

          //E S W N

 int x,y;

 int T;

 char s[MAXN];

 int main()

 {

     scanf("%s",s+);

     scanf("%d",&T);

     int len=strlen(s+);

     for(int i=;i<=len;i++){

         if('E'==s[i]){

             dx+=gx[];

             dy+=gy[];

         }

         else if('S'==s[i]){

             dx+=gx[];

             dy+=gy[];

         }

         else if('W'==s[i]){

             dx+=gx[];

             dy+=gy[];

         }

         else{

             dx+=gx[];

             dy+=gy[];

         }

     }

     int q=T/len;

     int p=T%len;

     x+=(dx*q),y+=(dy*q);

     if(p){

         for(int i=;i<=p;i++){

             if('E'==s[i]){

                 x+=gx[];

                 y+=gy[];

             }

             else if('S'==s[i]){

                 x+=gx[];

                 y+=gy[];

             }

             else if('W'==s[i]){

                 x+=gx[];

                 y+=gy[];

             }

             else{

                 x+=gx[];

                 y+=gy[];

             }

         }

     }

     printf("%d %d\n",x,y);

     return ;

 }

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)

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<cstring>

 #define MOD 1000000007

 #define ll long long

 using namespace std;

 struct Mat{

     ll s[][];

     Mat(){

         memset(s,,sizeof(s));

     }

     friend Mat operator * (const Mat &A,const Mat &B){

         Mat ret;

         for(int i=;i<;i++){

             for(int j=;j<;j++){

                 for(int k=;k<;k++){

                     ret.s[i][j]=(ret.s[i][j]+(A.s[i][k]*B.s[k][j])%MOD)%MOD;

                 }

             }

         }

         return ret;

     }

     Mat operator = (const Mat &A){

         for(int i=;i<;i++){

             for(int j=;j<;j++){

                 s[i][j]=A.s[i][j];

             }

         }

     }

 };

 int T;

 Mat Power(Mat A,int p){

     if(==p){

         return A;

     }

     if(p&){

         return Power(A*A,p>>)*A;

     }

     else{

         return Power(A*A,p>>);

     }

 }

 int main()

 {

 //    freopen("data.in","r",stdin);

     Mat A;

     A.s[][]=,A.s[][]=,A.s[][]=;

     A.s[][]=,A.s[][]=,A.s[][]=;

     A.s[][]=,A.s[][]=,A.s[][]=;

     scanf("%d",&T);

     for(int i=;i<=T;i++){

         int n;

         scanf("%d",&n);

         if(==n||==n||==n){

             printf("1\n");

             continue;

         }

         Mat t=Power(A,n-);

         ll ans=(t.s[][]+t.s[][])%MOD;

         ans=(ans+t.s[][])%MOD;

         printf("%lld\n",ans);

     }

     return ;

 }

Code2

T3:

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

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

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 #define MAXN 5005

 #define MAXM 30005

 #define INF 0x7f7f7f7f

 using namespace std;

 struct Node{

     int s,u;

     int d;

     Node(int ss,int uu,int dd){

         s=ss,u=uu,d=dd;

     }

     Node(){

         s=u=;

         d=INF;

     }

     friend bool operator < (const Node &p1,const Node &p2){

         return (p1.d<p2.d);

     }

     friend bool operator > (const Node &p1,const Node &p2){

         return !(p1.d<p2.d);

     }

 };

 priority_queue<Node> q;

 int d[][MAXN];

 int V,E;

 int s[MAXN];

 int w[MAXN];

 int first[MAXN],Next[MAXM],to[MAXM],W[MAXM],cnt;

 int p[][MAXN];

 // 0 not change 1 change

 int Abs(int x){

     return (x>)?x:-x;

 }

 void Add(int x,int y,int w){

     Next[++cnt]=first[x]; first[x]=cnt; to[cnt]=y; W[cnt]=w;

     //single edge

 }

 void dijk(){

     d[][]=;

     q.push(Node(,,));

     while(!q.empty()){

         Node t=q.top(); q.pop();

         // now using t.s

         int ds=(!t.s);

         int x=t.u;

         if(d[t.s][t.u]!=t.d){

             continue;

         }

         //stay

         if(!p[t.s][x]){

             if(d[ds][x]>d[t.s][x]){

                 d[ds][x]=d[t.s][x];

                 q.push(Node(ds,x,d[ds][x]));

             }

         }

         else{

             if(d[ds][x]>d[t.s][x]+s[x]){

                 d[ds][x]=d[t.s][x]+s[x];

                 q.push(Node(ds,x,d[ds][x]));

             }

         }

         for(int e=first[x];e;e=Next[e]){

             int y=to[e];

             int dw=W[e];

             if(p[t.s][x]!=p[t.s][y]){

                 //0 white 1 black

                 //0->1 w-=delta w=max(w,0)

                 //1->0 w+=delta

                 if(!p[t.s][x]){

                     dw-=Abs(w[x]-w[y]);

                     dw=max(dw,);

                 }

                 else{

                     dw+=Abs(w[x]-w[y]);

                 }

             }

             if(d[ds][y]>d[t.s][x]+dw){

                 d[ds][y]=d[t.s][x]+dw;

                 q.push(Node(ds,y,d[ds][y]));

             }

         }

     }

 }

 int main()

 {

 //    freopen("data.in","r",stdin);

     memset(d,0x7f,sizeof(d));

     scanf("%d%d",&V,&E);

     for(int i=;i<=V;i++){

         scanf("%d",&p[][i]);

         p[][i]=(!p[][i]);

     }

     for(int i=;i<=V;i++){

         scanf("%d",&w[i]);

     }

     for(int i=;i<=V;i++){

         scanf("%d",&s[i]);

     }

     for(int i=;i<=E;i++){

         int x,y,k;

         scanf("%d%d%d",&x,&y,&k);

         Add(x,y,k);

     }

     dijk();

     int ans=min(d[][V],d[][V]);

     printf("%d\n",ans);

     return ;

 }

Code3

后来改用SPFA，AC了

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 #define MAXN 5005

 #define MAXM 30005

 #define INF 0x7f7f7f7f

 using namespace std;

 struct Node{

     int s,u;

     int d;

     Node(int ss,int uu,int dd){

         s=ss,u=uu,d=dd;

     }

     Node(){

         s=u=;

         d=INF;

     }

 };

 int d[][MAXN];

 bool b[][MAXN];

 queue<Node> q;

 int V,E;

 int s[MAXN];

 int w[MAXN];

 int first[MAXN],Next[MAXM],to[MAXM],W[MAXM],cnt;

 int p[][MAXN];

 // 0 not change 1 change

 int Abs(int x){

     return (x>)?x:-x;

 }

 void Add(int x,int y,int w){

     Next[++cnt]=first[x]; first[x]=cnt; to[cnt]=y; W[cnt]=w;

     //single edge

 }

 void SPFA(){

     d[][]=;

     b[][]=;

     q.push(Node(,,));

     while(!q.empty()){

         Node t=q.front(); q.pop();

         int S=t.s;

         int ds=(!S);

         int x=t.u;

         b[S][x]=;

         // now using t.s

         //stay

         if(!p[S][x]){

             if(d[ds][x]>d[S][x]){

                 d[ds][x]=d[S][x];

                 if(!b[ds][x]){

                     b[ds][x]=;

                     q.push(Node(ds,x,d[ds][x]));

                 }

             }

         }

         else{

             if(d[ds][x]>d[S][x]+s[x]){

                 d[ds][x]=d[S][x]+s[x];

                 if(!b[ds][x]){

                     b[ds][x]=;

                     q.push(Node(ds,x,d[ds][x]));

                 }

             }

         }

         for(int e=first[x];e;e=Next[e]){

             int y=to[e];

             int dw=W[e];

             if(p[S][x]!=p[S][y]){

                 //0 white 1 black

                 //0->1 w-=delta w=max(w,0)

                 //1->0 w+=delta

                 if(!p[S][x]){

                     dw-=Abs(w[x]-w[y]);

                     dw=max(dw,);

                 }

                 else{

                     dw+=Abs(w[x]-w[y]);

                 }

             }

             if(d[ds][y]>d[S][x]+dw){

                 d[ds][y]=d[S][x]+dw;

                 if(!b[ds][y]){

                     b[ds][y]=;

                     q.push(Node(ds,y,d[ds][y]));

                 }

             }

         }

     }

 }

 int main()

 {

 //    freopen("data.in","r",stdin);

     memset(d,0x7f,sizeof(d));

     scanf("%d%d",&V,&E);

     for(int i=;i<=V;i++){

         scanf("%d",&p[][i]);

         p[][i]=(!p[][i]);

     }

     for(int i=;i<=V;i++){

         scanf("%d",&w[i]);

     }

     for(int i=;i<=V;i++){

         scanf("%d",&s[i]);

     }

     for(int i=;i<=E;i++){

         int x,y,k;

         scanf("%d%d%d",&x,&y,&k);

         Add(x,y,k);

     }

     SPFA();

     int ans=min(d[][V],d[][V]);

     printf("%d\n",ans);

     return ;

 }

Code4

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

巴特西

NOIP2014-5-10模拟赛

最新文章

热门文章