CSP 模拟 26
T1 博弈
博弈策略是显然的，只有当所有数的数量全是偶数是，才是后手必胜，考虑随机异或哈希，找一遍后直接统计。
T2 跳跃
容易想到的是一个 \(\mathcal{O}(nk)\) 的 dp，但是带了 \(k\)，比较难处理。
可以这样考虑，最后一定是到了一个位置 \(x\)，以 \(x\) 为右端点，在它的区间最大左端点之间反复横跳。
设 \(f_i\) 表示向右第一次调到 \(i\) 位置的最小跳跃次数，\(d_i\) 表示此时的最大权值。因为这样的设计，所以不会有 \(f_i\) 由 \(j\ge i\) 转移而来，因此没有后效性。
预处理出每个位置向左最大的左端点，转移就是枚举 \(j<i\)，计算它反复横跳多少次才能跳到 \(i\)，细节比较多，要注意奇偶和负数，挺多特判。
点击查看代码
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=1005,inf=2e9;
std::pair<int,int> f[N];
int n,a[N],s[N],mx[N],L[N],k;
signed main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
int T=read();
while(T--){
n=read();k=read();int min=0,pos=0;
for(int i=1;i<=n;++i){
a[i]=read(),s[i]=s[i-1]+a[i],f[i]={inf,0},L[i]=pos,mx[i]=s[i]-s[pos];
if(min>s[i])pos=i,min=s[i];
}
for(int i=1;i<=n;++i)if(s[i]>=0)f[i]={1,s[i]};
for(int i=2;i<=n;++i){
for(int j=1;j<i;++j){
if(f[j].first>=k||f[j].first>f[i].first)continue;
if(f[j].second+mx[j]>=0&&f[j].second+mx[j]+(s[i]-s[L[j]])>=0){
int cnt=f[j].first+2,val=f[j].second+mx[j]+s[i]-s[L[j]];
if((f[i].first==cnt&&f[i].second<val)||f[i].first>cnt)f[i]={cnt,val};
}else if(mx[j]>0){
int cnt=(std::abs(s[i]-s[L[j]])-f[j].second-1)/mx[j]+1;
if((cnt&1)==0)cnt++;
int val=f[j].second+cnt*mx[j]+s[i]-s[L[j]];cnt=f[j].first+cnt+1;
if((f[i].first==cnt&&f[i].second<val)||f[i].first>cnt)f[i]={cnt,val};
}
}
}int ans=0;
for(int i=1;i<=n;++i)if(k>=f[i].first)ans=std::max(ans,f[i].second+(k-f[i].first)*mx[i]);
std::cout<<ans<<'\n';
}
}
T3 大陆
给树分块方式的板子，从底往上分块一定没问题，考虑递归处理问题。
维护一个栈，这个栈中保存的是还未进行分块的节点，当进入一个节点 \(u\) 时，将他入栈，记一下当前栈的大小为 \(now\)，考虑对于 \(u\) 的子节点 \(v\)，当搜索完 \(v\) 的子树后，如果当前栈的大小减去 \(now\) 大于等于 \(B\)，直接将他们分块，省会是节点 \(u\)，弹栈直到栈的大小等于 \(now\)，处理完所有子节点之后，将 \(u\) 入栈。最后栈中会剩下一些节点，他们属于最后一个块。
- 来仔细思考这个过程，首先，每次解决完子节点 \(v\) 后，子节点最多会往栈里贡献 \(B-1\) 个点，所以对于这样分出的一个块他的大小最大是 \(2B-1\) 的，同理最后最多剩下 \(B\) 个节点未分块，将他们并入最后一个块，保证了块的大小是小于等于 \(3B-1\) 的。
点击查看代码
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=1e5+10;
int n,s[N],top,B,cnt,rt[N],bl[N];
std::vector<int> e[N],ans[N];
inline void dfs(int u,int fa){
int zc=top;
for(int v:e[u]){
if(v==fa)continue;
dfs(v,u);
if(top-zc>=B){
rt[++cnt]=u;
while(top>zc)bl[s[top--]]=cnt;
}
}
s[++top]=u;
}
signed main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read(),B=read();for(int i=2,u,v;i<=n;++i)u=read(),v=read(),e[u].emplace_back(v),e[v].emplace_back(u);dfs(1,0);
if(!cnt)rt[++cnt]=1;while(top)rt[cnt]=s[top],bl[s[top--]]=cnt;
std::cout<<cnt<<'\n';for(int i=1;i<=n;++i)std::cout<<bl[i]<<' ';std::cout<<'\n';for(int i=1;i<=cnt;++i)std::cout<<rt[i]<<' ';std::cout<<'\n';
}
T4 排列
平衡树，
总结
开场T1淀粉质，想给他随机异或哈希，然后想到了春色春恋春熙风，寻思那个东西需要状压，这个这么多，感觉不可做，开始思考博弈策略没转化好，然后不会了（忽略了这题只有一种状态）
T2没想，直接ABC了，假做法50pts。
T3树分块的板子，当时说没用，没学，然后心想这种东西我一定胡不出来，跳了。
T4差分后发现这玩意太有前途了，直接给区间修变成单点修了，然后就一直想线段树维护，发现不会维护，然后把时间想完了，然后暴力也懒得打了。