2019-01-27模拟赛

发表于 | 评论数： | 阅读次数：

考后总结

深深地明白了自己的弱小…
（这是自己的总结，就不放题了）

正文

T1

一道DP题…
这里是连续子串，但我写成了不连续子序列……
转移方程式： 

1
2
if(a[i]==b[j]) f[i][j][k]=f[i-1][j-1][k]+1;
else f[i][j][k]=f[i][j][k-1]+1;

就是这样……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
int n,k,f[303][303][303];
char a[333],b[333];
int main(){
	scanf("%d%d",&n,&k);
	scanf("%s%s",a+1,b+1);
	if(k>=n){//这个特判不要也行
		printf("%d\n",n);
		return 0;
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	if(a[i]==b[j]) for(int l=0;l<=k;l++)
		f[i][j][l]=f[i-1][j-1][l]+1;
	else for(int l=1;l<=k;l++)
	    f[i][j][l]=f[i-1][j-1][l-1]+1;//转移
	int maxx=0;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
  	    for(int l=0;l<=k;l++)
	      maxx=max(maxx,f[i][j][l]);//找答案
	printf("%d\n",maxx);
	return 0;
}

T2

这题是可以用暴力骗出40到70不等。但是正解也是很简单的。
用bitset就可以将70分的暴力改为满分。
单然，还要一点数学知识：乘法原理。
还有一点就是会有三元环，要对答案适当的减去三元环中的重复解和不可能的解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
const int maxn=1555;
int n,d[maxn]; char aa;
bitset<maxn>b[maxn],bb;//c++STL中的bitset
long long ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++){
	  	aa=getchar();
	  	while(aa!='0'&&aa!='1') aa=getchar();
	  	b[i][j]=aa-'0';
	  	if(b[i][j]) d[i]++;
	  }
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	  if(i!=j&&b[i][j]){
	  	ans+=(d[i]-1)*(d[j]-1);
	  	bb=b[i]&b[j];//记录重复部分
	  	ans-=bb.count();//bb.count():查询在这个bitset二进制中有多少个1
	  }
	printf("%lld\n",ans);
	return 0;
}

T3

这题可以说是难度大，但有40分可以很简单的拿到（40分就可以了？？

这题要对图拆点，因为只有0或1的遍，所以用BFS加DFS解决这题！！

正解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
int tot,n,m,h0[maxn],h1[maxn],cnt,dis[maxn];
struct node{
	int nxt,to;
}edge[maxn];
queue<int>que;
void add0(int x,int y){
	edge[++cnt]=(node){h0[x],y};
	h0[x]=cnt;
}
void add1(int x,int y){
	edge[++cnt]=(node){h1[x],y};
	h1[x]=cnt;
}
void dfs(int x,int val){
	if(dis[x]!=-1) return;
	dis[x]=val,que.push(x);
	for(int i=h0[x];i;i=edge[i].nxt) dfs(edge[i].to,val);
	if(x>tot) return;
	for(int i=0;i<20;i++)
	if(x&(1<<i)) dfs(x^(1<<i),val);
}
int main(){
	scanf("%d%d",&n,&m);
	tot=1<<20;
	int x,y;
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		add1(tot+i,x); add0(x,tot+i);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		add1(tot+x,tot+y);
	}
	memset(dis,-1,sizeof(dis));
	dfs(tot+1,0);
	while(que.size()){
		int d=que.front();que.pop();
		for(int i=h1[d];i;i=edge[i].nxt) 
		dfs(edge[i].to,dis[d]+1);
	}
	for(int i=1;i<=n;i++) printf("%d\n",dis[tot+i]);
	return 0;
}

(之后补充…)