2016-2017 ACM-ICPC, Egyptian Collegiate Programming Contest(solved 8/11)

这套题似乎是省选前做的，一直没来写题解～～～补上补上>_<

链接：http://codeforces.com/gym/101147

一样先放上惨不忍睹的成绩好了～～～

Problem A 1Y(2h52min)

Problem B DNF

Problem C DNF

Problem D 1Y(3min)

Problem E 2Y(19min)

Problem F DNF

Problem G 6Y(2h40min)

Problem H 1Y(36min)

Problem I 2Y(4h55min)

Problem J DNF

Problem K DNF

总之我非常非常菜就对了啦～

Problem A:

一个很棒棒的博弈题呢～

博弈题不会的时候，不如打个表找找规律～～～

然后分类讨论一下，

a是奇数的时候，b的奇偶性决定了sg函数的值，

a是偶数的时候，b%(a+1)决定了sg函数的值，（这里还要分类讨论一下）

于是全部xor一下就做完了。

代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int read()
 4 {
 5     int x=0,f=1;char ch=getchar();
 6     while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
 7     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 8     return x*f;
 9 }
10 int T,ans,n,a,b;
11 int main()
12 {
13     freopen("powers.in","r",stdin);
14     T=read();
15     while (T--)
16     {
17         ans=0;
18         n=read();
19         for (int i=1;i<=n;i++)
20         {
21             a=read(),b=read();
22             if (a%2==1)
23             {
24                 if (b%2==1) ans^=1;
25             }
26             else
27             {
28                 b=b%(a+1);
29                 if (b==a) ans^=2;
30                 if (b%2==1) ans^=1;
31             }
32         }
33         if (ans==0) printf("%d
",2); else printf("%d
",1);
34     }
35     return 0;
36 }

Problem B:

这题好像是个计算几何啊。。。不做不做（这是virtual participate时候的我），啊哼>_<

其实这题很好做啊，把矩形之间两两最短距离细节全部判出来，

然后直接跑SPFA最短路不就好了嘛。

注意细节啊～～～

代码如下：

 1 #include <bits/stdc++.h>
 2 #define Maxn 107
 3 #define Maxm 200007
 4 #define inf 1500000007
 5 using namespace std;
 6 int read()
 7 {
 8     int x=0,f=1;char ch=getchar();
 9     while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
10     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
11     return x*f;
12 }
13 int T,n,L,R,cnt,s,t;
14 int d[Maxn],h[Maxn],k[Maxn],w[Maxn];
15 int pre[Maxm],other[Maxm],last[Maxm];
16 int que[Maxm*2];
17 double dis[Maxn],len[Maxm];
18 bool vis[Maxn];
19 void insert(int u,int v,double d)
20 {
21     other[++cnt]=v,pre[cnt]=last[u],last[u]=cnt,len[cnt]=d;
22     other[++cnt]=u,pre[cnt]=last[v],last[v]=cnt,len[cnt]=d;
23 }
24 void spfa()
25 {
26     int lx=0,rx=1;
27     memset(vis,false,sizeof(vis));
28     vis[s]=true;
29     for (int i=1;i<=t;i++) dis[i]=inf*1.0;
30     que[1]=s;
31     while (lx<rx)
32     {
33         int u=que[++lx];
34         for (int q=last[u];q;q=pre[q])
35         {
36             int v=other[q];
37             if (dis[v]>dis[u]+len[q])
38             {
39                 dis[v]=dis[u]+len[q];
40                 if (!vis[v])
41                 {
42                     vis[v]=true;
43                     que[++rx]=v;
44                 }
45             }
46         }
47         vis[u]=false;
48     }
49 }
50 int main()
51 {
52     freopen("street.in","r",stdin);
53     T=read();
54     while (T--)
55     {
56         n=read(),L=read(),R=read();
57         for (int i=1;i<=n;i++)
58             h[i]=read(),w[i]=read(),d[i]=read(),k[i]=read();
59         cnt=0;
60         memset(last,0,sizeof(last));
61         s=0,t=n+1;
62         insert(s,t,1.0*L);
63         for (int i=1;i<=n;i++) insert(s,i,d[i]*1.0);
64         for (int i=1;i<=n;i++) insert(i,t,(L-h[i]-d[i])*1.0);
65         for (int i=1;i<=n;i++)
66             for (int j=i+1;j<=n;j++)
67             {
68                 int dely=abs(d[j]+h[j]-d[i]);
69                 dely=min(dely,abs(d[i]+h[i]-d[j]));
70                 if (k[i]!=k[j]&&d[i]+h[i]>=d[j]&&d[i]+h[i]<=d[j]+h[j]) dely=0;
71                 if (k[i]!=k[j]&&d[j]+h[j]>=d[i]&&d[j]+h[j]<=d[i]+h[i]) dely=0;
72                 if (k[i]==k[j]||w[i]+w[j]>=R) insert(i,j,dely*1.0); else
73                 {
74                     int delx=R-w[i]-w[j];
75                     insert(i,j,(double)sqrt(1LL*dely*dely+1LL*delx*delx));
76                 }
77             }
78         spfa();
79         printf("%.6lf
",dis[t]);
80     }
81     fclose(stdin);
82     return 0;
83 }

Problem D:

组合数会不会呀～～～

写程序会不会呀～～～（捂脸熊）

代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int T,n,m;
 4 long long pre[25];
 5 int main()
 6 {
 7     freopen("popcorn.in","r",stdin);
 8     cin>>T;
 9     pre[1]=1;
10     for (int i=2;i<=20;i++) pre[i]=1LL*pre[i-1]*i;
11     while (T--)
12     {
13         cin>>n>>m;
14         long long ans=1;
15         for (int i=n-m+1;i<=n;i++) ans=1LL*ans*i;
16         ans=ans/pre[m];
17         cout << ans << endl;
18     }
19     return 0;
20 }

Problem E:

这题时间限制辣么长，是不是可以暴力大搜索啊～（当然不行。。。）

我们对于每一个点i，将i和i-di和i+di分别连边，然后直接SPFA最短路就行了。

（其实这题我的第一反应是DP呢。。。）

代码如下：

 1 #include <bits/stdc++.h>
 2 #define Maxn 100007
 3 #define Maxm 1000007
 4 #define inf 1000000007
 5 using namespace std;
 6 int read()
 7 {
 8     int x=0,f=1;char ch=getchar();
 9     while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
10     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
11     return x*f;
12 }
13 int T,n,cnt;
14 int d[Maxn];
15 int last[Maxm],pre[Maxm],other[Maxm],dis[Maxn],que[Maxm];
16 bool vis[Maxn];
17 void insert(int u,int v)
18 {
19     other[++cnt]=v,pre[cnt]=last[u],last[u]=cnt;
20 }
21 void spfa()
22 {
23     memset(que,0,sizeof(que));
24     for (int i=1;i<=n;i++) dis[i]=inf;
25     dis[n]=0;
26     int lx=0,rx=1;
27     vis[n]=true;
28     que[1]=n;
29     while (lx<rx)
30     {
31         int u=que[++lx];
32         vis[u]=false;
33         for (int q=last[u];q;q=pre[q])
34         {
35             int v=other[q];
36             if (dis[v]>dis[u]+1)
37             {
38                 dis[v]=dis[u]+1;
39                 if (!vis[v])
40                 {
41                     vis[v]=true;
42                     que[++rx]=v;
43                 }
44             }
45         }
46     }
47 }
48 int main()
49 {
50     freopen("jumping.in","r",stdin);
51     T=read();
52     while (T--)
53     {
54         n=read();
55         memset(last,0,sizeof(last));
56         for (int i=1;i<=n;i++) d[i]=read();
57         cnt=0;
58         for (int i=1;i<n;i++)
59         {
60             if (i+d[i]<=n) insert(i+d[i],i);
61             if (i-d[i]>0) insert(i-d[i],i);
62         }
63         spfa();
64         for (int i=1;i<=n;i++)
65             if (dis[i]<=inf/3) printf("%d
",dis[i]); else printf("%d
",-1);
66     }
67     return 0;
68 }

Problem G:

这题的答案就是第二类斯特林数再乘上一个阶乘就好了，

然后稍微与处理一下就好了的吧。。。

代码如下：

 1 #include <bits/stdc++.h>
 2 #define modp 1000000007
 3 using namespace std;
 4 int read()
 5 {
 6     int x=0,f=1;char ch=getchar();
 7     while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
 8     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 9     return x*f;
10 }
11 int T,n,k;
12 long long f[1007][1007],pre[1007];
13 int main()
14 {
15     freopen("galactic.in","r",stdin);
16     T=read();
17     memset(f,0,sizeof(f));
18     f[0][0]=1;
19     for (int i=1;i<=1000;i++)
20     {
21         f[i][i]=1;
22         for (int j=1;j<=i;j++)
23             f[i][j]=(1LL*j*f[i-1][j]+f[i-1][j-1])%modp;
24     }
25     pre[1]=1;
26     for (int i=2;i<=1000;i++) pre[i]=(1LL*pre[i-1]*i)%modp;
27     while (T--)
28     {
29         n=read(),k=read();
30         if (k>n) printf("%d
",0); else printf("%d
",(1LL*pre[k]*f[n][k])%modp);
31     }
32     return 0;
33 }

Problem H:

这题不是10*10*10的DP一下就好了嘛。。。

代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int read()
 4 {
 5     int x=0,f=1;char ch=getchar();
 6     while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
 7     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 8     return x*f;
 9 }
10 int T,n,w[15][15][15],f[15][15][15];
11 int main()
12 {
13     freopen("commandos.in","r",stdin);
14     T=read();
15     while (T--)
16     {
17         n=read();
18         memset(w,0,sizeof(w));
19         memset(f,0,sizeof(f));
20         for (int i=1;i<=n;i++)
21         {
22             int f=read(),y=read(),x=read(),h=read();
23             w[f][y][x]=h;
24         }
25         for (int i=10;i;i--)
26             for (int j=1;j<=10;j++)
27                 for (int k=1;k<=10;k++)
28                 {
29                     f[i][j][k]=max(f[i+1][j][k], max(f[i][j-1][k],f[i][j][k-1]))+w[i][j][k];
30                 }
31         printf("%d
",f[1][10][10]);
32     }
33     return 0;
34 }

Problem I:

这题是个可做的计算几何呢～～～

首先我们把每个圆与x轴的交点都预处理出来，

然后排个序，类似扫描线的从左到右扫一遍就行了。

代码如下：

 1 #include <bits/stdc++.h>
 2 #define Maxn 100007
 3 using namespace std;
 4 int read()
 5 {
 6     int x=0,f=1;char ch=getchar();
 7     while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
 8     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 9     return x*f;
10 }
11 int T,n,R,cnt;
12 pair <double,int> s[2*Maxn];
13 int main()
14 {
15     freopen("walk.in","r",stdin);
16     T=read();
17     while (T--)
18     {
19         n=read(),R=read();
20         cnt=0;
21         for (int i=1;i<=n;i++)
22         {
23             int x=read(),y=read(),r=read();
24             if (!(r>R||y>R-r||y<r-R))
25             {
26                 double dis=sqrt(1.0*(R-r)*(R-r)-1.0*y*y);
27                 s[++cnt]=make_pair(-1.0*dis+1.0*x,-r);
28                 s[++cnt]=make_pair(1.0*dis+1.0*x,r);
29             }
30         }
31         sort(s+1,s+cnt+1);
32         long long ans=0,now=0;
33         for (int i=1;i<=cnt;i++)
34         {
35             now+=s[i].second;
36             ans=max(ans,-now);
37         }
38         cout<<ans<<endl;
39     }
40     return 0;
41 }

Problem J:

为什么你们这个题都会做啊，我就不会。。。

我们对整个树做一下DFS，然后在DFS的时候动态维护出当前的路径，

对于当前的节点我们考虑它对答案的贡献度，

然后发现其实只要在路径上二分以下就做完了。

代码如下：

 1 #include <bits/stdc++.h>
 2 #define Maxn 1000007
 3 using namespace std;
 4 int read()
 5 {
 6     int x=0,f=1;char ch=getchar();
 7     while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
 8     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 9     return x*f;
10 }
11 int T,n,cnt;
12 int val[Maxn];
13 long long path[Maxn],ans[Maxn],depth[Maxn];
14 int pre[Maxn],other[Maxn],last[Maxn],len[Maxn];
15 int father[Maxn];
16 void insert(int u,int v,int dis)
17 {
18     other[++cnt]=v,pre[cnt]=last[u],len[cnt]=dis,last[u]=cnt;
19 }
20 void dfs(int u,int fa,int num)
21 {
22     for (int q=last[u];q;q=pre[q])
23     {
24         int v=other[q];
25         if (v!=fa)
26         {
27             father[v]=u;
28             path[num]=v;
29             depth[num]=depth[num-1]+len[q];
30             int pos=lower_bound(depth,depth+num+1,depth[num]-val[v])-depth;
31             if (pos<num)
32             {
33                 ++ans[u];
34                 --ans[father[path[pos]]];
35             }
36             dfs(v,u,num+1);
37             ans[u]+=ans[v];
38         }
39     }
40 }
41 int main()
42 {
43     freopen("car.in","r",stdin);
44     T=read();
45     while (T--)
46     {
47         n=read(),cnt=0;
48         memset(last,0,sizeof(last));
49         for (int i=1;i<=n;i++) val[i]=read();
50         for (int i=1;i<n;i++)
51         {
52             int u=read(),v=read(),dis=read();
53             insert(u,v,dis),insert(v,u,dis);
54         }
55         memset(depth,0,sizeof(depth));
56         memset(path,0,sizeof(path));
57         memset(ans,0,sizeof(ans));
58         path[0]=1,depth[0]=0;
59         dfs(1,-1,1);
60         for (int i=1;i<=n;i++) printf("%lld ",ans[i]);
61         printf("
");
62     }
63     return 0;
64 }