Codeforces Round #459 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #459 (Div. 2)
过题数：4
排名：75/10531

A. Eleven

题意

输出一个长度为 $n$ 的字符串，如果 $i$ 是斐波那契数列中的某个数字，则这个字符串的第 $i$ 位为 $O$，否则它的第 $i$ 位为 $o$。

输入

输入只包含一个整数 $n~(1\leq n\leq1000)$

输出

输出所求字符串。

样例

题解

预处理出 $1000$ 以内的斐波那契数列，每次二分查找数列中是否存在 $i$ 来判断输出 $O$ 还是 $o$。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
int n;
int fib[maxn];
int *it;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    fib[1] = fib[2] = 1;
    for(int i = 3; i < 20; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    while(scanf("%d", &n) != EOF) {
        for(int i = 1; i <= n; ++i) {
            it = lower_bound(fib, fib + 20, i);
            if(*it == i) {
                printf("O");
            } else {
                printf("o");
            }
        }
        printf("\n");
    }
    return 0;
}

B. Radio Station

题意

每个 $ip$ 地址都有一个名字 $name$，总共有 $n$ 个 $ip$，有 $m$ 条关于 $ip$ 的命令，现在要在每条命令后面加上 $ip$ 的名字并输出。

输入

第一行为两个整数 $n,m~(1\leq n,m\leq1000)$，接下去 $n$ 行，每行由一个字符串 $name~(1\leq|name|\leq10)$ 和一个 $ip$ 地址组成，$ip$ 地址的格式一定为 $a.b.c.d$，其中 $0\leq a,b,c,d\leq255$ 且没有前导零，接下去 $m$ 行每行由一条字符串 $command~(1\leq|command|\leq10)$ 和一个 $ip$ 地址组成，$name$ 和 $command$ 都只由小写字母组成。

输出

输出 $m$ 行，每行为一条命令所对应的输出。

样例

题解

按题意写，用一个 $map$ 存一下字符串之间的映射。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
int n, m;
string name, ip, command;
map<string, string> mp;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(cin >> n >> m) {
        mp.clear();
        for(int i = 0; i < n; ++i) {
            cin >> name >> ip;
            mp[ip] = name;
        }
        for(int i = 0; i < m; ++i) {
            cin >> command >> ip;
            cout << command << " " << ip << " #" << mp[ip.substr(0, ip.length() - 1)] << endl;
        }
    }
    return 0;
}

C. The Monster

题意

给定一个只由 (、) 和 ? 组成的字符串，问有多少个 $(l,r)$ 区间，将这些区间中的所有 ? 用 ( 或者 ) 替换后，能够成为一个合法的括号序列。

输入

输入为一个只含有 (、) 和 ? 的字符串 $s~(2\leq|s|\leq5000)$。

输出

输出所有满足条件的区间数量。

样例

题解

