技术教程 编程教程 Noip模拟84 2021.10.27 正文

Noip模拟84 2021.10.27

2023-05-13,,

以后估计都是用\(markdown\)来写了，可能风格会有变化

T1 宝藏

这两天老是会的题打不对，还是要细心。。。

考场上打的是维护\(set\)的做法，但是是最后才想出来的，没有维护对于是没有交。。

然后觉得细节太多于是下午来的就去打了比较好搞得权值线段树

基本思想就是用一个指针\(pos\)指向当前需要更新的答案（\(pos\times 2+1\)是题目输入的选择的数的个数，这样解释应该就好懂了）

那么考虑先将所有宝藏按照价值从小到大排序，发现从最后开始向前扫每一个宝藏，他可以更新的\(pos\)是单调递增的

例如，当前考虑下标为\(x\)的宝藏价值为中位数最大值的时候，

他的可以更新的这个\(pos\)值域取在\([pos,\min(n-x,x-1)]\)一段区间，

那么我们只需要看，从\(x\)的左边和右边分别选择\(pos\)个宝藏，他们的\(\sum t\)是否有可能小于\(T\)，

显然每次找到最小的前\(pos\)个\(t\)的\(\sum\)是最优的，所以开两颗权值线段树分别维护当前的\(x\)左边和右边的值即可

treasure
 
#include<bits/stdc++.h>

#define int long long

using namespace std;

const int NN=3e5+5;

namespace AE86{

	auto read=[](){

		int x=0,f=1;char ch=getchar();

		while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}

		return x*f;

	};

	auto write=[](int x,char opt='\n'){

		char ch[20];short len=0;if(x<0)x=~x+1,putchar('-');

		do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);

		for(short i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);

	};

}using namespace AE86;

int n,T,Q,x,ans[NN],mx,dis[NN];

struct node{

	int w,t;

	bool operator<(const node&a)const{

		return w==a.w?t<a.t:w<a.w;

	}

}p[NN];

struct SNOWtree{

	#define lid (id<<1)

	#define rid (id<<1|1)

	int ll[NN<<2],rr[NN<<2],nm[NN<<2],sm[NN<<2];

	inline void pushup(int id){if(ll[id]==rr[id])return;nm[id]=nm[lid]+nm[rid];sm[id]=sm[lid]+sm[rid];}

	inline void build(int id,int l,int r){ll[id]=l;rr[id]=r;if(l==r)return;int mid=l+r>>1;build(lid,l,mid);build(rid,mid+1,r);}

	inline void insert(int id,int pos,int v){

		if(ll[id]==rr[id])return nm[id]+=v,sm[id]+=v*dis[pos],void();int mid=ll[id]+rr[id]>>1;

		if(pos<=mid)insert(lid,pos,v); else insert(rid,pos,v); pushup(id);

	}

	inline int query(int id,int lim){

		if(!lim) return 0;

		if(nm[id]<=lim) return sm[id];

		if(ll[id]==rr[id]) return dis[ll[id]]*lim;

		int mid=ll[id]+rr[id]>>1;

		if(lim<=nm[lid]) return query(lid,lim);

		return sm[lid]+query(rid,lim-nm[lid]);

	}

}ri,le;

int pos;

auto solve=[](int x){

	int r=min(n-x,x-1); if(pos>r) return;

	while(pos<=r){

		int tot=ri.query(1,pos)+le.query(1,pos)+dis[p[x].t];

		if(tot<=T) ans[pos*2+1]=p[x].w,++pos; else break;

	}

};

namespace WSN{

	inline short main(){

		// freopen("in.in","r",stdin);freopen("bl.out","w",stdout);

		freopen("treasure.in","r",stdin);freopen("treasure.out","w",stdout);

		n=read();T=read();Q=read();

		for(int i=1;i<=n;i++) p[i].w=read(),p[i].t=read(),dis[i]=p[i].t;

		sort(p+1,p+n+1); memset(ans,-1,sizeof(ans));

		sort(dis+1,dis+n+1); mx=unique(dis+1,dis+n+1)-dis-1;

		for(int i=1;i<=n;i++) p[i].t=lower_bound(dis+1,dis+mx+1,p[i].t)-dis;

		ri.build(1,1,mx);le.build(1,1,mx);

		for(int i=1;i<=n;++i) le.insert(1,p[i].t,1);

		for(int i=n;i;--i) le.insert(1,p[i].t,-1),solve(i),ri.insert(1,p[i].t,1);

		while(Q--) x=read(),write(ans[x]);

		return 0;

	}

}

signed main(){return WSN::main();}

T2 寻找道路

对不起，坏孩子没有打正解，直接使用\(bitset\)可以淼过去

考场上打了一半的\(bitset\)然后发现使用\(dijkstra\)无法优化其对于堆优化时候的比较函数

然后当时不知道咋想的，也没有试一试\(spfa\)，\(spfa\)只有一次比较，写起来非常方便

只要写了\(spfa+bitset\)就可以切掉了，但是只能说是淼过去的

非常好写，就是注意删除前导\(0\)就可以了

path
 
#include<bits/stdc++.h>

#define int long long

