Codeforces Round #270

A暴力判断即可

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
bool inprim(int a){
    int i;
    int k=sqrt(a);
    for(i=2;i<=k;i++){
        if(a%i==0)return 1;
    }
    return 0;
}
int main(){
    int n,i,j,k;
    while(scanf("%d",&n)!=EOF){
        for(i=3;i<=n/2;i++){
            if(inprim(i)&&inprim(n-i)){
                printf("%d %d\n",i,n-i);
                break;
            }
        }
    }
    return 0;
}

 2贪心的思路，每次都先把所有人都运到需要到达的最低一层，去掉到达这一层的人之后继续网上运

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
bool inprim(int a){
    int i;
    int k=sqrt(a);
    for(i=2;i<=k;i++){
        if(a%i==0)return 1;
    }
    return 0;
}
int main(){
    int n,i,j,k;
    while(scanf("%d",&n)!=EOF){
        for(i=3;i<=n/2;i++){
            if(inprim(i)&&inprim(n-i)){
                printf("%d %d\n",i,n-i);
                break;
            }
        }
    }
    return 0;
}

 

C，根据对输入的数据建图，然后dfs判断是否符合条件

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int nMax = 200007;
const int mMax = 1000008;
int n,m,nk,vis[nMax];
int smark[nMax],sum,marksort[nMax],vvv;
class edge{
public:
    int v,nex;
};edge e[mMax];
int k,head[nMax];
void addedge(int a,int b){
 //   cout<<a<<" add "<<b<<endl;
    e[k].v=b;
    e[k].nex=head[a];
    head[a]=k;k++;
}
char str1[nMax][54],str2[nMax][54];
int ipt[100012];
bool dfs(int loc){
    vis[loc]=1;
    if(loc==ipt[n]||loc==ipt[n]+n)return 1;
    for(int i=head[loc];i;i=e[i].nex){
        int v=e[i].v;
        if(vis[v]==1)continue;
        if(dfs(v))return 1;
    }return 0;
}
int main(){
    int i;
    while(scanf("%d",&n)!=EOF){
        for(i=1;i<=n;i++){
            scanf("%s%s",str1[i],str2[i]);
        }
        for(i=1;i<=n;i++){
            scanf("%d",&ipt[i]);
        }
        if(n==1){
            printf("YES\n");
            continue;
        }
        k=1;
        memset(head,0,sizeof(head));
        addedge(0,ipt[1]);
        addedge(0,ipt[1]+n);
        for(i=1;i<n;i++){
            int j=i+1;
            if(strcmp(str1[ipt[i]],str1[ipt[j]])<0){
                addedge(ipt[i],ipt[j]);
            }
            if(strcmp(str1[ipt[i]],str2[ipt[j]])<0){
                addedge(ipt[i],ipt[j]+n);
            }
            if(strcmp(str2[ipt[i]],str1[ipt[j]])<0){
                addedge(ipt[i]+n,ipt[j]);
            }
            if(strcmp(str2[ipt[i]],str2[ipt[j]])<0){
                addedge(ipt[i]+n,ipt[j]+n);
            }
        }
        memset(vis,0,sizeof(vis));
        if(dfs(0)){
            printf("YES\n");
        }else
            printf("NO\n");
    }
    return 0;
}

 D 很有意思的一题，一直以为是用floyd，后来发现不仅效率过不去，而且算法有漏洞。正确办法是，先对图求出prim最小生成树。再对最小生成树进行dfs求出任意两点间距，如果求出的这个间距和输入的矩阵相等则输出yes。要注意处理n==1的情况！一个点不是树但是空树是树！

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const long long inf=1e+20;
const int nMax=2002;
const int mMax=8000003;
long long map[2002][2002],n,ans;
long long dis[2002];
class edge{
public:
    int u,v,nex,w;
};edge e[mMax];
int k,head[nMax];//head[i]是以点i为起点的链表头部

void addedge(int a,int b,int c){//向图中加边的算法，注意加上的是有向边//b为a的后续节点既是a---->b
  //  cout<<a<<" add "<<b<<" with "<<c<<endl;
    e[k].u=a;
    e[k].v=b;
    e[k].w=c;
    e[k].nex=head[a];
    head[a]=k;k++;
}
int fff[nMax];
void prim(){   //  自己的prim模板。
    int i, j, now,aaa,bbb;
    long long  min_node, min_edge;
    for(i = 0; i < n; i ++)
        dis[i] = inf;
    now = 0;
    ans = 0;
    for(i = 0; i < n-1; i ++){
        dis[now] = -1;    //   将dis[]的值赋-1，表示已经加入生成树中。
        min_edge = inf;
        for(j = 0; j < n; j ++)    //   更新每个顶点所对应的dis[]值。
            if(now != j && dis[j] >= 0){
                if(map[now][j]<dis[j]){
                    dis[j]=map[now][j];
                    fff[j]=now;
                }
                if(dis[j] < min_edge){
                    min_edge = dis[j];
                    min_node = j;
            //        cout<<j<<"de\n";
                }
            }
        now = min_node;
        aaa=now;
        bbb=fff[now];
        ans += min_edge;
        addedge(aaa,bbb,min_edge);
        addedge(bbb,aaa,min_edge);
    }
}
bool vis[2002];
int paint[2002][2002],loc;
void dfs(int a,int w){
    vis[a]=1;
    for(int i=head[a];i;i=e[i].nex){
        int v=e[i].v;
        if(!vis[v]){
            paint[v][loc]=w+e[i].w;
            dfs(v,w+e[i].w);
        }
    }
}
int main(){
    int i,j;
    bool flag;
    while(scanf("%d",&n)!=EOF){
        flag=0;
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                scanf("%I64d",&map[i][j]);
                if(map[i][j]!=0){
                    flag=1;
                }
            }
        }
        if(n==1){
            if(map[0][0]==0)
                printf("YES\n");
            else
                printf("NO\n");
            continue;
        }
        if(!flag){
            printf("NO\n");
            continue;
        }
        flag=0;
        for(i=0;i<n;i++){
            if(map[i][i]!=0){
                    flag=1;
                    continue;
            }
        }
        if(flag){
            printf("NO\n");
            continue;
        }
        k=1;
        memset(head,0,sizeof(head));
        prim();
        memset(paint,0,sizeof(paint));
        for(i=0;i<n;i++){
            memset(vis,0,sizeof(vis));
            loc=i;
            dfs(i,0);
        }
        flag=0;
        for(i=0;i<n&&!flag;i++){
            for(j=0;j<n&&!flag;j++){
                   // cout<<paint[i][j]<<" ";
                if(map[i][j]!=paint[i][j]){
                    flag=1;
                    break;
                }
            }//cout<<endl;
        }
        if(flag){
            printf("NO\n");
        }
        else{
            printf("YES\n");
        }
    }
}