2021-10-06 模拟赛

• • 1、[P2679 [NOIP2015 提高组] 子串](https://www.luogu.com.cn/problem/P2679)
  • 2、[P2341 [USACO03FALL][HAOI2006]受欢迎的牛 G](https://www.luogu.com.cn/problem/P2341)
  • 3、[P1092 [NOIP2004 提高组] 虫食算](https://www.luogu.com.cn/problem/P1092)
  • 4、[P2350 [HAOI2012]外星人](https://www.luogu.com.cn/problem/P2350)

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

（订正AC）

#include

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
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< 
估分：10
 实际得分：10
 想法：万恶的DP ，但其实难度不大，还是自身的蒟蒻问题。
 还有就是要注意如果 a[ i ] 与 b[ j ] 不匹配时 dp[ i&1 ][ j ][ k ][1]=0
 
2、P2341 [USACO03FALL][HAOI2006]受欢迎的牛 G 
算法思路：宽搜
 可能的思路：Tarjan
 
（原码60pts）
 
#include

using namespace std;

const int N=1e4+10;

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

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

bool check(int x){
	int tot=0;
	queue q;
	clean();
	vis[x]=1;
	q.push(x);
	while(!q.empty()){
		int t=q.front();
		q.pop();
		for(int i=0;i 
3、P1092 [NOIP2004 提高组] 虫食算 
算法思路：???
 可能的思路：高斯消元，搜索
 估分：???
 实际得分：???
 
4、P2350 [HAOI2012]外星人 
算法思路：
 可能的思路：数论?!
 估分：???
 实际得分：???
 
总分：70/400（有点慌张）
 反思：算法还要继续学，DP还要继续练。
 蒟蒻的国庆模拟赛（四）
 ——2021.10.6