• 周二. 9月 27th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

2021牛客暑期多校训练营3

admin

11月 28, 2021

2021牛客暑期多校训练营3

B Black and white

对于一个位置((i,j)),选择这个位置的数就给((out_i,in_j))连一条边,考虑四个点((i,j)(i,k)(l,j)(l,k))被涂成黑色对应了(out_i out_l)(in_i in_l)构成的一个四元环。其中一个点自动涂黑就是四元环断一条边,即这四个点刚好连通。
类似的,全部位置涂黑其实就是求图中的一棵生成树。
所以用prim(O(n^2))求最小生成树即可。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define LL long long 
#define INF 2147483647
#define N 5050 
int read(){
	int sum=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
	return sum*f;
}
int e[N*2][N*2];
int dis[N*2];
bool vis[N*2];
signed main(){
	int n=read(),m=read();
	LL a=read(),b=read(),c=read(),d=read(),p=read();
	for(int i=1;i<=n+m;i++)
		for(int j=1;j<=m+n;j++)
			e[i][j]=INF;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			a=(a*a%p*b%p+a*c%p+d)%p;
			e[i][j+n]=e[j+n][i]=a;
		}
	for(int i=1;i<=n+m;i++)dis[i]=INF;
	dis[1]=0;
	LL ans=0;
	for(int i=1;i<=n+m;i++){
		int u,tmp=INF;
		for(int j=1;j<=n+m;j++)
			if(vis[j]==0&&dis[j]<tmp)tmp=dis[j],u=j;
		ans+=dis[u];vis[u]=1;
		for(int j=1;j<=n+m;j++)
			dis[j]=min(dis[j],e[u][j]);
	}
	printf("%lld",ans); 
	return 0;
} 

C Minimum grid

考虑最大的(C_j)(B_i)
填数时只能选择满足条件的行和列并的若干个格子。
一个格子((i,j))中可以填数代表选择了从(out_i)(in_j)的一条边。
其实就是二分图的最小边覆盖。
最小边覆盖=总点数-最大匹配
求最大匹配即可。
之后求次大的(C_j)(B_i)直到满足所有条件为止。
那么证明若干个最小边覆盖(就是最优的选点方案)没有冲突呢?
发现可以使答案变优的解在满足条件的行和列的交上。
这些交不能在考虑其他(C_j)(B_i)时填数,不能使答案更优就随便填,我们不关心具体位置。因为题目保证了至少有一种可行方案,所以不用考虑。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2111;
int cnt,head[N*2],match[N*2],id_n[N],id_m[N];
bool vis[N*2],E[N][N];
struct edge{
	int to,nxt;
}e[N*N];
struct limit{
	int id,type,w;
}c[N*2];
bool cmp(limit a,limit b){
	return a.w>b.w;
}
void add_edge(int u,int v){
	cnt++;
	e[cnt].nxt=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}
int read(){
	int sum=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
	return sum*f;
}
bool dfs(int u){
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(vis[v])continue;
		vis[v]=1;
		if(!match[v]||dfs(match[v])){
			match[v]=u;
			return true;
		}
	}
	return false;
}
int main(){
	int n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++)
		c[i].type=1,c[i].w=read(),c[i].id=i;	 
	for(int i=1;i<=n;i++)
		c[i+n].type=2,c[i+n].w=read(),c[i+n].id=i;
	for(int i=1;i<=m;i++)E[read()][read()]=1;
	sort(c+1,c+1+2*n,cmp);
	int now=1;
	int ans=0;
	int num_n=0,num_m=0;
	while(now<=n*2+1){
		if(c[now].w!=c[now-1].w){
			cnt=0;
			memset(head,0,sizeof(head));
			for(int i=1;i<=num_n;i++)
				for(int j=1;j<=num_m;j++){
					if(E[id_n[i]][id_m[j]]==0)continue;
					add_edge(id_n[i],id_m[j]+n);
					add_edge(id_m[j]+n,id_n[i]); 
				}
			memset(match,0,sizeof(match));
			int tmp=0;
			for(int i=1;i<=num_n;i++){
				memset(vis,0,sizeof(vis));
				tmp+=dfs(id_n[i]);
			}
			ans+=(num_n+num_m-tmp)*c[now-1].w;
			num_n=num_m=0;
		}
		if(c[now].type==1)id_n[++num_n]=c[now].id;
		if(c[now].type==2)id_m[++num_m]=c[now].id;
		now++;
	}
	printf("%d",ans);
	return 0;
}