#define si(i,x) for(int i=head[x],y=e[i].to;i;i=e[i].next,y=e[i].to)

using namespace std;

const int NN=2e6+5,mod=1e9+7;

namespace AE86{

	auto read=[](){

		int x=0,f=1;char ch=getchar();

		while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}

		return x*f;

	};

	auto write=[](int x,char opt='\n'){

		char ch[20];short len=0;if(x<0)x=~x+1,putchar('-');

		do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);

		for(short i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);

	};

}using namespace AE86;

int n,m;

struct SNOW{int to,val,next;}e[NN];int head[NN],rp=1;

auto add=[](int x,int y,int z){e[++rp]=SNOW{y,z,head[x]};head[x]=rp;};

int dis[NN],wei[NN];

bitset<1001> bt[NN],tmp;

bool vis[NN];

queue<int>q;

auto spfa=[](){

	for(int i=1;i<=n;i++)

		dis[i]=1e18,wei[i]=1000,bt[i].flip();

	q.push(1); vis[1]=true;

	dis[1]=0; wei[1]=1; bt[1].reset(); bt[1]=0;

	while(!q.empty()){

		int x=q.front(); q.pop(); vis[x]=false;

		si(i,x){

			bool cmp=0; int wi=wei[x]+1;

			if(bt[x][wei[x]]==0) --wi;

			tmp=bt[x]<<1; tmp[1]=e[i].val;

			if(wei[y]>wi) cmp=1;

			else if(wei[y]<wi) cmp=0;

			else{

				for(int j=wei[y];j;--j){

					if(bt[y][j]>tmp[j]) {cmp=1;break;}

					else if(bt[y][j]<tmp[j]) {cmp=0;break;}

				}

			}

			if(cmp){

				bt[y]=tmp; wei[y]=wi;

				dis[y]=(dis[x]*2%mod+e[i].val)%mod;

				if(!vis[y]){

					vis[y]=true;

					q.push(y);

				}

			}

		}

	}

};

namespace WSN{

	inline short main(){

		freopen("path.in","r",stdin);

		freopen("path.out","w",stdout);

		n=read();m=read();

		for(int i=1,u,v,w;i<=m;i++)

			u=read(),v=read(),w=read(),add(u,v,w);

		spfa();

		for(int i=2;i<=n;i++)

			if(dis[i]>=1e18) write(-1,' ');

			else write(dis[i],' ');

		puts("");

		return 0;

	}

}

signed main(){return WSN::main();}

T3 猪国杀

又搞这一套，又想吓我，已经无法被吓倒了

不过题目还是很神仙的假期望，真计数

设方案数为\(ans\)，那么答案就是

\(ans=\sum\limits_{i=0}^{n}\sum\limits_{j=1}^{A}\sum\limits_{k=1}^{n-i}g_{i,j-1,m-j*k}\times C_n^i\sum\limits_{t\geq k}C_{n-i}^{t}\times(A-j)^{n-i-t}\)

其中\(g_{i,j,k}\)表示有多少个长度为\(i\)的序列满足每一个数字都不大于\(j\)且所有数字的总和不大于\(k\)

以上式子可以理解为枚举序列的长度，然后枚举最大值\(j\)，然后再枚举最大值的个数\(k\)，然后剩下的\(n-i\)个可以在去掉最大值的限制后随便选

你可能会问，这个算方案数的式子为什么不用考虑每次的贡献？

实际上他每个合法的序列计算的次数正好为他做的贡献数，即每个合法序列都会计算\(i+k\)次

那么考虑容斥出\(g_{i,j,k}=\sum\limits_{t=0}^{i}(-1)^t\times C_i^t\times C_{k-j*t}^{i}\)

那么原式的转化我就不写了，随便代一下就出来了，直接照这个式子抄就可以了，把没有贡献的地方直接跳过不计算

legend
 
#include<bits/stdc++.h>

#define int long long

#define si(i,x) for(int i=head[x],y=e[i].to;i;i=e[i].next,y=e[i].to)

using namespace std;

const int NN=101,MM=3001,mod=998244353;

namespace AE86{

	auto read=[](){

		int x=0,f=1;char ch=getchar();

		while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}

		return x*f;

	};

	auto write=[](int x,char opt='\n'){

		char ch[20];short len=0;if(x<0)x=~x+1,putchar('-');

		do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);

		for(short i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);

	};

}using namespace AE86;

int n,m,A,ans;

namespace Math{

	int h[MM],v[MM];

	auto qmo=[](int a,int b,int ans=1){

		int c=mod;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;

		return ans;

	};

	auto inv=[](int x){return qmo(x,mod-2);};

	auto prework=[](){

		h[0]=h[1]=1; v[0]=v[1]=1; for(int i=2;i<MM;++i)h[i]=h[i-1]*i%mod;

		v[MM-1]=inv(h[MM-1]); for(int i=MM-2;i>=2;--i)v[i]=v[i+1]*(i+1)%mod;

	};

	auto C=[](int n,int m){return (n<m||n<0||m<0) ? 0 : (h[n]*v[n-m]%mod*v[m]%mod);};

}using namespace Math;

