Codeforces Round #376 (Div. 2)

A:随便c

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main(){
 4     int n,m,ans=0;
 5     char ch[108];
 6     scanf("%s",ch);
 7     int q,l=strlen(ch)-1;int a,b,pre='a';
 8     for(int i=0;i<=l;i++){
 9         if(ch[i]<pre) a=ch[i],b=pre;
10         else a=pre,b=ch[i];q=b-a;
11         if(q>a+26-b) q=a+26-b;
12         ans+=q;pre=ch[i];
13     }printf("%d
",ans);
14     return 0;
15 }

View Code

B：太过相信自己的英语，prohibited是不行的意思，按顺序c就行

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main(){
 4     int n,m,ans=0;
 5     int x[1000008];scanf("%d",&n);
 6     for(int i=1;i<=n;i++) scanf("%d",&x[i]);
 7     ans=1;
 8     for(int i=1;i<=n+1;i++){
 9         if(x[i]==-1) {ans=0;break;}
10         x[i]=x[i]%2;
11         if(x[i]) x[i+1]--;
12     }if(ans) printf("YES
");
13     else printf("NO
");
14     return 0;
15 }

View Code

C：vector或者搜索，每次给当前访问的加标记，标记相同就++，不同则初始化为1.

#include<bits/stdc++.h>
using namespace std;
int x[200005],st[200005],tot,colors[200005],n,ne,m,k,ans,head[200005],cnt;
bool vis[200005];
struct{int to,next;}e[400005];
void dfs(int k,int t){
    tot++;
    vis[k]=1;if(st[x[k]]!=t) colors[x[k]]=1;else colors[x[k]]++;st[x[k]]=t;
    if(colors[x[k]]>colors[ne]) ne=x[k];
    for(int i=head[k];i;i=e[i].next){
        if(!vis[e[i].to]) dfs(e[i].to,t);
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) scanf("%d",&x[i]);int a,b;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        e[++cnt].to=b;e[cnt].next=head[a];head[a]=cnt;
        e[++cnt].to=a;e[cnt].next=head[b];head[b]=cnt;
    }
    for(int i=1;i<=n;i++){ne=0;colors[ne]=0;tot=0;
        if(!vis[i]) dfs(i,i);
        ans+=tot-colors[ne];
    }
    printf("%d
",ans);
    return 0;
}

//证明：总空间是O（n）的 
//PS：dfs遍历就好

View Code

D:给你n个word，每个word都有若干个字母，现在要使得从上到下的word都必须小于或等于下一个word，你可以操作一次钥匙将所有word的所有字母都加上1，如果>c，就变为1，问是否有解，有的话随意输出，没有的话就输出-1；

每两个需交换的word确定一个区间。扫一遍即可