Codeforces Round #124 (Div. 二)

Codeforces Round #124 (Div. 2)

转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

A：博弈问题，一个矩形中，放入半径等于r的圆，谁不能放，就输了。

一开始比较茫然，仔细想一下发现有对称性质，一开始在中心放入一个圆，便将矩形分为对称区域，对手放入一个圆，则自己可以在对称的区域相同的位置放入圆。

#include&lt;iostream&gt;#include&lt;cstring&gt;#include&lt;queue&gt;#include&lt;string&gt;#include&lt;cstdio&gt;#include&lt;vector&gt;#include&lt;algorithm&gt;#include&lt;stack&gt;#define N 105using namespace std;int main(){    int a,b,r;    while(scanf("%d%d%d",&a,&b,&r)!=EOF){         if(2*r&gt;a||2*r&gt;b)             printf("Second\n");         else             printf("First\n");    }    return 0;}

B：取极限问题，比较简单，想清楚所有的情况就OK了

#include&lt;iostream&gt;#include&lt;cstring&gt;#include&lt;queue&gt;#include&lt;string&gt;#include&lt;cstdio&gt;#include&lt;algorithm&gt;#define N 105using namespace std;int gcd(int a,int b){    return b==0?a:gcd(b,a%b);}int main(){    int n,m;    int a[105],b[105];    while(scanf("%d%d",&n,&m)!=EOF){         for(int i=0;i&lt;=n;i++)         scanf("%d",&a[i]);         for(int j=0;j&lt;=m;j++)         scanf("%d",&b[j]);         if(n==m){             if(a[0]*b[0]&lt;0)                 printf("-");             printf("%d/%d\n",abs(a[0])/gcd(abs(a[0]),abs(b[0])),abs(b[0])/gcd(abs(a[0]),abs(b[0])));         }         else if(n&gt;m){              if(a[0]*b[0]&lt;0)                 printf("-");              printf("Infinity\n");         }         else             printf("0/1\n");    }    return 0;}

C：选出字典序最大的子序列，维护一个单调栈就OK了

#include&lt;iostream&gt;#include&lt;cstring&gt;#include&lt;queue&gt;#include&lt;string&gt;#include&lt;cstdio&gt;#include&lt;vector&gt;#include&lt;algorithm&gt;#include&lt;stack&gt;#define N 105using namespace std;char str[200005];stack&lt;char&gt;s,ans;int main(){    while(scanf("%s",str)!=EOF){        while(!s.empty())            s.pop();        while(!ans.empty())            ans.pop();        int len=strlen(str);        for(int i=0;i&lt;len;i++){            if(s.empty())                s.push(str[i]);            else{                 if(str[i]&lt;=s.top())                      s.push(str[i]);                 else{                      while(1){                          if(s.empty())                              break;                          if(str[i]&gt;s.top())                              s.pop();                          else                              break;                      }                      s.push(str[i]);                 }            }        }            while(!s.empty()){            ans.push(s.top());            s.pop();        }        while(!ans.empty()){            printf("%c",ans.top());            ans.pop();        }        printf("\n");            }    return 0;}

D：一个无限大的地图，问是否能无限走下去。

对于每一个位置，如果可以从多个位置到达，则说明进入了循环，便将是可以无限移动的。

#include&lt;iostream&gt;#include&lt;iomanip&gt;#include&lt;cstdio&gt;#include&lt;cstring&gt;#include&lt;algorithm&gt;#include&lt;cstdlib&gt;#include&lt;cmath&gt;#include&lt;map&gt;#include&lt;set&gt;#include&lt;queue&gt;#include&lt;string&gt;#include&lt;vector&gt;#define eps 1e-10#define LL long long#define LD long double#define pi acos(-1.0)using namespace std;struct Node{int x,y;}s,u,v,tt;int n,m;int way[4][2]={{0,1},{0,-1},{1,0},{-1,0}};bool flag[1505][1505];int vis[1505][1505][2];char str[1505][1505];bool bfs(){queue&lt;Node&gt;que;que.push(s);memset(flag,false,sizeof(flag));while(!que.empty()){u=que.front();que.pop();for(int i=0;i&lt;4;i++){v=u;v.x+=way[i][0];v.y+=way[i][1];tt.x=((v.x%n)+n)%n;tt.y=((v.y%m)+m)%m;if(str[tt.x][tt.y]=='#')continue;if(flag[tt.x][tt.y]){if(v.x!=vis[tt.x][tt.y][0]||v.y!=vis[tt.x][tt.y][1])return true;}else{flag[tt.x][tt.y]=true;vis[tt.x][tt.y][0]=v.x;vis[tt.x][tt.y][1]=v.y;que.push(v);}}}return false;}int main(){while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i&lt;n;i++){scanf("%s",str[i]);for(int j=0;j&lt;m;j++)if(str[i][j]=='S'){s.x=i;s.y=j;}}printf("%s\n",bfs()?"YES":"NO");}return 0;}

E：构造？？？还没搞定，待更新。

Codeforces Round #124 (Div. 二)

热点推荐