2024.10.05 刷题记录
P7597 「EZEC-8」猜树 加强版
不难发现 \(u\) 的儿子的条件是在 \(u\) 的子树内且深度比 \(u\) 恰好大 \(1\)。
每次询问子树内的所有节点深度或许可以解决此题，但询问次数达到了 \(n^2\)。
在 \(u\) 的子树内，如果知道所属其他儿子的子树的节点，知道属于 \(u\) 子树的节点，那么可以推出剩下最后一个儿子所属子树的节点。
借用树链剖分的思想，不难发现最后一个儿子是重儿子一定是最优的。
这里可以 rand 一个 \(u\) 子树内的节点，不妨假设它属于 \(u\) 的重儿子的子树，然后对 \(u\) 的儿子依次询问距离，找出 \(u\) 的重儿子。
知道重儿子后不难找出 \(u\) 的其他节点所属的儿子的子树。
#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
int n;
int siz[maxn],hso[maxn],sontree[maxn][maxn],fa[maxn],dep[maxn];
bool vis[maxn];
inline void dfs(int u)
{
if(!siz[u]) return ;
int tmp=sontree[u][rand()%siz[u]+1];
random_shuffle(sontree[u]+1,sontree[u]+1+siz[u]);
for(int i=1;i<=siz[u];i++)
{
int v=sontree[u][i];
if(dep[v]!=dep[u]+1) continue;
int dis=0;
if(tmp!=v) printf("? 1 %d %d\n",v,tmp),fflush(stdout),scanf("%d",&dis);
if(dis==dep[tmp]-dep[v])
{
hso[u]=v;
break;
}
}
memset(vis,0,sizeof(vis));
for(int i=1;i<=siz[u];i++)
{
int v=sontree[u][i];
if(dep[v]==dep[u]+1&&v!=hso[u])
{
printf("? 2 %d\n",v);fflush(stdout);
scanf("%d",&siz[v]);siz[v]--;
int cnt=0;
for(int j=1;j<=siz[v]+1;j++)
{
int tmp;
scanf("%d",&tmp);vis[tmp]=true;
if(tmp==v) continue;
sontree[v][++cnt]=tmp;
}
}
}
for(int i=1;i<=siz[u];i++)
{
int v=sontree[u][i];
if(!vis[v]&&v!=hso[u]) sontree[hso[u]][++siz[hso[u]]]=v;
}
for(int i=1;i<=siz[u];i++)
{
int v=sontree[u][i];
if(dep[v]==dep[u]+1)
{
fa[v]=u;
dfs(v);
}
}
}
int main()
{
srand(time(0));
scanf("%d",&n);
for(int i=2;i<=n;i++)
{
sontree[1][++siz[1]]=i;
printf("? 1 1 %d\n",i);fflush(stdout);
scanf("%d",&dep[i]);
}
dfs(1);
printf("! ");
for(int i=2;i<=n;i++) printf("%d ",fa[i]);
puts("");fflush(stdout);
}
P3469 POI2008 BLO-Blockade
线段树分治板题，线段树的区间表示这区间内节点删除的情况下都有的边，直接线段树分治即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
const int maxn=500005;
struct Edge{int u,v;}E[maxn];
int n,m;
ll cnt;
ll ans[maxn];
namespace linetree
{
#define lch(p) p*2
#define rch(p) p*2+1
vector<int>ts[maxn*4];
int f[maxn],sz[maxn];
stack<pii>rf,rsz;
stack<ll>rcnt;
inline void init(){for(int i=1;i<=n;i++) f[i]=i,sz[i]=1;}
inline int fr(int u){return f[u]==u?u:fr(f[u]);}
inline void merge(int u,int v)
{
if(sz[u]>sz[v]) swap(u,v);
rcnt.push(cnt);
cnt-=1ll*sz[v]*sz[u];
rf.push({u,f[u]});
f[u]=v;
rsz.push({v,sz[v]});
sz[v]+=sz[u];
}
inline void un_do()
{
sz[rsz.top().fi]=rsz.top().se;
f[rf.top().fi]=rf.top().se;
cnt=rcnt.top();
rsz.pop(),rf.pop(),rcnt.pop();
}
inline void insert(int p,int l,int r,int lx,int rx,int v)
{
if(rx<lx) return ;
if(r<lx||l>rx) return ;
if(lx<=l&&r<=rx) {ts[p].push_back(v);return ;}
int mid=(l+r)>>1;
insert(lch(p),l,mid,lx,rx,v),insert(rch(p),mid+1,r,lx,rx,v);
}
inline void solve(int p,int l,int r)
{
int level=rf.size();
for(auto i:ts[p])
{
int u=E[i].u,v=E[i].v;
int fu=fr(u),fv=fr(v);
if(fu==fv) continue;
merge(fu,fv);
}
if(l==r) ans[l]=cnt;
else
{
int mid=(l+r)>>1;
solve(lch(p),l,mid),solve(rch(p),mid+1,r);
}
while(level<rf.size()) un_do();
}
}
int main()
{
scanf("%d%d",&n,&m);cnt=1ll*n*(n-1)/2;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&E[i].u,&E[i].v);
if(E[i].u>E[i].v) swap(E[i].u,E[i].v);
linetree::insert(1,1,n,1,E[i].u-1,i);
linetree::insert(1,1,n,E[i].u+1,E[i].v-1,i);
linetree::insert(1,1,n,E[i].v+1,n,i);
}
linetree::init();
linetree::solve(1,1,n);
for(int i=1;i<=n;i++) printf("%lld\n",ans[i]*2);
}
P4630 APIO2018 铁人两项
看见两点间路径统计点数，考虑转为圆方树。
发现两点间经过的圆点数加上经过的方点所连接圆点数（去重，不算首尾），就是两点间可以选择的转换点个数。
将圆点附点权 \(-1\)，方点附点权周围圆点的个数，统计所有点对间权值和就是总的答案。
所有点对间权值和并不难统计，本题即可在 \(O(n)\) 的时间内解决。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+5,maxm=4e5+5;
struct Edge
{
int tot;
int head[maxn*2];
struct edgenode{int to,nxt;}edge[maxn*10];
void add(int x,int y)
{
tot++;
edge[tot].to=y;
edge[tot].nxt=head[x];
head[x]=tot;
}
}T,G;
int n,m,tot,cok,sfn;
int tx[maxn*2];
ll ans;
int dfn[maxn],low[maxn];
stack<int>stk;
void tarjin(int u)
{
sfn++;
dfn[u]=low[u]=++cok;
stk.push(u);
for(int i=G.head[u];i;i=G.edge[i].nxt)
{
int v=G.edge[i].to;
if(!dfn[v])
{
tarjin(v);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
tot++;
tx[tot]++;
T.add(tot,u);
T.add(u,tot);
int x=0;
do{
x=stk.top();
tx[tot]++;
T.add(x,tot),T.add(tot,x);
stk.pop();
}while(x!=v);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
int siz[maxn*2],w[maxn*2];
void dfs(int u,int fa)
{
if(u<=n) w[u]=-1;
else w[u]=tx[u];
siz[u]=(u<=n);
for(int i=T.head[u];i;i=T.edge[i].nxt)
{
int v=T.edge[i].to;
if(v==fa) continue;
dfs(v,u);
ans+=2ll*siz[u]*siz[v]*w[u];
siz[u]+=siz[v];
}
ans+=2ll*(sfn-siz[u])*siz[u]*w[u];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
G.add(x,y),G.add(y,x);
}
tot=n;
for(int i=1;i<=n;i++) if(!dfn[i])
{
sfn=0;
tarjin(i);
dfs(i,0);
}
printf("%lld",ans);
}
P3273 SCOI2011 棘手的操作
并查集加 set，每个 set 维护并查集内的最大值，每个并查集同时维护一个 \(tag\) 表示该并查集内共同加的值。
对于全局最大值，每个并查集提供一个最大值并额外维护一个全局的 set 即可。
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int maxn=3e5+5;
int n,al;
int f[maxn],a[maxn],tag[maxn];
multiset<pii>s[maxn];
inline int read()
{
int n=0,f=1;
char c=getchar();
for(;c!='-'&&(c<'0'||c>'9');c=getchar());
if(c=='-') c=getchar(),f=-1;
for(;c>='0'&&c<='9';c=getchar()) n=(n<<1)+(n<<3)+c-'0';
return n*f;
}
inline int fr(int x){return f[x]==x?x:f[x]=fr(f[x]);}
inline void merge(int fx,int fy)
{
if(s[fx].size()>s[fy].size()) swap(fx,fy);
multiset<pii>::iterator it=s[fx].begin();
s[0].erase({s[fx].rbegin()->fi+tag[fx],fx});
s[0].erase({s[fy].rbegin()->fi+tag[fy],fy});
for(;it!=s[fx].end();it++)
{
a[(*it).se]=(*it).fi-tag[fy]+tag[fx];
s[fy].insert({(*it).fi-tag[fy]+tag[fx],(*it).se});
}
s[0].insert({s[fy].rbegin()->fi+tag[fy],fy});
f[fx]=fy;
s[fx].clear();tag[fx]=0;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
// scanf("%d",&a[i]);
a[i]=read();
f[i]=i,s[i].insert({a[i],i});
s[0].insert({a[i],i});
}
int _;
scanf("%d",&_);
for(int k=1;k<=_;k++)
{
char ch[3];int x,y;
cin>>ch;
if(ch[0]=='U')
{
scanf("%d%d",&x,&y);
int fx=fr(x),fy=fr(y);
if(fx==fy) continue;
merge(fx,fy);
}
else if(ch[0]=='A'&&ch[1]=='1')
{
scanf("%d%d",&x,&y);
int fx=fr(x);
s[0].erase({s[fx].rbegin()->fi+tag[fx],fx});s[fx].erase({a[x],x});
a[x]+=y;
s[fx].insert({a[x],x});s[0].insert({s[fx].rbegin()->fi+tag[fx],fx});
}
else if(ch[0]=='A'&&ch[1]=='2')
{
scanf("%d%d",&x,&y);
int fx=fr(x);
s[0].erase({s[fx].rbegin()->fi+tag[fx],fx});
tag[fx]+=y;
s[0].insert({s[fx].rbegin()->fi+tag[fx],fx});
}
else if(ch[0]=='A'&&ch[1]=='3')
{
scanf("%d",&x);
al+=x;
}
else if(ch[0]=='F'&&ch[1]=='1')
{
scanf("%d",&x);
printf("%d\n",a[x]+tag[fr(x)]+al);
}
else if(ch[0]=='F'&&ch[1]=='2')
{
scanf("%d",&x);
int fx=fr(x);
multiset<pii>::iterator it=s[fx].end();it--;
printf("%d\n",tag[fx]+(*it).fi+al);
}
else if(ch[0]=='F'&&ch[1]=='3')
{
printf("%d\n",s[0].rbegin()->fi+al);
}
}
}
P2825 HEOI2016/TJOI2016 游戏
考虑没有硬石头，每一行作为二分图的左部点，列作为右部点，如果可以在一个位置放炸弹，就把对应的列和行连一条边，做最大匹配即可。
对于一行中的硬石头，我们可以把这一行拆成两行来建图，列也做相同操作，行列有相交的部分就建边，做最大匹配即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
struct Edge
{
int tot;
int head[maxn];
struct edgenode{int to,nxt;}edge[maxn*2];
inline void add(int x,int y)
{
tot++;
edge[tot].to=y;
edge[tot].nxt=head[x];
head[x]=tot;
}
}G;
int n,m,cnt;
int idh[maxn][maxn],idw[maxn][maxn],cur[maxn];
char mp[maxn][maxn];
bool vis[maxn];
inline int dfs(int u)
{
for(int i=G.head[u];i;i=G.edge[i].nxt)
{
int v=G.edge[i].to;
if(vis[v]) continue;
vis[v]=true;
if(!cur[v]||dfs(cur[v]))
{
cur[v]=u;
return 1;
}
}
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>mp[i][j];
for(int i=1;i<=n;i++)
{
cnt++;
for(int j=1;j<=m;j++)
{
if(mp[i][j]=='#') continue;
if(mp[i][j-1]=='#') cnt++;
idh[i][j]=cnt;
}
}
for(int i=1;i<=m;i++)
{
cnt++;
for(int j=1;j<=n;j++)
{
if(mp[j][i]=='#') continue;
if(mp[j-1][i]=='#') cnt++;
idw[j][i]=cnt;
}
}
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(mp[i][j]=='*') G.add(idh[i][j],idw[i][j]);
int ans=0;
for(int i=1;i<=cnt;i++)
{
memset(vis,0,sizeof(vis));
if(dfs(i)) ans++;
}
printf("%d",ans);
}
P4620 SDOI2018 荣誉称号
题解来自：洛谷 P4620 SDOI2018荣誉称号 | ctz's blog
发现需要处理的数据规模较大，但 \(k\) 较小，考虑缩小数据规模。
观察发现：
\[a_{x/2}+a_{x/2/2}+\cdots\equiv 0 \mod m \]当 \(k=2\) 时会出现下面两个式子：
\[a_1+a_2+a_4\equiv 0 \mod m\\ a_2+a_4+a_8\equiv 0 \mod m \]于是有 \(a_1\equiv a_8 \mod m\)。
发现二叉树上第 \(i\) 层与第 \(i+k+1\) 层节点同余。
只需要使得前 \(k+1\) 层余数为 \(0\)，后面的层数自然满足余数为 \(0\)，这样 dp 考虑的点数降为 \(2^{k+1}\) 个。
设 \(f[i][j]\) 表示 \(i\) 向下到达 \(k+1\) 层的和取模后为 \(j\) 的最小代价。（兄弟节点的取值一定是同余的，那么每一层的节点都是同余的）
可以预处理一个 \(v(i,j)\) 表示将点 \(i\) 及其同余的点改为 \(j\) 的代价。
\[f[i][j]=\min(f[\frac{i}{2}][k]+f[\frac{i}{2}+1][k]+v(i,j-k+m)) \]从 \(2^{k+1}\) 开始倒序 dp，答案为 \(f[1][0]\)，单次复杂度 \(O(n+m^22^{k+1})\)。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e7+5,maxm=3005;
int n,m,k;
int a[maxn],b[maxn],id[maxn];
ll v[maxm][205],f[maxm][205],tmpv[maxm][205];
unsigned int SA, SB, SC;int p, A, B;
unsigned int rng61(){
SA ^= SA << 16;
SA ^= SA >> 5;
SA ^= SA << 1;
unsigned int t = SA;
SA = SB;
SB = SC;
SC ^= t ^ SA;
return SC;
}
void gen(){
scanf("%d%d%d%d%u%u%u%d%d", &n, &k, &m, &p, &SA, &SB, &SC, &A, &B);
for(int i = 1; i <= p; i++)scanf("%d%d", &a[i], &b[i]);
for(int i = p + 1; i <= n; i++){
a[i] = rng61() % A + 1;
b[i] = rng61() % B + 1;
}
}
int main()
{
int _;
scanf("%d",&_);
while(_--)
{
gen();k++;
memset(v,0,sizeof(v));memset(tmpv,0,sizeof(tmpv));memset(f,0x3f,sizeof(f));
for(int i=1;i<1<<k;i++) tmpv[id[i]=i][a[i]%=m]=b[i];
for(int i=1<<k;i<=n;i++) tmpv[id[i]=id[i/(1<<k)]][a[i]%=m]+=b[i];
for(int i=1;i<1<<k;i++)
{
for(int j=0;j<m;j++)
{
for(int k=0;k<j;k++) v[i][j]+=tmpv[i][k]*(j-k);
for(int k=j+1;k<m;k++) v[i][j]+=tmpv[i][k]*(j+m-k);
}
}
for(int i=1<<(k-1);i<1<<k;i++) for(int j=0;j<m;j++) f[i][j]=v[i][j];
for(int i=(1<<(k-1))-1;i;i--)
{
for(int j=0;j<m;j++)
{
for(int k=0;k<m;k++)
f[i][j]=min(f[i][j],f[i<<1][k]+f[i<<1|1][k]+v[i][(j-k+m)%m]);
}
}
printf("%lld\n",f[1][0]);
}
}