网络赛复现地址：
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;
}