洛谷 AC,小图灵/MarsOJ [30, 40] 求助
查看原帖
洛谷 AC,小图灵/MarsOJ [30, 40] 求助
727888
LCATreap楼主2022/12/2 23:05

rt,考场代码在下面,请问是哪里写挂了(考场上用 CCF 的样例测多测是过了的

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mod = 998244353LL;
const int N = 1100;
char a[N][N]; ll dp[N], lst[N]; 
ll sum[N], dw[N]; //dw, 当前位置往下能到达的最深位置 
int t, id, n, m, c, f; 
ll ans1 = 0, ans2 = 0; 
void getf(int k){
	//获取第 k 列的 dp 值和 dw 值 
	for (int i = 1; i <= n; i++)dp[i] = 0, dw[i] = 0;
	for (int i = n; i >= 1; i--){
		if (a[i][k] == '1')dw[i] = 0;
		else dw[i] = dw[i + 1] + 1;
	}
	for (int i = 1; i <= n; i++){
		if (lst[i] > 1)dp[i] = lst[i] - 1;
		else{
			for (int j = k; j <= m; j++){ 
				if (a[i][j] == '0')++dp[i];
				else break;
			}
		}
		lst[i] = dp[i];
	} 
}
void getc(int k){
	//获取第 k 列对 C 答案的贡献
	 for (int i = 1; i <= n; i++){
	 	if (!dp[i])continue;
	 	if (dp[i - 1] && dp[i] > 1){
	 		ll gx = ((sum[i - 1] - dp[i - 1] + 1) % mod) * ((dp[i] - 1) % mod) % mod;
	 		ans1 = (ans1 + gx) % mod; ans2 = (ans2 + gx * ((dw[i] - 1) % mod)) % mod;
	 	}
	 	sum[i] = sum[i - 1] + (dp[i] - 1);
	 }
	 for (int i = 1; i <= n; i++)sum[i] = 0;
}
int main(){
	ios::sync_with_stdio(false);
	cin >> t >> id;
	while (t--){
		cin >> n >> m >> c >> f;
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= m; j++){
				cin >> a[i][j];
			}
		}
		for (int i = 1; i <= n; i++){
			getf(i); getc(i);
		}
		cout << (ans1 * c) % mod << " " << (ans2 * f) % mod << "\n";
		for (int i = 1; i <= n; i++){
			dp[i] = lst[i] = sum[i] = dw[i] = ans1 = ans2 = 0LL;
			for (int j = 1; j <= m; j++)a[i][j] = '1';
		} 
	}
	return 0;
}
2022/12/2 23:05
加载中...