QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#602085 | #8776. Not Another Constructive! | ucup-team3691 | RE | 0ms | 0kb | C++20 | 2.6kb | 2024-09-30 19:07:03 | 2024-09-30 19:07:03 |
answer
#include <iostream>
#include <bitset>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <random>
#include <ctime>
#include <cstdlib>
#include <chrono>
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
string s;
cin >> s;
vector<vector<vector<bitset<2500>>>> dp(n + 1, (vector<vector<bitset<2500>>> (n + 1, vector<bitset<2500>>(n + 1))));
int tc = count(s.begin(), s.end(), 'C');
int tf = count(s.begin(), s.end(), '?');
for (int i = tc; i <= tc + tf; ++i) {
dp[0][0][i] = 1;
}
s = " " + s;
for (int i = 1; i <= n; ++i) {
bool nac = false;
if (s[i] == 'C' || s[i] == '?') {
nac = true;
for (int nn = 0; nn <= i; ++nn) {
for (int nc = 0; nc <= n - i; ++nc) {
dp[i][nn][nc] |= dp[i - 1][nn][nc + 1];
}
}
}
if (s[i] == 'N' || s[i] == '?') {
nac = true;
for (int nn = 0; nn < i; ++nn) {
for (int nc = 0; nc <= n - i; ++nc) {
dp[i][nn + 1][nc] |= dp[i - 1][nn][nc];
}
}
}
if (s[i] == 'A' || s[i] == '?') {
for (int nn = 0; nn <= i; ++nn) {
for (int nc = 0; nc <= n - i; ++nc) {
dp[i][nn][nc] |= dp[i - 1][nn][nc] << (nn * nc);
}
}
}
if (!nac || s[i] == '?') {
for (int nn = 0; nn <= i; ++nn) {
for (int nc = 0; nc <= n - i; ++nc) {
dp[i][nn][nc] |= dp[i - 1][nn][nc];
}
}
}
}
string ans;
for (int nn = 0; nn <= n; ++nn) {
if (dp[n][nn][0].test(k)) {
int i = n;
int nc = 0;
while (i > 0) {
char ch;
if (s[i] == 'N' || (s[i] == '?' && nn > 0 && dp[i - 1][nn - 1][nc].test(k))) {
ch = 'N';
nn -= 1;
} else if (s[i] == 'C' || (s[i] == '?' && nc + 1 <= n && dp[i - 1][nn][nc + 1].test(k))) {
ch = 'C';
nc += 1;
} else if (s[i] == 'A' || (s[i] == '?' && nn * nc <= k && dp[i - 1][nn][nc].test(k - nn * nc))) {
ch = 'A';
k -= nn * nc;
} else {
ch = s[i];
if (s[i] == '?')
s[i] = 'X';
}
ans.push_back(ch);
--i;
}
reverse(ans.begin(), ans.end());
cout << ans << "\n";
return;
}
}
cout << "-1\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
while (t--)
solve();
return 0;
}
詳細信息
Test #1:
score: 0
Runtime Error
input:
22 2 N??A??????C???????????