Codeforces Round #124 (Div. 2)

Problem A

水题，以前写过类似的，给你一个正方形，两个人轮流画圆，画不下的一方为输，如果第一个画的下

肯定先手赢，反之后手赢，因为，先手可以画在正中间，然后对称地跟着后手画就好了。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,r;
    cin>>a>>b>>r;
    if(2*r<=a && 2*r<=b) puts("First");
    else puts("Second");
    return 0;
}

View Code

Problem B

简单高数知识?一开始手误WA了一次。。菜啊这都能打错，反省反省。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[101],b[101];
int main()
{
    cin>>n>>m;
    for(int i=0;i<=n;i++) scanf("%d",&a[i]);
    for(int i=0;i<=m;i++) scanf("%d",&b[i]);
    if(n>m)
    {
        if(a[0]*b[0]>0) puts("Infinity");
        else puts("-Infinity");
    }
    else if(m>n)
    {
        puts("0/1");
    }
    else
    {
        int g=__gcd(a[0],b[0]);
        if(a[0]*b[0]>0) printf("%d/%d
",a[0]/g,b[0]/g);
        else
        {
            printf("-%d/%d
",abs(a[0]/g),abs(b[0]/g));
        }
    }
    return 0;
}

View Code

Problem C

水题,让你从一个字符串里面取出一些字符，要求这些字符组成的字符串字典序最大。

随便写一写，好像写的有点搓，看别人20多行解决，我居然写了这么多！！！

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3;
char s[N];
struct node
{
    int cnt;
    char c;
}w[26];
vector <char> ans;
int main()
{
    scanf("%s",s);
    int len=strlen(s);
    char mx='a';
    int item=0;
    for(int i=0;i<26;i++) w[i].cnt=0,w[i].c=i+'a';
    for(int i=0;i<len;i++)
    {
        w[s[i]-'a'].cnt++;
        if(mx<s[i])
        {
            mx=s[i];
            item=i;
        }
    }
    char now;
    int pos=25;
    int cans=0;
    for(int i=0;i<len;i++)
    {
        while(!w[pos].cnt) pos--;
        now=w[pos].c;
        if(s[i]==now)
        {
            w[pos].cnt--;
            ans.push_back(s[i]);
            cans++;
        }
        else w[s[i]-'a'].cnt--;
    }
    for(int i=0;i<cans;i++) printf("%c",ans[i]);
    puts("");
    return 0;
}

View Code

Problem D

题目大意：给你一个n*m的图，将这个图无限扩充，对即任意的i，j , map[i][j]=map[i%n][j%m]。问你从

起点开始能不能走无限远。

我刚开始想的时候的思路是，如果我能从一个起始点走到另一个对应起始点的点就行了，这样就能无限

循环走下去，可是我在写dfs(bfs)的时候是用在原图中的对应点表示的，这样我就没招了，其实应该是用

实际的点表示，如在递归的时候我们应该保存的是x+d[i],y+d[i],而不是(x+d[i])%n,(y+d[i])%m;,这样的话

我们就用一个pair类型item[i][j] 表示对应i,j这个点之前的实际点。如果遇到一个item[i][j]表示的x，y与现在

的实际位置不同则是YES，因为可以无限循环了。

#include<bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N=1505;
int n,m;
bool flag,vis[N][N];
char w[N][N];
pii item[N][N];
int dx[]={0,0,-1,1},dy[]={1,-1,0,0};
void dfs(int x,int y)
{
    int nx=x,ny=y;
    while(nx<0) nx+=n;
    while(ny<0) ny+=m;
    nx%=n;ny%=m;
    if(vis[nx][ny] && ((item[nx][ny].first!=x) || (item[nx][ny].second!=y)) )
    {
        flag=true;
        return;
    }
    if(vis[nx][ny] || w[nx][ny]=='#') return;
    item[nx][ny]=make_pair(x,y);
    vis[nx][ny]=true;
    for(int i=0;i<4;i++)
    {
        dfs(x+dx[i],y+dy[i]);
        if(flag) return;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%s",w[i]);
    int sx,sy;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            if(w[i][j]=='S')
            {
                sx=i;sy=j;
                i=n;
                break;
            }
        }
    flag=false;
    dfs(sx,sy);
    if(flag) puts("Yes");
    else puts("No");
    return 0;
}

View Code