前言
- 比赛链接。
T1 普及了一下异或哈希，T2、T3 赛时应该算乱搞题，还搞挂了，T4 高级平衡树题，不太可做。
- 原题全部出自：2022牛客OI赛前集训营-提高组（第四场）。
T1 博弈
-
部分分 \(30pts\)：\(O(n^2)\) 暴力。
-
正解：
不难推出必胜策略就是 \((x,y)\) 路径上每个边权出现的次数不全为偶数，考虑如何维护这个玩意儿。
不难想到异或和，但可能存在不是全为偶数但异或和凑成 \(0\) 的情况导致出错。
于是用到异或哈希，每个权值映射到一个值域更大的数上再进行上述操作，从而出错的概率大大降低。
点击查看代码
#include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define endl '\n' #define sort stable_sort using namespace std; const int N=5e5+10,M=1e6+10; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0; for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);} template<typename Tp> inline void wt(Tp x) {if(x>9)wt(x/10);putchar((x%10)+'0');} template<typename Tp> inline void write(Tp x) {if(x<0)putchar('-'),x=~x+1;wt(x);} template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);} int T,n,m,tot,head[N],nxt[M],to[M],cnt[N]; ull w[M],dis[N]; ll ans; unordered_map<ull,int>pos; unordered_map<int,ull>rd; void add(int x,int y,ull z) { nxt[++tot]=head[x]; to[tot]=y; w[tot]=z; head[x]=tot; } void dfs(int x,int fa) { if(!pos[dis[x]]) pos[dis[x]]=++tot; cnt[pos[dis[x]]]++; for(int i=head[x];i;i=nxt[i]) { int y=to[i]; ull z=w[i]; if(y==fa) continue; dis[y]=dis[x]^z; dfs(y,x); } } signed main() { read(T); srand(time(0)); while(T--) { read(n); ans=1ll*n*(n-1)/2; tot=0,pos.clear(),rd.clear(); memset(head,0,4*(n+1)),memset(cnt,0,4*(n+1)); for(int i=1,x,y,z;i<n;i++) { read(x,y,z); if(!rd[z]) rd[z]=1llu*rand()*rand()*rand()*rand(); add(x,y,rd[z]),add(y,x,rd[z]); } tot=0; dfs(1,0); for(int i=1;i<=tot;i++) if(cnt[i]>=2) ans-=1ll*cnt[i]*(cnt[i]-1)/2; write(ans),puts(""); } }
T2 跳跃
赛时赛后都有好多错解过去了，下面的错解赛后通过部分同学的努力全部 hack 掉了。
-
部分分：\(O(nk)\) 暴力模拟 DP，发现他跳个几百遍几千遍差不多就截住了？于是通过此题，卡的方式就是另 \(a_1=1\)，再来一串负数，之后随机，从而本来跳几万遍能过去的他被截住不跳就死了。
点击查看代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define sort stable_sort using namespace std; const int N=1e3+10; const ll inf=1e18; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0; for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);} template<typename Tp> inline void wt(Tp x) {if(x>9)wt(x/10);putchar((x%10)+'0');} template<typename Tp> inline void write(Tp x) {if(x<0)putchar('-'),x=~x+1;wt(x);} template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);} int T,n,m,a[N],ml[N],mr[N]; ll ans,f[N]; signed main() { read(T); while(T--) { read(n,m); ans=0; for(int i=1;i<=n;i++) read(a[i]),a[i]+=a[i-1]; int tmp=0; for(int i=1;i<=n;i++) ml[i]=a[i]-tmp,tmp=min(tmp,a[i]); tmp=a[n]; for(int i=n;i>=1;i--) mr[i]=tmp-a[i-1],tmp=max(tmp,a[i]); memset(f,-0x3f,sizeof(f)); f[1]=0; for(int j=1;j<=min(5000,m);j++) { ll maxx=-inf; if(j&1) for(int i=1;i<=n;i++) { maxx=max(maxx,f[i]-a[i-1]); f[i]=maxx+a[i]>=0?maxx+a[i]:-inf; ans=max(ans,f[i]+max(0ll,1ll*(m-j)*ml[i])); } else for(int i=n;i>=1;i--) { maxx=max(maxx,f[i]+a[i]); f[i]=maxx-a[i-1]>=0?maxx-a[i-1]:-inf; ans=max(ans,f[i]+max(0ll,1ll*(m-j)*mr[i])); } } write(ans),puts(""); } } -
部分分：各种乱搞，不解释了。
-
正解：
设 \(f_i\) 表示最少跳几步到达点 \(i\) 以及此时的权值，可以 \(O(n^2)\) 转移，最后答案就是让其永远在 \(i\) 这儿跳下去，枚举 \(i\) 即可。
点击查看代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define sort stable_sort using namespace std; const int N=1010; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0; for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);} template<typename Tp> inline void wt(Tp x) {if(x>9)wt(x/10);putchar((x%10)+'0');} template<typename Tp> inline void write(Tp x) {if(x<0)putchar('-'),x=~x+1;wt(x);} template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);} int T,n,m,a[N],mx[N]; pair<int,ll>f[N]; ll ans; signed main() { read(T); while(T--) { read(n,m); ans=0,memset(f,0,sizeof(f)); for(int i=1,tmp=0;i<=n;i++) { read(a[i]),a[i]+=a[i-1]; mx[i]=a[i]-tmp,tmp=min(tmp,a[i]); if(a[i]>0) f[i]=make_pair(m-1,a[i]); } for(int i=2;i<=n;i++) for(int j=1;j<=i-1;j++) { int x=f[j].first; ll y=f[j].second; if(x<=0) continue; int cnt=max(1,(int)ceil(1.0*(a[j]-a[i]-y)/(2.0*mx[j]))); y+=a[i]-a[j]+2ll*cnt*mx[j]; cnt=y<0?5e8:cnt; x-=2ll*cnt; auto tmp=make_pair(x,y); if(tmp>f[i]) f[i]=tmp; } for(int i=1;i<=n;i++) { int x=f[i].first; ll y=f[i].second; ans=max(ans,1ll*x*mx[i]+y); } write(ans),puts(""); } }
T3 大陆
转化题面，一个省要么自身构成一个联通块，要么加上其省会刚好成为联通块。
那么自下而上处理，对于节点 \(x\)，将其所有儿子 \(y\) 的集合合并到 \(x\) 的集合中，一旦 \(x\) 中集合元素数量超过 \(B\) 就分出一个省，省会为 \(x\)，并将这些元素从集合中删除，这样处理完 \(x\) 后 \(x\) 的集合中会剩余部分元素留给 \(fa_x\)。
这样构造能够保证每个集合内元素数量一定小于 \(B\)，从而一个省的城市数量一定小于 \(2B\)，最后会剩下一些点凑不够一个 \(B\)，就将它全部归到最后一个组，因为前者数量小于 \(B\)，后者元素数量小于 \(2B\)，那么最后加起来一定小于 \(3B\)，是必定合法的构造方案。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e4+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,m,tot,ans[N],id[N];
vector<int>e[N],s[N];
void check(int x)
{
if(s[x].size()<m) return ;
ans[++tot]=x;
for(int pos:s[x]) id[pos]=tot;
s[x].clear();
}
void merge(int x,int y)
{
if(s[x].size()<s[y].size()) swap(s[x],s[y]);
for(int pos:s[y]) s[x].push_back(pos);
}
void dfs(int x,int fa)
{
for(int y:e[x]) if(y!=fa) dfs(y,x),merge(x,y),check(x);
s[x].push_back(x),check(x);
}
signed main()
{
read(n,m);
for(int i=1,x,y;i<=n-1;i++)
read(x,y),e[x].push_back(y),e[y].push_back(x);
dfs(1,0); for(int i=1;i<=n;i++) if(!id[i]) id[i]=tot;
write(tot),puts("");
for(int i=1;i<=n;i++) write(id[i]),putchar(' '); puts("");
for(int i=1;i<=tot;i++) write(ans[i]),putchar(' ');
}
T4 排列
- 部分分 \(40pts\)：\(O(nq)\) 暴力。
正解是 fhq_treap 平衡树，但是不太可做，溜了溜了。
总结
T1 不应该没想到映射，更不应该死磕，T2 乱搞挂成 \(0\) 了不应该，T3 挺简单的赛时应该仔细想想。
附录
刚开始放的题有两道原题来自 南昌起义，于是换题了。
标签：write,read,void,30,Tp,2024,int,inline,集训 From： https://www.cnblogs.com/Charlieljk/p/18372443