T1 最短路（P2966 [USACO09DEC] Cow Toll Paths G）
考察 Floyd 的理解，Floyd 本身是 \(O(n^3)\) 的空间复杂度。\(f_{k,i,j}\) 表示只经过前 \(k\) 个点（不包含 \(i,j\)），从 \(i\) 到 \(j\) 的最短距离。
发现这个 \(k\) 的顺序是没有任何影响的。
所以以点权的顺序枚举 \(k\)，这样保证算的路径中的最大值都是已知的，直接 Floyd 就行了。
点击查看代码
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=310;
int n,f[N][N],m,w[N],q,dis[N][N];
std::pair<int,int>temp[N];
signed main(){
// freopen("path.in","r",stdin);freopen("path.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read(),m=read();q=read();
memset(f,0x3f,sizeof(f));memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=n;++i)w[i]=temp[i].first=read(),temp[i].second=i,dis[i][i]=0;
for(int i=1;i<=m;++i){
int u=read(),v=read();
dis[u][v]=dis[v][u]=std::min(dis[u][v],read());
}
std::sort(temp+1,temp+n+1);
for(int z=1,k=temp[z].second;z<=n;++z,k=temp[z].second){
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
dis[i][j]=std::min(dis[i][j],dis[i][k]+dis[k][j]),f[i][j]=std::min(f[i][j],dis[i][j]+std::max(std::max(w[i],w[k]),w[j]));
}
for(int i=1;i<=q;++i){
int u=read(),v=read();
std::cout<<(f[u][v]==f[0][0]?-1:f[u][v])<<'\n';
}
}
T2 方格取数（P3474 [POI2008] KUP-Plot purchase）
先特判不可能合法的点和一定合法的点，然后就只剩下权值在 \([1,k-1]\) 中的点，这时考虑找到一个子矩阵的权值和大于 \(k\)，则此时一定有解。
- 考虑这个子矩阵的从上到下每一行，如果这一行的权值和大于 \(k\)，那么答案属于这一行，因为这时的所有点权小于 \(k\)，所以可以一个一个删使这一行达到合法范围。
- 如果这一行权值小于 \(k\)，删去这一行后继续往下找。以此类推，直到剩下的矩阵权值和在合法范围中。
具体来说，处理出每一个点能向上扩展的最大高度，然后单调栈找最大矩阵即可，因为权值是正整数，所以这样一定可以扫描到权值和最大的矩阵，找到之后就执行上述操作即可。
点击查看代码
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=2e3+10;
int n,k,a[N][N],s[N][N],l[N][N],q[N],head,tail,wi[N],sum[N][N];
inline int ask(int i,int j,int x,int y){
return sum[x][y]-sum[i-1][y]-sum[x][j-1]+sum[i-1][j-1];
}
signed main(){
// freopen("matrix.in","r",stdin);freopen("matrix.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
k=read(),n=read();
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){
a[i][j]=read();
if(a[i][j]>=k&&a[i][j]<=2*k){std::cout<<j<<' '<<i<<' '<<j<<' '<<i<<'\n';exit(0);}
if(a[i][j]<k){
l[i][j]=l[i-1][j]+1;
s[i][j]=1;
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)
sum[i][j]=a[i][j]+sum[i][j-1];
for(int j=1;j<=n;++j)
sum[i][j]+=sum[i-1][j];
}
int res=0;
int x=0,y=0,w=0,c=0,pd=0;
for(int i=1;i<=n;++i){
for(int i=1;i<=n+1;++i)wi[i]=0;
head=0,tail=0;
for(int j=1;j<=n+1;++j){
int p=l[i][j],zc=0;
while(p<q[tail]){
zc+=wi[tail];
x=i,y=j-1;w=i-q[tail--]+1,c=j-zc;
if(ask(w,c,x,y)>=k){
pd=1;
res=ask(w,c,x,y);break;
}
}
if(pd)break;
q[++tail]=p;wi[tail]=zc+1;
}
if(pd)break;
}
if(res<k){std::cout<<"NIE\n";exit(0);}
if(res>=k&&res<=k*2){std::cout<<c<<' '<<w<<' '<<y<<' '<<x<<'\n';exit(0);}
for(int i=w;i<=x;++i){
if(res>=k&&res<=k*2){std::cout<<c<<' '<<i<<' '<<y<<' '<<x<<'\n';exit(0);}
int zc=ask(i,c,i,y);
if(zc>=k){
for(int j=c;j<=y;++j){
zc=ask(i,j,i,y);
if(zc>=k&&zc<=2*k){std::cout<<j<<' '<<i<<' '<<y<<' '<<i<<'\n';exit(0);}
}
}
res-=zc;
}
}
T3 数组（CF1114F Please, another Queries on Array? ）
欧拉函数的求法 \(\phi(n)=n\prod_{i=1}^{cnt}\frac{p_i-1}{p_i}\)，\(p\) 表示 \(n\) 的质因数。
知道这个之后就是线段树板题了，维护区间乘积和区间质因数状态即可。
注意到 \(300\) 之内只有 \(63\) 个质因数，long long 直接就能存下。
点击查看代码
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=4e5+10,mod=1e9+7;
int n,a[N],as[N],p[N],tot,ny[N];
struct TREE{int ans,s,tag1,tag2,l,r;}t[N<<2];
bool vis[N];
inline void init(){
int MAXN=305;
for(int i=2;i<=MAXN;++i){
if(!vis[i])p[++tot]=i,as[i]|=(1ll<<tot-1);
for(int j=1;j<=tot&&p[j]*i<=MAXN;++j){
int x=p[j]*i;
vis[x]=1;as[x]=as[p[j]]|as[i];
if(i%p[j]==0)break;
}
}
}
inline int qpow(int a,int b){
int res=1;
for(;b;b>>=1,a=a*a%mod)if(b&1)res=res*a%mod;
return res;
}
inline void update(int p){t[p].ans=t[p<<1].ans*t[p<<1|1].ans%mod;t[p].s=t[p<<1].s|t[p<<1|1].s;}
inline void pushdown(int p){
int ls=p<<1,rs=p<<1|1;
int zc=qpow(t[p].tag1,t[ls].r-t[ls].l+1);
t[ls].ans=t[ls].ans*zc%mod;
t[ls].s=t[ls].s|t[p].tag2;
t[ls].tag1=t[ls].tag1*t[p].tag1%mod;
t[ls].tag2=t[ls].tag2|t[p].tag2;
zc=qpow(t[p].tag1,t[rs].r-t[rs].l+1);
t[rs].ans=t[rs].ans*zc%mod;
t[rs].s=t[rs].s|t[p].tag2;
t[rs].tag1=t[rs].tag1*t[p].tag1%mod;
t[rs].tag2=t[rs].tag2|t[p].tag2;
t[p].tag1=1;t[p].tag2=0;
}
inline void build(int p,int l,int r){
t[p].l=l,t[p].r=r;t[p].tag1=1;
if(l==r){t[p]={a[l],as[a[l]],1,0,l,r};return ;}
int mid=l+r>>1;
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
update(p);
}
inline void add(int p,int l,int r,int x,int y,int v){
if(l>=x&&r<=y){
int zc=qpow(v,r-l+1);
t[p].tag1=t[p].tag1*v%mod;
t[p].tag2=t[p].tag2|as[v];
t[p].ans=t[p].ans*zc%mod;
t[p].s|=as[v];
return;
}
pushdown(p);
int mid=l+r>>1;
if(x<=mid)add(p<<1,l,mid,x,y,v);
if(y>mid)add(p<<1|1,mid+1,r,x,y,v);
update(p);
}
inline std::pair<int,int> ask(int p,int l,int r,int x,int y){
if(l>=x&&r<=y){return {t[p].ans,t[p].s};}
pushdown(p);
int mid=l+r>>1,_1=1,_2=0;
if(x<=mid){auto it=ask(p<<1,l,mid,x,y);_1=_1*it.first%mod;_2|=it.second;}
if(y>mid){auto it=ask(p<<1|1,mid+1,r,x,y);_1=_1*it.first%mod,_2|=it.second;}
return {_1,_2};
}
signed main(){
// freopen("array.in","r",stdin);freopen("array.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read();int q=read();
init();
for(int i=1;i<=n;++i)a[i]=read();build(1,1,n);
for(int i=1;i<=tot;++i)ny[i]=qpow(p[i],mod-2);
for(int i=1;i<=q;++i){
char opt[10];
scanf("%s",opt);
int l=read(),r=read();
if(opt[0]=='M')add(1,1,n,l,r,read());
else{
auto it=ask(1,1,n,l,r);
int ans=it.first,s=it.second;
for(int j=1;j<=63;++j){
if(s&(1ll<<j-1)){
ans=ans*(p[j]-1)%mod*ny[j]%mod;
}
}
std::cout<<ans<<'\n';
}
}
}
T4 树（P3591 [POI2015] ODW）
考虑根号分治，处理出每个点的 \(k\le\sqrt n\) 级祖先和前缀值。
对于 \(c\le \sqrt n\)，找出 LCA 后直接树上差分即可，时间复杂度在于求 LCA。
对于 \(c>\sqrt n\)，直接每次跳 \(\sqrt n\) 步来凑 \(c\) 即可，时间复杂度 \(O(\sqrt n)\)。
整个算法的时间复杂度为 \(O(n\sqrt n)\)，和长链剖分一样优秀。
点击查看代码
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=5e4+10,M=250;
int n,w[N],b[N],c[N],st[N][20],dep[N],dis[N][M],f[N][M],dfn[N];
std::vector<int> e[N];
inline void dfs(int u,int fa){
st[u][0]=fa;f[u][1]=fa;
if(u!=1)dis[u][1]=dis[fa][1]+w[u];
for(int i=2;i*i<=n&&i<=dep[u];++i){
f[u][i]=f[f[u][i-1]][1];
dis[u][i]=dis[f[u][i]][i]+w[u];
}
for(int i=1;i<=std::__lg(dep[u]);++i)st[u][i]=st[st[u][i-1]][i-1];
for(int v:e[u])if(v!=fa)dep[v]=dep[u]+1,dfs(v,u);
}
inline int LCA(int u,int v){
if(dep[u]<dep[v])std::swap(u,v);
while(dep[u]>dep[v])u=st[u][std::__lg(dep[u]-dep[v])];
if(v==u)return v;
for(int i=std::__lg(dep[u]);i>=0;--i)
if(st[u][i]!=st[v][i])u=st[u][i],v=st[v][i];
return st[u][0];
}
inline void ask1(int u,int v,int k){
int lca=LCA(u,v),res=0;
if((dep[u]-dep[lca])%k==0)res-=w[lca];
int zc=dep[u]-dep[lca];
zc-=zc%k;
int x=u;
if(zc){
for(int i=std::__lg(zc);i>=0;--i)
if(zc>=(1<<i))zc-=1<<i,x=st[x][i];
}
res+=dis[u][k]-dis[x][k]+w[x];
u=v;
zc=dep[u]-dep[lca];
zc-=zc%k;
x=u;
if(zc){
for(int i=std::__lg(zc);i>=0;--i)
if(zc>=(1<<i))zc-=1<<i,x=st[x][i];
}
res+=dis[u][k]-dis[x][k]+w[x];
std::cout<<res<<'\n';
}
inline void ask2(int u,int v,int k){
int lca=LCA(u,v),res=w[u]+w[v];
int zc=(dep[u]-dep[lca])/k;
if((dep[u]-dep[lca])%k==0)res-=w[lca];
for(int i=1;i<=zc;++i){
int wk=k,x=sqrt(n);
while(wk>=x){
u=f[u][x];
wk-=x;
}
if(wk)u=f[u][wk];
res+=w[u];
}
u=v;
zc=(dep[u]-dep[lca])/k;
for(int i=1;i<=zc;++i){
int wk=k,x=sqrt(n);
while(wk>=x){
u=f[u][x];
wk-=x;
}
if(wk)u=f[u][wk];
res+=w[u];
}
std::cout<<res<<'\n';
}
signed main(){
// freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read();
for(int i=1;i<=n;++i)w[i]=read();
for(int i=1;i<n;++i){int u=read(),v=read();e[u].push_back(v);e[v].push_back(u);}
for(int i=1;i<=n;++i)b[i]=read();
for(int i=1;i<n;++i)c[i]=read();
dfs(1,0);
for(int i=1;i<n;++i){
if(c[i]*c[i]>=n){ask2(b[i],b[i+1],c[i]);}
else ask1(b[i],b[i+1],c[i]);
}
return 0;
}
赛时相当于保龄了，明明 T3 和 T4 一眼就切了，赛时代码小改一下就 A 了，赛时没分，感觉自己总是不能把想到的很迅速地实现，期望得分和实际差得太多，这场期望 350pts，除了 T2 想了想没啥思路，别的都挺一眼的。
赛时策略也唐氏了，先冲的 T4，赛后发现空间炸了，一分没有，改下块长就过了。
T3 没打很不好，T1没判断好也傻逼。
还是得多打比赛，