首页 > 其他分享 >NOIP2024

NOIP2024

时间:2024-12-14 13:54:22浏览次数:8  
标签:int text ll st maxn LCA NOIP2024

T1

显然,若 \(t[l,r]\) 均为 \(\texttt1\),会让 \(s[l,r]\) 可以任意重排。

从左到右按位匹配,考虑让一位匹配的代价,可能会让其后面缺少一个数进行匹配,也就是后面的答案最多减少 \(1\)。而匹配一位已经有了 \(1\) 的贡献,故贪心匹配一定不劣。

预处理后暴力匹配即可,附上赛时代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=100007;
ll n,ans,a1[maxn],a2[maxn],b1[maxn],b2[maxn],v1[maxn],v2[maxn],s1[maxn][2],s2[maxn][2],c1,c2;
int main(void){
    //freopen("edit.in","r",stdin);
    //freopen("edit.out","w",stdout);
    ll T=1; cin>>T;
    for(;T--;){
        cin>>n; char t; ans=0;
        for(int i=1;i<=n;i++) cin>>t,a1[i]=(t=='1');
        for(int i=1;i<=n;i++) cin>>t,a2[i]=(t=='1');
        for(int i=1;i<=n;i++) cin>>t,b1[i]=(t=='1');
        for(int i=1;i<=n;i++) cin>>t,b2[i]=(t=='1');

        memset(s1,0,sizeof(s1)),memset(s2,0,sizeof(s2)),memset(v1,0,sizeof(v1)),memset(v2,0,sizeof(v2));
        c1=1,s1[c1][0]=s1[c1][1]=0;
        for(int i=1;i<=n;i++){
            if(!b1[i]) c1++,s1[c1][0]=s1[c1][1]=0;
            else v1[i]=c1,s1[c1][a1[i]]++;
        }
        c2=1,s2[c2][0]=s2[c2][1]=0;
        for(int i=1;i<=n;i++){
            if(!b2[i]) c2++,s2[c2][0]=s2[c2][1]=0;
            else v2[i]=c2,s2[c2][a2[i]]++;
        }
        //for(int i=1;i<=n;i++) cout<<v1[i]<<" "; cout<<"\n";

        for(int i=1;i<=n;i++){
            if(b1[i]==0&&b2[i]==0) ans+=(a1[i]==a2[i]);
            else if(b1[i]==1&&b2[i]==0){
                if(s1[v1[i]][a2[i]]) s1[v1[i]][a2[i]]--,ans++;
            }else if(b1[i]==0&&b2[i]==1){
                if(s2[v2[i]][a1[i]]) s2[v2[i]][a1[i]]--,ans++;
            }else{
                if(s1[v1[i]][0]&&s2[v2[i]][0]){
                    s1[v1[i]][0]--,s2[v2[i]][0]--;
                    ans++;
                }else if(s1[v1[i]][1]&&s2[v2[i]][1]){
                    s1[v1[i]][1]--,s2[v2[i]][1]--;
                    ans++;
                }
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}

T2

首先给一元限制按 \(c\) 排序,对于两个相邻的一元限制 \((p,x),(q,y)\),计数安排 \(a[p,q-1],b[p,q-1]\) 的不合法方案数。

可以发现,一个不合法的方案形如 \(a_p=x,a_{p+1}=b_p,a_{p+2}=b_{p+1},\ldots,a_{q-1}=b_{q-2},b_{q-1}\neq y\)。其中有 \(b_{p},b_{p+1},\ldots,b_{q-2} \) 可以取 \([1,V]\) 中任意值,\(b_{q-1}\) 可以取 \([1,V]/\{y\}\) 中任意值,于是总共有 \(V^{p-q-1}(V-1)\) 中不合法方案。

容斥回来,共有 \(V^{2(p-q)}-V^{p-q-1}(V-1)\) 种合法方案。

排序后直接计数即可,注意第一个和最后一个一元限制。

附上赛时代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=100007,p=1e9+7;
ll n,m,v;
pair<ll,ll> a[maxn];
ll qpow(ll a,ll b){ll E=1; for(;b;b>>=1,a=a*a%p)if(b&1) E=E*a%p; return E;}
ll solve(void){
    for(int i=1;i<m;i++){
        if(a[i].first==a[i+1].first&&a[i].second!=a[i+1].second) return 0;
    }
    m=unique(a+1,a+1+m)-a-1;
    ll res=qpow(v,2*(a[1].first-1))*qpow(v,2*(n-a[m].first))%p;
    for(int i=1;i<m;i++) res=res*(qpow(v,2*(a[i+1].first-a[i].first))-(qpow(v,a[i+1].first-a[i].first-1)*(v-1)%p+p)%p+p)%p;
    return res;
}
int main(void){
    //freopen("assign.in","r",stdin);
    //freopen("assign.out","w",stdout);
    ll T=1; cin>>T;
    for(;T--;){
        cin>>n>>m>>v;
        for(int i=1;i<=m;i++) cin>>a[i].first>>a[i].second;
        sort(a+1,a+1+m);
        cout<<solve()<<"\n";
    }
    return 0;
}

T3

\(k=1\) 时,考虑走到原树上一个点的出边,则这个点的其他出边可以任意安排顺序,总方案数为 \(\prod{(d_i-1)!}\)。

\(k>1\) 时,容斥不好做,于是观察一个新树能被原树上的哪些边走出来。

对于新树上某个原树上点的出边,必然有 \([1,2]\) 条边和另一条原树上不是这个点出边的边相连。只有这 \([1,2]\) 条边才能作为可行的起点。

把每个点的这些边连起来,发现形成了一条原树上叶子到叶子的链,我们将这个链称之为这颗新树的关键链。

对于一条链,能够生成的以这条链为关键链的新树数量为 \(\prod(d_i-1)!\times\prod_{x\in S}(d_x-1)^{-1}\),其中 \(S\) 为这条链的点集。

总方案就是 \(\prod(d_i-1)!\times\sum_{S\text{ is valid}}{\prod_{x\in S}(d_x-1)^{-1}}\),只需要计数合法 \(S\) 的权值之和即可。

可以通过树形 dp 解决。设 \(f_{u,0/1}\),表示考虑 \(u\) 的子树,没有/有关键边的 \(u\) 到叶子的链的 \(\prod(d_x-1)\) 之和,转移是简单的。

#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
#define mp make_pair
using namespace std;
typedef unsigned long long ll;
typedef double db;
const ll maxn=100007,ee=1e18,p=1e9+7;
struct Edge{ll to,id,nxt;}edge[maxn<<1];
ll n,k,ans,frac[maxn],inv[maxn],deg[maxn],f[maxn][2],fs[maxn],head[maxn],ent,vis[maxn];
void addedge(ll u,ll v,ll id){edge[++ent]=Edge{v,id,head[u]},head[u]=ent;}
void ups(ll &a,ll b){a=(a+b>=p?a+b-p:a+b);}
ll qpow(ll a,ll b){ll E=1; for(;b;b>>=1,a=a*a%p)if(b&1) E=E*a%p; return E;}
void init(void){
    frac[0]=1;
    for(int i=1;i<maxn;i++) frac[i]=frac[i-1]*i%p;
    inv[maxn-1]=qpow(frac[maxn-1],p-2);
    for(int i=maxn-1;i>=1;i--) inv[i-1]=inv[i]*i%p;
    for(int i=maxn-1;i>=1;i--) inv[i]=inv[i]*frac[i-1]%p; inv[0]=1;
}
void dfs(ll u,ll fa){
    if(deg[u]<=1) f[u][0]++;
    ll s=0;
    for(ll i=head[u],v,id;i;i=edge[i].nxt){
        v=edge[i].to,id=edge[i].id;
        if(v==fa) continue;
        dfs(v,u);
        if(vis[id]) ups(f[v][1],f[v][0]),f[v][0]=0;
        ups(s,f[u][1]*f[v][0]%p),ups(s,(f[u][0]+f[u][1])*f[v][1]%p);
        ups(f[u][1],f[v][1]),ups(f[u][0],f[v][0]);
    }
    ups(ans,s*inv[deg[u]-1]%p);
    f[u][0]=f[u][0]*inv[deg[u]-1]%p;
    f[u][1]=f[u][1]*inv[deg[u]-1]%p;
}
ll solve(void){
    for(int i=1;i<=n;i++) deg[i]=head[i]=vis[i]=f[i][0]=f[i][1]=0; ent=0; ans=0;
    cin>>n>>k;
    for(int i=1,u,v;i<n;i++) cin>>u>>v,deg[u]++,deg[v]++,addedge(u,v,i),addedge(v,u,i);
    for(int i=1,x;i<=k;i++) cin>>x,vis[x]=1;
    if(n==2) return 1;
    ll rt=0;
    for(int i=1;i<=n;i++)if(deg[i]>1){rt=i; break;}
    dfs(rt,0);
    for(int i=1;i<=n;i++) ans=ans*frac[deg[i]-1]%p;
    return ans;
}
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll id,T; cin>>id>>T; init();    
    for(;T--;) cout<<solve()<<"\n";
    return 0;
}

T4

观察 \(\text{LCA}^{*}(l,r)\to\text{LCA}^*(l,r+1)\),只需要看 \(\text{LCA}^*(l,r)\) 与 \(\text{LCA}^*(r,r+1)\) 哪个深度更小即可。

推而广之,得到 \(\text{dep}_{\text{LCA}^*(l,r)}=\min_{i=l}^{r-1}\text{dep}_{\text{LCA}^*(i,i+1)}\)。

用单调栈求出 \(\text{dep}_{\text{LCA}^*(i,i+1)}\) 能够取为最小值的最大左端点和右端点 \([L_i,R_i]\)。若这个区间与查询区间的交的大小大于等于 \(k\),则其一定能贡献一个小于等于 \(\text{dep}_{\text{LCA}^*(i,i+1)}\) 的值。

对于询问 \([l,r,k]\) 能够覆盖 \([l,l+k-1],[l+1,l+k],\ldots,[r-k+1,r]\) 中的任意一个区间的 \([L_i,R_i]\),其 \(\text{dep}_{\text{LCA}^*(i,i+1)}\) 能够被贡献。

转化为二维偏序问题,变成求在线段 \((l,l+k-1)\to(r-k+1,r)\) 上方或左方的点的权值最大值。分成查询 \((l,l+k-1),(r-k+1,r)\) 两个点左上方点权最大值,以及坐标系顺时针旋转 \(45\) 度时的一个矩形内点权最大值即可。

#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
#define mp make_pair
using namespace std;
typedef unsigned long long ll;
typedef double db;
const ll maxn=500007,ee=1e18;
struct Qry{ll l,r,id;};
ll n,q,dep[maxn],fs[maxn],top[maxn],son[maxn],siz[maxn],val[maxn],L[maxn],R[maxn];
ll ql[maxn],qr[maxn],qk[maxn],ans[maxn];
vector<ll> edge[maxn],st;
vector<Qry> Q[maxn];
vector<pair<ll,ll> > P[maxn];
void ups(ll &a,ll b){a=(a<b?b:a);}
struct Tree{
	ll val[maxn<<3];
	void init(void){memset(val,0,sizeof(val));}
	void upd(ll l,ll r,ll x,ll z,ll rt){
		ups(val[rt],z);
		if(l==r) return; ll mid=(l+r)>>1;
		if(x<=mid) upd(l,mid,x,z,rt<<1); else upd(mid+1,r,x,z,rt<<1|1);
	}
	ll qry(ll l,ll r,ll x,ll y,ll rt){
		if(l>r||r<x||y<l) return 0;
		if(x<=l&&r<=y) return val[rt]; ll mid=(l+r)>>1;
		return max(qry(l,mid,x,y,rt<<1),qry(mid+1,r,x,y,rt<<1|1));
	}
}tree;
void pre1(ll u,ll fa){
	dep[u]=dep[fa]+1,fs[u]=fa,siz[u]=1;
	for(auto v:edge[u]){
		if(v==fa) continue;
		pre1(v,u),siz[u]+=siz[v];
		if(siz[son[u]]<siz[v]) son[u]=v;
	}
}
void pre2(ll u,ll tp){
	top[u]=tp;
	if(son[u]) pre2(son[u],tp);
	for(auto v:edge[u]){
		if(v==fs[u]||v==son[u]) continue;
		pre2(v,v);
	}
}
ll LCA(ll x,ll y){
	for(;top[x]!=top[y];){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		x=fs[top[x]];
	}
	return (dep[x]>dep[y]?y:x);
}
int main(void){
	//freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1,u,v;i<n;i++) cin>>u>>v,edge[u].pb(v),edge[v].pb(u);
	pre1(1,0),pre2(1,1);

	for(int i=1;i<n;i++) val[i]=dep[LCA(i,i+1)],L[i]=1,R[i]=n;
	for(int i=1;i<n;i++){
		for(;!st.empty()&&val[st.back()]>=val[i];) R[st.back()]=i,st.pob();
		st.pb(i);
	}
	st.clear();
	for(int i=n-1;i>=1;i--){
		for(;!st.empty()&&val[st.back()]>val[i];) L[st.back()]=i+1,st.pob();
		st.pb(i);
	}

	cin>>q;
	for(ll i=1;i<=q;i++){
		cin>>ql[i]>>qr[i]>>qk[i];
		Q[ql[i]].pb(Qry{ql[i]+qk[i]-1,n,i});
		Q[qr[i]-qk[i]+1].pb(Qry{qr[i],n,i});
	}
	for(ll i=1;i<n;i++) P[L[i]].pb(R[i],val[i]);
	for(int i=1;i<=n;i++){
		for(auto x:P[i]) tree.upd(1,n,x.first,x.second,1);
		for(auto x:Q[i]) ups(ans[x.id],tree.qry(1,n,x.l,x.r,1));
	}

	tree.init();
	for(int i=1;i<=n;i++) Q[i].clear(),P[i].clear();
	for(ll i=1;i<=q;i++) Q[qk[i]-1].pb(Qry{ql[i]*2+qk[i]-1,qr[i]*2-qk[i]+1,i});
	for(int i=1;i<n;i++) P[R[i]-L[i]].pb(L[i]+R[i],val[i]);
	for(int i=1;i<=n;i++) P[0].pb(2*i,dep[i]);
	for(int i=n;i>=0;i--){
		for(auto x:P[i]) tree.upd(1,2*n,x.first,x.second,1);
		for(auto x:Q[i]) ups(ans[x.id],tree.qry(1,2*n,x.l,x.r,1));
	}
	
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
	return 0;
}

标签:int,text,ll,st,maxn,LCA,NOIP2024
From: https://www.cnblogs.com/aeiouaoeiu/p/18606639

相关文章

  • noip2024 游记
    day-inf前情提要由于csp的超常发挥,喜提SC-0001。day0浮躁。浮躁。浮躁。但这并不是那么严重,因为其实csp前我也挺浮躁的(不过和csp不一样的是入睡前非常兴奋。由于害怕被叠失眠debuff,来了半粒安眠药(人生第一次吃安眠药qwq),神奇的是吃了以后一下就睡着了。day1这天......
  • noip2024
    day0发手机的时候没找到数据线,不过huge居然借了我一个......
  • NOIP2024游记
    过了挺久才敢开始写的,主要是重温一遍考场上的经历实在太可怕了,但无论如何,也算是给这段时间以来的自己一个交代吧。Day-infcsp出分了之后状态一直不太好,每天都不知道自己在干些什么。后来被赠送了dp题单,恰好csp被卡t3遂决定练一练dp。Day-7大概noip前一周吧,状态开始慢慢回升,......
  • NOIP2024 游记
    8:00到考场,感觉有点困,小睡了一会。8:30开考。先通读了一遍题面。感觉T1T2很可做,差不多有了思路。T3感觉非常神秘,T4则是有一点想法,但不是很多。于是还是选择了顺序开题。感觉T1直接贪心就是对的,但是细节也许有点多。在写的时候注意了一下实现,大概在9:00左右过了T1。......
  • NOIP2024 耐摔王记录
    回顾为了分析问题,尽力详细。坐最后一排。5min缺省源。t1想了10min,发现zyd开始打了,红温了,开大样例想,发现贪心匹配做法,但是写出的代码是按点匹配而不是按连续段匹配的。大样例输出66674,答案66647,看上去以为自己过了,结果调到1h。上个厕所红温了,跑路开t2,一眼秒了,过大样......
  • NOIP2024游记
    2024NOIP总结Day016、20、22、24、25、38、40、41、42、43、44、46、47、49、53因为我们就是在本校考,下午到了机房之后就去明儿考试的座位上看了一下,打了一下键盘感觉比较正常,祈祷明儿吧。我们三点半就放了,肩膀不是很舒服,然后没有跟着停课所以没反应过来,放了之后人有点懵,本来......
  • NOIP2024 复盘总结
    考试过程先把题都看了一遍,感觉T2<T1,就从T2开。推了1h的组合数,发现算重了,就先把\(v\le2\)和\(m\le1\)写了。T2应该是45ptsT2短时间推不出正解,就再看看T1。最开始的思路就是把所有的\(0\)可以移动的区间全部预处理出来,然后贪心匹配。发现大样例没过然后又用了30min修......
  • NOIP2024 游记
    NOIP2024游记关于我停一个月晚修&&一星期whk的NOIP最后一舞11/2912:00到了南宁,打算先来半日游。先去了航洋,然后发现霸王茶姬新店开业,十分火爆,抱着10块一杯不喝白不喝的心态去了(比__西__州__级__学食堂还便宜),然后发现友谊太过火爆,全都是先做好一坨然后现场贴标,但很不幸的......
  • [NOIP2024]遗失的赋值
    https://www.luogu.com.cn/problem/P11362参考:https://www.luogu.com/article/9pagx8eg由于\(v>1\),所以对于(2,3)或(3,4)的关系,必定能够确保至少存在一种赋值(只要\(x_2\neqx_3\)即可),无需考虑。只需考虑关系链\(3\sim6\)。因为\(x_3=a_3\),从这里出发一直推导,可以发......
  • NOIP2024 游记
    比赛历程保持以往的策略,先将每一道题都想一遍。T1想了一个贪心,简单地证明感受了一下正确性。接着T2想了一个计数DP,感觉上它是对的。然后T3还是计数,一样简单地推了一个DP然后去看T4。这时莫名的感觉时间有点紧,于是没有想多,想了一个可以拿到不错的分数的暴力就开始打代码......