求助
查看原帖
求助
685183
LightSpot楼主2025/6/17 12:20

代码如下,为什么本地测出来是对的在洛谷IDE上就错了

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10 , NUM = 19771019 , MOD = 998244353;
int p , k , n , len;
char a[MAXN] , s[11][MAXN];
int f[MAXN][44] , w[MAXN][MAXN];
unsigned long long pw[MAXN] , hash1[MAXN] , hash2[MAXN];
bool vis[220];
void calc_hash()
{
	pw[0] = 1;
	for(int i = 1 ; i <= len ; i++) pw[i] = pw[i - 1] * NUM % MOD;
	for(int i = 1 ; i <= len ; i++) hash1[i] = (hash1[i - 1] * NUM + a[i]) % MOD;
	for(int i = 1 ; i <= n ; i++) for(int j = 1 ; j <= strlen(s[i] + 1) ; j++) hash2[i] = (hash2[i] * NUM + s[i][j]) % MOD;
	return;
}
unsigned long long get_hash(int l , int r)
{
	return (hash1[r] - hash1[l - 1] * pw[r - l + 1] % MOD + MOD) % MOD;
}
void init()
{
	calc_hash();
	for(int i = 1 ; i <= len ; i++)
	{
		memset(vis , 0 , sizeof(vis));
		for(int j = i ; j <= len ; j++)
		{
			w[i][j] = w[i][j - 1];
			for(int u = 1 ; u <= n ; u++)
			{
				int l = j - strlen(s[u] + 1) + 1 , r = j;
				if(l < i || vis[l]) continue;
				if(get_hash(l , r) == hash2[u])
				{
					w[i][j]++ , vis[l] = 1;
//					printf("%d %d %d\n" , l , r , u);
				}
			}
		}
	}
	return;
}
int main()
{
	cin >> p >> k;
	len = p * 20;
	cin.sync(); 
	for(int i = 1 ; i <= p ; i++)
	{
		char tmp;
		int cnt = 0;
		while((tmp = getchar()) != '\n') a[++cnt + 20 * (i - 1)] = tmp;
	}
	cin >> n;
	for(int i = 1 ; i <= n ; i++) cin >> s[i] + 1;
	init();
//	for(int i = 1 ; i <= n ; i++) cout << hash2[i] << endl;
	for(int i = 1 ; i <= len ; i++) for(int j = 1 ; j <= min(i , k) ; j++) for(int u = j - 1 ; u <= i - 1 ; u++) f[i][j] = max(f[i][j] , f[u][j - 1] + w[u + 1][i]);
	cout << f[len][k];
	return 0;
}
2025/6/17 12:20
加载中...