$n^2$ 扫描所有区间，对于每个区间，$O(1)$ 地统计区间中左括号和右括号的配对情况（用一个变量 $tmp$ 记录，遇到左括号则 $+1$，遇到右括号则 $-1$），以及问号的个数 $num$，则对于任意一个区间，如果出现 $tmp+num<0$ 的情况，说明后面无论是什么样的序列都无法完成匹配，直接跳出循环，如果是 $abs(tmp)\leq num$ 且 $num-abs(tmp)$ 为偶数，则可能可以构成一个合法的序列，但是这样无法区分 ????((() 和 (((????) 的情况（两种情况都满足前面的条件，第一个序列显然不合法而第二个序列显然合法），因此可以反过来从后往前再扫一遍整个字符串，取两次扫描合法区间的交集的个数，就是答案。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 5000 + 100;
int num, tmp, len, ans;
char str[maxn];
int cnt[maxn][maxn];
void solve(int Begin, int End, int d, char chl, char chr) {
    for(int i = Begin; i != End; i += d) {
        tmp = num = 0;
        for(int j = i; j != End; j += d) {
            if(str[j] == chl) {
                ++tmp;
            } else if(str[j] == chr) {
                --tmp;
            } else {
                ++num;
            }
            if(num + tmp < 0) {
                break;
            }
            if(num >= abs(tmp) && (num - abs(tmp)) % 2 == 0) {
                if(Begin < End) {
                    ++cnt[i][j];
                } else {
                    ++cnt[j][i];
                }
            }
        }
    }
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%s", str + 1) != EOF) {
        ans = 0;
        len = strlen(str + 1);
        for(int i = 1; i <= len; ++i) {
            memset(cnt[i], 0, sizeof(int) * (len + 1));
        }
        solve(1, len + 1, 1, '(', ')');
        solve(len, 0, -1, ')', '(');
        for(int i = 1; i <= len; ++i) {
            for(int j = i; j <= len; ++j) {
                if(cnt[i][j] == 2) {
                    ++ans;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

D. MADMAX

题意

$Max$ 和 $Lucas$ 两个人在一个 $n$ 个节点的 $DAG$ 上进行博弈游戏，每条边上都有一个小写字母，最初两个人分别在节点 $i$ 和节点 $j$ 上，由 $Max$ 开始两个人轮流进行移动，除了第一次移动，后面的每一次移动经过的边上的字母的 $ASCII$ 码都必须不小于前一次移动所经过的边上的字母，最终无法移动的人失败，在两人都采取最优策略的情况下，问谁将获胜。

输入

第一行为两个整数 $n,m~(2\leq n\leq100,1\leq m\leq\frac{n(n-1)}{2})$，接下来 $m$ 行每行两个整数 $u,v~(1\leq v,u\leq n,v\neq u)$ 以及一个小写字母 $c$，表示从 $u$ 到 $v$ 有一条有向边，边上的字母为 $c$。

输出

输出一个 $n\times n$ 的字符矩阵，若最初 $Max$ 在第 $i$ 个节点且 $Lucas$ 在第 $j$ 个节点时，在双方都采取最优策略下 $Max$ 会获胜，则矩阵的第 $i$ 行第 $j$ 列为 $A$，否则为 $B$。

样例

输入	输出	提示
4 4 1 2 b 1 3 a 2 4 c 3 4 b	BAAA ABAA BBBA BBBB	地图如下：
5 8 5 3 h 1 2 c 3 1 c 3 2 r 5 1 r 4 3 z 5 4 r 5 2 h	BABBB BBBBB AABBB AAABA AAAAB	地图如下：

题解

记录状态 $dp[i][j][k]$ 表示先手在第 $i$ 个节点而后手在第 $j$ 个节点，且当前先手走过的边上的字符必须不小于 $'a'+k$ 时，先手必胜还是必败，最后输出 $dp[i][j][0]$，就是答案。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 100 + 100;
struct Node {
    int pos;
    char ch;
    Node() {}
    Node(int p, char c) {
        pos = p;
        ch = c;
    }
};
int n, m, u, v;
char ch[2];
vector<Node> G[maxn];
char str[maxn][maxn][26];
int id(char ch) {
    return ch - 'a';
}
char dfs(int x, int y, char ch) {
    if(str[x][y][id(ch)] != '\0') {
        return str[x][y][id(ch)];
    }
    char ret = 'B';
    int len = G[x].size();
    for(int i = 0; i < len; ++i) {
        int pos = G[x][i].pos;
        char c = G[x][i].ch;
        if(c >= ch && dfs(y, pos, c) == 'B') {
            ret = 'A';
            break;
        }
    }
    str[x][y][id(ch)] = ret;
    return ret;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        memset(str, 0, sizeof(str));
        for(int i = 1; i <= n; ++i) {
            G[i].clear();
        }
        for(int i = 0; i < m; ++i) {
            scanf("%d%d%s", &u, &v, ch);
            G[u].push_back(Node(v, ch[0]));
        }
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                dfs(i, j, 'a');
            }
        }
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                printf("%c", str[i][j][0]);
            }
            printf("\n");
        }
    }
    return 0;
}