T1
对于每一个点 \(u\) ，计算点权最大的三个点，满足 \(dis(u,v)\le k+1,dis(1,v)\le k+1\) 。
然后枚举 \(B,C\) ,\(3^2\) 枚举即可。复杂度 \(O(n^2)\) 。
考场代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool di[2510][2510];
int n,m,K;
int head[2510],to[20100],nxt[20100],c;
void add(int u,int v){
to[++c]=v,nxt[c]=head[u],head[u]=c;
}
queue<int>q;
int d[2510];
ll a[2510];
int mx[2510][3];
int main(){
freopen("holiday.in","r",stdin);
freopen("holiday.out","w",stdout);
scanf("%d%d%d",&n,&m,&K);
for(int i=2;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
for(int s=1;s<=n;s++){
memset(d,0,sizeof(d));
d[s]=1;
while(!q.empty())q.pop();
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
di[s][u]=1;
if(d[u]-1==K+1)continue;
for(int i=head[u];i;i=nxt[i])if(!d[to[i]])
d[to[i]]=d[u]+1,q.push(to[i]);
}
}
for(int i=2;i<=n;i++){
for(int j=1;j<=n;j++)if(i!=j&&di[i][j]&&di[j][1]){
for(int k=0;k<3;k++)if(a[j]>a[mx[i][k]]){
for(int k2=2;k2>k;k2--)mx[i][k2]=mx[i][k2-1];
mx[i][k]=j;break;
}
}
}
ll ans=0;
for(int i=2;i<=n;i++)for(int j=i+1;j<=n;j++)if(di[i][j]){
for(int k=0;k<3;k++)if(mx[i][k])
for(int k2=0;k2<3;k2++)if(mx[j][k2]){
int A=mx[i][k],B=i,C=j,D=mx[j][k2];
if(A!=D&&A!=C&&B!=D)
ans=max(ans,a[A]+a[B]+a[C]+a[D]);
}
}
return printf("%lld",ans),0;
}
T2
RMQ ，计算区间正/负数最大/小值以及是否有 \(0\) ，\(5^2\) 枚举即可，复杂度 \(O(n\log n)\)
考场代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,q;
ll a[2][101000];
const ll I=2e9,II=2e18;
struct qq{
ll mi0,mi1,mx0,mx1;
bool yk;
};
qq operator + (const qq &e,const qq &b){
qq c;
c.mi0=min(e.mi0,b.mi0);
c.mi1=min(e.mi1,b.mi1);
c.mx0=max(e.mx0,b.mx0);
c.mx1=max(e.mx1,b.mx1);
c.yk=e.yk|b.yk;
return c;
}
struct SGT{
qq t[401000];
inline void build(int ty,int p,int l,int r){
if(l==r){
ll z=a[ty][l];
t[p].yk=(z==0);
if(z<0)t[p].mi0=t[p].mx0=z;
else t[p].mi0=I,t[p].mx0=-I;
if(z>0)t[p].mi1=t[p].mx1=z;
else t[p].mi1=I,t[p].mx1=-I;
return;
}
int mid=(l+r)>>1;
build(ty,p<<1,l,mid),build(ty,p<<1|1,mid+1,r);
t[p]=t[p<<1]+t[p<<1|1];
}
inline qq ask(int p,int l,int r,int x,int y){
if(x<=l&&r<=y)return t[p];
int mid=(l+r)>>1;
if(y<=mid)return ask(p<<1,l,mid,x,y);
if(x>mid)return ask(p<<1|1,mid+1,r,x,y);
return ask(p<<1,l,mid,x,y)+ask(p<<1|1,mid+1,r,x,y);
}
}T[2];
vector<ll>cl (qq e){
vector<ll>b;
if(e.yk)b.push_back(0);
if(e.mi0!=I)b.push_back(e.mi0);
if(e.mi1!=I)b.push_back(e.mi1);
if(e.mx0!=-I)b.push_back(e.mx0);
if(e.mx1!=-I)b.push_back(e.mx1);
return b;
}
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)scanf("%lld",&a[0][i]);
for(int i=1;i<=m;i++)scanf("%lld",&a[1][i]);
T[0].build(0,1,1,n),T[1].build(1,1,1,m);
for(int i=1,l1,r1,l2,r2;i<=q;i++){
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
qq e=T[0].ask(1,1,n,l1,r1),b=T[1].ask(1,1,m,l2,r2);
vector<ll>x,y;
x=cl(e),y=cl(b);
ll ans=-II;
for(ll j:x){
ll now=II;
for(ll k:y)now=min(now,j*k);
ans=max(ans,now);
}
printf("%lld\n",ans);
}
return 0;
}
T3
xor-hashing 。
对每一个点随机赋一个值，维护所有边 \((u,v)\) 的 \(a_u\) 异或和即可。
发现条件等价于边数为 \(n\) ，以及异或和为所有 \(a_i\) 的异或和。
发现操作不难维护，复杂度 \(O(n+m+q)\) 。
考场代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,sz[500100],su[501000];
ll a[501000],ot[500100],on[501000];
ll bigrand(){int A=rand(),B=rand();return ((1ll*A)<<30)^(1ll*B);}
int main(){
freopen("galaxy.in","r",stdin);
freopen("galaxy.out","w",stdout);
srand(time(0));
scanf("%d%d",&n,&m);
ll all=0;
for(int i=1;i<=n;i++)a[i]=bigrand(),all^=a[i];
int sum=m;ll al=0;
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
al^=a[u],ot[v]^=a[u],on[v]^=a[u],sz[v]++,su[v]++;
}
int q;scanf("%d",&q);
for(int i=1,op,x,y;i<=q;i++){
scanf("%d%d",&op,&x);
if(op==1){
scanf("%d",&y);
on[y]^=a[x],al^=a[x];
su[y]--,sum--;
}
if(op==3){
scanf("%d",&y);
on[y]^=a[x],al^=a[x];
su[y]++,sum++;
}
if(op==2){
al^=on[x],on[x]=0;
sum-=su[x],su[x]=0;
}
if(op==4){
al^=on[x],on[x]=ot[x],al^=on[x];
sum+=sz[x]-su[x],su[x]=sz[x];
}
if(sum==n&&all==al)printf("YES\n");
else printf("NO\n");
}
return 0;
}
T4
倍增，矩阵维护 dp ，套路题。
考场代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,Q,K;
ll a[201000];
vector<int>g[201000];
int f[201000][20],d[201000];
ll ds[201000];
void dfs(int x){
for(int v:g[x])if(f[x][0]!=v){
f[v][0]=x,d[v]=d[x]+1;
ds[v]=ds[x]+a[v];
for(int i=1;i<20;i++)f[v][i]=f[f[v][i-1]][i-1];
dfs(v);
}
}
int lca(int u,int v){
if(d[u]<d[v])swap(u,v);int a=d[u]-d[v];
for(int i=19;i>=0;i--)if((a>>i)&1)u=f[u][i];
if(u==v)return u;
for(int i=19;i>=0;i--)if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
return f[u][0];
}
void pts16(){
for(int u,v,i=1;i<=Q;i++){
scanf("%d%d",&u,&v);int lc=lca(u,v);
printf("%lld\n",ds[u]+ds[v]-ds[lc]-ds[f[lc][0]]);
}
}
const ll I=1e18;
struct qq{
ll a[3][3];
}w1[201000][20],w2[201000][20];
void cl(qq &x){
for(int i=0;i<K;i++)for(int j=0;j<K;j++)x.a[i][j]=I;
}
qq mul(qq a,qq b){
qq c;cl(c);
for(int k=0;k<K;k++)for(int i=0;i<K;i++)for(int j=0;j<K;j++)
c.a[i][j]=min(c.a[i][j],a.a[i][k]+b.a[k][j]);
return c;
}
int id[201000][3][3];
ll val[201000][3][3];
ll wW[201000][3];
ll ex1(int x,int v,int d){
if(id[x][d][0]!=v)return val[x][d][0];
return val[x][d][1];
}
ll ex2(int x,int v1,int v2,int d){
if(id[x][d][0]!=v1&&id[x][d][0]!=v2)return val[x][d][0];
if(id[x][d][1]!=v1&&id[x][d][1]!=v2)return val[x][d][1];
return val[x][d][2];
}
void dfs2(int x){
val[x][0][0]=a[x],id[x][0][0]=x;
for(int v:g[x])if(v!=f[x][0]){
dfs2(v);
for(int i=1;i<K;i++){
ll os=val[v][i-1][0];
for(int j=0;j<3;j++)if(!id[x][i][j]||os<val[x][i][j]){
for(int k=2;k>j;k--)id[x][i][k]=id[x][i][k-1],val[x][i][k]=val[x][i][k-1];
val[x][i][j]=os,id[x][i][j]=v;
break;
}
}
}
if(f[x][0]){
wW[x][1]=a[f[x][0]];
wW[x][2]=ex1(f[x][0],x,1);
if(f[x][1])wW[x][2]=min(wW[x][2],a[f[x][1]]);
}
}
void dfs3(int x){
for(int v:g[x])if(v!=f[x][0]){
cl(w1[v][0]);
for(int i=0;i<K;i++)for(int j=0;j<K;j++)if(i+j+1<=K)
w1[v][0].a[i][j]=min(w1[v][0].a[i][j],ex1(x,v,j));
for(int i=0;i+1<K;i++)w1[v][0].a[i][i+1]=0;
w2[v][0]=w1[v][0];
for(int i=1;i<20;i++)if(f[v][i])w1[v][i]=mul(w1[v][i-1],w1[f[v][i-1]][i-1]),w2[v][i]=mul(w2[f[v][i-1]][i-1],w2[v][i-1]);
dfs3(v);
}
}
void pts84(){
dfs2(1);dfs3(1);
for(int u,v,ee=1;ee<=Q;ee++){
scanf("%d%d",&u,&v);
if(d[u]<d[v])swap(u,v);
int lc=lca(u,v);
qq now;cl(now);now.a[0][0]=a[u];
if(lc==v){
int kb=d[u]-d[v]-1,o=u;
for(int j=19;j>=0;j--)if((kb>>j)&1)
now=mul(now,w1[o][j]),o=f[o][j];
}
else{
int o=u,kb=d[u]-d[lc]-1;
for(int j=19;j>=0;j--)if((kb>>j)&1)
now=mul(now,w1[o][j]),o=f[o][j];
int ou=o;
o=v,kb=d[v]-d[lc]-1;
qq p2;bool az=0;
for(int j=19;j>=0;j--)if((kb>>j)&1){
if(!az)p2=w2[o][j],az=1;
else p2=mul(w2[o][j],p2);
o=f[o][j];
}
if(!az){
cl(p2);
for(int i=0;i<K;i++)p2.a[i][i]=0;
}
o=v,kb=d[v]-d[lc]-1;
for(int j=19;j>=0;j--)if((kb>>j)&1)o=f[o][j];
int ov=o;
ll r[3]={a[lc],I,I};
for(int i=1;i<K;i++)r[i]=min(ex2(lc,ou,ov,i),wW[lc][i]);
qq ks;cl(ks);
for(int i=0;i+1<K;i++)ks.a[i][i+1]=0;
for(int i=0;i<K;i++)for(int j=0;j<K;j++)if(i+j+1<=K)
ks.a[i][j]=min(ks.a[i][j],r[j]);
now=mul(now,ks);
now=mul(now,p2);
}
ll ans=I;
for(int i=0;i<K;i++)ans=min(ans,now.a[0][i]);
printf("%lld\n",ans+a[v]);
}
}
int main(){
freopen("transmit.in","r",stdin);
freopen("transmit.out","w",stdout);
scanf("%d%d%d",&n,&Q,&K);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(int u,v,i=1;i<n;i++){
scanf("%d%d",&u,&v);
g[u].push_back(v),g[v].push_back(u);
}
for(int i=1;i<=n;i++)for(int j=0;j<3;j++)for(int k=0;k<3;k++)val[i][j][k]=I;
for(int i=1;i<=n;i++)for(int j=0;j<3;j++)wW[i][j]=I;
ds[1]=a[1];dfs(1);
if(K==1)pts16();
else pts84();
return 0;
}