前言
这次不是之前学长吃完吐出来的 shi，这次是新拉的热乎的烫嘴的 shi。
T1、2、3、4 大样例全部错一遍，T1 题面和时限再错一遍哈哈哈。
T4 假做法有 60 哈哈哈，大样例跑出来半个对的都没有能得 60 哈哈哈。
accoders T1 前半小时没数据做得快的全部都死哈哈（还好我第一份被卡常了后来又交了一份过了）。
T1 图书管理
中位数经典套路，枚举 \(a_i\)，\(>a_i\) 的变为 \(1\)，\(<a_i\) 的变为 \(-1\)，那么如果存在左右端点内的和为 \(0\) 则 \(a_i\) 是这个区间的中位数，左区间先扫一遍扔桶里右区间再统计答案即可，复杂度 \(O(n^2)\)，用 STL 会被卡常，建议用数组。
- 然后竟然真的有人打 \(O(n^2\log n)\) 的部分分，就是用对顶堆什么的暴力跑，之前没听说过这玩意啊，学了一下，但是部分分真不是比正解难想又难打？
点击查看代码
#include<bits/stdc++.h>
#pragma GCC optimize(3)
#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_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,a[N],b[N],sum[N<<1]; ll ans,res;
signed main()
{
freopen("book.in","r",stdin),freopen("book.out","w",stdout);
read(n); for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=n;ans+=res*a[i++],res=0,memset(sum,0,sizeof(sum)))
{
for(int j=1;j<=n;j++) b[j]=a[j]>a[i]?1:-1; b[i]=0;
for(int j=i,pre=0;j;j--) pre+=b[j],sum[pre+n]+=j;
for(int j=i,suf=0;j<=n;j++) suf+=b[j],res+=1ll*sum[n-suf]*j;
}
write(ans);
}
T2 两棵树
结论题：树（森林）的连通块数 \(=\) 点数 \(-\) 边数。
那么结果可以拆成 \(点_U\times 点_T-点_U\times 边_T-边_U\times 点_T+边_U\times 边_T\)。 统计这四部分的贡献即可。
-
\(点\times 点\)：设 \(x,u\) 分别表示 \(U,T\) 中一点，则 \(x,u\) 同时存在的概率等于 \([x\ne u]\dfrac{1}{4}\)，所以该部分答案为 \(\dfrac{n(n-1)}{4}\)。
-
\(点\times 边\)：设 \(x\) 表示 \(U\) 中一点，\((u,v)\) 表示 \(T\) 中一边，则 \(x,(u,v)\) 同时存在概率为 \([x\ne u \wedge x\ne v]\dfrac{1}{8}\)，这个贡献要 \(\times -2\)。
-
\(边\times 边\)：设 \((x,y),(u,v)\) 分别表示 \(U,T\) 中一边，则 \((x,y),(u,v)\) 同时存在概率为 \([x\ne u\wedge x\ne v\wedge y\ne u\wedge y\ne v]\dfrac{1}{16}\)，可以枚举 \(U\) 中边 \((x,y)\)，则该条边的贡献为 \(\dfrac{n-1-deg_x-deg_y+[(u,v)=(x,y)]}{16}\)，\([(u,v)=(x,y)]\) 表示 \(T\) 中存在 \((u,v)=(x,y)\)。
最后都加起来即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10,P=998244353;
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,ans,deg[N]; set<int>vis[N];
inline int mod(int x,int y) {return (x+=y)>=P?x-P:x;}
signed main()
{
freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);
read(n); for(int i=1,x,y;i<n;i++)
{
read(x,y),(x>y)&&(x^=y^=x^=y);
deg[x]++,deg[y]++,vis[x].insert(y);
}
for(int i=1,x,y;i<n;i++)
{
read(x,y),(x>y)&&(x^=y^=x^=y);
ans=mod(ans,n-1-deg[x]-deg[y]+vis[x].count(y));
}
write((935854081ll*ans%P+499122177ll*(n-1)%P)%P);
}
T3 函数
-
部分分 \(60pts\)：暴力也能拿这个分，真正应该拿到这个分的是可持久化 01trie，找二分 \([l,mid]\) 中最大值与最小值是否异号，复杂度 \(O(n\log n\log v)\)。
-
正解：
判无解是容易的，找到最大值和最小值，判断二者是否异号即可，设其位置为 \(l,r\)。
若有解，那么目前满足 \(l,r\) 异号，二分一个 \(mid\)，一定满足 \(mid\) 和 \(l,r\) 中的一个异号，由此二分不断缩小范围最后找到答案，复杂度 \(O(n(\log n+\log v))\)。
点击查看代码
#include<bits/stdc++.h> #pragma GCC optimize(3) #define ll long long #define endl '\n' #define sort stable_sort using namespace std; const int N=1e6+10,M=3e7+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,tot=1,s[N],pos[M],t[M][2]; inline void insert(int x,int id,int p=1) { for(int i=29,c;~i;i--,p=t[p][c]) (!t[p][c=(x>>i)&1])&&(t[p][c]=++tot); pos[p]=id; } inline int ask(int x,int v,int p=1) { for(int i=29,c;~i&&p;i--) t[p][(c=(x>>i)&1)^v]?p=t[p][c^v]:p=t[p][c^(!v)]; return pos[p]; } signed main() { freopen("fun.in","r",stdin),freopen("fun.out","w",stdout); read(n,m); for(int i=1;i<=n;i++) read(s[i]),insert(s[i],i); for(int a,b,l,r,mid;m;m--) { read(a,b),l=ask(a,1),r=ask(a,0); if((!((s[l]^a)-b>0)^((s[r]^a)-b>0))) {puts("-1"); continue;} for((l>r)&&(l^=r^=l^=r);l+1<r;) (((s[mid=l+r>>1]^a)-b>0)^((s[r]^a)-b>0))?l=mid:r=mid; write(l),puts(""); } }
T4 编辑
-
部分分 \(60pts\)：
\(O(n^3)\) DP 是显然的，对于两个串 \(s,t\)，设 \(f_{i,j}\) 表示 \(s\) 的前 \(i\) 位和 \(t\) 的前 \(j\) 位匹配最少需要的操作数，有 \(f_{i,j}=\min(f_{i-1,j}+1,f_{i,j-1}+1,f_{i-1,j-1}+[s_i\ne t_j])\)，这个 DP 可以继承，所以是 \(O(n^3)\) 的。
但是发现他和最长公共子序列的转移是那么的相似，完全就是这个 DP 反过来，那么是不是用什么玩意儿减去最长公共子序列长度即可？但事实证明完全不对，大样例跑出来和答案一毛不一样，唉但是他交上去也有 \(60\)，奇怪不奇怪？
-
正解：
发现上面那个做法单次 DP 是 \(O(n^2)\) 的因为 \(n\) 很大，发现 \(k\) 很小，考虑设计状态时改成和 \(k\) 相关的，从而使单次复杂度变为 \(O(k^2)\)。
设 \(f_{i,j}\) 表示操作 \(i\) 次，二者长度差为 \(j\) 时最大的匹配长度（\(j\) 可以 \(<0\)）。
对于每一种状态确定了下一次匹配的起点，\(s\) 的起点是 \(f_{i,j}+1\)，\(t\) 的起点是 \(f_{i,j}+j+1\)，此时可以跳过一些已经匹配好的，即二者此时的最长公共前缀，这个是后缀数组板子，二分哈希也能做（但复杂度不太正确），即：
\[f_{i,j}=f_{i,j}+lcp(s[f_{i,j}+1,|s|],t[f_{i,j}+j+1,|t|]) \]接下来考虑转移：
\[\begin{cases}f_{i+1,j-1}=\max(f_{i+1,j-1},f_{i,j}+1)\\f_{i+1,j}=\max(f_{i+1,j},f_{i,j}+1)\\f_{i+1,j+1}=\max(f_{i+1,j+1},f_{i,j})\\\end{cases} \]分别对应添加、修改和删除操作。
由此枚举起点跑 DP 即可，发现 \(i\in[0,k],j\in[-k,k]\)，所以单次 DP 复杂度为 \(O(k^2)\)，总复杂度为 \(O(nk^2)\)（用二分哈希多个 \(\log\)）。
点击查看代码
#include<bits/stdc++.h> #pragma GCC optimize(3) #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 k,n,m,res,f[35][65],ans[35]; char s[N],t[N>>1]; class suffix_array { private: int n,sa[N],rk[N],id[N],cnt[N],key[N],oldrk[N],height[N],mn[20][N]; inline void count_sort(int n,int m) { memset(cnt,0,4*(m+1)); for(int i=1;i<=n;i++) cnt[key[i]=rk[id[i]]]++; for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1]; for(int i=n;i;i--) sa[cnt[key[i]]--]=id[i]; } public: inline void init(int len) { n=len; int m=27,w,tot=0,num=0; for(int i=1;i<=n;i++) rk[id[i]=i]=s[i]-'a'+1,key[i]=rk[id[i]]; for(count_sort(n,m),w=1;w<n&&tot!=n;w<<=1,m=tot,num=0) { for(int i=n;i>=n-w+1;i--) id[++num]=i; for(int i=1;i<=n;i++) (sa[i]>w)&&(id[++num]=sa[i]-w); count_sort(n,m),memcpy(oldrk,rk,4*(n+1)),tot=0; for(int i=1;i<=n;i++) rk[sa[i]]=(tot+=(oldrk[sa[i]]!=oldrk[sa[i-1]]||oldrk[sa[i]+w]!=oldrk[sa[i-1]+w])); } for(int i=1,k=0;i<=n;i++) if(rk[i]) {for(k-=!!k;s[i+k]==s[sa[rk[i]-1]+k];k++); height[rk[i]]=k;} memset(mn,0x3f,sizeof(mn)); for(int i=1;i<=n;i++) mn[0][i]=height[i]; for(int i=1;i<=__lg(n);i++) for(int j=1;j<=n;j++) mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<(i-1))]); } inline int lcp(int l,int r,int t=0) { ((l=rk[l])>(r=rk[r]))&&(l^=r^=l^=r),t=__lg(r-(++l)+1); return (!l||!r)?0:min(mn[t][l],mn[t][r-(1<<t)+1]); } }sa; inline int lcp(int x,int y) {return min({sa.lcp(x,n+y+1),n-x+1,m-y+1});} inline void solve(int st) { memset(f,-1,sizeof(f)),f[0][k]=0; for(int i=0;i<=k;i++) for(int j=0,h;j<=(k<<1);j++) if(f[i][j]!=-1&&f[i][j]+(h=j-k)>=0&&st+f[i][j]+h-1<=m) { f[i][j]+=lcp(f[i][j]+1,st+f[i][j]+h); if(i==k) continue; (j)&&(f[i+1][j-1]=max(f[i+1][j-1],f[i][j]+(f[i][j]!=n))); f[i+1][j]=max(f[i+1][j],f[i][j]+(f[i][j]!=n)); f[i+1][j+1]=max(f[i+1][j+1],f[i][j]); } for(int i=0;i<=(k<<1);i++) for(int j=0;j<=k;j++) if(f[j][i]==n&&i-k+n>0&&st+i-k+n-1<=m) {ans[j]++; break;} } signed main() { freopen("edit.in","r",stdin),freopen("edit.out","w",stdout); read(k),scanf("%s%s",s+1,t+1),n=strlen(s+1),m=strlen(t+1); s[n+1]='{',strcat(s+1,t+1),sa.init(n+m+1); for(int i=1;i<=m;i++) solve(i); for(int i=0;i<=k;i++) write(ans[i]),puts(""); }