1994(div1+div2)
A. Diverse Game
佩特看了谢尔盖的数据流,得出了一个
给你一个矩阵
只有
直接暴力构造会有一个问题:若
void solve() {
int n, m;cin >> n >> m;
vector<vector<int>> a(n + 1, vector<int>(m + 1)), b(n + 1, vector<int>(m + 1));
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) {
cin >> a[i][j];b[i][j] = a[i][j];
}
}
if (n == 1 && m == 1) {
cout << "-1\n";return;
}
vector<int> vis(n * m + 1);
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) {
for (int k = 1;k <= n * m;k++) {
if (a[i][j] != k && !vis[k]) {
b[i][j] = k;vis[k] = 1;break;
}
}
}
}
if (b[n][m] == a[n][m])swap(b[1][1], b[n][m]);
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) {
cout << b[i][j] << " \n"[j == m];
}
}
}
标准答案:
直接输出 a[(i + 1) % n][(j + 1) % m]
即可,没有想到...
B. Fun Game
游戏开始时,沃瓦选择长度为
判断序列
当字符串
void solve() {
int n;cin >> n;
string s, t;cin >> s >> t;
for (int i = 0;i < s.size();i++) {
if (s[i] == '0') {
if (t[i] != s[i]) {
cout << "NO\n";
}
} else {
break;
}
}
cout << "YES\n";
}
C. Hungry Games
雅罗斯拉夫正在玩一款电脑游戏,在其中一个关卡中,他遇到了
角色的毒性等级为
- 角色的毒性等级会增加
。 - 如果
,过程继续;否则, 变为零,过程继续。
雅罗斯拉夫感兴趣的是,有多少种方法可以选择
Solution
DP
想要直接将某个数组做前缀和直接:partial_sum(a.begin() + 1, a.end(), a.begin() + 1);
(针对下标 1~n)
对于下标
即
DP 动态转移方程:
#define int long long
void solve() {
int n, x;cin >> n >> x;
vector<int> a(n + 1);
for (int i = 1;i <= n;i++)cin >> a[i];
partial_sum(a.begin() + 1, a.end(), a.begin() + 1);
vector<int> f(n + 2);
for (int i = n - 1;i >= 0;i--) {
int j = upper_bound(a.begin(), a.end(), a[i] + x) - a.begin();
f[i] = f[j] + j - i - 1;
}
cout << accumulate(f.begin(), f.end(), 0ll) << '\n';
}
D. Funny Game
Vanya 有一个包含
操作数
- 选择
个不同的数字 ,使得 可以被 整除。 - 在顶点
和 之间添加一条无向边。
使用
Solution
抽屉原理
操作需要倒着进行(对答案没有影响):从操作数
根据抽屉原理,每一次操作都一定能够找到两个点
void solve() {
int n;cin >> n;
vector<int> a(n), p(n);
iota(p.begin(), p.end(), 0);
vector<pair<int, int>> ans;
for (auto& i : a)cin >> i;
for (int i = n - 1;i >= 1;i--) {
vector<int> occ(i, -1);
for (auto j : p) {
if (occ[a[j] % i] != -1) {
ans.push_back({j, occ[a[j] % i]});
p.erase(find(p.begin(), p.end(), j));
break;
}
occ[a[j] % i] = j;
}
}
cout << "YES\n";
reverse(ans.begin(), ans.end());
for (auto [x, y] : ans)cout << x + 1 << " " << y + 1 << "\n";
}
E. Wooden Game
有一片森林,里面有
- 选择其中一棵树的任意顶点的子树 ,并将其从树中移除。
蒂莫菲喜欢位运算,因此他希望删除的子树的大小的 bitwise OR 是最大的。请帮助他,找出他能得到的最大结果。
Solution
这个题目所给出的树没有任何用处,只有顶点个数
对于某个树,设每次删除的子树大小为
若无子树大小为
,可以将子树中的节点一个一个删除从而构造出
因此,对于这个树,可以构造
对于某个树,
非常妙!
void solve() {
int k;cin >> k;
vector<int> a(k);
for (int i = 0;i < k;i++) {
cin >> a[i];
for (int j = 0;j < a[i] - 1;j++) {
int x;cin >> x;
}
}
sort(a.rbegin(), a.rend());
int ans = 0;
for (auto x : a) {
for (int i = __lg(x);i >= 0;i--) {
if ((x >> i) & 1) {
int y = (ans >> i) & 1;
if (y == 0) {
ans |= (1 << i);
} else {
ans |= (1 << i) - 1;
break;
}
}
}
}
cout << ans << '\n';
}
F. Stardew Valley
鹈鹕镇由
帮助农夫找到一条符合以下属性的路线:
- 路线从某个房子开始,沿着道路走,最后在同一个房子结束。
- 每条道路经过次数不能超过一次。
- 所有含有 NPC 的路都要走一次,没有 NPC 的道路则不用。
可以保证:只需在有 NPC 的道路上行走,就可以从任何其他房屋到达任何其他房屋。
Solution
类似的题目还有:F - Perils in Parallel
题目意思即这个图是 NPC 边的全集
加上 无 NPC 边的子集
(即删除一些无 NPC 的边) ,求这个图的欧拉回路。
拥有欧拉图的条件是每个顶点的度数都是偶数
对于删除单独的某一条边,可以使用代码中的技巧,
g[u].push(i),edge[i]=u^v->int to=edge[i]^u
。
对于这个题,可能需要删除部分无 NPC 的边组成的图来做欧拉回路。只要图中的每个顶点的度数都是偶数,则一定存在欧拉回路,否则一定不存在欧拉回路。
将图中无 NPC 的边组成一个图,对于这个图进行处理,若能够使得所有顶点度数为偶,则继续求欧拉回路。
若有奇数个顶点有奇数的度数,则无法通过删边达到都为偶数度数,在搜索的过程中若某个顶点的度数为奇数,则需要将这个顶点和其连接的顶点之间的边删去一个
void solve() {
int n, m;cin >> n >> m;
vector<vector<int>> g(n + 1), blk(n + 1);
vector<int> edge(m + 1);
for (int i = 1;i <= m;i++) {
int u, v, is;cin >> u >> v >> is;
g[u].push_back(i);
g[v].push_back(i);
edge[i] = u ^ v;
if (!is) {
blk[u].push_back(i);
blk[v].push_back(i);
}
}
vector<int> deg(n + 1);
for (int i = 1;i <= n;i++)deg[i] = g[i].size() & 1;
vector<int> del(m + 1), vis(n + 1);
auto dfs = [&](auto self, int u)->void {
vis[u] = 1;
for (auto x : blk[u]) {
int to = edge[x] ^ u;
if (vis[to])continue;
self(self, to);
if (deg[to]) {
del[x] = 1;
deg[to] ^= 1;
deg[u] ^= 1;
}
}
};
int ok = 1;
for (int i = 1;i <= n;i++) {
if (vis[i])continue;
dfs(dfs, i);
ok &= !deg[i];
}
if (!ok) {
cout << "NO\n";return;
}
cout << "YES\n";
cout << m - accumulate(del.begin() + 1, del.end(), 0) << '\n';
auto euler = [&](auto self, int u) ->void {
while (g[u].size()) {
int x = g[u].back();g[u].pop_back();
int to = edge[x] ^ u;
if (del[x])continue;
del[x] = 1;
self(self, to);
}
cout << u << " ";
};
euler(euler, 1);
cout << '\n';
}