网络赛复现地址：
https://codeforces.com/gym/105336
L网络预选赛：
做法：
直接枚举两行两列即可
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
char a[N][N];
int main() {int n,m; cin >> n >> m;for(int i = 0; i < n; i++)for(int j = 0; j < m; j++) cin >> a[i][j];int ans = 0;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(a[i][j] == 'c' && a[i + 1][j] == 'p' &&a[i][j + 1] == 'c' && a[i + 1][j + 1] == 'c') ans ++;}}cout << ans <<'\n';return 0;
}
Problem K. 取沙子游戏
做法一：
特殊情况判断：k >= n，Alice取完，Alice必赢
首先如果n是奇数的话，Alice取1，此时Bob只能取一，Alice必赢
如果n是偶数的话，根据规律，我们需要找到2的整数倍，使得n / base(base初始化为2)的商为奇数，此时Alice赢否则Bob赢。
代码一：
#include <bits/stdc++.h>
using namespace std;int main() {int t; cin >> t;while(t--){int n,k; cin >> n >> k;if(k >= n){cout <<"Alice\n";continue;}if(n & 1){cout <<"Alice\n";continue;}int base = 2;bool flag = false;while(base <= k){if((n / base) & 1) {flag = true;break;}base *= 2;}if(flag) cout <<"Alice\n";else cout << "Bob\n";}return 0;
}
做法二：
- 如果 lowbit(n) 小于等于 k，那么 Alice 通过拿走 lowbit(n) 粒沙子，就能保证她可以重复 Bob 的取法，从而最终获胜。
- 如果 lowbit(n) 大于 k，则无论 Alice 如何取，Bob 总是可以进入一个 Alice 无法获胜的局面。
证明
- 当 lowbit(n) 小于等于 k时，Alice 可以取走 lowbit(n)粒沙子，之后无论 Bob 取走多少粒沙子，Alice 只需要重复他的策略即可取胜。
- 当 lowbit(n) 大于 k，Alice 无法取到一个有效的 lowbit(n)，这时无论 Alice 如何取沙子，Bob 都能够通过合理的策略取胜。
假设：
- n=12（一共有 12 粒沙子）
- k=4（每次最多可以取 4 粒沙子）
Alice 的第一步：
- n=12，二进制表示为
1100，因此 lowbit(12)=4，Alice 可以取走 4粒沙子。 - 此时剩下的沙子数量 n′=12−4=8，二进制为
1000，接下来轮到 Bob。
Bob 的第一步：
- n′=8，二进制表示为
1000，因此 lowbit(8)=8，但是 k=4，Bob 无法一次性取走 8 粒沙子。 - 因此，Bob 最大只能取走 k=4 粒沙子，他取走 4 粒后，剩下 n′′=8−4=4′
Alice 的第二步：
- n′′=4n'' = 4n′′=4，二进制表示为
100，lowbit(4)=4lowbit(4) = 4lowbit(4)=4，Alice 取走剩下的 4 粒沙子，游戏结束，Alice 获胜。
代码二：
#include <bits/stdc++.h>
using namespace std;// Function to compute lowbit
int lowbit(int n) {return n & (-n);
}int main() {int t; cin >> t;while(t--) {int n, k; cin >> n >> k;// 如果k大于等于n，Alice可以直接拿完，获胜if(k >= n) {cout << "Alice\n";continue;}// 如果n是奇数，Alice获胜if(n & 1) {cout << "Alice\n";continue;}// 否则通过 lowbit 判断if(lowbit(n) <= k) {cout << "Alice\n";} else {cout << "Bob\n";}}return 0;
}
做法一和做法二的关联：
做法一基于奇偶性分析：
这实际上和 lowbit 的分析思路是一样的——每次把最小有效的位（最低的 1）取掉，直到把偶数变成奇数。
- 当 n是奇数时，Alice 直接获胜
- 当n 是偶数时，通过除以 2 逐步缩小 n，相当于在剥离掉最右侧的 0（即 lowbit 所表示的部分）。当 Alice 使 n变为奇数时，局面重新对 Alice 有利。
两种方法的本质一致性
- lowbit 方法 是直接观察二进制的最低位 1 的位置，通过每次取走 lowbit(n) 来减少沙子，并构造有利局面。
- 奇偶分析法 是通过逐次除以 2 的方式，慢慢缩减问题规模，直到剩下奇数或更小的偶数，这和 lowbit 的核心思想也是一致的。
Problem B. 军训 II：
做法：
只要按照大小顺序排，那么不整齐度就会最小。因此，将数组顺序或者倒序排序即可，答案可以直接暴力或 O(n) 计算。对于方案数，统计一下每个数 的出现次数 cnti，那么方案数就是 2 * cnti !。特别地，当所有数都一样的时候，答案为 n!。
fac和Min一定要开long long不然过不了
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e3 + 10,mod = 998244353;
int a[N];
ll fac[N];
map<int, int> mp;
int main() {int n; cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];mp[a[i]] ++;}sort(a + 1, a + 1 + n);fac[0] = 1;for(int i = 1; i <= n; i++){fac[i] = fac[i - 1] * i % mod;}int ans = 1;for(auto i : mp){if(i.second >= 2) ans = ans * fac[i.second] % mod;}if(mp.size() != 1) ans = 2 * ans % mod;ll Min = 0;for(int i = 1; i <= n; i++){for(int j = i + 1; j <= n; j++){Min += a[j] - a[i];}}cout << Min << " " << ans <<'\n';return 0;
}
