2021ICPC济南
时隔一年再来补题，金牌题以下还是可以补的。
C（组合数学，DP，贪心）
题意
两人每次从序列中取数字，希望自己拿到的数字和最大。求可行的操作序列方案数。
思路
看起来是博弈，其实和博弈关系不大。
要分类讨论，先考虑序列中数字出现次数全是偶数的情况。可以发现要想达到最优，如果一个人拿了一个数字 \(x\) 并且 \(x\) 是最大数另一个人必须跟一个 \(x\) 。所以可以将数字配对考虑。同时还注意到这个结论对除去 \(x\) 的子序列仍然是成立的。
然后如果出现单个数字，如果这个单个数字做为最大数，先手第一次一定拿它。
在知道以上两个结论后，如果直接用组合数计算很困难。此时可以把它转成一个序列的排序方案数问题。
比如 \([1,1,2,2,3,3]\) 这组数，\(A:[1,3,2],B:[3,2,1]\) 可以变成 \([1,3,3,2,2,1]\) 。
我们需要意识到这个是可以递推的。这里可以解释：除去最大值3的子序列，仍然满足上面说的性质。也就是出现又一个相似的子问题。
定义 \(f[i]\) 表示当前最大数为 \(i\) 的答案。
当新加入一个大数 \(mx\) 后，如果这个数的数量是奇数，先手一定会选择一个 \(mx\) ，问题又转到了 \(mx\) 数量为偶数的情况。所以只用讨论出现次数为偶数情况。
我们将 \(mx\) 两个一组捆绑考虑后，发现就是往之前生成的合法操作序列中插空，比如 \([1,3,3,2,2,1]\) 就是 \([1,2,2,1]\) 插入一对 \([3,3]\) 形成的。那么这个就可以用插隔板解决：
\[f[i]*C_{tot+\frac{cnt_{mx}}{2}}^{\frac{cnt_{mx}}{2}} \]这里面 \(tot\) 是之前操作序列长度。
插好空还要分配 \(mx\) 的次序，再做一个排列。总的递推式如下。
\[f[i+1]=f[i]*C_{tot+\frac{cnt_{mx}}{2}}^{\frac{cnt_{mx}}{2}}*A_{cnt_{mx}}^{cnt_{mx}} \]代码用py写的。
mod = 998244353
N = 10**6 + 5
def ksm(a, b):
ans = 1
a %= mod
while b:
if b & 1: ans = a * ans % mod
b >>= 1
a = a * a % mod
return ans
fac = [0] * N
invfac = [0] * N
fac[0] = invfac[0] = 1
for i in range(1, N):
fac[i] = fac[i - 1] * i % mod
invfac[N - 1] = ksm(fac[N - 1], mod - 2)
for i in range(N - 2, 0, -1):
invfac[i] = invfac[i + 1] * (i + 1) % mod
def C(n, m):
if n < m: return 0
if not m: return 1
return fac[n] * invfac[m] % mod * invfac[n - m] % mod
n = int(input())
a = list(map(int, input().split()))
c = [0] * (N + 1)
for x in a:
c[x] += 1
ans, s = 1, 0
for i in range(1, N):
if not c[i]:
pass
else:
x = c[i] // 2
ans = ans * C(s + x, x) % mod * fac[c[i]] % mod
s += c[i]
print(ans)
D（三分，等差数列，推式子）
题意
给一个数列每个数加或者减1，问把它整成一个等差数列的最小代价。
思路
把代价表达式写出来
\[\sum_{i=1}^{n}|a_i-c_1+(i-1)d| \]其中 \(c\) 是最终等差数列， \(d\) 是公差。
另 \(t_i=a_i-(i-1)d\) 做一个变形
\[\sum_{i=1}^{n}|t_i-c_1| \]这个就是货舱选址问题的表达式，我们知道当 \(c_1\) 等于 \(t\) 的中位数时最优。并且代价函数 \(f(d)\) 是一个单峰函数。
于是，三分公差，用货舱选址求出 \(c_1\) 算答案 \(check\) 。
另外注意爆 long long 和卡 sort() 的代码细节。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<bitset>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<random>
#include<cassert>
#include<functional>
#include<iomanip>
#define i128 __int128_t
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3fll
#define endl '\n'
#define ll long long
// #define int long long
#define SZ(x) (int)x.size()
#define rep(i,a,n) for(int i = (a);i <= (n);i++)
#define dec(i,n,a) for(int i = (n);i >= (a);i--)
using namespace std;
using PII = pair<int,int>;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
const int N =10 + 2e5 ,mod=1e9 + 7;
int n;
ll a[N];
i128 b[N];
i128 chk(ll d) {
for(int i = 0;i < n;i ++) b[i] = a[i] + (i128)i * d;
nth_element(b, b + n / 2, b + n);
i128 ans = 0, m = b[n / 2];// 0 1 2 3
for(int i = 0;i < n;i ++) ans += b[i] > m ? b[i] - m : m - b[i];
return ans;
}
void write(i128 x) {
if (x < 0) { putchar('-'); x = -x; }
if (x > 9)write(x / 10);
putchar((x % 10) ^ 48);
}
void solve()
{
scanf("%d", &n);
for(int i = 0;i < n;i ++) scanf("%lld", a + i);
ll l = -1e13, r = 1e13;
while(l < r) {
ll midl = l + (r - l) / 3, midr = r - (r - l) / 3;
if(chk(midl) <= chk(midr)) r = midr - 1;
else l = midl + 1;
}
i128 ans = chk(r);
write(ans);
}
signed main()
{
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//int T;cin>>T;
//while(T--)
solve();
return 0;
}
J（高斯消元，行列式）
题意
给一个矩阵和他的行列式的值的绝对值，判断行列式值的正负。
思路
会行列式求值板子就会写，不然就寄。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<bitset>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<random>
#include<cassert>
#include<functional>
#include<iomanip>
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3fll
#define endl '\n'
#define ll long long
#define int long long
#define SZ(x) (int)x.size()
#define rep(i,a,n) for(int i = (a);i <= (n);i++)
#define dec(i,n,a) for(int i = (n);i >= (a);i--)
using namespace std;
using PII = pair<int,int>;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
const int N =100 ,mod=1e9 + 7;
int n;
int a[N][N];
int ksm(int a,int b) {
int ans = 1;
a %= mod;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
int guass(int a[][N], int n, int m) {
int cnt = 0, ans = 1;
for(int c = 0;c < min(n, m);c ++) {
int r = c;
for(int i = r + 1;i < n;i ++) if(a[i][c] > a[r][c])
r = i;
cnt += r != c;
swap(a[c], a[r]);
if(a[r][c] == 0) {
return 0;
}
ans = ans * a[c][c] % mod;
for(int i = 0;i < n;i ++) if(i != c) {
int t = a[i][c] * ksm(a[c][c], mod - 2) % mod;
for(int j = c;j < m;j ++) {
a[i][j] -= t * a[c][j] % mod;
a[i][j] = (a[i][j] % mod + mod) % mod;
}
}
}
if(cnt & 1) ans = mod - ans;
return ans;
}
int cal(string &s) {
int ans = 0;
for(auto c : s) ans = (ans * 10 % mod + c - '0') % mod;
return ans;
}
void solve()
{
cin >> n;
string s; cin >> s;
int ans = cal(s);
for(int i = 0;i < n;i ++)
for(int j = 0;j < n;j ++)
cin >> a[i][j];
if(ans != guass(a, n, n))
cout << "-\n";
else
cout << "+\n";
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--)
solve();
return 0;
}