F 24dian

爆搜,心态爆炸,做题之前一定要确定题目的意思。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
int pos[10],book[10],n,m,cnt,b[40000][10],c[10],type[10],id[10],vis[10],d[10];
bool Map[15][15][15][15];
double a[10];
int read(){
	int sum=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		sum=sum*10+ch-'0';
		ch=getchar();
	}
	return sum*f;
}
bool cnm(){
	double ans;
	for(int i=1;i<=n;i++)a[i]=c[id[i]];
	for(int i=1;i<n;i++)pos[i]=d[i];
	bool flag=0;
	for(int i=1;i<=n-1;i++){
		if(type[i]==1)ans=a[pos[i]]+a[pos[i]+1];
		if(type[i]==2)ans=a[pos[i]]-a[pos[i]+1];
		if(type[i]==3)ans=a[pos[i]]*a[pos[i]+1];
		if(type[i]==4){
			if(a[pos[i]+1]==0)return false;
			if(flag==0){
				int x=(int)a[pos[i]],y=(int)a[pos[i]+1]; 
				if(x%y!=0)flag=1;
			}
			ans=a[pos[i]]/a[pos[i]+1];
		}
		a[pos[i]]=ans;
		for(int j=pos[i]+1;j<=n;j++)a[j]=a[j+1];
		for(int j=i+1;j<=n-1;j++)
			if(pos[j]>pos[i])pos[j]--;
	}
	if(abs(ans-1.0*m)<=1e-5&&flag==0)Map[c[1]][c[2]][c[3]][c[4]]=1;
	if(abs(ans-1.0*m)<=1e-5)return true;
	else return false;
}
bool mmp(int x){
	if(x==n+1){
		if(cnm())return true;
		else return false;
	}
	int flag=0; 
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		id[x]=i;
		vis[i]=1;
		if(mmp(x+1))flag=1;
		vis[i]=0; 
	}
	if(flag==1)return true;
	return false;
}
bool check(int x){
	if(x==n){
		vis[1]=vis[2]=vis[3]=vis[4]=0;
		if(mmp(1))return true;
		else return false;
	}
	int flag=0;
	for(int i=1;i<=4;i++){
		type[x]=i;
		if(check(x+1))flag=1;
	}
	if(flag)return true;
	return false;
}
bool judge(int x){//x是 
	if(x==n){
		if(check(1))return true;
		return false;
	}
	int flag=0;
	for(int i=1;i<=n-1;i++){
		if(book[i])continue;
		book[i]=1;
		d[x]=i;//第x个操作 i 是第几个位置的符号 
		if(judge(x+1))flag=1;
		book[i]=0;
	}
	if(flag)return true;
	return false;
}
void dfs(int x){
	if(x==n+1){
		book[1]=book[2]=book[3]=0; 
		if(judge(1)){
			if(Map[c[1]][c[2]][c[3]][c[4]]==1)return;
			cnt++;
			for(int i=1;i<=n;i++)b[cnt][i]=c[i];
		}
		return;
	}
	for(int i=1;i<=13;i++){
		if(i<c[x-1])continue;
		c[x]=i;
		dfs(x+1);
	}
}
int main(){
	n=read(),m=read();
	dfs(1);
	cout<<cnt<<endl;
	for(int i=1;i<=cnt;i++){
		for(int j=1;j<=n;j++){
			cout<<b[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
} 

发表回复

您的电子邮箱地址不会被公开。