Codeforces Round #394 (Div. 2)

前一半是刚刚打完比赛的时候写的……不知为啥手腕有点僵，估计是前一个小时用力过度了吧= =

前四题看着还好，后两题就有点懵逼了……现在还不知道E题的题意到底是啥……

不管了……还没找着官方题解，贴一下自己的做法算了……

A显然是傻逼题啊……没注意到a,b都是0的情况，被hack了一次……

 #include<cstdio>

 using namespace std;

 int main(){

     int a,b;

     scanf("%d%d",&a,&b);

     if(a==&&b==)printf("NO");

     else{

         if(a>b){

             int t=a;

             a=b;

             b=t;

         }

         printf(b-a<=?"YES":"NO");

     }

     return ;

 }

B也是傻逼题，暴力判断就行……

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 bool judge();

 int n,m,a[],b[];

 int main(){

     bool ok=false;

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)scanf("%d",&a[i]);

     for(int i=;i<=n;i++)scanf("%d",&b[i]);

     for(int i=;i<n;i++){

         if(judge()){

             ok=true;

             break;

         }

         rotate(a+,a+,a+n+);

     }

     printf(ok?"YES":"NO");

     return ;

 }

 bool judge(){

     int tmp=(a[]-b[]+m)%m;

     for(int i=;i<=n;i++)if((a[i]-b[i]+m)%m!=tmp)return false;

     return true;

 }

C也是傻逼题，枚举三种符号出现在哪三行，其余的行就不用动了。

为了防止花式TLE我写了预处理代价……

 #include<cstdio>

 #include<cstring>

 #include<cctype>

 #include<algorithm>

 using namespace std;

 const int maxn=;

 char s[maxn];

 int n,m,f[maxn][],ans=0x3f3f3f3f;

 int main(){

     scanf("%d%d",&n,&m);

     memset(f,,sizeof(f));

     for(int i=;i<n;i++){

         scanf("%s",s);

         for(int j=;j<m;j++){

             if(isdigit(s[j]))f[i][]=min(f[i][],min(j,m-j));

             else if(islower(s[j]))f[i][]=min(f[i][],min(j,m-j));

             else if(s[j]=='#'||s[j]=='*'||s[j]=='&')f[i][]=min(f[i][],min(j,m-j));

         }

     }

     for(int i=;i<n;i++)for(int j=;j<n;j++)if(i!=j)for(int k=;k<n;k++)if(i!=k&&j!=k)ans=min(ans,f[i][]+f[j][]+f[k][]);

     printf("%d",ans);

     return ;

 }

D也不难吧……看了看觉得就是按排名贪心，sort一下就好了……

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn=;

 struct A{

     int x,pos;

     bool operator<(const A &a)const{return x<a.x;}

 }c[maxn];

 int n,a[maxn],b[maxn],l,r,last=-1e9+;

 int main(){

     scanf("%d%d%d",&n,&l,&r);

     for(int i=;i<=n;i++)scanf("%d",&a[i]);

     for(int i=;i<=n;i++){

         scanf("%d",&c[i].x);

         c[i].pos=i;

     }

     sort(c+,c+n+);

     bool ok=true;

     for(int i=;i<=n;i++){

         b[c[i].pos]=max(l,last+a[c[i].pos]+);

         last=b[c[i].pos]-a[c[i].pos];

         if(b[c[i].pos]>r){

             ok=false;

             break;

         }

     }

     if(ok)for(int i=;i<=n;i++){

         if(i>)printf(" ");

         printf("%d",b[i]);

     }

     else printf("-1");

     return ;

 }

E听说主要考读题……药丸啊药丸

我理解的题意是说所有边长度为1，边之间只能成直角或平角，问树是否可以画在平面上……

反正n的范围这么小，找个重心之后求个bfs序，按bfs序暴搜……反正我过了Pretest，跑的还挺快……

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<queue>

 using namespace std;

 const int maxn=,dx[]={,,-,},dy[]={-,,,};

 void getcenter(int);

 void dfs(int);

 vector<int>G[maxn];

 bool vis[maxn][maxn]={false};

 int size[maxn]={},son[maxn]={},id[maxn],tim=;

 int n,center=,x,y,du[maxn]={},a[maxn],b[maxn],p[maxn];

 bool ok=false;

 int main(){

     scanf("%d",&n);

     for(int i=;i<n;i++){

         scanf("%d%d",&x,&y);

         G[x].push_back(y);

         G[y].push_back(x);

         du[x]++;

         du[y]++;

     }

     bool bad=false;

     for(int i=;i<=n;i++)if(du[i]>){

         bad=true;

         break;

     }

     if(bad){

         printf("NO");

         return ;

     }

     getcenter();

     x=center;

     getcenter(center);

     a[x]=b[x]=;

     vis[][]=true;

     dfs();

     if(ok){

         printf("YES\n");

         for(int i=;i<=n;i++)printf("%d %d\n",a[i],b[i]);

     }

     else printf("NO");

     return ;

 }

 void getcenter(int x){

     queue<int>q;

     int tim=;

     fill(p,p+n+,);

     q.push(x);

     while(!q.empty()){

         x=q.front();

         q.pop();

         id[++tim]=x;

         size[x]=;

         for(int i=;i<(int)G[x].size();i++)if(G[x][i]!=p[x]){

             p[G[x][i]]=x;

             q.push(G[x][i]);

         }

     }

     for(int i=n;i;i--){

         x=id[i];

         size[p[x]]+=size[x];

         if(size[x]>size[son[p[x]]])son[p[x]]=x;

     }

     for(int i=;i<=n;i++){

         x=id[i];

         if(!center||max(n-size[x],size[son[x]])<max(n-size[center],size[son[center]]))center=x;

     }

 }

 void dfs(int k){

     if(k==n+){

         ok=true;

         return;

     }

     register int x=id[k];

     for(int i=;i<;i++)if(!vis[a[p[x]]+dx[i]+][b[p[x]]+dy[i]+]){

         a[x]=a[p[x]]+dx[i];

         b[x]=b[p[x]]+dy[i];

         vis[a[x]+][b[x]+]=true;

         dfs(k+);

         if(ok)return;

         vis[a[x]+][b[x]+]=false;

     }

 }

UPD：理解错了题意了…… 然后就WA了，英死早……

话说这次的比赛不太资瓷啊……room老是炸，中间好不容易能看了，lock了C之后看别人的代码，看着看着突然发现有个傻小伙把m-j写成了n-j+1，火速造了个小数据，交上去之后也不知到底hack上了没有……

本来做出来了四道水题，然后因为CF的系统不太资瓷结果unrated了……不好玩……

巴特西

Codeforces Round #394 (Div. 2)

最新文章

热门文章