QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#742838#9536. Athlete Welcome CeremonyO_startWA 12ms230568kbC++173.6kb2024-11-13 17:26:332024-11-13 17:26:33

Judging History

This is the latest submission verdict.

  • [2024-11-13 17:26:33]
  • Judged
  • Verdict: WA
  • Time: 12ms
  • Memory: 230568kb
Show
  • [2024-11-13 17:26:33]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX (int)2e5+50
const ll mod = (ll)1000000007;

ll dp[305][305][3][2]; //0a 1b 2c
ll res[305][305];
ll ans[305][305][305];
int a[3];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;
	int n, i, j, k, q, t;
	cin >> n >> q;
	string s;
	cin >> s;
	int cnt = 0;
	memset(dp, 0, sizeof dp);
	memset(res, 0, sizeof res);
	memset(ans, 0, sizeof ans);
	for (i = 0; i < n; i++) {
		if (s[i] == '?')
			++cnt;
	}
	int now = 0;
	int tot = 0;
	if (s[0] == '?') {
		++tot;
		dp[1][0][0][0] = 1;
		dp[0][1][1][0] = 1;
		dp[0][0][2][0] = 1;
	}
	else {
		dp[0][0][s[0] - 'a'][0] = 1;
	}
	for (i = 1; i < n; i++) {
		now = i % 2;
		if (s[i] == '?')
			++tot;
		for (j = 0; j <= cnt; j++) {
			for (k = 0; k <= cnt; k++) {
				for (t = 0; t < 3; t++) {
					dp[j][k][t][now] = 0;
				}
				if (s[i] == '?') {
					if (j + k > tot)
						continue;
					//insert a
					for (int other = 0; other < 3; other++) {
						if (other == 0 || j == 0)
							continue;
						dp[j][k][0][now] += dp[j - 1][k][other][1 - now];
						dp[j][k][0][now] %= mod;
					}
					for (int other = 0; other < 3; other++) {
						if (other == 1 || k == 0)
							continue;
						dp[j][k][1][now] += dp[j][k - 1][other][1 - now];
						dp[j][k][1][now] %= mod;
					}
					for (int other = 0; other < 3; other++) {
						if (other == 2 || j + k >= tot)
							continue;
						dp[j][k][2][now] += dp[j][k][other][1 - now];
						dp[j][k][2][now] %= mod;
					}
				}
				else {
					if (j + k > tot)
						continue;
					int tmp = s[i] - 'a';
					for (int other = 0; other < 3; other++) {
						if (other == tmp)
							continue;
						if (other == 0) {
							dp[j][k][tmp][now] += dp[j][k][other][1 - now];
							dp[j][k][tmp][now] %= mod;
						}
						else if (other == 1) {
							dp[j][k][tmp][now] += dp[j][k][other][1 - now];
							dp[j][k][tmp][now] %= mod;
						}
						else if(other == 2){
							dp[j][k][tmp][now] += dp[j][k][other][1 - now];
							dp[j][k][tmp][now] %= mod;
						}
					}
				}
				//if (i == n - 1)
				//	cout << j << ' ' << k << ' ' << dp[j][k][0][now] << ' ' << dp[j][k][1][now] << ' ' << dp[j][k][2][now] << '\n';
			}
		}
	}
	int las = (n - 1) % 2;
	for (i = 0; i <= cnt; i++) {
		for (j = 0; i + j <= cnt; j++) {
			for (k = 0; k < 3; k++) {
				res[i][j] += dp[i][j][k][las];
				//cout << i << ' ' << j << ' ' << k << ' ' << dp[i][j][k][las] << '\n';
				res[i][j] %= mod;
			}
			//cout << i << ' ' << j << ' ' << res[i][j] << '\n';
		}
	}
	for (k = 0; k <= cnt; k++) {
		int tmp = cnt - k;
		for (i = 0; i <= tmp; i++) {
			ans[i][tmp - i][k] = res[i][tmp - i];
		}
		ll ma = 0;
		for (i = 0; i <= tmp; i++) {
			for (j = tmp - i + 1; j <= tmp; j++) {
				ans[i][j][k] = ans[tmp - j][j][k] + ans[i][j - 1][k];
				ans[i][j][k] %= mod;
			}
		}
		ma = ans[tmp][tmp][k];
		for (i = 0; i <= cnt; i++) {
			for (j = 0; j <= cnt; j++) {
				if (i <= tmp && j <= tmp)
					continue;
				else
					ans[i][j][k] = ma;
			}
		}
	}
	for (i = 0; i <= cnt; i++) {
		for (j = 0; j <= cnt; j++) {
			for (k = 1; k <= cnt; k++) {
				ans[i][j][k] += ans[i][j][k - 1];
				ans[i][j][k] %= mod;
			}
		}
	}
	//for (i = 0; i <= cnt; i++) {
	//	for (j = 0; j <= cnt; j++) {
	//		for (k = 0; k <= cnt; k++) {
	//			cout << i << ' ' << j << ' ' << k << ' ' << ans[i][j][k] << '\n';
	//		}
	//	}
	//}
	for (i = 0; i < q; i++) {
		for (j = 0; j < 3; j++) {
			cin >> a[j];
			if (a[j] > cnt)
				a[j] = cnt;
		}
		cout << ans[a[0]][a[1]][a[2]] << '\n';
	}
}
源文件, 语言: C++17

