Codeforces Round #124 (Div. 2)

A：博弈问题，一个矩形中，放入半径等于r的圆，谁不能放，就输了。
一开始比较茫然，仔细想一下发现有对称性质，一开始在中心放入一个圆，便将矩形分为对称区域，对手放入一个圆，则自己可以在对称的区域相同的位置放入圆。
[cpp] 
#include<iostream> 
#include<cstring> 
#include<queue> 
#include<string> 
#include<cstdio> 
#include<vector> 
#include<algorithm> 
#include<stack> 
#define N 105 
using namespace std; 
int main(){ 
    int a,b,r; 
    while(scanf("%d%d%d",&a,&b,&r)!=EOF){ 
         if(2*r>a||2*r>b) 
             printf("Second/n"); 
         else 
             printf("First/n"); 
    } 
    return 0; 
} 

B：取极限问题，比较简单，想清楚所有的情况就OK了
[cpp] 
#include<iostream> 
#include<cstring> 
#include<queue> 
#include<string> 
#include<cstdio> 
#include<algorithm> 
#define N 105 
using 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<=n;i++) 
         scanf("%d",&a[i]); 
         for(int j=0;j<=m;j++) 
         scanf("%d",&b[j]); 
         if(n==m){ 
             if(a[0]*b[0]<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>m){ 
              if(a[0]*b[0]<0) 
                 printf("-"); 
              printf("Infinity/n"); 
         } 
         else 
             printf("0/1/n"); 
    } 
    return 0; 
} 

C：选出字典序最大的子序列，维护一个单调栈就OK了
[cpp] 
#include<iostream> 
#include<cstring> 
#include<queue> 
#include<string> 
#include<cstdio> 
#include<vector> 
#include<algorithm> 
#include<stack> 
#define N 105 
using namespace std; 
char str[200005]; 
stack<char>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<len;i++){ 
            if(s.empty()) 
                s.push(str[i]); 
            else{ 
                 if(str[i]<=s.top()) 
                      s.push(str[i]); 
                 else{ 
                      while(1){ 
                          if(s.empty()) 
                              break; 
                          if(str[i]>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：一个无限大的地图，问是否能无限走下去。
对于每一个位置，如果可以从多个位置到达，则说明进入了循环，便将是可以无限移动的。
[cpp]
#include<iostream> 
#include<iomanip> 
#include<cstdio> 
#include<cstring> 
#include<algorithm> 
#include<cstdlib> 
#include<cmath> 
#include<map> 
#include<set> 
#include<queue> 
#include<string> 
#include<vector> 
#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<Node>que; 
    que.push(s); 
    memset(flag,false,sizeof(flag)); 
    while(!que.empty()){ 
        u=que.front();   www.2cto.com
        que.pop(); 
        for(int i=0;i<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<n;i++){ 
            scanf("%s",str[i]); 
            for(int j=0;j<m;j++) 
                if(str[i][j]=='S'){ 
                    s.x=i; 
                    s.y=j; 
                } 
        } 
        printf("%s/n",bfs()?"YES":"NO"); 
    } 
    return 0; 
} 

作者：ACM_cxlove