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;
}

(之后补充…)