Codeforces Round #207 (Div. 2)

A:超级大水题；

代码：

 1 #include<cstdio>
 2 #define maxn 105
 3 using namespace std;
 4 int n,a[maxn],x,y,ans;
 5 int main()
 6 {
 7     scanf("%d",&n);
 8     for(int i=1; i<=n; i++)
 9     {
10         scanf("%d",&x);
11         a[i]=a[i-1]+x;
12         ans+=x;
13     }
14     scanf("%d%d",&x,&y);
15     int i;
16     for(i=1; i<=n; i++)
17         if(a[i]>=x&&a[i]<=y&&(ans-a[i])>=x&&(ans-a[i])<=y)
18         {
19             printf("%d",i+1);
20             break;
21         }
22     if(i>n)printf("0");
23     return 0;
24 }

View Code

B：因为每次跳舞最多只有一个人以前跳过，所以很简单；

 1 #include<cstdio>
 2 #define maxn 100005
 3 using namespace std;
 4 
 5 int n,m,color[maxn],x,y,z;
 6 
 7 int main()
 8 {
 9     scanf("%d%d",&n,&m);
10     for(int i=0;i<m;i++)
11     {
12         scanf("%d%d%d",&x,&y,&z);
13         if(color[x]!=0)
14         {
15             color[y]=(6-color[x])/2+1;
16             color[z]=(6-color[x]-color[y]);
17         }
18         else if(color[y]!=0)
19         {
20             color[x]=(6-color[y])/2+1;
21             color[z]=(6-color[x]-color[y]);
22         }
23         else if(color[z]!=0)
24         {
25             color[x]=(6-color[z])/2+1;
26             color[y]=(6-color[x]-color[z]);
27         }
28         else
29         {
30             color[x]=1;
31             color[y]=2;
32             color[z]=3;
33         }
34     }
35     for(int i=1;i<=n;i++)
36         printf("%d ",color[i]);
37     return 0;
38 }

View Code

C：自己没出，学习了大神们的代码

用并查集来缩点太妙了！

 1 #include <cstdio>
 2 using namespace std;
 3 #define maxn 300100
 4 int r[maxn],ret[maxn];
 5 int find(int x)
 6 {
 7     if(x!=r[x])r[x]=find(r[x]);
 8     return r[x];
 9 }
10 int n,m,L,R,x;
11 int main()
12 {
13     scanf("%d%d",&n,&m);
14     for(int i=1; i<=n+1; i++)r[i]=i;
15     while(m--)
16     {
17         scanf("%d%d%d",&L,&R,&x);
18         int u;
19         u=find(L);
20         while(1)
21         {
22             if(u>=x)break;
23             ret[u]=x;
24             r[u]=u+1;
25             u=find(u);
26         }
27         u=find(x+1);
28         while(1)
29         {
30             if(u>R)break;
31             ret[u]=x;
32             r[u]=u+1;
33             u=find(u);
34         }
35     }
36     for(int i=1; i<=n; i++)
37         printf("%d ",ret[i]);
38     return 0;
39 }

View Code

本题还可以用线段树来做，可惜当初学得太渣了！

花了一个下午学习线段树的延迟标记，终于会敲了！

线段树版代码：

 1 #include<cstdio>
 2 #define maxn 300010
 3 using namespace std;
 4 
 5 struct tree
 6 {
 7     int l,r,flag;
 8     tree *left,*right;
 9 } tr[maxn<<1];
