CH Round #53 -【Nescafé 32】杯NOIP模拟赛

A.GCD Path http://ch.ezoj.tk/contest/CH%20Round%20%2353%20-%E3%80%90Nescaf%C3%A9%2032%E3%80%91%E6%9D%AFNOIP%E6%A8%A1%E6%8B%9F%E8%B5%9B/GCD%20Path

题解：我想掀桌。。。

          刚开始没思路，打了个30分的暴力把结果打出来，找规律。

          发现x-y的最短路貌似就是 x/gcd（x，y）的质因数分解加起来？

          果断 for 2 to sqrt()  枚举。。。。。。。。。。。。。。。。。。

          还以为能AC，妈蛋，爆零了。。。。。。。。。。。。。。。。

          你以为质因数分解是判素数？？？？？？？？？？？？？？？？

          呵呵。。。。。。。 呵呵。。。。。。。。呵呵。。。。。。。

          加上 if(x==1)ans+=x 瞬间50。。。。。。。。。。。。。。。。

          加上 if(x==y)cout<<0<<endl 瞬间AC。。。。。。。。。。。。。

          极度郁闷中。。。。。。。。。。。。。。。。。。。。。。。

          如果我会用linux的diff的话大概会和暴力比较一下，结果只看了100的数据就以为对了。。。。

          如果我10.30走的话也许会在对拍一下。。。。。。。。。。。

          没办法，还是人太弱。。。。。。。。。。。。。。。。。。。

代码：

 1 #include<cstdio>
 2 
 3 #include<cstdlib>
 4 
 5 #include<cmath>
 6 
 7 #include<cstring>
 8 
 9 #include<algorithm>
