[数据结构与算法]2021-10-06 模拟赛

1、P2679 [NOIP2015 提高组] 子串

算法思路：DP （蒟蒻尝试失败）
可能的思路：???

（订正AC）

#include<bits/stdc++.h>

using namespace std;

const int mod=1000000007;
typedef long long ll;

int n,m,ki;
ll dp[2][210][210][2];
char a[1010],b[210];

int main(){
	scanf("%d%d%d",&n,&m,&ki);
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=m;i++)
		cin>>b[i];
	dp[0][0][0][0]=1;
	dp[1][0][0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=1;k<=ki;k++){
				if(a[i]==b[j]){
					dp[i&1][j][k][1]=(dp[i&1^1][j-1][k][1]+dp[i&1^1][j-1][k-1][0])%mod;
					dp[i&1][j][k][1]+=dp[i&1^1][j-1][k-1][1];
					dp[i&1][j][k][1]%=mod;
					dp[i&1][j][k][0]=dp[i&1^1][j][k][1]+dp[i&1^1][j][k][0];
					dp[i&1][j][k][0]%=mod;
				}
				else{
					dp[i&1][j][k][0]=dp[i&1^1][j][k][0]+dp[i&1^1][j][k][1];
					dp[i&1][j][k][0]%=mod;
					dp[i&1][j][k][1]=0;
				}
			}
		}
	}
	ll ans=(dp[n&1][m][ki][1]+dp[n&1][m][ki][0])%mod;
	printf("%lld",ans);
	return 0;
}

极简代码
（来源于洛谷Rumia的题解，有细微更改）

#include<iostream>
using namespace std;
long long f[201][201]={1},sum[201][201],n,m,ki;
char a[1001],b[201];
int main(){
    cin>>n>>m>>ki>>a>>b;
    for(int i=1;i<=n;i++)
      for(int j=m;j>=1;j--)
        for(int k=ki;k>=1;k--)
              f[j][k]=(f[j][k]+ (sum[j][k]= a[i-1]==b[j-1]? sum[j-1][k]+f[j-1][k-1] : 0))%1000000007;
    cout<<f[m][ki];
    return 0;
}

估分：10
实际得分：10
想法：万恶的DP ，但其实难度不大，还是自身的蒟蒻问题。
还有就是要注意如果 a[ i ] 与 b[ j ] 不匹配时 dp[ i&1 ][ j ][ k ][1]=0

2、P2341 [USACO03FALL][HAOI2006]受欢迎的牛 G

算法思路：宽搜
可能的思路：Tarjan

（原码60pts）

#include<bits/stdc++.h>

using namespace std;

const int N=1e4+10;

int n,m;
vector<int> f[N];
int vis[N];

void clean(){
	memset(vis,0,sizeof(vis));
}

bool check(int x){
	int tot=0;
	queue<int> q;
	clean();
	vis[x]=1;
	q.push(x);
	while(!q.empty()){
		int t=q.front();
		q.pop();
		for(int i=0;i<f[t].size();i++){
			if(!vis[f[t][i]]){
				vis[f[t][i]]=1;
				tot++;
				q.push(f[t][i]);
			}
		}
	}
	if(tot+1==n) return true;
	else return false;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		f[y].push_back(x);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(check(i)) ans++;
	}
	printf("%d",ans);
	return 0;
}

3、P1092 [NOIP2004 提高组] 虫食算

算法思路：???
可能的思路：高斯消元，搜索
估分：???
实际得分：???

4、P2350 [HAOI2012]外星人

算法思路：
可能的思路：数论?!
估分：???
实际得分：???

总分：70/400（有点慌张）
反思：算法还要继续学，DP还要继续练。
蒟蒻的国庆模拟赛（四）
——2021.10.6