M. Matrix Construction
乱搞规律题。
手玩几个数据发现：
如果列为偶数：顺序输出数字，行间数之和为奇数，列间数之和为偶数，
并且由于递增的关系必然不会有两两相等，符合题意；
反之：如果当前行数 i 为奇数，可以先打乱顺序，比如尝试第一个数不变，其余数字倒序；
如果 i 为偶数，该行数字全部倒序，随便举一例可以显然证明满足题意。
void solve()
{cin >> n >> m;if (m % 2){yes;cout << '\n';k = 1;for (int i = 1; i <= n; i++){if (i % 2){t = i * m;cout << t - (m - 1);for (int tt = 1; tt <= m - 1; tt++){cout << ' ' << t + 1 - tt;}}else{t = i * m;cout << t--;for (int tt = 1; tt <= m - 1; tt++){cout << ' ' << t--;}}cout << '\n';}}else{yes;cout << '\n';int k = 1;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cout << k++ << ' ';}cout << '\n';}}
}
J. Just another Sorting Problem
分类讨论题。
1、先特判，如果 \(n=2\)，一定是 Alice 赢。
2、如果 \(n=3\)：
\(num=0\)，包含在情况3；
\(num=2\)，包含在情况4；
\(num=3\)，谁先手谁输。
3、如果一开始就单调递增， Alice 赢。
4、找出被调换的数字个数：
如果恰好 \(num=2\)，Alice先手则可以调回获胜；
如果 \(num>2\)，则 Alice必输。
void solve()
{cin >> n >> s1; for (int i = 1; i <= n; i++){cin >> a[i];}if (n == 2){cout << "Alice";re;}if (is_sorted(a + 1, a + 1 + n)){cout << "Alice";re;}num=0;for (int i = 1; i <= n; i++){if (a[i] != i){num++;}}if (s1[0] == 'A'){if (num == 2){cout << "Alice";re;}}if(n==3&&num==3){if(s1[0]=='B'){cout<<"Alice";re;}}cout << "Bob";
}
H. Horizon Scanning
计算几何。
先考虑用atan2函数将所有点转化为极角。
然后从小到大排序，复制一份，确保范围内有 \(k\) 个，可以转化为求 \(min(a[i+k]-a[i])\)。
const ind pi = acos(-1);
void solve()
{cin >> n >> k;int x, y;for (int i = 1; i <= n; i++){cin >> x >> y;a[i] = atan2(y, x);}sort(a + 1, a + 1 + n);for (int i = 1; i <= n; i++){a[i + n] = a[i] + pi * 2;}ind ans = 0;for (int i = 1; i <= n; i++){ans = max(ans, a[i + k] - a[i]);}cout << fixed << setprecision(10) << ans;
}
L. Last Chance: Threads of Despair
贪心。
所有血量 \(>1\) 的随从可以先造成一点伤害。
所有血量 \(=1\) 的随从总共最多可以先造成一点伤害。
对两堆随从按生命从小到大排序。
循环遍历：
如果 \(a[i]-1<=k\)，减一是因为前面造成的一点伤害自己也会受到伤害，满足则说明这个随从会发动亡语。
如果 \(b[j]<=k\)，说明这个随从会发动亡语。
如果都不满足，说明 \(b[j]>k\)，考虑用前面的总伤害 \(sum-b[j]\) ，如果不够则跳出循环；反之继续循环。
最后将 \(j\) 与 \(m\)比较即可得出判断。
void solve()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= m; i++){cin >> b[i];}sort(a + 1, a + 1 + n);sort(b + 1, b + 1 + m);sum = 0; // 随从可以造成的伤害for (int i = 1; i <= n; i++){if (a[i] > 1){sum++;}}if (a[1] == 1) // 用1去自爆sum++;int i = 1, j = 1, k = 0; // k是炸弹伤害的斩杀线while (j <= m){while (j <= m || i <= n){if (i <= n && a[i] - 1 <= k){ // 1连锁爆炸i++;k++;}else if (j <= m && b[j] <= k){ // 2连锁爆炸j++;k++;}else{break;}}if (j <= m){if (sum >= b[j] - k){sum -= (b[j] - k);k++;j++;}elsebreak;}}if (j > m){yes;re;}no;
}