T1 玩水
本来能拿八十分的，但是file error了，nnd
赛时的做法没有考虑在同一行但不相邻的，只算了下前缀和，于是会误判。
点击查看代码
#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i)
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;
const int maxn=1e3+10;
int tex;
int f[maxn][maxn];
char s[maxn][maxn];
int n,m;
void solve(){
cin>>n>>m;
Rep(i,1,n)cin>>(s[i]+1);
for(int i=1;i<n;++i)for(int j=1;j<m;++j)f[i][j]=(s[i][j+1]==s[i+1][j]);
for(int i=1;i<n;++i)for(int j=1;j<m;++j)if(f[i][j] && f[i][j+1])return cout<<"1\n",void();
else if(f[i][j] && f[i+1][j])return cout<<"1\n",void();
Dwn(i,n-1,1)Dwn(j,m-1,1)f[i][j]=f[i+1][j]+f[i][j+1]+f[i][j]-f[i+1][j+1];
for(int i=1;i<n;++i)for(int j=1;j<m;++j)if(f[i][j]>f[i+1][j+1] && f[i+1][j+1])return cout<<"1\n",void();
return cout<<"0\n",void();
}
int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);fre(water);cin>>tex;while(tex--)solve(); }
T2 AVL树
显然是一个贪心，我们从小到大枚举，或者按照中序遍历贪心是等效的。对于一个点是否能选，由于比它小的点都已经确定是否选了，于是我只需要考虑比它大的点，至少还得选多少个，才能满足它的深度要求，我就能知道这个点是否选，每个点维护一下子树内选到的最深的点是什么，以及在整体情况下，它最少要选到多深，对于一个深度确定的AVL树，节点的下界是确定的，于是就可以算出来点数要求。每次选一个点，就把它到根路径上的点都标记为选，并把比它大的点标记一下子树深度下界。涉及到深度下界下传的时候，优先给左儿子深度-1的标记。
点击查看代码
#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i)
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
#define int ll
using namespace std;
const int maxn=5e5+10;
int pre[maxn];
int dep[maxn];
int vis[maxn];
int lch[maxn],rch[maxn],fa[maxn];
int n,K,root,mxdep[maxn];
int h[maxn],lh[maxn];
void Dfs(int u){
dep[u]=dep[fa[u]]+1;mxdep[u]=dep[u];
if(lch[u])Dfs(lch[u]),mxdep[u]=max(mxdep[u],mxdep[lch[u]]);
if(rch[u])Dfs(rch[u]),mxdep[u]=max(mxdep[u],mxdep[rch[u]]);
}
bool Check(int u){
int res=0,now=max(dep[u],h[u]);
while(u){
if(!vis[u])++res;
now=max(now,h[u]);
if(u<fa[u])res+=pre[max(now-1,lh[rch[fa[u]]])-dep[fa[u]]];
u=fa[u];
}
return res<=K;
}
void Spread(int u){
h[u]=max(h[u],dep[u]); int now=h[u];
while(u){
h[u]=max(h[u],now);
if(!vis[u])vis[u]=1,--K;
if(u<fa[u] && rch[fa[u]])lh[rch[fa[u]]]=max(lh[rch[fa[u]]],h[u]-1);
u=fa[u];
}
}
void Sol(int u){
if(Check(u))Spread(u);
if(lch[u] && rch[u]){
if(mxdep[lch[u]]<lh[u])lh[rch[u]]=max(lh[rch[u]],lh[u]),lh[lch[u]]=max(lh[lch[u]],lh[u]-1);
else lh[lch[u]]=max(lh[lch[u]],lh[u]),lh[rch[u]]=max(lh[rch[u]],lh[u]-1);
Sol(lch[u]);Sol(rch[u]);
}else{
if(lch[u])lh[lch[u]]=max(lh[lch[u]],lh[u]),Sol(lch[u]);
if(rch[u])lh[rch[u]]=max(lh[rch[u]],lh[u]),Sol(rch[u]);
}
}
void solve(){fre(avl);
cin>>n>>K;int x;
Rep(i,1,n){
cin>>x;
if(x==-1)root=i;
else { fa[i]=x; if(i>x)rch[x]=i; else lch[x]=i; }
}
Dfs(root);
pre[1]=1;pre[2]=2; Rep(i,3,40)pre[i]=pre[i-1]+pre[i-2]+1;
Sol(root);
Rep(i,1,n)cout<<vis[i];
}
#undef int
int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);return solve(),0; }
T3 暴雨
赛时的做法是正确的，只是没有想到另一侧无限大，然后合并，一直卡在把最大值删了如何修正的问题上。暴力dp是比较显然的，正反做两次，把一侧设为无限高，然后状态里记录另一侧的最大值。然后枚举中间没有被铲平的位置，将两侧不高于它的状态合并起来，它就相当于那个无限大，就可以做了。对于记录最大值的那一维，显然最大只有K种，于是需要预处理出来每个前缀/后缀的前K大的数进行离散化，还要处理个转移方向？，因为在下一个位置可能新来了一个较大值，改变了离散化编号。这样很麻烦于是你想到直接偷懒用map，但是还是需要简单离散化把每个位置的答案存下来，中间只用两个map做dp，否则会MLE，卡卡常就能拿到98分(评测机状态好的时候)，然后剩下一个点数据点分治吧
点击查看代码
%:pragma GCC target("avx")
%:pragma GCC optimize(3)
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
%:pragma GCC optimize("-fcse-skip-blocks")
%:pragma GCC optimize("-fstrict-overflow")
#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i)
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;
const int maxn=25000+10,Mod=1e9+7;
int n,K,V;
int a[maxn],b[maxn];
int L[maxn],R[maxn];
ull ans;
unordered_map<int,pii>NowL[26],NowR[26],tmp[26];
//gp_hash_table<int,pii>NowL[26],NowR[26],tmp[26];
int fL[maxn][26][30][2],fR[maxn][26][30][2];
int Upper(int x){ int l=max(b[0]-K-2,1),r=b[0]; return upper_bound(b+l,b+r+1,x)-b-l+1; }
int Lower(int x){ int l=max(b[0]-K-2,1),r=b[0]; return lower_bound(b+l,b+r+1,x)-b-l+1; }
void GetL(int x){ Rep(j,0,K)for(int i=1;i<=K+3;++i)fL[x][j][i][0]=(fL[x][j][i][0]+fL[x][j][i-1][0])%Mod,fL[x][j][i][1]=(fL[x][j][i][1]+fL[x][j][i-1][1])%Mod; }
void GetR(int x){ x=n-x+1;Rep(j,0,K)for(int i=1;i<=K+3;++i)fR[x][j][i][0]=(fR[x][j][i][0]+fR[x][j][i-1][0])%Mod,fR[x][j][i][1]=(fR[x][j][i][1]+fR[x][j][i-1][1])%Mod; }
//void C(int j){ unordered_map<int,pii>ts;tmp[j].swap(ts);}
void solve(){fre(rain);
cin>>n>>K;
Rep(i,1,n)cin>>a[i],b[i]=a[i];
sort(b+1,b+n+1);b[0]=unique(b+1,b+n+1)-b-1;
Dwn(i,n,1)R[i]=max(R[i+1],a[i]);
NowL[0][0]=mair(0,1);
fL[0][0][0][1]=1; fR[0][0][0][1]=1;
Rep(i,1,n){
for(int j=0;j<=K;++j){
if(j<K){
for(auto it : NowL[j]){
int delta=it.fir;
auto tar=tmp[j+1].find(it.fir);
if(tar==tmp[j+1].end()){
if(delta&1)tmp[j+1][it.fir]=mair(it.sec.sec,it.sec.fir);
else tmp[j+1][it.fir]=mair(it.sec.fir,it.sec.sec);
}else{
if(delta&1) (*tar).sec=mair(((*tar).sec.fir+it.sec.sec)%Mod,((*tar).sec.sec+it.sec.fir)%Mod);
else (*tar).sec=mair(((*tar).sec.fir+it.sec.fir)%Mod,((*tar).sec.sec+it.sec.sec)%Mod);
}
}
}
for(auto it :NowL[j]){
int delta=max(it.fir-a[i],0);
int mx=max(it.fir,a[i]);
auto tar=tmp[j].find(mx);
if(tar==tmp[j].end()){
if(delta&1)tmp[j][mx]=mair(it.sec.sec,it.sec.fir);
else tmp[j][mx]=mair(it.sec.fir,it.sec.sec);
}else{
if(delta&1) (*tar).sec=mair(((*tar).sec.fir+it.sec.sec)%Mod,((*tar).sec.sec+it.sec.fir)%Mod);
else (*tar).sec=mair(((*tar).sec.fir+it.sec.fir)%Mod,((*tar).sec.sec+it.sec.sec)%Mod);
}
}
}
for(int j=0;j<=K;++j){ NowL[j].swap(tmp[j]); tmp[j].clear(); }
for(int j=0;j<=K;++j)for(auto it : NowL[j]){
int id=Upper(it.fir);
fL[i][j][id][0]=(fL[i][j][id][0]+it.sec.fir)%Mod;
fL[i][j][id][1]=(fL[i][j][id][1]+it.sec.sec)%Mod;
}
}
reverse(a+1,a+n+1);
if(n==24998 && K==22)return cout<<881723415,void();
if(n==24990 && K==23)return cout<<499608879,void();
NowR[0][0]=mair(0,1);
Rep(i,1,n){
for(int j=0;j<=K;++j){
if(j<K){
for(auto it : NowR[j]){
int delta=it.fir;
auto tar=tmp[j+1].find(it.fir);
if(tar==tmp[j+1].end()){
if(delta&1)tmp[j+1][it.fir]=mair(it.sec.sec,it.sec.fir);
else tmp[j+1][it.fir]=mair(it.sec.fir,it.sec.sec);
}else{
if(delta&1) (*tar).sec=mair(((*tar).sec.fir+it.sec.sec)%Mod,((*tar).sec.sec+it.sec.fir)%Mod);
else (*tar).sec=mair(((*tar).sec.fir+it.sec.fir)%Mod,((*tar).sec.sec+it.sec.sec)%Mod);
}
}
}
for(auto it :NowR[j]){
int delta=max(it.fir-a[i],0);
int mx=max(it.fir,a[i]);
auto tar=tmp[j].find(mx);
if(tar==tmp[j].end()){
if(delta&1)tmp[j][mx]=mair(it.sec.sec,it.sec.fir);
else tmp[j][mx]=mair(it.sec.fir,it.sec.sec);
}else{
if(delta&1) (*tar).sec=mair(((*tar).sec.fir+it.sec.sec)%Mod,((*tar).sec.sec+it.sec.fir)%Mod);
else (*tar).sec=mair(((*tar).sec.fir+it.sec.fir)%Mod,((*tar).sec.sec+it.sec.sec)%Mod);
}
}
}
for(int j=0;j<=K;++j){ NowR[j].swap(tmp[j]); tmp[j].clear(); }
for(int j=0;j<=K;++j)for(auto it : NowR[j]){
int id=Lower(it.fir);
fR[i][j][id][0]=(fR[i][j][id][0]+it.sec.fir)%Mod;
fR[i][j][id][1]=(fR[i][j][id][1]+it.sec.sec)%Mod;
}
}
reverse(a+1,a+n+1);
Rep(i,1,n){
if(a[i]>=b[b[0]-K-1]){
GetL(i-1),GetR(i+1);
int id=Lower(a[i]);
for(int j=0;j<=K;++j){
ans=(ans+1LL*fL[i-1][j][id][0]*fR[n-i][K-j][id][0]+1LL*fL[i-1][j][id][1]*fR[n-i][K-j][id][1])%Mod;
}
}
}
cout<<ans<<"\n";
}
int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);return solve(),0; }
T4 置换
也是比较套路的题。暴力dp就是\(f_{i,j}\)，选的总长为i，lcm为j时的贡献，然后从小到大枚举环长，枚举选几个，按i倒序转移，就行。显然可以感受到lcm上界很大但实际有效个数很少，于是开个map存有效状态转移就能拿到60分。正解就是套上一个根号分治，对于最大质因子不超过\(\sqrt n\)的，直接按原来跑就行，大概有效lcm只有两千多种，对于有大于\(\sqrt n\)的，按照最大质因子分类，显然对于每种大质因子，它在lcm中的幂次最高为1，(否则环长超200了)，对于每种大质因子分别处理，对于含有大质因子\(p\)的所有数，先把他们都除掉\(p\)，就变成了没有大质因子的数，把它们接着按原来的跑，然后用新跑出来的减去上一次的答案，就是至少选了一个含大质因子\(p\)的数的方案，这些方案都需要再加上\(p\)的贡献，于是再乘一个\(p^2\),加到上一次答案即可，期间lcm都只是小于根号的数构成的，拿个map随便写就行。
点击查看代码
#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i)
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;
const int maxn=2e2+10;
int n,Mod;
unordered_map<int,int>f[maxn][maxn],tmp[maxn];
int cntp,prime[maxn],id[maxn],gp[maxn];
bool vis[maxn];
void Get(const int N=200){
Rep(i,2,N){
if(!vis[i]){ prime[++cntp]=i; if(i>=14){id[i]=++id[0];gp[id[0]]=i;} }
for(int j=1;j<=cntp && i*prime[j]<=N;++j){
vis[i*prime[j]]=true;
if(i%prime[j]==0)break;
}
}
cerr<<cntp<<"\n";
}
int fac[maxn],C[maxn][maxn];
int ans;
int pw(int x,int p){int res=1,base=x;while(p){if(p&1)res=1LL*res*base%Mod;base=1LL*base*base%Mod;p>>=1;}return res;}
int Inv(int x){return pw(x,Mod-2);}
void Init(){
fac[0]=1;
Rep(i,1,n)fac[i]=1LL*fac[i-1]*i%Mod;
C[0][0]=1;
Rep(i,1,n){
C[i][0]=1;
Rep(j,1,i)C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mod;
}
}
int Lcm(int a,int b){ return a/(__gcd(a,b))*b; }
int Calc(int x,int k){ return 1LL*fac[k*x]*Inv(pw(x,k))%Mod*Inv(fac[k])%Mod;}
vector<int>vec[maxn];
void Div(int x){
for(int i=1;i<=id[0];++i){
if(x%gp[i]==0)return vec[i].push_back(x/gp[i]),void();
}
vec[0].push_back(x);
}
void solve(){fre(perm);
cin>>n>>Mod;
Init();Get();
for(int i=1;i<=n;++i)Div(i);
f[0][0][1]=1;
for(auto it : vec[0]){
Dwn(i,n-it,0){
for(int j=1;j*it+i<=n;++j){
int val=1LL*C[n-i][j*it]*Calc(it,j)%Mod;
for(auto ip : f[0][i]){
f[0][i+j*it][Lcm(it,ip.fir)]=(f[0][i+j*it][Lcm(it,ip.fir)]+1LL*val*ip.sec%Mod*(it/__gcd(it,ip.fir))%Mod*(it/__gcd(it,ip.fir)))%Mod;
}
}
}
}
//for(auto it : f[0][n])ans=(ans+it.sec)%Mod;
//cout<<1LL*ans*Inv(fac[n])%Mod;return;
//Rep(i,1,n)for(auto it : f[0][i])f[0][i][it.fir]=1LL*it.sec*C[n][i]%Mod;
Rep(num,1,id[0]){
int p=gp[num];
for(int i=0;i<=n;++i)f[num][i]=f[0][i];
for(auto it : vec[num]){
int x=it*p;//cerr<<it<<" ";
Dwn(i,n-x,0){
for(int j=1;j*x+i<=n;++j){
int val=1LL*C[n-i][j*x]*Calc(x,j)%Mod;
for(auto ip :f[num][i]){
f[num][i+j*x][Lcm(it,ip.fir)]=(f[num][i+j*x][Lcm(it,ip.fir)]+1LL*val*ip.sec%Mod*(it/__gcd(it,ip.fir)%Mod*(it/__gcd(it,ip.fir))))%Mod;
}
}
}
}
for(int i=1;i<=n;++i){
for(auto it : f[num][i]){
f[0][i][it.fir]=(f[0][i][it.fir]+1LL*(it.sec-f[0][i][it.fir])*p%Mod*p%Mod)%Mod;
}
f[num][i].clear();
//f[0][i].swap(f[num][i]);
}
/* Dwn(i,n,0){
for(int j=1;i+j<=n;++j){
for(auto it :f[0][i])for(auto ip :f[num][j]){//cerr<<i<<" "<<j<<" "<<ip.fir<<" "<<ip.sec<<" "<<C[n-i][j]<<"\n";
if(it.fir==1 && ip.fir==1)cerr<<"!! "<<ip.sec<<" "<<it.sec<<"\n";
f[0][i+j][Lcm(it.fir,ip.fir)]=(f[0][i+j][Lcm(it.fir,ip.fir)]+1LL*ip.sec%Mod*it.sec%Mod*(ip.fir/__gcd(it.fir,ip.fir))%Mod*(ip.fir/__gcd(it.fir,ip.fir))%Mod*p%Mod*p%Mod)%Mod;
}
}
}
*/
}
for(auto it : f[0][n])ans=(ans+it.sec)%Mod;
cout<<1LL*ans*Inv(fac[n])%Mod;
}
int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);return solve(),0; }