A. 本场比赛灵感来源于树状数组出题组
本场比赛灵感来源于树状数组出题组
题意：
如果有大于等于 \(80%\) 的数字小于 \(a_x\) 则将其分在 \(A\) 组，求 \(A\) 组数字和。
题解：
暴力求有多少数字大于自己就行，如果大于 \(80%\) 上取整就放入 \(A\) 组。
#include<bits/stdc++.h>
#define int long long
using namespace std;void sol(){int n; cin >> n;vector<int> a(n);for(int i = 0;i < n;i ++) cin >> a[i];int ans = 0;for (int i = 0; i < n;i ++) {int cnt = 0;for (int j = 0; j < n;j ++)if (a[j] <= a[i]) cnt ++;if (cnt - 1 >= (4 * (n - 1) +4) / 5) ans += a[i];}cout << ans << endl;
}signed main(){int t = 1; //cin >> t;while(t --) sol();return 0;
}
B. 构造部落
构造部落
题意：
有 \(n\) 位首领依次连续在位，第 1 位首领在位第 1 年对应公元 \(s\) 年。第 \(i\) 位首领在位 \(t_i\) 年，上一位结束后的下一年即由下一位首领即位。现在有 \(q\) 个询问，每个询问给出 \((x,y)\)，表示第 \(x\) 位首领在位的第 \(y\) 年，要求你计算这一年对应的公元年份。
题解：
先对在位年数做前缀和 \(a_i\)，表示前 \(i\) 位首领一共在位多少年。
那么第 \(x\) 位首领在位的第 1 年是公元 \(s + a_{x-1}\)年，第 \(y\) 年再往后推 \(y-1\) 年，因此答案为 \(s+a_{x-1}+y−1\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;void sol(){int n, q, s, t; cin >> n >> q >> s;vector<int> a(n + 1);for (int i = 1; i <= n;i ++) cin >> t, a[i] = a[i - 1] + t;while (q --) {int x, y; cin >> x >> y;cout << s + a[x - 1] + y - 1 << endl;}
}signed main(){int t = 1; //cin >> t;while(t --) sol();return 0;
}
I. 初华的扭蛋机
初华的扭蛋机
题意：
你有 6 枚筹码，可以决定每一枚是押在某一种颜色上，还是干脆不押、留在手里。颜色一共有 6 种。下注完成后，机器会随机抽 3 次球，每次抽到任意一种颜色的概率都相同。然后按颜色分别结算：如果某种颜色在这 3 次中出现了 1 次、2 次或 3 次，而你在该颜色上押了 \(x\) 枚筹码，就分别能得到 \(2x\)、\(3x\) 或 \(10x\) 枚筹码；没押的颜色就什么也得不到。留在手里的筹码不会变化，直接计入最终数量。你的目标是自己设计一个长度为 6 的字符串，表示这 6 枚筹码各自的去向，使得最终得到的筹码数量的期望值最大。
题解：
看起来好像不赌就不会输。
print("######")
C. 墨提斯的排列
墨提斯的排列
题意：
要构造一个长度为 \(2^n\) 的排列，包含所有 \(0\sim 2^n-1\) 的数各一次，使得相邻元素的异或值之和尽可能小。
题解：
格雷码正好符合，格雷码相邻两个数的二进制表示只相差 \(1\) 位，因此它们的异或值是一个 \(2\) 的幂，已经是能做到的最小变化。
#include<bits/stdc++.h>
#define int long long
using namespace std;void sol(){int n; cin >> n;int nn = 1 << n;for (int i = 0; i < nn; i++)cout << (i ^ (i >> 1)) << ' ';cout << endl;
}signed main(){int t = 1; //cin >> t;while(t --) sol();return 0;
}
H. 时不时……
题意：
在一个 \(n \times m\) 的网格地图上分布着若干敌人，玩家可以使用“玉米加农炮”选择一个中心点 \((x, y)\) 进行攻击，其攻击范围覆盖所有与中心点曼哈顿距离不超过 2 的方格。敌方会进行 \(q\) 次动态增援，每次在指定坐标增加 \(z\) 名敌人。要求在每一次增援后，立即找出一个攻击后能消灭敌人数量最多的中心点坐标，若有多个最大值位置，输出任意一个即可。
题解：
观察到， \(z\) 始终为正，这意味着每个打击中心，其能消灭的敌人总数是单调不减。我们只需维护一个当前的最优坐标 \((mx, my)\)。每次在 \((x, y)\) 处增援时，只有那些攻击范围能覆盖 \((x, y)\) 的点的杀敌总数会增加。
新的全局最大值只可能产生于这两个来源：
-
一是原先的最优坐标
-
二是这 13 个刚刚被增加值的坐标。
预处理后，每次仅需要处理这 13 个受影响的局部点，并与当前答案对比。
#include<bits/stdc++.h>
#define int long long
using namespace std;int s[510][510], a[510][510],dx[] = {0, 0, 0, 1,-1, 1, 1,-1,-1, 0, 0, 2,-2},dy[] = {0, 1,-1, 0, 0, 1,-1, 1,-1, 2,-2, 0, 0};void sol() {int n, m, q; cin >> n >> m >> q;for (int i = 1; i <= n;i ++)for (int j = 1; j <= m;j ++) cin >> a[i][j];for (int i = 1; i <= n;i ++) for (int j = 1; j <= m;j ++) {if (a[i][j] == 0) continue;for (int k = 0; k < 13; k++) if (i + dx[k] >= 1 && i + dx[k] <= n && j + dy[k] >= 1 && j + dy[k] <= m)s[i + dx[k]][j + dy[k]] += a[i][j];}int mx = 1, my = 1;for (int i = 1; i <= n;i ++) for (int j = 1; j <= m;j ++)if (s[i][j] > s[mx][my]) mx = i, my = j;while (q --) {int x, y, z; cin >> x >> y >> z;for (int i = 0; i < 13; i++) if (x + dx[i] >= 1 && x + dx[i] <= n && y + dy[i] >= 1 && y + dy[i] <= m) {s[x + dx[i]][y + dy[i]] += z;if (s[x + dx[i]][y + dy[i]] > s[mx][my])mx = x + dx[i], my = y + dy[i];}cout << mx << ' ' << my << endl;}
}signed main() {int t = 1; //cin >> t;while (t --) sol();return 0;
}
F. 爱音的01串构造
爱音的01串构造
题意：
我们需要用 \(a\) 个 0 和 \(b\) 个 1 构造一个字符串，使得所有连续子串的 \(\operatorname{mex}\) 之和最大。在 01 串中，纯 1 子串的 \(\operatorname{mex}\) 为 0（得分最低），纯 0 子串为 1，而既有 0 又有 1 的子串为 2（得分最高）。因此，目标就是通过合理排列，尽可能让更多的子串同时包含 0 和 1，并尽量减少连续纯 1 串的出现。
题解：
为得分最大化，要让 0 和 1 尽可能均匀交替出现。我们使用插空的处理：
-
如果 0 的数量较多，就用 1 作为分隔，将 0 均匀地分配到 \(b+1\) 个空中。
-
如果 1 的数量较多，就用 0 作为分隔，将 1 均匀地分配到 \(a+1\) 个空中。
通过这种方式可以破坏长段的重复字符，产生大量 \(\operatorname{mex}=2\) 的子串，达到全局最优解。
#include<bits/stdc++.h>
#define int long long
using namespace std;void sol() {int a, b; cin >> a >> b;string ans;if (a >= b) {for(int i = 0; i < b + 1;i ++) {for(int j = 0;j < a / (b + 1) + (i < a % (b + 1));j ++) ans += '0';if (i < b) ans += '1';}} else {for(int i = 0; i < (a + 1);i ++) {for(int j = 0;j < b / (a + 1) + (i < b % (a + 1));j ++) ans += '1';if (i < a) ans += '0';}}cout << ans << endl;
}signed main() {int t = 1; cin >> t;while (t --) sol();return 0;
}