A - Majority
先这样再那样最后这样，就是这样。
点击查看代码
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n, a;
char s[15];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
scanf("%s", s);
if(s[0] == 'F') a ++;
}
if(a > n - a) puts("Yes");
else puts("No");
return 0;
}
B - Postal Card
直接记录每个串的后三位，用 bool 数组记录是否出现，
循环枚举就好。
点击查看代码
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1005;
int n, m, ans;
bool vis[N];
char s[10], t[N][10];
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i ++) {
scanf("%s", t[i]);
}
for(int i = 1; i <= m; i ++) {
scanf("%s", s);
int tmp = 0;
for(int j = 0; j < 3; j ++) tmp = tmp * 10 + s[j] - '0';
vis[tmp] = 1;
}
for(int i = 1; i <= n; i ++) {
int tmp = 0;
for(int j = 3; j < 6; j ++) tmp = tmp * 10 + t[i][j] - '0';
if(vis[tmp]) ans ++;
}
printf("%d", ans);
return 0;
}
C - Path Graph?
分析可得，满足条件的边数为 n - 1 且图中不存在度数 > 2 的点，
然后继续递归判断。
完了。
点击查看代码
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 2e5 + 5;
int n, m, in[N];
int tot, head[N], nex[N << 1], to[N << 1];
void add(int x, int y) {
to[++tot] = y, nex[tot] = head[x], head[x] = tot;
}
queue<int> q;
bool vis[N];
void dfs() {
q.push(1), vis[1] = 1;
int now, ver;
while(!q.empty()) {
now = q.front(), q.pop();
for(int i = head[now]; i; i = nex[i]){
ver = to[i];
if(!vis[ver]) {
vis[ver] = 1;
q.push(ver);
}
}
}
}
int main() {
scanf("%d %d", &n, &m);
int u, v;
for(int i = 1; i <= m; i ++) {
scanf("%d %d", &u, &v);
add(u, v), add(v, u);
in[u] ++, in[v] ++;
}
if(n - 1 != m) {
puts("No");
return 0;
}
for(int i = 1; i <= n; i ++) {
if(in[i] > 2) {
puts("No");
return 0;
}
}
dfs();
for(int i = 1; i <= n; i ++) {
if(!vis[i]) {
puts("No");
return 0;
}
}
puts("Yes");
return 0;
}
D - Match or Not
双指针判断两个字符串的公共前后缀长度，再逐一枚举 x 进行比较。
点击查看代码
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 3e5 + 5;
int n, m;
char s[N], t[N];
bool check(int x, int y) {
return s[x] == t[y] || s[x] == '?' || t[y] == '?';
}
int main() {
scanf("%s %s", s, t);
n = strlen(s) - 1, m = strlen(t);
int l = 0, r = 0;
for(int i = 0; i < m; i ++) {
if(check(i, i)) l ++;
else break;
}
for(int i = m - 1; i >= 0; i --) {
if(check(n, i)) r ++, n --;
else break;
}
for(int i = 0; i <= m; i ++) {
if(i <= l && m - i <= r) puts("Yes");
else puts("No");
}
return 0;
}
E - Karuta
建立 trie 树，每个点标记在所有字符串中出现的次数，
完了再搜一遍，当记录次数为 1 时，说明能遍历到当前位置的字符串只有它自己，
于是输出。
点击查看代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;
const int N = 5e5 + 5;
vector<string> s;
string str;
int n, tot, num[N], tr[N][26];
void ins(string &s) {
int v, len = s.length(), now = 0;
for(int i = 0; i < len; i ++) {
v = s[i] - 'a';
if(!tr[now][v]) tr[now][v] = ++tot;
now = tr[now][v];
num[now] ++;
}
}
int query(string &s) {
int res = 0, len = s.length(), v, now = 0;
for(int i = 0; i < len; i ++) {
v = s[i] - 'a';
now = tr[now][v];
if(num[now] == 1) return res;
res ++;
}
return res;
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
cin >> str;
s.push_back(str);
ins(str);
}
for(int i = 0; i < n; i ++) {
printf("%d\n", query(s[i]));
}
return 0;
}
F - Components
树形 DP。
(忘了)
点击查看代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;
#define int long long
const int N = 5005, mod = 998244353;
int n, dp[N][N][2], f[N][2], siz[N];
vector<int> G[N];
void dfs(int x, int fa) {
dp[x][0][0] = dp[x][1][1] = siz[x] = 1;
int ver;
for(int i = 0; i < G[x].size(); i ++) {
ver = G[x][i];
if(ver == fa) continue;
dfs(ver, x);
for(int j = 0; j <= siz[x] + siz[ver]; j ++) {
f[j][0] = dp[x][j][0], f[j][1] = dp[x][j][1];
dp[x][j][0] = dp[x][j][1] = 0;
}
for(int j = siz[x] + siz[ver]; j >= 0; j --) {
for(int k = max(0ll, j - siz[x]); k <= min(j, siz[ver]); k ++) {
dp[x][j][0] = (dp[x][j][0] + (dp[ver][k][0] + dp[ver][k][1]) % mod * f[j - k][0] % mod) %mod;
dp[x][j][1] = (dp[x][j][1] + dp[ver][k][0] * f[j - k][1] % mod + dp[ver][k + 1][1] * f[j - k][1]) % mod;
}
}
siz[x] += siz[ver];
}
}
signed main() {
scanf("%lld", &n);
int u, v;
for(int i = 1; i < n; i ++) {
scanf("%lld %lld", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, 1);
for(int i = 1; i <= n; i ++) printf("%lld\n", (dp[1][i][0] + dp[1][i][1]) % mod);
return 0;
}