Good Bye 2017

Codeforces

Contests 链接：Good Bye 2017
过题数：3
排名：1074/10923

A. New Year and Counting Cards

题意

有一些卡片，每张卡片有正反两面，一面为小写字母，另一面为一位数字，如果对于每个元音字母背面都是一个偶数的话，这些卡片的状态就为真，否则就为假，给出 $n$ 张卡片，问最坏情况下，最少需要看多少张卡片的背面，才能确定所有卡片的状态，卡片用字符串 $s$ 表示。

数据范围

$1\leq \left|s\right|\leq50$

题解

统计字符串中奇数与元音字母的个数。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100;
char str[maxn];
char ch[11] = "aeiou13579";
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%s", str) != EOF) {
        int ans = 0;
        for(int i = 0; str[i]; ++i) {
            for(int j = 0; j < 10; ++j) {
                if(str[i] == ch[j]) {
                    ++ans;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

B. New Year and Buggy Bot

题意

给机器人一个指令 $s$，指令中只包含 $0,1,2,3$，每个数字代表"上下左右"中的一个方向，但是机器人忘了它们分别是如何一一对应的，问存在多少种指令的分配方式，使得机器人在 $n\times m$ 的矩阵中，能够从 $S$ 位置移动到 $E$ 位置，其中 $\#$ 是障碍物，机器人不能通过。

数据范围

$2\leq n,m\leq50\\1\leq\left|s\right|\leq100$

题解

用 next_permutation 函数将所有分配方式都在图上模拟跑一遍，存在一次可行，就输出计数加一。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 200;
int n, m, x, y;
char str[maxn];
char G[maxn][maxn];
const int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
int f[10];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
//    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        for(int i = 1; i <= n; ++i) {
            scanf("%s", G[i] + 1);
            G[i][0] = G[i][m + 1] = '#';
            for(int j = 1; j <= m; ++j) {
                if(G[i][j] == 'S') {
                    x = i;
                    y = j;
                }
            }
        }
        for(int i = 0; i <= m + 1; ++i) {
            G[0][i] = G[n + 1][i] = '#';
        }
        scanf("%s", str);
        for(int i = 0; i < 4; ++i) {
            f[i] = i;
        }
        int ans = 0;
        int xx, yy;
        do {
            xx = x;
            yy = y;
            for(int i = 0; str[i]; ++i) {
                int tmp = str[i] - '0';
                xx += dir[f[tmp]][0];
                yy += dir[f[tmp]][1];
                if(G[xx][yy] == 'E') {
                    ++ans;
                    break;
                } else if(G[xx][yy] == '#') {
                    break;
                }
            }
        } while(next_permutation(f, f + 4));
        printf("%d\n", ans);
    }
    return 0;
}

C. New Year and Curling

题意

$n$ 个半径为 $r$ 的圆，从 $x=x_i,y$→$\infty$ 的地方向 $y=0$ 竖直下落，碰到之前的圆或者 $y=0$ 则停止，输出每次下落后，每个圆停止位置的圆心纵坐标，输出精确到小数点后六位。

数据范围

$1\leq n,r\leq1000\\1\leq x_i\leq1000$

题解

因为 $n$ 很小，所以每次下落 $O(n)$ 判断是否和已经停止的圆相切，如果相切，则计算出纵坐标，否则纵坐标为 $r$，可以 $O(n^2)$ 解决。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
struct Node {
    LL x;
    long double y;
};
int n;
LL r;
Node node[maxn];
long double get_y(LL x, long double y, LL xtmp) {
    if(abs(x - xtmp) > 2 * r) {
        return r;
    }
    return sqrt((4 * r * r) - (x - xtmp) * (x - xtmp)) + y;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
//    ios::sync_with_stdio(false);
    while(scanf("%d%I64d", &n, &r) != EOF) {
        for(int i = 0; i < n; ++i) {
            scanf("%I64d", &node[i].x);
            long double ans = r;
            for(int j = 0; j < i; ++j) {
                ans = max(ans, get_y(node[j].x, node[j].y, node[i].x));
            }
            node[i].y = ans;
            printf("%.11f\n", (double)node[i].y);
        }
    }
    return 0;
}