noip模拟83 solutions
真难，真难，真难，难死我了！！！
所以我啥时候可以\(AK\)一次啊？？？
今天好多自己应该会的但是没有做出来。。。
T1 树上排列
这就是一个可重集哈希大板子题，可是我竟然忘记了！！？？
考场上一直想着要用线段树判重，害，真脑残！。。
所以我莫名其妙的开发了一个序列判重的办法
直接\(set\)记录前驱，线段树维护区间最大前驱是不是在区间内，如果在就有重复的
序列判重
set<int> st[N];
int pre[N];
struct XDS{
#define ls x<<1
#define rs x<<1|1
int mx[N],las[N];
void pushup(int x){
mx[x]=max(mx[ls],mx[rs]);
las[x]=max(las[ls],las[rs]);
return ;
}
void build(int x,int l,int r){
if(l==r){
mx[x]=a[l];las[x]=pre[l];
return ;
}
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(x);return ;
}
void ins(int x,int l,int r,int pos){
if(l==r){
mx[x]=a[l];las[x]=pre[l];
return ;
}
int mid=l+r>>1;
if(pos<=mid)ins(ls,l,mid,pos);
else ins(rs,mid+1,r,pos);
pushup(x);return ;
}
int query_mx(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return mx[x];
int mid=l+r>>1,ret=0;
if(ql<=mid)ret=max(ret,query_mx(ls,l,mid,ql,qr));
if(qr>mid)ret=max(ret,query_mx(rs,mid+1,r,ql,qr));
pushup(x);return ret;;
}
int query_las(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return las[x];
int mid=l+r>>1,ret=0;
if(ql<=mid)ret=max(ret,query_las(ls,l,mid,ql,qr));
if(qr>mid)ret=max(ret,query_las(rs,mid+1,r,ql,qr));
pushup(x);return ret;;
}
#undef ls
#undef rs
}xds;
void spj(){
//cout<<"SB"<<endl;
fo(i,1,n){
if(st[a[i]].begin()!=st[a[i]].end())pre[i]=*st[a[i]].rbegin();
st[a[i]].insert(i);
}
xds.build(1,1,n);
fo(i,1,q){
int tp,x,y;
tp=read();x=read();y=read();
if(tp==1){
if(x>y)swap(x,y);
int mx=xds.query_mx(1,1,n,x,y);
int las=xds.query_las(1,1,n,x,y);
if(mx==y-x+1&&las<x)printf("Yes\n");
else printf("No\n");
}
else {
set<int>::iterator it=st[a[x]].find(x);
if(next(it)!=st[a[x]].end()){
if(it!=st[a[x]].begin())pre[*next(it)]=*prev(it);
else pre[*next(it)]=0;
xds.ins(1,1,n,*next(it));
}
st[a[x]].erase(x);
a[x]=y;st[a[x]].insert(x);pre[x]=0;
it=st[a[x]].find(x);
if(next(it)!=st[a[x]].end()){
pre[*next(it)]=x;
xds.ins(1,1,n,*next(it));
}
if(it!=st[a[x]].begin())pre[x]=*prev(it);
//cout<<pre[3]<<" "<<pre[4]<<" "<<a[3]<<endl;
xds.ins(1,1,n,x);
//cout<<xds.query_las(1,1,n,4,4)<<endl;
}
}
}
正解非常简单，直接树剖+线段树，判断路径上的加和是否等于一个排列的加和就行了
如果怕被卡，可以用两个模数
战神指导：可以直接把每一个数都换掉！
AC_code
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
inline int read(){
int s=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
return s*f;
}
const int N=3e5+5;
const ull bas=131;
int T,n,q,a[N];
int to[N*2],nxt[N*2],head[N],rp;
void add_edg(int x,int y){
to[++rp]=y;
nxt[rp]=head[x];
head[x]=rp;
}
int ans;ull an[N];
int dfn[N],cnt,idf[N];
int fa[N],dep[N];
int son[N],siz[N],top[N];
ull ba[N];
struct XDS{
#define ls x<<1
#define rs x<<1|1
ull hs[N*4];
void pushup(int x){
hs[x]=hs[ls]+hs[rs];
return ;
}
void build(int x,int l,int r){
if(l==r){hs[x]=ba[a[idf[l]]];return ;}
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(x);return ;
}
void ins(int x,int l,int r,int pos){
if(l==r){hs[x]=ba[a[idf[l]]];return ;}
int mid=l+r>>1;
if(pos<=mid)ins(ls,l,mid,pos);
else ins(rs,mid+1,r,pos);
pushup(x);return ;
}
ull query(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return hs[x];
int mid=l+r>>1;ull ret=0;
if(ql<=mid)ret+=query(ls,l,mid,ql,qr);
if(qr>mid)ret+=query(rs,mid+1,r,ql,qr);
pushup(x);return ret;
}
#undef ls
#undef rs
}xds;
void dfs_fi(int x,int f){
siz[x]=1;son[x]=0;
dep[x]=dep[f]+1;fa[x]=f;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==f)continue;
dfs_fi(y,x);
siz[x]+=siz[y];
if(!son[x]||siz[y]>siz[son[x]])son[x]=y;
}
}
void dfs_se(int x,int f){
top[x]=f;dfn[x]=++cnt;idf[cnt]=x;
if(son[x])dfs_se(son[x],f);
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==fa[x]||y==son[x])continue;
dfs_se(y,y);
}
}
bool LCA(int x,int y){
ull ret=0;int len=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ret+=xds.query(1,1,n,dfn[top[x]],dfn[x]);
len+=dep[x]-dep[fa[top[x]]];x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
ret+=xds.query(1,1,n,dfn[y],dfn[x]);
len+=dep[x]-dep[y]+1;
return ret==an[len];
}
signed main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
T=read();
while(T--){
n=read();q=read();rp=0;cnt=0;
ba[0]=1;fo(i,1,n)ba[i]=ba[i-1]*bas,an[i]=an[i-1]+ba[i];
//cout<<an[1]<<" "<<an[2]<<" "<<an[5]<<endl;
fo(i,1,n)head[i]=0;
fo(i,1,n)a[i]=read();
fo(i,1,n-1){
int x,y;x=read();y=read();
add_edg(x,y);add_edg(y,x);
}
dfs_fi(1,0);dfs_se(1,1);
xds.build(1,1,n);
fo(i,1,q){
int tp,x,y;
tp=read();x=read();y=read();
if(tp==1){
if(!x||!y){printf("No\n");continue;}
if(LCA(x,y))printf("Yes\n");
else printf("No\n");
}
else {
a[x]=y;
xds.ins(1,1,n,dfn[x]);
}
}
}
return 0;
}
T2 连任
可撤销并查集？？！
不会，好像还有一个可持久化并查集。。
不会，都不会
所以我就去学习了一下，就是用一个栈记录合并信息，按秩合并，不能路径压缩
到时候直接把所有的合并全都倒出来就好了
还用到线段树分分治，说白了就是在线段树上\(dfs\)
不然的话无法撤销。。
AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
inline int read(){
int s=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
return s*f;
}
const int N=1e5+5;
const int mod=1e9+7;
int ksm(int x,int y){
int ret=1;
while(y){
if(y&1)ret=ret*x%mod;
x=x*x%mod;y>>=1;
}return ret;
}
int n,m,ans[N],tot,res;
map<pair<int,int>,int> mp;
pair<int,int> ys[N];
int bg[N],ed[N];
struct DSU{
int fa[N],siz[N];
pair<int,int> sta[N];
int top;
void init(){
fo(i,1,n)fa[i]=i,siz[i]=1;
top=0;
}
int find(int x){return fa[x]==x?x:find(fa[x]);}
int merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy)return 0;
if(siz[fx]>siz[fy])swap(fx,fy);
fa[fx]=fy;
res=res*ksm(siz[fx],mod-2)%mod*ksm(siz[fy],mod-2)%mod;
siz[fy]+=siz[fx];
res=res*siz[fy]%mod;
sta[++top]=make_pair(fx,fy);
return 1;
}
void cancel(){
fa[sta[top].first]=sta[top].first;
res=res*ksm(siz[sta[top].second],mod-2)%mod;
siz[sta[top].second]-=siz[sta[top].first];
res=res*siz[sta[top].second]%mod*siz[sta[top].first]%mod;
top--;return ;
}
}dsu;
struct XDS{
#define ls x<<1
#define rs x<<1|1
vector<int> vec[N*4];
void ins(int x,int l,int r,int ql,int qr,int v){
if(ql<=l&&r<=qr)return vec[x].push_back(v),void();
int mid=l+r>>1;
if(ql<=mid)ins(ls,l,mid,ql,qr,v);
if(qr>mid)ins(rs,mid+1,r,ql,qr,v);
return ;
}
void dfs(int x,int l,int r){
int num=0;
for(int i:vec[x])num+=dsu.merge(ys[i].first,ys[i].second);
if(l==r){
ans[l]=res;
while(num--)dsu.cancel();
return ;
}
int mid=l+r>>1;
dfs(ls,l,mid);
dfs(rs,mid+1,r);
while(num--)dsu.cancel();
return ;
}
#undef ls
#undef rs
}xds;
signed main(){
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
n=read();m=read();
fo(i,1,m){
int tp,u,v;
tp=read();u=read();v=read();
if(tp==1){
mp[make_pair(u,v)]=++tot;
ys[tot]=make_pair(u,v);
bg[tot]=i;ed[tot]=m;
}
else ed[mp[make_pair(u,v)]]=i-1;
}
dsu.init();
fo(i,1,tot)xds.ins(1,1,m,bg[i],ed[i],i);
res=1;xds.dfs(1,1,m);
fo(i,1,m)printf("%lld\n",ans[i]);
return 0;
}
T3 排列
这我考场上\(CDQ\)打假了..
原因是我有一个可以用\(lower_bound\)求的东西，我用双指针的时候没有卡边界。。
于是发现一个高级东西，三维偏序可以\(\mathcal{O(nlogn)}\)求出来
容斥呗！就这样啦
AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
inline int read(){
int s=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
return s*f;
}
const int N=1e6+5;
const int mod=998244353;
int n,ans;
struct node{int p,q,id;}a[N];
bool com1(node a,node b){return a.id<b.id;}
bool com2(node a,node b){return a.p<b.p;}
bool vis[N];
int pos[N],avl[N],cnt;
int inv[N],g[N];
struct BIT{
int tr[N];
void ins(int x,int v){
for(int i=x;i<=n;i+=(i&-i))tr[i]+=v;
}
int query(int x){
int ret=0;
for(int i=x;i;i-=(i&-i))ret+=tr[i];
return ret;
}
}bit;
signed main(){
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
// cerr<<(sizeof(dp)+sizeof(inv)*20>>20)<<endl;
n=read();
fo(i,1,n)a[i].p=read(),a[i].id=i;
fo(i,1,n){
a[i].q=read();
if(a[i].q!=-1)vis[a[i].q]=true;
}
inv[0]=inv[1]=1;
fo(i,2,n)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
fo(i,1,n)if(!vis[i])avl[++cnt]=i;
int now=1;
fo(i,1,n){
while(avl[now]<i&&now<=cnt)now++;
pos[i]=now;
}
fo(i,1,n){
ans=(ans+bit.query(a[i].p))%mod;
bit.ins(a[i].p,1);
}
fo(i,1,n)bit.ins(a[i].p,-1);
int sum=0,big=0;
fo(i,1,n){
if(a[i].q==-1){
ans=(ans+sum*inv[2])%mod;
ans=(ans+big)%mod;
sum++;
}
else {
ans=(ans+bit.query(a[i].q))%mod;
ans=(ans+(pos[a[i].q]-1)*inv[cnt]%mod*sum)%mod;
big=(big+(cnt-pos[a[i].q]+1)*inv[cnt])%mod;
bit.ins(a[i].q,1);
}
}
fo(i,1,n)if(a[i].q!=-1)bit.ins(a[i].q,-1);
sort(a+1,a+n+1,com2);
sum=0;big=0;
fo(i,1,n){
if(a[i].q==-1){
ans=(ans+sum*inv[2])%mod;
ans=(ans+big)%mod;
sum++;
}
else {
ans=(ans+bit.query(a[i].q))%mod;
ans=(ans+(pos[a[i].q]-1)*inv[cnt]%mod*sum)%mod;
big=(big+(cnt-pos[a[i].q]+1)*inv[cnt])%mod;
bit.ins(a[i].q,1);
}
}
fo(i,1,n)if(a[i].q!=-1)bit.ins(a[i].q,-1);
ans=(ans-n*(n-1)%mod*inv[2]%mod+mod)*inv[2]%mod;
printf("%lld",ans);
return 0;
}
T4 追逐
这个题就玄学，我调着调着样例过了，交上去就切了
我还没看懂题解呢，害，人品太好了。。。
所以最优策略问题我就没有做出来过，每次都是等着题解告诉我策略是啥。。
这个最优策略就是挤到一个角落里然后清出一条路来，直接走过去就行了
这个用二分实现。。
AC_code
#include<bits/stdc++.h>
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
inline int read(){
int s=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
return s*f;
}
const int N=1e6+5;
int n,t,s;
int to[N*2],nxt[N*2],head[N],rp;
void add_edg(int x,int y){
to[++rp]=y;
nxt[rp]=head[x];
head[x]=rp;
}
int dp[N],dep[N],fa[N],siz[N];
bool ifst[N];
vector<int> e[N];
bool com(int x,int y){return dp[x]>dp[y];}
void dfs_dp(int x,int f){
if(x==s)ifst[x]=true;
dep[x]=dep[f]+1;fa[x]=f;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==f)continue;
dfs_dp(y,x);
ifst[x]|=ifst[y];
}
if(ifst[x])return ;
int mx=0,mi=0,sum=0;
for(int i=head[x];i;i=nxt[i]){
if(to[i]==f)continue;
if(dp[to[i]]>=dp[mx])mi=mx,mx=to[i];
else if(dp[to[i]]>=dp[mi])mi=to[i];
sum++;
}
if(!mi&&!mx)dp[x]=0;
else if(!mi)dp[x]=1;
else {
dp[x]=dp[mi]+sum;
}
}
void dfs_siz(int x,int f){
siz[x]+=e[x].size();
for(int i=head[x];i;i=nxt[i]){
if(to[i]==f)continue;
siz[to[i]]+=siz[x];
dfs_siz(to[i],x);
}
}
bool check(int x){
int now=s,num=0,stp=1,tmp,mx=0;
while(now!=t){
tmp=0;
for(int i:e[now]){
if(dp[i]+siz[now]+num>x)tmp++;
else mx=max(mx,dp[i]);
}
num+=tmp;
if(num>stp)return false;
now=fa[now];stp++;
}
return mx+num<=x;
}
signed main(){
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
n=read();t=read();s=read();
fo(i,1,n-1){
int x=read(),y=read();
add_edg(x,y);add_edg(y,x);
}
dfs_dp(t,0);
fo(x,1,n){
if(x==t)continue;
for(int i=head[x];i;i=nxt[i]){
if(ifst[to[i]])continue;
e[x].push_back(to[i]);
}
sort(e[x].begin(),e[x].end(),com);
}
dfs_siz(t,0);
// cout<<siz[2]<<endl;
// cout<<dp[3]<<" "<<dp[4]<<endl;
int l=0,r=n,mid;
while(l<r){
mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%d",l);
return 0;
}