namespace WSN{

	inline short main(){

		freopen("legend.in","r",stdin);

		freopen("legend.out","w",stdout);

		n=read();m=read();A=read();prework();

		for(int i=0;i<=n;++i){

			for(int j=1;j<=A;++j){

				for(int k=1;k<=n-i;++k){

					if(m-k*j<0)continue;

					int tmp=0,res=0,bs=1;

					for(int t=0;t<=i&&m-k*j-t*(j-1)>=i;++t,bs=-bs)

						tmp=(tmp+bs*C(i,t)%mod*C(m-k*j-t*(j-1),i)%mod+mod)%mod;

					tmp=tmp*C(n,i)%mod;

					for(int t=k;t<=n-i;++t)

						res=(res+C(n-i,t)*qmo(A-j,n-i-t)%mod)%mod;

					ans=(ans+tmp*res%mod)%mod;

				}

			}

		}

		write(ans*inv(qmo(A,n))%mod);

		return 0;

	}

}

signed main(){return WSN::main();}

T4 数树

数据范围提示状态压缩，那么考虑如何设状态

设计状态\(f[x][S]\)表示\(x\)子树中的点集为\(S\)的方案数

例如，\(S=0001110\)就表示\(2，3，4\)这三个点是某一个点的子孙节点

那么因为\(T2\)的形状对于不同的节点做根可能会不一样，所以以每一个节点做根都跑一边\(dp\)

然后注意去重，具体操作就是用\(map\)预处理出会重复算多少次，最后的\(dp\)数组再把算重复的除掉就行了

count
 
#include<bits/stdc++.h>

#define int long long

#define pb push_back

using namespace std;

const int NN=3005,mod=998244353;

namespace AE86{

	auto read=[](){

		int x=0,f=1;char ch=getchar();

		while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}

		return x*f;

	};

	auto write=[](int x,char opt='\n'){

		char ch[20];short len=0;if(x<0)x=~x+1,putchar('-');

		do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);

		for(short i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);

	};

}using namespace AE86;

auto qmo=[](int a,int b,int ans=1){

	int c=mod;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;

	return ans;

};auto inv=[](int x){return qmo(x,mod-2);};

int n,m,v[11],S[1<<10],tot,root,T[11],dp[NN][1<<10],tmp[11];

vector<int> son[11];

struct Graph{

	#define star(e,i,x) for(int i=e.head[x],y=e.to[i];i;i=e.nxt[i],y=e.to[i])

	int to[NN<<1],nxt[NN<<1],head[NN],rp;

	inline void add(int x,int y){

		to[++rp]=y; nxt[rp]=head[x]; head[x]=rp;

		to[++rp]=x; nxt[rp]=head[y]; head[y]=rp;

	}

}e,g;

unordered_map<int,bool>mp;

unordered_map<int,int>t[11];

inline void dfs(int f,int x,int bs){

	S[x]|=(1<<x-1);tot+=bs;

	star(g,i,x) if(y!=f){

		son[x].pb(y); dfs(x,y,bs*10);

		++t[x][T[y]];

		S[x]|=S[y];T[x]+=T[y];

	}

	star(g,i,x) if(y!=f) if(t[x].find(T[y])!=t[x].end())

		tmp[x]=tmp[x]*v[t[x][T[y]]]%mod,t[x].erase(T[y]);

	T[x]+=bs;

}

int res[1<<10],ans;

inline void DP(int f,int x){

	for(int i=0;i<m;i++) dp[x][1<<i]=1;

	star(e,i,x) if(y!=f){

		DP(x,y);

		for(int j=1;j<(1<<m);j++) res[j]=dp[x][j];

		for(int j=1;j<(1<<m);j++) if(dp[x][j])

			for(int k=1;k<=m;k++) if(!(j&S[k])&&dp[y][S[k]])

				dp[x][S[k]|j]=(dp[x][S[k]|j]+dp[y][S[k]]*res[j]%mod)%mod;

	}

	for(int i=1;i<=m;i++) dp[x][S[i]]=dp[x][S[i]]*tmp[i]%mod;

	ans=(ans+dp[x][(1<<m)-1])%mod;

}

namespace WSN{

	inline short main(){

		freopen("count.in","r",stdin);freopen("count.out","w",stdout);

		v[0]=1; for(int i=1;i<=10;i++) v[i]=v[i-1]*inv(i)%mod;

		n=read();for(int i=1;i<n;i++)e.add(read(),read());

		m=read();for(int i=1;i<m;i++)g.add(read(),read());

		for(int i=1;i<=m;i++){

			for(int j=1;j<=m;j++)t[j].clear(),son[j].clear(),tmp[j]=1;

			memset(S,0,sizeof(S));

			memset(T,0,sizeof(T));

			memset(dp,0,sizeof(dp));

			tot=0; root=i;

			dfs(0,root,1);

			if(mp.find(tot)==mp.end())

				mp[tot]=true,DP(0,1);

		}

		write(ans);

		return 0;

	}

}

signed main(){return WSN::main();}

Noip模拟84 2021.10.27的相关教程结束。

《Noip模拟84 2021.10.27.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!