Codeforces Round #469 (Div. 2)

难得的下午场，又掉分了。。。。

Problem A: 怎么暴力怎么写。

 1 #include<bits/stdc++.h>
 2 #define fi first
 3 #define se second
 4 #define mk make_pair
 5 #define pii pair<int,int>
 6 #define read(x) scanf("%d",&x)
 7 #define sread(x) scanf("%s",x)
 8 #define dread(x) scanf("%lf",&x)
 9 #define lread(x) scanf("%lld",&x)
10 using namespace std;
11 
12 typedef long long ll;
13 const int inf=0x3f3f3f3f;
14 const int INF=0x3f3f3f3f3f3f3f3f;
15 const int N=1e6+7;
16 const int M=3013;
17 
18 int n;
19 
20 int l,r,m;
21 int main()
22 {
23     read(l); read(r); read(m);
24     int ret=min(l,r);
25     int ans=0;
26     ans+=ret*2;
27     l-=ret;
28     r-=ret;
29     ret=min(l,m);
30     ans+=ret*2;
31     l-=ret;
32     m-=ret;
33     ret=min(r,m);
34     ans+=2*ret;
35     r-=ret;
36     m-=ret;
37     if(m&1) m--;
38     printf("%d
",ans+m);
39     return 0;
40 }
41 /*
42 */

View Code

Problem B:

题目大意：把一段信息分别拆成 A里的n段和 B里的m段，A和B都重新组合一下，最多有多少个信息片段相同。

思路：刚开始以为拆了之后是无序的，发现不会，重读了一下题，原来就是相邻的。。。。处理一下前缀和，类似于

two point 搞一搞就好啦。

 1 #include<bits/stdc++.h>
 2 #define fi first
 3 #define se second
 4 #define mk make_pair
 5 #define pii pair<int,int>
 6 #define read(x) scanf("%d",&x)
 7 #define sread(x) scanf("%s",x)
 8 #define dread(x) scanf("%lf",&x)
 9 #define lread(x) scanf("%lld",&x)
10 using namespace std;
11 
12 typedef long long ll;
13 const int inf=0x3f3f3f3f;
14 const int INF=0x3f3f3f3f3f3f3f3f;
15 const int N=1e6+7;
16 const int M=3013;
17 
18 int n,m;
19 ll a[N],b[N],sum1[N],sum2[N];
20 int main()
21 {
22     read(n); read(m);
23     for(int i=1;i<=n;i++)
24         lread(a[i]);
25     for(int i=1;i<=m;i++)
26         lread(b[i]);
27 
28     for(int i=1;i<=n;i++)
29         sum1[i]=sum1[i-1]+a[i];
30     for(int i=1;i<=m;i++)
31         sum2[i]=sum2[i-1]+b[i];
32 
33     int p1=1,p2=1,ans=0;
34     while(p1<=n && p2<=m)
35     {
36 
37         while(sum1[p1]!=sum2[p2])
38         {
39             while(sum1[p1]<sum2[p2])
40                 p1++;
41 
42             while(sum1[p1]>sum2[p2])
43                 p2++;
44 
45         }
46         ans++;
47         p1++;
48         p2++;
49     }
50     printf("%d
",ans);
51     return 0;
52 }
53 /*
54 */

View Code

Problem C:

题意：给你一个0,1组成的串，要求你按时间顺序任意组合成若干个串，要求每个串首尾都是0，且0和1不相邻。

思路：想了5分钟就会写了，从前往后处理，如果当前是0，且以前的串里最后一位没有1的，那么新开一个串，

否则接在以前那个串的后边，如果当前的是0，且以前的串里最后一位没有0的，输出-1，否则接在以前那个串

的后边，最后判断一下所有串的首尾是不是都是0。

 1 #include<bits/stdc++.h>
 2 #define fi first
 3 #define se second
 4 #define mk make_pair
 5 #define pii pair<int,int>
 6 #define read(x) scanf("%d",&x)
 7 #define sread(x) scanf("%s",x)
 8 #define dread(x) scanf("%lf",&x)
 9 #define lread(x) scanf("%lld",&x)
10 using namespace std;
11 
12 typedef long long ll;
13 const int inf=0x3f3f3f3f;
14 const int INF=0x3f3f3f3f3f3f3f3f;
15 const int N=1e6+7;
16 const int M=3013;
17 
18 char s[N];
19 int cnt[N],tot,n;
20 vector<int> ans[N];
21 vector<int> num0,num1;
22 int main()
23 {
24     sread(s+1);
25     n=strlen(s+1);
26     for(int i=1;i<=n;i++)
27     {
28         if(s[i]=='0')
29         {
30             if(!num1.size())
31             {
32                 ans[tot].push_back(i);
33                 num0.push_back(tot);
34                 tot++;
35             }
36             else
37             {
38                 int id=num1[num1.size()-1];
39                 num1.pop_back();
40                 ans[id].push_back(i);
41                 num0.push_back(id);
42             }
43         }
44         else
45         {
46             if(!num0.size())
47             {
48                 puts("-1");
49                 return 0;
50             }
51             else
52             {
53                 int id=num0[num0.size()-1];
54                 num0.pop_back();
55                 ans[id].push_back(i);
56                 num1.push_back(id);
57             }
58         }
59     }
60     if(num1.size())
61     {
62         puts("-1");
63         return 0;
64     }
65     printf("%d
",tot);
66     for(int i=0;i<tot;i++)
67     {
68         printf("%d ",ans[i].size());
69         for(int j:ans[i])
70             printf("%d ",j);
71         puts("");
72     }
73     return 0;
74 }
75 /*
76 */

View Code

Problem D:

题意：有n个数，数i在 2*i-1的位置，每次操作将最后一个元素，放到与其最近的空位置，知道1-n位置被填满。

思路：刚开始想找规律，找了半天没找到，后来发现前n个位置里边如果本来就有元素，那么这个元素一定是不会

变的，原来空着的地方全部都是大于n位置上的元素跳过来的，比如说第一个空位上最后的元素肯定是从位置在n+1

上的元素跳过来的，如果n+1还是空位则递归处理，否则，这个元素就是第一个空位的元素。

最后写的太慌了，调了半天没有A掉，赛后马上就A了，气死了。。。。。

 1 #include<bits/stdc++.h>
 2 #define fi first
 3 #define se second
 4 #define mk make_pair
 5 #define pii pair<int,int>
 6 #define read(x) scanf("%d",&x)
 7 #define sread(x) scanf("%s",x)
 8 #define dread(x) scanf("%lf",&x)
 9 #define lread(x) scanf("%lld",&x)
10 using namespace std;
11 
12 typedef long long ll;
13 const int inf=0x3f3f3f3f;
14 const int INF=0x3f3f3f3f3f3f3f3f;
15 const int N=1e6+7;
16 const int M=3013;
17 
18 ll n,q,cnt=3;
19 ll dfs(ll x,ll l,ll r)
20 {
21     if(x&1)
22         return x;
23     if(l&1)
24     {
25         ll cnt=(x-l)/2+1;
26         ll num=(r+1)/2-(l+1)/2+1;
27         return dfs(l+num+cnt-1,l+num,r);
28     }
29     else
30     {
31         ll cnt=(x-l)/2+1;
32         ll num=(r+1)/2-(l+2)/2+1;
33         return dfs(l+num+cnt-1,l+num,r);
34     }
35 }
36 int main()
37 {
38     lread(n); lread(q);
39     for(int i=1;i<=q;i++)
40     {
41         ll x; lread(x);
42         ll ans=dfs(x,1,2*n-1);
43         printf("%lld
",(ans+1)/2);
44     }
45     return 0;
46 }
47 /*
48 */

View Code

Problem E:

题意：这个题意我真的讲不来。。。。。但是赛后补的时候感觉这个题比D简单。。

思路：对于c1,c2两个信息中心来说来说，如果t[c1] 是 t[c2] 前面一个时间，那么c1向c2建一条边，表明c1动了，c2必须动，

如果t[c2] 是 t[c1]前面一个时间，那么c2向c1建一条边，表明c2动了，c1必须动。直接跑一个强连通分量，缩点之后变成一个

拓扑图，对于每个强连通分量来说，只有没有出度的才有机会成为答案，那么在没有出度的里面找最小值就好啦。

 1 #include<bits/stdc++.h>
 2 #define fi first
 3 #define se second
 4 #define mk make_pair
 5 #define pii pair<int,int>
 6 #define read(x) scanf("%d",&x)
 7 #define sread(x) scanf("%s",x)
 8 #define dread(x) scanf("%lf",&x)
 9 #define lread(x) scanf("%lld",&x)
10 using namespace std;
11 
12 typedef long long ll;
13 const int inf=0x3f3f3f3f;
14 const int INF=0x3f3f3f3f3f3f3f3f;
15 const int N=3e6+7;
16 const int M=3013;
17 
18 int n,m,h,dindex,all,cnt,t[N],dfn[N],low[N],st[N],id[N],dg[N];
19 bool inst[N];
20 vector<int> edge[N],ans[N];
21 
22 void tarjan(int v)
23 {
24     dindex++;
25     dfn[v]=low[v]=dindex;
26     st[all++]=v; inst[v]=true;
27     for(int nx:edge[v])
28     {
29         if(!dfn[nx])
30         {
31             tarjan(nx);
32             low[v]=min(low[v],low[nx]);
33         }
34         else if(inst[nx]) low[v]=min(low[v],low[nx]);
35     }
36     if(dfn[v]==low[v])
37     {
38         cnt++;
39         while(1)
40         {
41             int cur=st[--all];
42             inst[cur]=false;
43             id[cur]=cnt;
44             ans[cnt].push_back(cur);
45             if(cur==v) break;
46         }
47     }
48 }
49 
50 int main()
51 {
52     read(n); read(m); read(h);
53     for(int i=1;i<=n;i++)
54         read(t[i]);
55     for(int i=1;i<=m;i++)
56     {
57         int c1,c2;
58         read(c1); read(c2);
59         if((t[c1]+1)%h==t[c2])
60             edge[c1].push_back(c2);
61         if((t[c2]+1)%h==t[c1])
62             edge[c2].push_back(c1);
63     }
64 
65     for(int i=1;i<=n;i++)
66         if(!dfn[i])
67             tarjan(i);
68 
69     for(int i=1;i<=n;i++)
70         for(int j:edge[i])
71             if(id[i]!=id[j])
72                 dg[id[i]]++;
73 
74     int ret=inf,pos;
75     for(int i=1;i<=cnt;i++)
76         if(dg[i]==0 && ans[i].size()<ret)
77             ret=ans[i].size(),pos=i;
78 
79     printf("%d
",ret);
80     for(int i:ans[pos])
81         printf("%d ",i);
82     puts("");
83     return 0;
84 }
85 /*
86 */

View Code