NOIP模拟赛 6.29

2017-6-29 NOIP模拟赛

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);

水过。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring> 
 5 #include <algorithm>
 6 #include <vector>
 7 #include <queue>
 8 inline void read(long long &x){x = 0;char ch = getchar();char c = ch;while(ch > '9' || ch < '0')c = ch, ch = getchar();while(ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();}
 9 inline int max(int a, int b){return a > b ? a : b;}
10 inline int min(int a, int b){return a < b ? a : b;}
11 inline void swap(int &a, int &b){int tmp = a;a = b;b = tmp;}
12 
13 const int INF = 0x3f3f3f3f;
14 const int MAXN = 5000 + 10;
15 
16 char s[MAXN];
17 long long t;
18 long long len, xx, yy;
19 long long x,y;
20 
21 int main()
22 {
23     scanf("%s", s + 1);
24     read(t);
25     len = strlen(s + 1);
26     if(t < len)
27     {
28         for(register int i = 1;i <= t;++ i)
29         {
30             if(s[i] == 'E')++ xx;
31             else if(s[i] == 'S')--yy;
32             else if(s[i] == 'W')--xx;
33             else ++yy;
34         }
35         x = xx;
36         y = yy;
37     }
38     else
39     {
40         for(register int i = 1;i <= len;++ i)
41         {
42             if(s[i] == 'E')++ xx;
43             else if(s[i] == 'S')--yy;
44             else if(s[i] == 'W')--xx;
45             else ++yy;
46         }
47         int group = t / len;
48         x = xx * group;
49         y = yy * group;
50         group = t % len;
51         for(register int i = 1;i <= group;i ++)
52         {
53             if(s[i] == 'E')++ x;
54             else if(s[i] == 'S')--y;
55             else if(s[i] == 'W')--x;
56             else ++y;
57         }
58     }
59     printf("%lld %lld", x, y);
60     return 0;
61 }
View Code

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；

 

矩阵快速幂。

构造矩阵：

1 1 0 0

0 1 0 1

0 1 0 0

0 0 1 0

和

an

a（n - 2）

a（n - 3）

a（n - 4）

 

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cstring> 
  5 #include <algorithm>
  6 #include <vector>
  7 #include <queue>
  8 inline void read(long long &x){x = 0;char ch = getchar();char c = ch;while(ch > '9' || ch < '0')c = ch, ch = getchar();while(ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();}
  9 inline int max(int a, int b){return a > b ? a : b;}
 10 inline int min(int a, int b){return a < b ? a : b;}
 11 inline void swap(int &a, int &b){int tmp = a;a = b;b = tmp;}
 12 
 13 const int INF = 0x3f3f3f3f;
 14 const int MOD = 1000000007;
 15 
 16 long long s1[10][10];
 17 long long s2[10];
 18 long long ans[10][10];
 19 long long base[10][10];
 20 long long tmp[10][10];
 21 
 22 long long pow(int b)
 23 {
 24     for(int i = 1;i <= 4;i ++)
 25     {
 26         ans[i][i] = 1;
 27         for(int j = 1;j <= 4;j ++)
 28         {
 29             base[i][j] = s1[i][j] % MOD;
 30         }
 31     }
 32     while(b)
 33     {
 34         
 35         if(b & 1)
 36         {
 37             for(int i = 1;i <= 4;++ i)
 38             {
 39                 for(int j = 1;j <= 4;++ j)
 40                 {
 41                     tmp[i][j] = ans[i][j] % MOD;
 42                 }
 43             }
 44             //    ans *= base;
 45             memset(ans, 0, sizeof(ans));
 46             for(int k = 1;k <= 4;++ k)
 47             {
 48                 for(int i = 1;i <= 4; ++ i)
 49                 {
 50                     for(int j = 1;j <= 4;++ j)
 51                     {
 52                         ans[i][j] += ((tmp[i][k] % MOD) * (base[k][j] % MOD)) % MOD;
 53                     }
 54                 }
 55             }
 56         }
 57         
 58         
 59         for(int i = 1;i <= 4;i ++)
 60         {
 61             for(int j = 1;j <= 4;j ++)
 62             {
 63                 tmp[i][j] = base[i][j] % MOD;
 64             }
 65         }
 66         memset(base, 0, sizeof(base));
 67         for(int k = 1;k <= 4;++ k)
 68         {
 69             for(int i = 1;i <= 4; ++ i)
 70             {
 71                 for(int j = 1;j <= 4;++ j)
 72                 {
 73                     base[i][j] += ((tmp[i][k] % MOD) * (tmp[k][j] % MOD)) % MOD;
 74                 }
 75             }
 76         }
 77         //base = base * base;
 78         b >>= 1;
 79     }
 80     return ((((ans[1][1]%MOD) * (s2[1]%MOD) % MOD) + ((ans[1][2]%MOD) * (s2[2]%MOD) % MOD))%MOD + (((ans[1][3]%MOD) *(s2[3]%MOD)) % MOD + ((ans[1][4]%MOD) * (s2[4]%MOD)) % MOD)%MOD) % MOD;
 81 }
 82 
 83 long long n,t;
 84 
 85 int main()
 86 {
 87     read(t);
 88     while(t)
 89     {
 90         memset(base, 0, sizeof(base));
 91         memset(tmp, 0, sizeof(tmp));
 92         memset(ans, 0, sizeof(ans));
 93         read(n);
 94         if(n == 1 || n == 2 || n == 3)
 95         {
 96             printf("1
");
 97             -- t;
 98             continue;
 99         }
100         else if(n == 4)
101         {
102             printf("2
");
103             -- t;
104             continue;
105         }
106         else if(n == 5)
107         {
108             printf("3
");
109             -- t;
110             continue;
111         }
112         s1[1][1] = 1;s1[1][2] = 1;s1[1][3] = 0;s1[1][4] = 0;
113         s1[2][1] = 0;s1[2][2] = 1;s1[2][3] = 0;s1[2][4] = 1;
114         s1[3][1] = 0;s1[3][2] = 1;s1[3][3] = 0;s1[3][4] = 0;
115         s1[4][1] = 0;s1[4][2] = 0;s1[4][3] = 1;s1[4][4] = 0;
116         s2[1] = 3;s2[2] = 1;s2[3] = 1;s2[4] = 1;
117         long long a = pow(n - 5);
118         printf("%lld
", a % MOD);
119         -- t;
120     } 
121     return 0;
122 }
View Code

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的路线。

 

不难发现，无论时间怎样变化，两个点的相对颜色总是不变（即总是同色或异色）

把一个点拆成两个点，分别代表白、黑，记为i,i'

每一s黑白互换，因此当i->j，权值为w时，我们令i->j',权值为w

又由于我们可以在某一个点上停留一个单位时间，从而使得点黑白互换，因此应让i->i'和i'->i连边即可。而又由于任何节点相对颜色不变，我们可以知道走这条边到达i'（i）后仍是合法的。

这样建图跑SPFA即可

 

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cstring> 
  5 #include <algorithm>
  6 #include <vector>
  7 #include <queue>
  8 inline void read(int &x){x = 0;char ch = getchar();char c = ch;while(ch > '9' || ch < '0')c = ch, ch = getchar();while(ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();}
  9 inline int max(int a, int b){return a > b ? a : b;}
 10 inline int min(int a, int b){return a < b ? a : b;}
 11 inline void swap(int &a, int &b){int tmp = a;a = b;b = tmp;}
 12  
 13 const int INF = 0x3f3f3f3f;
 14 const int MAXN = 1000000;
 15 const int MAXM = 3000000;
 16 
 17 int n,m;
 18 int bw[MAXN << 1],weight[MAXN],s[MAXN];
 19 int tmp1, tmp2, tmp3;
 20 
 21 struct Edge
 22 {
 23     int u,v,next,w;
 24 }edge[MAXM];
 25 int head[MAXN << 1],cnt;
 26 void insert(int a, int b, int c){edge[++cnt] = Edge{a, b, head[a], c};head[a] = cnt;}
 27 
 28 std::queue<int> q;
 29 int b[MAXN << 1],d[MAXN];
 30 
 31 void SPFA()
 32 {
 33     memset(d, 0x3f, sizeof(d));
 34     q.push(2);d[2] = 0;
 35     b[2] = true;
 36     register int u,v;
 37     while (!q.empty())
 38     {
 39         u = q.front();
 40         q.pop();
 41         b[u] = false;
 42         for (int pos = head[u];pos;pos = edge[pos].next)
 43         {
 44             v = edge[pos].v;
 45             if (d[v] > d[u] + edge[pos].w)
 46             {
 47                 d[v] = d[u] + edge[pos].w;
 48                 if (!b[v])
 49                 {
 50                     b[v] = true;
 51                     q.push(v);
 52                 }
 53             }
 54         }
 55     }
 56 }
 57 
 58 int main()
 59 {
 60     read(n);read(m);
 61     
 62     for (register int i = 1;i <= n;++ i)
 63     {
 64         read(bw[i << 1]);
 65         bw[i << 1 | 1] = 1 ^ bw[i << 1];
 66     }
 67     
 68     for (register int i = 1;i <= n;++ i)
 69     {
 70         read(weight[i]);
 71     }
 72     
 73     for (register int i = 1;i <= n;++ i)
 74     {
 75         read(s[i]);
 76         int w = s[i];
 77         if (!bw[i << 1])
 78             insert(i << 1, i << 1 | 1, 0),insert(i << 1 | 1, i << 1, s[i]); 
 79         else 
 80             insert(i << 1, i << 1 | 1, s[i]),insert(i << 1 | 1, i << 1, 0); 
 81     }
 82     
 83     for (register int i = 1;i <= m;++ i)
 84     {
 85         read(tmp1);read(tmp2);read(tmp3);
 86         int w1 = 0,w2 = 0;
 87         
 88         //0 白  1  黑
 89         
 90         //相同 不变化 
 91         
 92         if (bw[tmp1 << 1] == bw[tmp2 << 1])
 93             w1 = w2 = tmp3;
 94             
 95         //0 -> 1  减小weight差 ，负数记为0
 96         
 97         if (bw[tmp1 << 1] == 0 && bw[tmp2 << 1] == 1)
 98             w1 = tmp3 - abs(weight[tmp1] - weight[tmp2]);
 99         if (bw[tmp1 << 1 | 1] == 0 && bw[tmp2 << 1 | 1] == 1)
100             w2 = tmp3 - abs(weight[tmp1] - weight[tmp2]);
101             
102         //1 -> 0 增加weight差
103         
104         if (bw[tmp1 << 1] == 1 && bw[tmp2 << 1] == 0)
105             w1 = tmp3 + abs(weight[tmp1] - weight[tmp2]);
106         if (bw[tmp1 << 1 | 1] == 1 && bw[tmp2 << 1 | 1] == 0)
107             w2 = tmp3 + abs(weight[tmp1] - weight[tmp2]);
108             
109         if (w1 < 0)
110             w1 = 0;
111         if (w2 < 0)
112             w2 = 0;
113             
114         insert(tmp1 << 1, tmp2 << 1 | 1, w1);
115         insert(tmp1 << 1 | 1, tmp2 << 1, w2);
116     }
117     
118     SPFA();
119     
120     printf("%d", min(d[n << 1], d[n << 1 | 1]));
121     return 0;
122 }
View Code

第一次AK，开森~

题怪简单

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/huibixiaoxing/p/7093198.html