D-Zztrans 的班级合照
如果没有对序列大小关系的限制，只需要考虑 \(a_i\) 应该放在第一个序列还是第二个序列，我们定义 \(f_{i,j}\) 表示前 \(i\) 个数，第二个序列放了 \(j\) 个，第一个序列放了 \(i-j\) 个的方案。但是又考虑到数字相同时，放的顺序可以任意，所以我们直接把相同的数字 \(x\) 缩成一个点,设共有 \(t\) 个 \(x\)，枚举分配给第一个序列 \(q\) 个 \(x\) ,分配给第二个序列 \(t-q\) 个 \(x\)，这样 dp 就没有考虑顺序,所以最后乘以一个 \(t!\) 即可
然后虽然要三重循环，但是根本跑不满，大胆放心暴力 dp 即可。
查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int n,a[5005];
vector<int>v;
int f[5005][5005],fac[5005];
signed main(){
fac[0]=1;
for(int i=1;i<=5000;++i)fac[i]=fac[i-1]*i%mod;
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
f[0][0]=1;
int num=1;
sort(a+1,a+1+n);
for(int i=1;i<=n;++i){
if(a[i]==a[i+1])num++;
else v.push_back(num),num=1;
}
int cur=0;
for(auto u:v){
cur+=u;
for(int j=0;j<=cur-j;++j){
for(int k=0;k<=min(u,j);++k)f[cur][j]=(f[cur][j]+f[cur-u][j-k]*fac[u]%mod)%mod;
}
}
cout<<f[n][n/2];
return 0;
}
H - 鸡哥的 AI 驾驶
就是你考虑二分时间 \(t\)，然后 \(p\) 和 \(p+t\times v\) 做逆序对即可。
然后把同编号内部的减掉。
离散化或动态开点线段树。
代码又臭又长，不放了（
J - Alice and Bob-1
假设 Alice 所获价值为 \(|A|\)，Bob 所获价值为 \(|B|\)，本质都想使自己价值尽可能大。
由于所获价值都带有绝对值，因此对所有数取反并不会影响答案，我们不失一般性地
设 \(S=\sum_{i\in [1,n]}a_i \ge 0\)，那么 \(|A|-|S-A|=
\begin{cases}
S\space\space\space\space\space\space\space\space\space\space\space\space(A\geq S)\\
2A-S\space\space(0\leq A<S)\\
-S\space\space\space\space\space\space\space\space\space(A<0)
\end{cases}\)
查看代码
#include<bits/stdc++.h>
using namespace std;
int n,a[5005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
sort(a+1,a+n+1);
long long ans1=0,ans2=0,ans3=0,ans4=0;
for(int i=1;i<=n;i+=2)ans1+=a[i],ans2+=a[i+1];
for(int i=n;i>=1;i-=2)ans3+=a[i],ans4+=a[i-1];
cout<<max(abs(ans1)-abs(ans2),abs(ans3)-abs(ans4));
return 0;
}
K - Alice and Bob-2
暴力搜索求 SG 函数，然后上 Nim 游戏的结论（异或和为 \(0\)）。
查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
map<vector<int>,int>mp;
int SG(vector<int>cur){
if(mp.count(cur)){
return mp[cur];
}
set<int>v;
for(int i=0;i<26;i++){
if(!cur[i])continue;
vector<int>to(cur);
to[i]--;
sort(to.begin(),to.end());
v.insert(SG(to));
for(int j=i+1;j<26;j++){
if(cur[j]==0)continue;
vector<int>nxt(cur);
nxt[i]--;
nxt[j]--;
sort(nxt.begin(),nxt.end());
v.insert(SG(nxt));
}
}
for(int i=0;;i++)if(!v.count(i))return mp[cur]=i;
return 0;
}
int t,n;
string s[15];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--){
mp.clear();
cin>>n;
int ans=0;
for(int i=1;i<=n;++i){
cin>>s[i];
vector<int>cnt(26,0);
for(int j=0;j<s[i].size();++j)cnt[s[i][j]-'a']++;
sort(cnt.begin(),cnt.end());
ans^=SG(cnt);
}
if(!ans)cout<<"Bob\n";
else cout<<"Alice\n";
}
return 0;
}