10 
11 int m,n,ans,a[maxn],b[maxn],c[maxn],treecount;
12 
13 void build(tree *root,int l,int r)
14 {
15     root->l=l;
16     root->r=r;
17     root->flag=0;
18     if(l==r)return;
19     int mid=(l+r)>>1;
20     treecount++;
21     root->left=tr+treecount;
22     treecount++;
23     root->right=tr+treecount;
24     build(root->left,l,mid);
25     build(root->right,mid+1,r);
26 }
27 
28 void insert(tree *root,int l,int r,int w)
29 {
30     if(l<=root->l&&r>=root->r)
31     {
32         root->flag=w;
33         return;
34     }
35     if(root->flag!=0)
36     {
37         root->left->flag=root->right->flag=root->flag;
38         root->flag=0;
39     }
40     int mid=(root->l+root->r)>>1;
41     if(r<=mid)insert(root->left,l,r,w);
42     else if(l>=mid+1)insert(root->right,l,r,w);
43     else
44     {
45         insert(root->left,l,mid,w);
46         insert(root->right,mid+1,r,w);
47     }
48 }
49 
50 void query(tree *root,int x)
51 {
52     if(root->l==root->r){ans=root->flag;return;}
53     if(root->flag!=0)
54         root->left->flag=root->right->flag=root->flag;
55     int mid=(root->l+root->r)>>1;
56     if(x<=mid)query(root->left,x);
57     else query(root->right,x);
58 }
59 
60 int main()
61 {
62     scanf("%d%d",&n,&m);
63     build(tr,1,n);
64     for(int i=0; i<m; i++)
65         scanf("%d%d%d",&a[i],&b[i],&c[i]);
66     for(int i=m-1; i>=0; i--)
67     {
68         if(c[i]!=a[i])insert(tr,a[i],c[i]-1,c[i]);
69         if(c[i]!=b[i])insert(tr,c[i]+1,b[i],c[i]);
70     }
71     insert(tr,c[m-1],c[m-1],0);
72     for(int i=1; i<=n; i++)
73     {
74         query(tr,i);
75         printf("%d ",ans);
76     }
77     return 0;
78 }

View Code

假设la是第一个字符串的长度，lb是第二个的长度；

如果求出他们的最小公倍数 l 长度的串的哈密顿距离就行了；

但是不能直接求；

方法：找到任一一串中每个字符所对应的另外一个字符串中所出现的字符；

然后统计起来，乘上相应的倍数就行了！

代码：

 1 #define maxn 1000005
 2 #define ll long long
 3 #include<cstring>
 4 #include<iostream>
 5 using namespace std;
 6 
 7 char a[maxn],b[maxn];
 8 ll cnt[maxn][26];
 9 ll gcd(ll x,ll y)
10 {
11     return (x%y)?gcd(y,x%y):y;
12 }
13 int main()
14 {
15     ll n,m,la,lb,g,l,ans;
16     cin>>n>>m;
17     cin>>a>>b;
18     la=strlen(a),lb=strlen(b);
19     g=gcd(la,lb);
20     l=la/g*lb;
21     ans=l;
22     for(ll i=0;i<lb;i++)
23         cnt[i%g][b[i]-'a']++;
24     for(ll i=0;i<la;i++)
25         ans-=cnt[i%g][a[i]-'a'];
26     cout<<ans*(n*la/l)<<endl;
27     return 0;
28 }

View Code

E: 贪心

1.首先合并1和2，变成3；

2.如果1有剩，将1合并成3；如果合并完了之后还有剩：剩1，有3，+1；否则+2；

3.如果2有剩，将3个2合并成3，如果合并完之后还有剩，剩1个，有4，+1；否则+2；

代码：

 1 #include<iostream>
 2 using namespace std;
 3 int n,ans,a[5],x,s;
 4 int main()
 5 {
 6     cin>>n;
 7     while(n--)
 8     {
 9         cin>>x;
10         a[x]++,s+=x;
11     }
12     if(s<3||s==5){cout<<"-1";return 0;}
13     ans+=x=a[1]<a[2]?a[1]:a[2];
14     a[1]-=x,a[2]-=x,a[3]+=x;
15     if(a[1])
16     {
17         ans+=2*(x=a[1]/3);
18         a[1]-=x*3;
19         a[3]+=x;
20         if(a[1])
21         {
22             if(a[1]==1&&a[3])ans++;
23             else ans+=2;
24         }
25     }
26     else
27     {
28         ans+=2*(x=a[2]/3);
29         a[2]-=x*3;
30         a[3]+=x*2;
31         if(a[2])
32         {
33             if(a[2]==1&&a[4])ans++;
34             else ans+=2;
35         }
36     }
37     cout<<ans;
38 }

View Code