詳細信息

Test #1:

score: 100
Accepted
time: 8ms
memory: 230560kb

input:

6 3
a?b??c
2 2 2
1 1 1
1 0 2

output:

3
1
1

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 12ms
memory: 230360kb

input:

6 3
??????
2 2 2
2 3 3
3 3 3

output:

30
72
96

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 8ms
memory: 230296kb

input:

1 1
?
0 1 1

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 11ms
memory: 230292kb

input:

10 10
acab?cbaca
0 2 0
1 1 2
4 2 3
1 1 1
3 5 1
0 5 2
2 2 0
1 2 5
4 3 0
1 1 3

output:

0
1
1
1
1
0
1
1
1
1

result:

ok 10 lines

Test #5:

score: 0
Accepted
time: 8ms
memory: 230260kb

input:

10 10
?c?c?cbac?
10 5 1
5 8 7
9 2 6
5 7 1
5 2 6
5 6 5
5 10 3
9 1 10
2 5 9
1 2 9

output:

16
16
11
16
11
16
16
5
11
0

result:

ok 10 lines

Test #6:

score: -100
Wrong Answer
time: 7ms
memory: 230568kb

input:

50 100
?abacbacab?cbcbcb?acabcbabcbcacbababc?caba?acacbca
8 3 8
2 4 8
8 7 3
0 9 2
10 8 7
7 6 5
4 10 2
6 9 3
3 6 6
9 10 8
2 5 8
8 1 0
3 5 0
1 0 6
5 0 8
6 5 5
1 7 9
7 7 10
4 7 5
6 6 4
10 1 2
4 1 7
10 0 8
7 6 3
1 9 1
4 7 2
8 4 0
8 6 1
5 10 4
5 8 2
5 8 4
4 5 9
5 2 1
1 10 9
4 10 1
8 4 3
8 9 9
8 0 1
0 8 0...

output:

8
8
8
6
8
8
6
8
8
8
8
0
0
0
8
8
8
8
8
8
6
6
8
8
2
6
0
2
8
6
8
8
2
8
2
8
8
2
0
8
2
0
8
8
8
8
8
8
8
8
2
8
0
8
8
8
8
8
7
6
8
2
8
8
8
8
8
8
8
8
0
8
0
8
8
8
8
8
8
8
7
2
8
8
8
8
2
6
8
8
8
8
8
0
8
0
8
8
2
1

result:

wrong answer 4th lines differ - expected: '0', found: '6'
English 繁體中文 简体中文

伺服器時間: 2025-02-07 01:08:30 | 開源專案