前言
先痛骂没良心出题人，T1 \(n\sqrt n\) 多大你刚好给多大，一点不多给，T2 才是签到题，因为放了 T2 位置打了暴力就去想 T3 了，我是唐氏，谁让你 T1、T2 swap 的？T3 实则三道题。
但是还是感觉 T1 更简单啊，\(5e4\) 搁哪儿摆着呢一眼 \(O(n\sqrt n)\)，甚至空间也是这么多，太明显了。
挂分挂上天了，T1 本来是首切，第一发直接过了，但是因为排序多个 \(\log\) 怕过不去加了个桶排，结果空间刚好炸，挂成 \(50\)，然后因为赛时曾经过了赛后再过甚至不显示，但实际上存图的时候直接用 vector 下表为权值就是排好序的不需要再排序，属于脑瘫了，T3 空间开小暴力分全无哈哈。
T1 排列最小生成树
显然有每个边权都 \(\le n\)。
-
证明：
对于每个点，其位置相邻或权值相邻的点与他的边权一定 \(\le n\)。
点 \(i\) 连接 \(i-1\)，构成一条链，即一定存在一组所有权值都 \(\le n\) 的合法方案。
若存在一条边边权 \(>n\)，不妨断开这条边，分成两个大小分别为 \(n,m\) 的连通块，根据鸽巢原理，\(n\times m\) 条边中一定存在一条权值 \(\le n\) 的边，连该条即可，从而存在边权 \(>n\) 的方案一定不是最优解。
证毕。
从而对于一个点两边各扫 \(\sqrt{n}\) 即可（位置和权值），从而边数为不会超过 \(2n\sqrt n\)（没有判 \((x,y)=(y,x)\)），再跑最小生成树即可，注意建图方式（前言中已说）。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
using namespace std;
const int N=5e4+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar_unlocked();
for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
for(;isdigit(c);c=getchar_unlocked()) 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_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,t,tot,a[N],f[N],id[N]; ll ans,tmp; vector<pair<int,int> >e[N];
inline int find(int x) {return x==f[x]?x:f[x]=find(f[x]);}
signed main()
{
freopen("pmst.in","r",stdin),freopen("pmst.out","w",stdout);
read(n),t=sqrt(n); bool flag=0;
for(int i=1;i<=n;i++) read(a[i]),id[a[i]]=i,f[i]=i,flag|=(a[i]!=i);
if(!flag) return write(n-1),0;
for(int i=1;i<=n;i++)
{
for(int j=i-1;j>=max(1,i-t);j--)
if((tmp=1ll*abs(a[i]-a[j])*(i-j))<=n) e[tmp].pb(mkp(i,j));
for(int j=i+1;j<=min(n,i+t);j++)
if((tmp=1ll*abs(a[i]-a[j])*(j-i))<=n) e[tmp].pb(mkp(i,j));
for(int j=a[i]-1;j>=max(1,a[i]-t);j--)
if((tmp=1ll*(a[i]-j)*abs(i-id[j]))<=n&&abs(i-id[j])>t)
e[tmp].pb(mkp(i,id[j]));
for(int j=a[i]+1;j<=min(n,a[i]+t);j++)
if((tmp=1ll*(j-a[i])*abs(i-id[j]))<=n&&abs(i-id[j])>t)
e[tmp].pb(mkp(i,id[j]));
}
for(int i=1,x,y;i<=n;i++) for(auto j:e[i])
{
if((x=find(j.fi))==(y=find(j.se))) continue;
f[x]=y,ans+=i; if(++tot==n-1) return write(ans),0;
}
}
T2 卡牌游戏
每个 \(a_i\) 对应的所有 \(b_j\) 是固定的，定义 \(g=\gcd(n,m)\)，也就是说进行了 \(g\) 各循环，根据裴蜀定理 \(a_i\) 对应的所有 \(b_j\) 满足 \(i≡j\pmod p\)，从而对于每个 \(g\) 的余数分别排序双指针就做完了。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar_unlocked();
for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
for(;isdigit(c);c=getchar_unlocked()) 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_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,m,g,a[N],b[N]; ll ans1,ans2; vector<int>va,vb;
inline int gcd(int x,int y) {return !y?x:gcd(y,x%y);}
signed main()
{
freopen("cardgame.in","r",stdin),freopen("cardgame.out","w",stdout);
read(n,m),g=gcd(n,m);
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=m;i++) read(b[i]);
for(int i=0;i<g;i++,va.clear(),vb.clear())
{
for(int j=(!i)*g;j+i<=n;j+=g) va.push_back(a[j+i]);
for(int j=(!i)*g;j+i<=m;j+=g) vb.push_back(b[j+i]);
sort(va.begin(),va.end()),sort(vb.begin(),vb.end());
for(int j=0,k=0,sum1=0,sum2=0;j<va.size();j++)
{
if(j&&va[j]>va[j-1]) sum1+=sum2,sum2=0;
for(;k<vb.size()&&vb[k]<va[j];k++) sum1++;
for(;k<vb.size()&&vb[k]==va[j];k++) sum2++;
ans1+=sum1,ans2+=sum2;
}
}
write(ans1*=g),puts(""),write(1ll*n*m-ans1-(ans2*=g)),puts(""),write(ans2);
}
T3 比特跳跃
-
\(s=1\)：
若 \(n\) 为 \(2\) 的整数次幂，则 \(1\sim n-1\) 直接到 \(n\) 的代价都是 \(0\)。
否则找到最大的一个 \(i=2^j-1\)，那么 \(1\sim i-1\) 到 \(i\) 的代价都是 \(0\)，大于 \(i\) 的数可以先调到他的补再跳回来，还是 \(0\)，只有 \(2^{j+1}-1\) 例外，特判掉即可。
-
\(s=2\)：
跳跃的代价至于不同的 \(1\) 的个数有关，从而 \(x\to x ⊕ 2^{i}+x\to x ⊕ 2^{j}=x\to x ⊕ 2^i ⊕ 2^j\)，从而只需要连 \(O(n\log(n))\) 条边，跑最短路即可。
-
\(s=3\)：
跳两次一定不如跳一次，所以 \(i\) 要么直接从 \(1\) 跳过来，要么从 \(i\) 的子集跳过来（代价为 \(i\)），从而先跑一边最短路，再用子集更新答案再跑一边最短路即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e5+10,M=3.5e6+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar_unlocked();
for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
for(;isdigit(c);c=getchar_unlocked()) 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_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,m,s,tot,head[N],nxt[M],to[M]; ll k,f[N],w[M],dis[N]; bitset<N>vis;
priority_queue<pair<ll,int> >q;
void add(int x,int y,ll z)
{nxt[++tot]=head[x],to[tot]=y,w[tot]=z,head[x]=tot;}
void init1()
{memset(dis,0x3f,sizeof(dis)),dis[1]=0,q.push(make_pair(0,1));}
void init2()
{for(int i=1;i<=n;i++) q.push(make_pair(-dis[i],i)); vis.reset();}
void dijkstra()
{
while(!q.empty())
{
int x=q.top().second; q.pop(); if(vis[x]) continue; vis.set(x);
for(int i=head[x],y;~(y=to[i]);i=nxt[i]) if(dis[y]>dis[x]+w[i])
dis[y]=dis[x]+w[i],q.push(make_pair(-dis[y],y));
}
}
signed main()
{
freopen("jump.in","r",stdin),freopen("jump.out","w",stdout);
read(n,m,s,k); to[0]=-1;
if(s==1&&n==(1<<(__lg(n)+1))-1)
{
dis[n]=1e9; for(int i=1;i<n;i++) dis[n]=min(dis[n],k*(i&n));
for(int i=1,x,y,z;i<=m;i++)
read(x,y,z),(x==n||y==n)&&(dis[n]=min(dis[n],(ll)z));
}
else if(s==2)
{
for(int i=1;i<=n;i++) for(int j=0;j<=__lg(n);j++)
if((i>>j)&1) add(i,i^(1<<j),k*(1<<j)),add(i^(1<<j),i,k*(1<<j));
for(int i=1,x,y,z;i<=m;i++) read(x,y,z),add(x,y,z),add(y,x,z);
init1(),dijkstra();
}
else if(s==3)
{
for(int i=2;i<=n;i++) add(1,i,k*(i|1)),add(i,1,k*(i|1));
for(int i=1,x,y,z;i<=m;i++) read(x,y,z),add(x,y,z),add(y,x,z);
init1(),dijkstra(),memset(f,0x3f,sizeof(f)),f[1]=0;
for(int i=2;i<=n;i++) for(int j=0;j<=__lg(n);j++) if((i>>j)&1)
f[i]=min((dis[i]=min(dis[i],f[i^(1<<j)]+k*i)),f[i^(1<<j)]);
init2(),dijkstra();
}
for(int i=2;i<=n;i++) write(dis[i]),putchar_unlocked(' ');
}
T4 区间
-
部分分 \(35pts\)：二维前缀和直接做。
-
部分分 \(60pts\)：二维偏序，扫描线，对于 \(a_i\le 3,b_i\le 3\) 复杂度是对的。
-
正解：
线段树维护历史和板子，限制一可以单调栈维护，限制二可以单调栈里跑二分，因为没有强制在线，所以直接扫描线即可。
点击查看代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define sort stable_sort #define mid (l+r>>1) #define ls (mid<<1) #define rs (mid<<1|1) #define pb push_back #define mkp make_pair #define fi first #define se second using namespace std; const int N=3e5+10; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar_unlocked(); for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0; for(;isdigit(c);c=getchar_unlocked()) 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_unlocked((x%10)+'0');} template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);} template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);} int n,m,a[N],b[N],sta[N],sum[N<<1],tag[N<<1]; ll ans[N],hsum[N<<1]; vector<pair<int,int> >e[N]; inline void spread(int p,int l,int r) { hsum[ls]+=1ll*sum[ls]*tag[p],tag[ls]+=tag[p]; hsum[rs]+=1ll*sum[rs]*tag[p],tag[rs]+=tag[p],tag[p]=0; } void add(int p,int l,int r,int vl,int vr) { if(vl<=l&&vr>=r) return hsum[p]+=sum[p],tag[p]++,void(); spread(p,l,r); if(vl<=mid) add(ls,l,mid,vl,vr); if(vr>mid) add(rs,mid+1,r,vl,vr); sum[p]=sum[ls]+sum[rs],hsum[p]=hsum[ls]+hsum[rs]; } void change(int p,int l,int r,int x,int d) { if(l==r) return sum[p]+=d,void(); spread(p,l,r),x<=mid?change(ls,l,mid,x,d):change(rs,mid+1,r,x,d); sum[p]=sum[ls]+sum[rs],hsum[p]=hsum[ls]+hsum[rs]; } ll ask(int p,int l,int r,int vl,int vr) { if(vl<=l&&vr>=r) return hsum[p]; spread(p,l,r); ll res=0; if(vl<=mid) res+=ask(ls,l,mid,vl,vr); if(vr>mid) res+=ask(rs,mid+1,r,vl,vr); return res; } signed main() { freopen("interval.in","r",stdin),freopen("interval.out","w",stdout); read(n),change(1,1,n,sta[1]=1,1); for(int i=1;i<=n;i++) read(a[i]); for(int i=2;i<=n;i++) read(b[i]); read(m); for(int i=1,l,r;i<=m;i++) read(l,r),e[r].pb(mkp(l,i)); for(int i=2,top=1,pos,l,r;i<=n;i++) { for(pos=0,l=1,r=top;l<=r;) a[sta[mid]]<b[i]?r=(pos=mid)-1:l=mid+1; if(pos) add(1,1,n,sta[pos],i); for(auto it:e[i]) ans[it.se]=ask(1,1,n,it.fi,i); for(;top&&a[sta[top]]<=a[i];) change(1,1,n,sta[top--],-1); change(1,1,n,sta[++top]=i,1); } for(int i=1;i<=m;i++) write(ans[i]),puts(""); }