2019 牛客多校赛第二场

slove 0/10

rank

补题 4/10

------------------------------------------------------------------

https://ac.nowcoder.com/acm/contest/882#question

D、Kth Minimum Clique

题意：给你n个点,每个点都有权值,给出一个n*n的矩阵表示图的连通性,让你求第k小团(团中的每个点都和其他点连有边.注意不是联通!)

题解：暴力...首先根据题意,空集算最小的,然后从空集上扩展,每次都在上一次的基础上加入原先点集中没有的点,这个点要能和原先的点集中所有点都有边.用优先队列维护.用bitset之后代码会很优雅.
还有一个待解决的问题是如何避免相同的点集重复入队的情况. 做法是每次取出队顶点集时取点集中编号最大的点,然后扫描这个点编号之后的点,check一下是否和原来点集中所有的点都有边.是的话就把这个点加入当前点集并入队.为什么可以呢?很简单,因为每次入队都能保证编号最大的点是唯一的,仔细思考一下.

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 1e2+5;
struct stu{
	ll cost;
	bitset<105> s;
};
bool operator<(stu a,stu b){
	return a.cost>b.cost;
}
ll a[MAX],ans;
int n,k,t=0;
bitset<105> book[105];
void solve(){
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;++i) scanf("%lld",&a[i]);
	for(int i=0;i<n;++i){
		char s[n+1];
		scanf("%s",s);
		for(int j=0;s[j];++j) book[i][j]=s[j]-'0';
	}
	priority_queue<stu> list1;
	bitset<105> lis;lis.reset();
	list1.push({0,lis});
	while(!list1.empty()){
		++t;
		stu now = list1.top();list1.pop();
		if(t==k){
			ans=now.cost;
			break;
		}
		bitset<105> tem=now.s;
		int index=-1;
		for(int i=n-1;i>=0;--i){
			if(tem[i]){
				index=i;
				break;
			}
		}
		for(int i=index+1;i<n;++i){
			if(!tem[i]&&((tem&book[i])==tem)){
				tem.set(i);
				list1.push({now.cost+a[i],tem});
				tem.reset(i);
			}
		}
	}
	if(t==k) printf("%lld\n",ans);
	else printf("-1\n");
}
int main(void)
{
	solve();
	return 0;
}

E、MAZE

题意:给你一个n*m的迷宫,有Q次询问,两种类型,当Q==1时改变x,y的连通性.
当Q==2时,求从(1,x)到(n,y)的方案数

题解:有一个结论,给你一个迷宫,你只能走左边,右边,下边.
比如说一个2*2的迷宫,连通性为
00
00
然后将每一行的连通性变为矩阵
第一行变为
00
00,意思为(i,j)这一行的i能不能到j.
然后比如
0010
就是变为
0011
0011
1111
1110,

第三行其实是随便填,反正是障碍,没用的.然后把原来2*2的迷宫转化为的矩阵相乘.也就是
00 00
00*00
注意!!,0运算不了,还是0,虽然表示连通,所以改成1才能运算出结果乘后就变为22,这个时候的(i,j)就表示第一行的i到第n行的j有2个方案，为什么可以这样呢?用矩阵的相关知识仔细想想!!
然后这个题目就很简单了

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 2e5+5;
const int MAXN = 5e4+5;
const int mod = 1e9+7;
int n,m,q;
bool a[MAXN][11];
char s[12];
struct matrix{
	int a[11][11];
	friend matrix operator*(matrix a,matrix b){
		matrix c;
		memset(c.a,0,sizeof(c.a));
		for(int i=1;i<=m;++i)
			for(int j=1;j<=m;++j)
				for(int k=1;k<=m;++k)
					c.a[i][j]=(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j]%mod)%mod;
		return c;
	}
};
matrix node[MAX];
void connect(bool b[11],matrix &now){
	memset(now.a,0,sizeof(now.a));
	for(int i=1;i<=m;++i){
		int j = i;
		while(j>=1&&!b[j]) now.a[i][j]=1,--j;
		j=i;
		while(j<=m&&!b[j]) now.a[i][j]=1,++j; 
	}
}
void build(int p,int l,int r){
	if(l==r){
		connect(a[l],node[p]);
		return;
	}
	int mid = (l+r)/2;
	build(2*p,l,mid);
	build(2*p+1,mid+1,r);
	node[p]=node[2*p]*node[2*p+1];
}
void update(int p,int l,int r,int x){
	if(l==r){
		connect(a[l],node[p]);
		return;
	}
	int mid=(l+r)/2;
	if(l<=x&&mid>=x) update(2*p,l,mid,x);
	else update(2*p+1,mid+1,r,x);
	node[p]=node[2*p]*node[2*p+1];
}
void solve(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i){
		scanf("%s",s);
		for(int j=1;j<=m;++j){
			if(s[j-1]-'0'==1) a[i][j]=true;
			else a[i][j]=false;
		} 
	}
	build(1,1,n);
	for(int i=0;i<q;++i){
		int a1,a2,a3;
		scanf("%d%d%d",&a1,&a2,&a3);
		if(a1==1){
			a[a2][a3]^=1;
			update(1,1,n,a2);
		}
		else printf("%d\n",node[1].a[a2][a3]);
	}
}
int main(void)
{
	solve();
	return 0;
}

F、Partition problem

题意:给你2n*2n的矩阵,(i,j)表示i和j在不同团队的竞争价值,有A,B两个队
求把所有的人划分为AB两个队之后能得到的最大竞争价值

题解:
只有14个点,DFS暴力跑....原来我的思路是DFS完了然后一起算贡献.我也考虑到了
上一次的贡献能优化下一次的计算,但是还是超时,可能是写的太捞了..然后就可以在每次dfs时候都
算一下贡献,这样复杂度就是均摊的了,会降一(hen)点(duo)
然后随便容斥一下就过了

#include<bits/stdc++.h>
#define rep1(i,a,b) for(int i=a;i<=b;++i) 
#define rep2(i,b,a) for(int i=b;i>=a;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define ll long long 
using namespace std;
const int MAX = 30; 
int n;
ll a[MAX][MAX],b[MAX],ans=0,tem[MAX];
void dfs(int index,int countt,ll cost){
	if(countt==n){ ans=max(ans,cost); return;}
	if(index>2*n) return;
	rep1(i,index,2*n) {
		tem[countt]=i;
		ll temp = cost; temp+=b[i];//b[i]为i对其他所有人的竞争价值总和 
		rep1(j,0,countt-1) temp-=a[i][tem[j]]*2;
		//然后减去跟同一队的人的竞争价值,记住要*2, 因为你在之前相当于也算了一遍 
		dfs(i+1,countt+1,temp);
	} 
}
void solve(){
	scanf("%d",&n);
	rep1(i,1,2*n) rep1(j,1,2*n) scanf("%lld",&a[i][j]),b[i]+=a[i][j];
	dfs(1,0,0);
	printf("%lld\n",ans);
}
int main(void)
{
	solve();
	return 0;
 }