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;
} 
京公网安备 11010502036488号