Education CodeForces Round 25 题解
A. Binary Protocol
题意
给出一个01串，这个串由十进制串encode得到，方法是每一位数字映射成为相同数量的1，数字之间用0隔开。
思路
水。
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, cur = 0, cnt = 0;
char s[100], ans[100];
scanf("%d%s", &n, s);
for (int i = 0; i < n; ++i)
s[i]-'0'? ++cnt : (ans[cur++] = cnt + '0', cnt = 0);
ans[cur++] = cnt + '0';
ans[cur] = '\0';
puts(ans);
return 0;
}
B. Five-In-a-Row
题意
给出一个五子棋盘，判断其中'X'是否是必胜态。
思路
模拟。
代码
#include <bits/stdc++.h>
using namespace std;
char maps[15][15];
int dir[8][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
bool flag = 0;
void judge(int x, int y) {
maps[x][y] = 'X';
for (int i = 0, cnt = 0; i < 10; ++i) {
maps[x][i] == 'X'? ++cnt : cnt = 0;
if (cnt == 5) flag = 1;
}
for (int i = 0, cnt = 0; i < 10; ++i) {
maps[i][y] == 'X'? ++cnt : cnt = 0;
if (cnt == 5) flag = 1;
}
for (int i = 0, j = 0, cnt = 0; i < 10 && j < 10; ++i, ++j){
int u = i, v = y - x + j;
if (y < 0 || y > 9) continue;
maps[u][v] == 'X'? ++cnt : cnt = 0;
if (cnt == 5) flag = 1;
}
for (int i = 0, j = 0, cnt = 0; i < 10 && j < 10; ++i, ++j) {
int u = i, v = y + x - j;
if (y > 9 || y < 0) continue;
maps[u][v] == 'X'? ++cnt : cnt = 0;
if (cnt == 5) flag = 1;
}
maps[x][y] = '.';
}
void check(int x, int y) {
for (int i = 0; i < 8; ++i) {
int u = x + dir[i][0], v = y + dir[i][1];
if (u < 0 || v < 0 || u > 9 || v > 9) continue;
if (maps[u][v] == '.') judge(u, v);
if (flag) return;
}
}
int main(){
#ifdef LOCAL
freopen("in.txt", "r", stdin);
#endif
for (int i = 0; i < 10; ++i) scanf("%s", maps[i]);
for (int i = 0; i < 10; ++i)
for (int j = 0; j < 10; ++j) {
if (maps[i][j] == 'X') check(i, j);
if (flag) goto a; // 闲的蛋疼
}
a:
puts(flag ? "YES" : "NO");
return 0;
}
C. Multi-judge Solving
题意
如果Makes做过难度为i的题目，他就可以做出i*2的题目。
一开始Makes做过的最高难度题是k，他要刷完他列表中所有的题，问中间需要多少道题作为跳板。
思路
贪心。把k放进数组中，然后排个序，upper_bound得到比k之后的一道题，判断是否能做出它，如果可以的话就继续upper_bound，否则判断一下需要多少道题作为跳板。
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, k, num[1007], ans = 0;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i)
scanf("%d", num+i);
num[0] = k;
sort(num, num+n+1);
for (int now = k, nxt = upper_bound(num, num+n+1, now<<1) - num, cur = 1; nxt <= n; nxt = upper_bound(num, num+n+1, now<<1) - num) {
now = num[nxt-1], cur = nxt-1;
nxt = upper_bound(num, num+n+1, now<<1) - num;
while (nxt == cur+1 && nxt != n+1) {
++ans, now <<= 1;
nxt = upper_bound(num, num+n+1, now<<1) - num;
}
}
printf("%d\n", ans);
return 0;
}
D. Suitable Replacement
题意
给出一个主串s和一个模式串t，主串中有若干'?'，需要把这些'?'填补起来。填补之后的字符串要求任意顺序中可以找到最多的模式串t。
思路
本来想的是模拟+贪心，但是想想代码量会很大。
看了dalao的代码之后换一种思路：首先统计主串中有除了'?'之外的字符数量。然后遍历主串，每遇到一个'?'就找当前'?'数量相对应的t串的位置，如果这个位置是字符是主串中含有的，就将主串这个字符的数量--，并且重新遍历这个'?'，直到遍历到一个主串中已经不含有的字符，就将t串这个字符填进去。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int main(){
int hash[26] = {}, cur = 0, len_t;
char s[maxn], t[maxn];
scanf("%s%s", s, t);
len_t = strlen(t);
for (int i = 0; s[i]; ++i) ++hash[s[i]-'a'];
for (int i = 0; s[i]; ++i) if (s[i] == '?') {
++cur, cur %= len_t;
hash[t[cur]-'a'] > 0 ? (--hash[t[cur]-'a'], --i) : s[i] = t[cur];
}
puts(s);
return 0;
}
E. Minimal Labels
题意
给出一张有向无环图，按照这张图的拓扑序给这张图的每一个节点标号，要求标号的排列是可能排列中字典序最小的。
思路
一开始想的是正常跑拓扑序，然后用优先队列来给最小的标号，但奚政巨hack了这种方法。主要问题还在于题意没有读清楚。我以为是标号对于的点的编号排列字典序最小。
既然正着不行，就反着来。反向建图，依然是优先队列，只是在拓扑序的过程中给最大的点标上最大的号。这样贪心就可以得到最佳匹配。
代码
#include <bits/stdc++.h>
using namespace std;
//#define LOCAL
const int maxn = 1e5+7;
struct Edge {
int to, nxt, dis;
}edge[maxn];
int head[maxn], tot;
int degree[maxn] = {}, v[maxn], n;
priority_queue<int> q;
void init() {
tot = 0;
memset(head, -1, sizeof head);
memset(degree, 0, sizeof degree);
}
void addnode(int u, int v) {
++degree[v];
edge[tot].to = v;
edge[tot].nxt = head[u];
head[u] = tot++;
}
void topo_sort(int n) {
int cur = n;
for (int i = 1; i <= n; ++i)
if (!degree[i]) q.push(i);
while (!q.empty()) {
int u = q.top(); q.pop();
v[u] = cur--;
for (int i = head[u]; i != -1; i = edge[i].nxt) {
int v = edge[i].to;
--degree[v];
if (!degree[v]) q.push(v);
}
}
}
int main(){
#ifdef LOCAL
freopen("in.txt", "r", stdin);
#endif
init();
int m; scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) v[i] = i;
for (int i = 0, u, v; i < m; ++i) {
scanf("%d%d", &v, &u);
addnode(u, v);
}
topo_sort(n);
for (int i = 1; i < n; ++i)
printf("%d ", v[i]);
printf("%d\n", v[n]);
return 0;
}
