前言
赛时本来 rk3，赛后自己加 hack 卡自己于是成 rk4 了。
因为这场是假做法大战，T1 假贪心有 \(92pts\)；T2 \(O(n^2m)\) 能过（是因为数据里 \(m\le 10\)）；
T3 相当抽象，赛时我打的爆搜只加了一个剪枝能得 \(70pts\)，赛后发现无解的时候会跑满，于是提前判掉无解就过了甚至最优解 \(30ms\)，发现数据里的数据生成器好像是错的？\(m\) 全都很小，但是发现 \(m\) 很大的时候基本上直接输出最短路就是答案，所以造一组 \(m\) 不大不小的就卡掉了；
然后我想了一个假做法，刚开始我还以为是真的还上去讲，结果大家全都跟着打假做法和爆搜，经过与 wang54321 等人的分析发现是假的，于是造了好长时间的 hack,刚开始不知道怎么造才能完全掉随机打乱，发现及时随机打乱原来能错的仍有不小的错误率，所以直接多随几组能错的绑包就好了。
然后就有了菜等人数据点分治过 hack（因为 hack 数据不是很大），丁真研发新的假做法继续过 hack，xrlong 发现我的数据有自环（我记得我判了呀不是），遂重造 hack，现在除了正解都死了。
本来以为 T3 已经是假做法巅峰了，结果下午发现 T4 目前没有任何一个人打的是正解……
因为 && 和 || 有短路，T4 暴力先判并查集比先判是否有交快得多（因为并查集常数小，而 check 全是 if 常数巨大）。
T1 玩游戏
-
部分分 \(24pts\)：\(O(n^2)\) 区间 DP。
-
正解：
贪心，考虑如果移动一次断点不可能只移动到一个更大的位置就停了，只要移一定移到更小的位置，所以可以处理处 next。
发现跳到最小值位置就停了，考虑再反正跳一遍就好了，跳的过程中判是否能安全走完更大的那部分即可，复杂度 \(O(n)\)。
点击查看代码
#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 T,n,m,cnt1,cnt2,nxt1[N],nxt2[N]; ll a[N],b[N],c[N],pre[N],suf[N]; bool flag; signed main() { for(read(T);T;T--,memset(nxt1,0,4*(n+1)),memset(nxt2,0,4*(n+1))) { read(n,m); for(int i=1;i<=n;i++) read(c[i]); a[cnt1=1]=0; for(int i=m;i>=2;i--) a[++cnt1]=c[i]; b[cnt2=1]=0; for(int i=m+1;i<=n;i++) b[++cnt2]=c[i]; for(int i=1;i<=cnt1;i++) pre[i]=pre[i-1]+a[i]; for(int i=1;i<=cnt2;i++) suf[i]=suf[i-1]+b[i]; if(pre[cnt1]+suf[cnt2]>0) {puts("No"); continue;} for(int i=2,x=1;i<=cnt1;i++) if(pre[i]<pre[x]) nxt1[x]=i,x=i; for(int i=cnt1-1,x=cnt1;i;i--) if(pre[i]<pre[x]) nxt1[x]=i,x=i; for(int i=2,x=1;i<=cnt2;i++) if(suf[i]<suf[x]) nxt2[x]=i,x=i; for(int i=cnt2-1,x=cnt2;i;i--) if(suf[i]<suf[x]) nxt2[x]=i,x=i; for(int x=1,y=1;nxt1[x]||nxt2[y];flag=0) { for(int i=x+1;i<=nxt1[x];i++) if(pre[i]+suf[y]>0) {flag=1; break;} if(!(flag|=(!nxt1[x]))) {x=nxt1[x]; continue;} flag=0; for(int i=y+1;i<=nxt2[y];i++) if(pre[x]+suf[i]>0) {flag=1; break;} if(flag|=(!nxt2[y])) break; y=nxt2[y]; } if(flag) {flag=0,puts("No"); continue;} for(int x=cnt1,y=cnt2;nxt1[x]||nxt2[y];flag=0) { for(int i=x-1;i>=nxt1[x];i--) if(pre[i]+suf[y]>0) {flag=1; break;} if(!(flag|=(!nxt1[x]))) {x=nxt1[x]; continue;} flag=0; for(int i=y-1;i>=nxt2[y];i--) if(pre[x]+suf[i]>0) {flag=1; break;} if(flag|=(!nxt2[y])) break; y=nxt2[y]; } puts(flag?"No":"Yes"),flag=0; } }
T2 排列
-
部分分 \(50pts\)：爆搜，发现 \(k=1\) 时为 \(2^{n-1}\)。
-
正解：
逆天 DP，感觉不是我赛时能想出来的。
\(f_{i,j,0/1,0/1}\) 表示长度为 \(i\) 的区间能在不超过 \(j\) 次操作后仅剩最大值的方案数，\(0/1\) 表示左/右端是否存在比区间最大值更大的值。
转移考虑在两个区间的中间加入一个最大值 \(k\) 的贡献：
-
\(k\) 为整个序列最大值：
\[f_{i,j,0,0}=\sum\limits_{k=1}^iC_{i-1}^{k-1}\times f_{k-1,j,0,1}\times f_{i-k,j,1,0} \] -
\(k\) 为右区间最大值，左区间左侧还有更大值,左区间需要留一次操作消最大值 \(k\)：
\[f_{i,j,1,0}=\sum\limits_{k=1}^iC_{i-1}^{k-1}\times f_{k-1,j-1,1,1}\times f_{i-k,j,1,0} \] -
\(k\) 位左区间最大值，右区间右侧还有更大值，同理：
\[f_{i,j,0,1}=\sum\limits_{k=1}^iC_{i-1}^{k-1}\times f_{k-1,j,0,1}\times f_{i-k,j-1,1,1} \] -
左右区间两侧都有更大值，左右任意区间在 \(j-1\) 内消完即可，去掉两边都是 \(j\) 的贡献：
\[f_{i,j,1,1}=\sum\limits_{k=1}^iC_{i-1}^{k-1}\times [f_{k-1,j,1,1}\times f_{i-k,j,1,1}-(f_{k-1,j,1,1}-f_{i-k,j-1,1,1})\times (f_{i-k,j,1,1}-f_{i-k,j-1,1,1})] \]
最后答案为 \(f_{n,n,0,0}\)，发现每次操作最少消除 \(\dfrac{n}{2}\) 个点，所以合法的 \(m\le \log_2(n)\)，复杂度 \(O(n^2m)\) 实则为 \(O(n^2\log n)\) 级别，需特判不合法的 \(m\)。
点击查看代码
#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_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,P,c[N][N],f[N][11][2][2]; inline int mod(int x,int y) {return (x+=y)>=P?x-P:x;} signed main() { read(n,m,P); if(m>10) return write(0),0; for(int i=0;i<=n;i++) c[i][0]=1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c[i][j]=mod(c[i-1][j],c[i-1][j-1]); for(int i=0;i<=m;i++) f[0][i][0][0]=f[0][i][0][1]=f[0][i][1][0]=f[0][i][1][1]=1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=i;k++) { f[i][j][0][0]=mod(f[i][j][0][0],1ll*f[k-1][j][0][1]*f[i-k][j][1][0]%P*c[i-1][k-1]%P); f[i][j][1][0]=mod(f[i][j][1][0],1ll*f[k-1][j-1][1][1]*f[i-k][j][1][0]%P*c[i-1][k-1]%P); f[i][j][0][1]=mod(f[i][j][0][1],1ll*f[k-1][j][0][1]*f[i-k][j-1][1][1]%P*c[i-1][k-1]%P); f[i][j][1][1]=mod(f[i][j][1][1],1ll*(1ll*f[k-1][j][1][1]*f[i-k][j][1][1]%P-1ll*(f[k-1][j][1][1]-f[k-1][j-1][1][1])*(f[i-k][j][1][1]-f[i-k][j-1][1][1])%P+P)%P*c[i-1][k-1]%P); } write(mod(f[n][m][0][0],P-f[n][m-1][0][0])); } -
T3 最短路
-
部分分 \(70pts\sim 99pts\)：爆搜加剪枝。
-
部分分 \(99pts\)：丁真的假做法。
-
部分分 \(99pts\)：建反图，\(dis_{i,j}\) 表示从 \(1\) 沿正边跑到 \(i\) 加上沿反边跑到 \(j\) 的距离和，那么答案就是 \(dis_{n,n}\)，bitset 压状态判有没有走过一个点，跑二维 dijkstra。最短路径不唯一的时候就死了，复杂度 \(O(m\log m)\)。
-
正解：
考虑 \(n\to 1\) 的路径一定是沿着 \(1\to n\) 的路径走一段，再沿着不是 \(1\to n\) 的路径走一段，如此往复，称这一段的起点为 A 类点，终点为 B 类点，那么 A 和 B 一定交错出现，\(f_{i,j}\) 表示 \(i\) 为当前最后一个 A，\(j\) 为当前最后一个 B，\(g_{i,j}\) 类似的表示 \(i,j\) 均为 A，那么对于 \(f\) 枚举下一个 A，\(g\) 枚举中间的 A，发现又可以二维 dijkstra 了，复杂度 \(O(n^3\log n)\)。
点击查看代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define sort stable_sort using namespace std; const int N=255; 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],dis[N][N],f[2][N][N]; bool vis[2][N][N]; struct aa { int op,x,y,w; inline bool operator < (const aa a) const {return w>a.w;} }; priority_queue<aa>q; signed main() { read(n,m),memset(f,0x3f,sizeof(f)),memset(dis,0x3f,sizeof(dis)); for(int i=1;i<=n;i++) read(a[i]),dis[i][i]=a[i]; for(int i=1,x,y;i<=m;i++) read(x,y),dis[x][y]=min(dis[x][y],a[x]+a[y]); for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) if(dis[i][k]!=0x3f3f3f3f) for(int j=1;j<=n;j++) if(dis[k][j]!=0x3f3f3f3f) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]-a[k]); for(f[0][1][1]=a[1],q.push({0,1,1,a[1]});!q.empty();) { aa it=q.top(); q.pop(); int op=it.op,x=it.x,y=it.y; if(vis[op][x][y]) continue; vis[op][x][y]=1; if(!op) for(int z=1,w;z<=n;z++) { w=f[0][x][y]+dis[y][z]-a[y]-(x==z&&x!=y)*a[z]; if(f[1][x][z]>w) f[1][x][z]=w,q.push({1,x,z,w}); } else for(int z=1,w;z<=n;z++) { w=f[1][x][y]+dis[y][z]+dis[z][x]-a[x]-a[y]-a[z]+(x==z&&x==y)*a[z]; if(f[0][y][z]>w) f[0][y][z]=w,q.push({0,y,z,w}); } } write(f[0][n][n]==0x3f3f3f3f?-1:f[0][n][n]); }
T4 矩形
写一个错误的解法吧，复杂度貌似能卡，随机数据下应该是 \(O(n\log n)\)。
直接扫描线加并查集，扫到第一条边的时候查一下扔到并查集里，第二条边直接加进去即可。
点击查看代码
#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)
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,ans,f[N],up[N<<1],val[N<<1],now[N<<1],add[N<<1];
struct aa {int x1,y1,x2,y2;}e[N];
inline int find(int x) {return x==f[x]?x:f[x]=find(f[x]);}
inline void pushup(int p,int l,int r)
{
if(val[ls]==2||val[rs]==2) val[p]=2;
else if(now[ls]==now[rs]) now[p]=now[ls],up[p]=up[ls],val[p]=1;
else val[p]=2;
}
inline void spread(int p,int l,int r)
{add[ls]=add[rs]=add[p],now[ls]=now[rs]=now[p],up[ls]=up[rs]=up[p],add[p]=0;}
inline void change(int p,int l,int r,int vl,int vr,int d,int id)
{
if(vl<=l&&vr>=r&&val[p]==1)
return (up[p]<d)&&(up[p]=d)&&(now[p]=id)&&(add[p]=1),void();
if(add[p]) spread(p,l,r);
if(vl<=mid) change(ls,l,mid,vl,vr,d,id);
if(vr>mid) change(rs,mid+1,r,vl,vr,d,id);
pushup(p,l,r);
}
inline void ask(int p,int l,int r,int vl,int vr,int d,int id)
{
if(vl<=l&&vr>=r&&val[p]==1)
return (up[p]>=d)&&(f[find(id)]=find(now[p])),void();
if(add[p]) spread(p,l,r);
if(vl<=mid) ask(ls,l,mid,vl,vr,d,id);
if(vr>mid) ask(rs,mid+1,r,vl,vr,d,id);
}
signed main()
{
read(n); for(int i=1;i<=n;i++) f[i]=i;
for(int i=1,a,b,c,d;i<=n;i++) read(a,b,c,d),e[i]={a,b,c,d},m=max({m,b,d});
fill(val+1,val+1+(m<<1),1);
sort(e+1,e+1+n,[](aa a,aa b){return a.x1==b.x1?a.x2<b.x2:a.x1<b.x1;});
for(int i=1;i<=n;i++)
{
ask(1,1,m,e[i].y1,e[i].y2,e[i].x1,i);
change(1,1,m,e[i].y1,e[i].y2,e[i].x2,i);
}
for(int i=1;i<=n;i++) ans+=(f[i]==i); write(ans);
}