10 
11 #include<iostream>
12 
13 #include<vector>
14 
15 #include<map>
16 
17 #include<set>
18 
19 #include<queue>
20 
21 #include<string>
22 
23 #define inf 1000000000
24 
25 #define maxn 500+100
26 
27 #define maxm 500+100
28 
29 #define eps 1e-10
30 
31 #define ll long long
32 
33 #define pa pair<int,int>
34 
35 #define for0(i,n) for(int i=0;i<=(n);i++)
36 
37 #define for1(i,n) for(int i=1;i<=(n);i++)
38 
39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
40 
41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
42 
43 #define mod 1000000007
44 
45 using namespace std;
46 
47 inline int read()
48 
49 {
50 
51     int x=0,f=1;char ch=getchar();
52 
53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
54 
55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
56 
57     return x*f;
58 
59 }
60 int n,m;
61 inline int gcd(int x,int y){return y?gcd(y,x%y):x;}
62 
63 int main()
64 
65 {
66 
67     freopen("input.txt","r",stdin);
68 
69     freopen("output.txt","w",stdout);
70 
71     n=read();m=read();
72     while(m--)
73     {
74         int x=read(),y=read(),t=(int)sqrt(x),ans=0;
75         if(x==y){cout<<0<<endl;continue;}
76         x/=gcd(x,y);if(x==1){cout<<1<<endl;continue;};
77         for2(i,2,t)if(x%i==0)
78         {
79             while(x%i==0)x/=i,ans+=i;
80         }
81         if(x!=1)ans+=x;
82         printf("%d
",ans);
83     }
84 
85     return 0;
86 
87 }
View Code

B.密室http://ch.ezoj.tk/contest/CH%20Round%20%2353%20-%E3%80%90Nescaf%C3%A9%2032%E3%80%91%E6%9D%AFNOIP%E6%A8%A1%E6%8B%9F%E8%B5%9B/%E5%AF%86%E5%AE%A4

题解：发现一个结论：只要开的门的集合相同，那么拥有的钥匙数一定相同。显然。。。

          然后我们只需要判断能否到达每个门了。。。发现不会判囧。。。。。。。。。。

          那BFS吧，既然写暴力就裸一点

          x表示红的，y表示蓝的，z表示白的，w表示经过的点集合。。。。

          会T？那到maxn break吧，估计能骗个5.60分。。。。。。。。。

          成绩一下来逗逼了，90，这么照顾暴力。。。。。。。。。。。。。

代码：

 1 #include<cstdio>
 2 
 3 #include<cstdlib>
 4 
 5 #include<cmath>
 6 
 7 #include<cstring>
 8 
 9 #include<algorithm>
10 
11 #include<iostream>
12 
13 #include<vector>
14 
15 #include<map>
16 
17 #include<set>
18 
19 #include<queue>
20 
21 #include<string>
22 
23 #define inf 1000000000
24 
25 #define maxn 5000000
26 
27 #define maxm 500+100
28 
29 #define eps 1e-10
30 
31 #define ll long long
32 
33 #define pa pair<int,int>
34 
35 #define for0(i,n) for(int i=0;i<=(n);i++)
36 
37 #define for1(i,n) for(int i=1;i<=(n);i++)
38 
39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
40 
41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
42 
43 #define mod 1000000007
44 
45 using namespace std;
46 
47 inline int read()
48 
49 {
50 
51     int x=0,f=1;char ch=getchar();
52 
53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
54 
55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
56 
57     return x*f;
58 
59 }
60 struct rec1{int x,y,z;}a[20],b[20];
61 struct rec2{int x,y,z,w;}q[maxn];
62 int n;
63 
64 int main()
65 
66 {
67 
68     freopen("input.txt","r",stdin);
69 
70     freopen("output.txt","w",stdout);
71 
72     n=read();
73     for1(i,n)a[i].x=read();
74     for1(i,n)a[i].y=read();
75     for1(i,n)b[i].x=read();
76     for1(i,n)b[i].y=read();
77     for1(i,n)b[i].z=read();
78     int l=0,r=0;
79     q[++r].x=read(),q[r].y=read(),q[r].z=read(),q[r].w=0;
80     int ans=q[r].x+q[r].y+q[r].z;
81     while(l!=r)
82     {
83         rec2 now=q[++l];if(l==maxn)break;    
84         for1(i,n)
85          if((((now.w)&(1<<(i-1)))==0)&&(max(a[i].x-now.x,0)+max(a[i].y-now.y,0)<=now.z))
86          {
87           q[++r].x=max(now.x-a[i].x,0)+b[i].x;if(r==maxn)r=0;
88           q[r].y=max(now.y-a[i].y,0)+b[i].y;
89           q[r].z=now.z-max(a[i].x-now.x,0)-max(a[i].y-now.y,0)+b[i].z;
90           q[r].w=now.w+(1<<(i-1));
91           ans=max(ans,q[r].x+q[r].y+q[r].z);
92          }
93     }     
94     printf("%d
",ans);
95 
96     return 0;
97 
98 }
View Code

C.数据备份http://ch.ezoj.tk/contest/CH%20Round%20%2353%20-%E3%80%90Nescaf%C3%A9%2032%E3%80%91%E6%9D%AFNOIP%E6%A8%A1%E6%8B%9F%E8%B5%9B/%E6%95%B0%E6%8D%AE%E5%A4%87%E4%BB%BD

题解：发现x节点选了x-1和x+1都不能选,和cf某题比较像？

          卧操!n=10W,k=5w,你在逗我？

          算了，还是n*k的暴力算了，空间上用滚动就行了。。。

          居然能拿65，是在补偿我第一题吗T_T

代码：

 1 #include<cstdio>
 2 
 3 #include<cstdlib>
 4 
 5 #include<cmath>
 6 
 7 #include<cstring>
 8 
 9 #include<algorithm>
10 
11 #include<iostream>
12 
13 #include<vector>
14 
15 #include<map>
16 
17 #include<set>
18 
19 #include<queue>
20 
21 #include<string>
22 
23 #define inf 1000000000
24 
25 #define maxn 150000
26 
27 #define maxm 500+100
28 
29 #define eps 1e-10
30 
31 #define ll long long
32 
33 #define pa pair<int,int>
34 
35 #define for0(i,n) for(int i=0;i<=(n);i++)
36 
37 #define for1(i,n) for(int i=1;i<=(n);i++)
38 
39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
40 
41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
42 
43 #define mod 1000000007
44 
45 using namespace std;
46 
47 inline int read()
48 
49 {
50 
51     int x=0,f=1;char ch=getchar();
52 
53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
54 
55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
56 
57     return x*f;
58 
59 }
60 int n,k,a[maxn],f[2][maxn][2];
61 
62 int main()
63 
64 {
65 
66     freopen("input.txt","r",stdin);
67 
68     freopen("output.txt","w",stdout);
69 
70     n=read();k=read();
71     for1(i,n)a[i]=read();
72     for0(i,n)f[0][i][0]=f[0][i][1]=f[1][i][0]=f[1][i][1]=inf;
73     f[0][0][0]=0;
74     int t=0;
75     for1(i,n-1)
76     {
77         t=1-t;
78         for0(j,(i>>1)+1)
79          {
80              f[t][j][1]=f[t][j][0]=inf;
81              if(j)f[t][j][1]=f[1-t][j-1][0]+a[i+1]-a[i];
82              f[t][j][0]=min(f[1-t][j][0],f[1-t][j][1]);
83          }
84         //for0(j,k)cout<<i<<' '<<j<<' '<<f[t][j][0]<<' '<<f[t][j][1]<<endl; 
85     }
86     printf("%d
",min(f[t][k][0],f[t][k][1]));
87 
88     return 0;
89 
90 }
View Code

2.3正解待会儿补

UPD:我想上天台。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

        卧操，我2题居然是正解，把maxn改成1000W就A了？？？？？？？？？？？？？？？？？？？？？

        T_T

代码：

 1 #include<cstdio>
 2 
 3 #include<cstdlib>
 4 
 5 #include<cmath>
 6 
 7 #include<cstring>
 8 
 9 #include<algorithm>
10 
11 #include<iostream>
12 
13 #include<vector>
14 
15 #include<map>
16 
17 #include<set>
18 
19 #include<queue>
20 
21 #include<string>
22 
23 #define inf 1000000000
24 
25 #define maxn 10000000
26 
27 #define maxm 500+100
28 
29 #define eps 1e-10
30 
31 #define ll long long
32 
33 #define pa pair<int,int>
34 
35 #define for0(i,n) for(int i=0;i<=(n);i++)
36 
37 #define for1(i,n) for(int i=1;i<=(n);i++)
38 
39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
40 
41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
42 
43 #define mod 1000000007
44 
45 using namespace std;
46 
47 inline int read()
48 
49 {
50 
51     int x=0,f=1;char ch=getchar();
52 
53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
54 
55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
56 
57     return x*f;
58 
59 }
60 struct rec1{int x,y,z;}a[20],b[20];
61 struct rec2{int x,y,z,w;}q[maxn];
62 int n;
63 
64 int main()
65 
66 {
67 
68     freopen("input.txt","r",stdin);
69 
70     freopen("output.txt","w",stdout);
71 
72     n=read();
73     for1(i,n)a[i].x=read();
74     for1(i,n)a[i].y=read();
75     for1(i,n)b[i].x=read();
76     for1(i,n)b[i].y=read();
77     for1(i,n)b[i].z=read();
78     int l=0,r=0;
79     q[++r].x=read(),q[r].y=read(),q[r].z=read(),q[r].w=0;
80     int ans=q[r].x+q[r].y+q[r].z;
81     while(l!=r)
82     {
83         rec2 now=q[++l];if(l==maxn)break;    
84         for1(i,n)
85          if((((now.w)&(1<<(i-1)))==0)&&(max(a[i].x-now.x,0)+max(a[i].y-now.y,0)<=now.z))
86          {
87           q[++r].x=max(now.x-a[i].x,0)+b[i].x;if(r==maxn)r=0;
88           q[r].y=max(now.y-a[i].y,0)+b[i].y;
89           q[r].z=now.z-max(a[i].x-now.x,0)-max(a[i].y-now.y,0)+b[i].z;
90           q[r].w=now.w+(1<<(i-1));
91           if(q[r].x+q[r].y+q[r].z>ans)ans=q[r].x+q[r].y+q[r].z;
92          }
93     }     
94     printf("%d
",ans);
95 
96     return 0;
97 
98 }
View Code

 好吧。真正的正解其实在这里。我的只不过能AC罢了。。。。。。。。

不理解，怎么能只访问一次就不走了呢，估计是数据弱？求大神指导

代码：

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 #define N 50000 + 5
 8 
 9 int n, x, y, z, ans, door[21][2], key[21][3];
10 bool Open[N], Vis[N];
11 
12 inline void dfs(int state, int r, int g, int w)
13 {
14     if (Vis[state]) return ;
15     ans = max(ans, r + g + w);
16     for (int i = 1; i <= n; i ++)
17         if (!Open[i])
18         {
19             int _r = r - door[i][0];
20             int _g = g - door[i][1];
21             int _w = w + min(_r, 0) + min(_g, 0);
22             if (_w < 0) continue ;
23             _r = max(_r, 0) + key[i][0];
24             _g = max(_g, 0) + key[i][1];
25             _w += key[i][2];
26             Open[i] = 1;
27             dfs(state ^ (1 << i - 1), max(_r, 0), max(_g, 0), _w);
28             Open[i] = 0;
29         }
30     Vis[state] = 1;
31 }
32 
33 int main()
34 {
35     scanf("%d", &n);
36     for (int i = 0; i < 2; i ++)
37         for (int j = 1; j <= n; j ++)
38             scanf("%d", door[j] + i);
39     for (int i = 0; i < 3; i ++)
40         for (int j = 1; j <= n; j ++)
41             scanf("%d", key[j] + i);
42     scanf("%d%d%d", &x, &y, &z);
43     dfs(0, x, y, z);
44     printf("%d
", ans);
45     return 0;
46 }
View Code

 妈蛋，吐槽第二题，下面这程序都能AC，数据是有多弱，当时我本来就打算写这个。。。

代码：

 1 #include<stdio.h>
 2 int a[15],b[15],c[15],d[15],e[15];
 3 int r,g,w,hh;
 4 int main()
 5 {
 6     int n,i,ans=0;
 7     scanf("%d",&n);
 8     for(i=1;i<=n;i++)
 9     scanf("%d",&a[i]);
10     for(i=1;i<=n;i++)
11     scanf("%d",&b[i]);
12     for(i=1;i<=n;i++)
13     scanf("%d",&c[i]);
14     for(i=1;i<=n;i++)
15     scanf("%d",&d[i]);
16     for(i=1;i<=n;i++)
17     scanf("%d",&e[i]);
18     scanf("%d %d %d",&r,&g,&w);
19     ans=r+g+w;
20     if(n==1)
21     {
22       ans=r-a[1]+g-b[1]+w+c[1]+d[1]+e[1];
23       if(ans<r+g+w+c[1]+d[1]+e[1])
24         ans=r+g+w+c[1]+d[1]+e[1];
25     }
26     for(i=1;i<=n;i++)
27     {
28         if(c[i]+d[i]+e[i]-a[i]-b[i]>0)ans=ans-a[i]-b[i]+c[i]+d[i]+e[i];
29     }
30     printf("%d",ans);
31     return 0;
32 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/zyfzyf/p/3985651.html