Codeforces Round 1117 (Div. 2) 题解
A
题意：给定$n$个单词组成的集合，每次操作从这个集合中选择若干个单词（无序，可重复）取其首字母拼成新串，新串放回集合中，重复该过程若干次，判断给定的一组串能否由该过程生成
这道题只需关注每个单词的首字母。因为每次操作我们取若干已有串的首字母拼成新串，新串加入集合后，后续操作也只取它的首字母。因此整个过程中所有能作为首字母出现的字符，都来自于初始 $n$ 个单词的首字母，不会产生任何新的字母。
一个目标串能被生成，当且仅当它的每一个字符都在初始首字母集合中出现过.因为只要字符存在，就可以在一次操作中直接选择对应数量的初始单词（或已生成的单字符串）拼出该串（因为顺序任意），不需要额外的依赖关系。
所有可能生成的目标串就是能生成的最大目标串（把所有的首字母都用上）的每个排列组合的任意子集
所以只需读入初始单词，将其首字母存入集合，然后检查每个目标串的每个字符是否都在集合中，若全部满足则输出 YES，否则 NO。时间复杂度 $O((n+m)L)$。
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin >> T;
while (T--)
{
int n, m;
cin >> n >> m;
set<char> st;
for (int i = 0; i < n; i++)
{
string w;
cin >> w;
st.insert(toupper(w[0]));
}
bool ok = true;
for (int i = 0; i < m; i++)
{
string a;
cin >> a;
for (char c : a)
{
if (st.find(c) == st.end())
{
ok = false;
}
}
}
cout << (ok ? "YES" : "NO") << '\n';
}
return 0;
}B
题意：两个巨人 Bea 和 Ver 各自有一排山，高度从左到右非递增。Bea 的山从左往右编号，Ver 的山从右往左编号（即两人面对面站着）。初始两人都站在各自第 1 座山上。每回合当前玩家选择对方当前站着的山，将其高度减 1。然后检查自己面前的山（编号 +1）是否比当前站着的山更高，如果是则跳到那座山；如果自己站在高度为 0 的山上且前面没有山了，则认输。Bea 先手，问谁赢。
考虑每个人能撑的回合数只取决于第一座山的高度加上后面山的数量。因为山的高度非递增，且每回合对手只能攻击你当前站着的山，把它减1。当这座山降到0时，如果你后面还有山，你就会跳到下一座山。（因为当前山的高度为$0$,下一座的高度一定大雨$0$）每座山被攻击的次数等于它的高度，而跳到下一座山需要额外的1次“移动”，所以总可承受攻击次数为 $a_1 + n - 1$。同理 Ver 为 $b_1 + m - 1$。Bea 先手，若 Bea 的可承受次数大于等于 Ver 的，则 Bea 赢，否则 Ver 赢。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100005;
int n, m;
long long a[N], b[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin >> T;
while (T--)
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++)
cin >> b[i];
int nb = a[1] + n - 1;
int nv = b[1] + m - 1;
cout << (nv <= nb ? 1 : 2) << '\n';
}
return 0;
}C
题意：给定一棵 $n$ 个节点的有根，其中有 $m$ 个特殊节点。你需要选择若干个节点，使得每个特殊节点到根的路径上至少有一个被选中的节点，且选中的节点不能是特殊节点本身。要求选中的节点数量尽可能少，并在数量最少的前提下输出这些节点的编号。
这显然是一道贪心题。从叶子向根处理，记录每个子树中是否包含特殊节点 has[u]，以及子树中是否已被覆盖 cov[u]。
对于节点 $u$，先处理完所有子节点。如果 $u$ 本身是特殊节点，它必须被覆盖，但不能选 $u$ 本身，所以只能从子节点中选取那些已被覆盖的子节点来覆盖 $u$。
如果 $u$ 不是特殊节点，统计有多少个子节点已被覆盖：若没有，且 $u$ 的子树中有特殊节点，则 $u$ 必须被选中；若只有一个，则 $u$ 不需要额外选，直接继承该覆盖；若有多个，则选 $u$ 可以合并这些覆盖，减少总选中数量，所以选 $u$ 并替换掉这些子节点。
由于从叶子节点向上，所以能够确保每个子树应用的都是最优策略，每一步都是当前的最优策略（注意这里为什么不说继承的都是最优策略呢？因为如果我们发现有多个特殊节点在一个子树里会合并，不合并时继承下去的显然不是最优的，但是我们在进行到那个子树的根之前显然是不知道不是最优的，当时最优的选择就只是这个，所以只是当前步骤是最优策略），所以贪心是最优策略。
最后输出选中的节点编号即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100005;
int n, m;
int p[N];
bool vis[N], has[N], cov[N];
int out[N], tot;
int head[N], to[N], nxt[N], cnt;
void add(int u, int v)
{
to[++cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
{
cin >> n;
for (int i = 1; i <= n; i++)
{
head[i] = 0;
vis[i] = 0;
has[i] = 0;
cov[i] = 0;
}
cnt = 0;
for (int i = 2; i <= n; i++)
{
cin >> p[i];
add(p[i], i);
}
cin >> m;
for (int i = 1; i <= m; i++)
{
int x;
cin >> x;
vis[x] = 1;
}
tot = 0;
for (int u = n; u >= 1; u--)
{
has[u] = has[u] || vis[u];
if (!has[u])
continue;
int sz = 0;
int gm[N];
for (int i = head[u]; i; i = nxt[i])
{
int v = to[i];
if (cov[v])
gm[++sz] = v;
}
if (vis[u])
{
for (int i = 1; i <= sz; i++)
out[++tot] = gm[i];
cov[u] = 1;
}
else
{
if (sz == 0)
{
cov[u] = 0;
}
else if (sz == 1)
{
cov[u] = 1;
}
else
{
for (int i = 1; i < sz; i++)
out[++tot] = gm[i];
cov[u] = 1;
}
}
if (u > 1)
{
has[p[u]] = has[p[u]] || has[u];
}
}
sort(out + 1, out + tot + 1);
cout << tot;
for (int i = 1; i <= tot; i++)
cout << ' ' << out[i];
cout << '\n';
}
return 0;
}D
题意：