Good Bye 2017

A New Year and Counting Cards

题目链接：

http://codeforces.com/contest/908/problem/A

思路：

如果卡片上面是数字，如果是奇数，就需要检查一下。如果是字母，如果是原音字母，需要检查一下。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1504;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string s,t;
    t="aeiou";
    cin>>s;
    int ans=0;
    int lens=s.length();
    int lent=t.length();
    for(int i=0;i<lens;++i) {
        if(s[i]>='0'&&s[i]<='9') {
            int num=s[i]-'0';
            if(num%2) ++ans;
        } else {
            for(int j=0;j<lent;++j) {
                if(s[i]==t[j]) {
                    ++ans;
                    break;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

B New Year and Buggy Bot

题目链接：

http://codeforces.com/contest/908/problem/B

思路：

设置方向数组，全排列。暴力DFS检查每一种的可能性。要注意DFS判断最后一步的下标，少了最后一步，结果WA8，好可惜...

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 55;
char mp[maxn][maxn];
char op[105];
int n,m,sx,sy,ex,ey;
int a[4]={0,1,2,3};
int ans=0;
int len;
bool dfs(int x, int y, int index) {
    if(index>=len) {
        if(x==ex&&y==ey) return true;
        return false;
    }
    if(x==ex&&y==ey) return true;
    int xx,yy;
    for(int i=0;i<4;++i) {
        if(op[index]-'0'==a[i]) {
            if(i==0) {
                xx=x;
                yy=y-1;
            } else if(i==1) {
                xx=x-1;
                yy=y;
            } else if(i==2) {
                xx=x;
                yy=y+1;
            } else if(i==3) {
                xx=x+1;
                yy=y;
            }
        }
    }
    if(xx<0||xx>=n||yy<0||yy>=m) return false;
    if(mp[xx][yy]=='#') return false;
    return dfs(xx,yy,index+1);
}
int main() {
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;++i) scanf("%s",mp[i]);
    scanf("%s",op);
    len=strlen(op);
    for(int i=0;i<n;++i) {
        for(int j=0;j<m;++j) {
            if(mp[i][j]=='S') {
                sx=i;
                sy=j;
            } else if(mp[i][j]=='E') {
                ex=i;
                ey=j;
            }
        }
    }
    do {
        if(dfs(sx,sy,0)) ++ans;
    } while(next_permutation(a,a+4));
    printf("%d\n",ans);
    return 0;
}

C New Year and Curling

题目链接：

http://codeforces.com/contest/908/problem/C

思路：

这道题目，按照先后顺序依次访问每一个掉落下来的圆。计算和之前的圆是否存在相交或者是相切的关系，如果存在，计算出纵坐标。然后在纵坐标中渠道最大值即可。因为碰到第一个圆就停止了，不可能再与其他的圆相切。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1005;
int x[maxn];
double y[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,r;
    cin>>n>>r;
    for(int i=1;i<=n;++i) {
        cin>>x[i];
        y[i]=r*1.0;
    }
    for(int i=2;i<=n;++i) {
        for(int j=i-1;j>=1;--j) {
            int ll=1005,rr=1;
            ll=min(min(ll,x[j]-r),x[i]-r);
            rr=max(max(rr,x[j]+r),x[i]+r);
            if(rr-ll>4*r) continue;
            double temp=sqrt(4*r*r*1.0-(x[i]*1.0-x[j]*1.0)*(x[i]*1.0-x[j]*1.0))+y[j];
            y[i]=max(temp,y[i]);
        }
    }
    for(int i=1;i<=n;++i) {
        if(i==1) cout<<setiosflags(ios::fixed)<<setprecision(8) << y[i];
        else cout<<" "<<setiosflags(ios::fixed)<<setprecision(8) << y[i];
    }
    cout<<endl;
    return 0;
}