2023牛客暑期多校训练营4(A, F, J, L)
A.Bobo String Construction
题意:
给定一个01串t，构造一个长度为n的01串s，时的t + s + t中t只在首和尾出现。
分析：
结论，s取全0或者全1。
①t全0或者全1，那我s和t取相反的即可。
②t既包含0又包含1，首先t不可能是s的子串，那我们只需考虑t是否可以由t的后缀加上s再加上t的前缀得到。假设对于当前的串s全0且存在t的后缀加上s加上t的前缀等于t，那么我们将s变为全1则一定不等于t，当前串s全为1同理。
综上，我们只需要分别判断s全为0和全为1即可。
代码：
#include <bits/stdc++.h>
using namespace std;
int check(string &s, string &s2) {
int cnt = 0;
for (int i = 0; i < s.size(); i ++) {
if (s.substr(i, s2.size()) == s2)
cnt ++;
}
return cnt;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --) {
int n;
string s, s0, s1;
cin >> n >> s;
for (int i = 0; i < n; i ++) {
s0 += '0';
s1 += '1';
}
string s3 = s + s0 + s;
if (check(s3, s) == 2)
cout << s0 << endl;
else
cout << s1 << endl;
}
return 0;
}
F.Election of the King
题意：
有n个人竞选国王，\(a_i\)表示第i个人的从政理念，每轮通过投票淘汰一位竞选者，每个人将投给与自己从政理念相差最大的人。
票数最多的将被淘汰，如果票数相同淘汰值最大的，如果值相同则淘汰编号最大的。
分析：
由于每个人投的是与自己执政理念相差最大的人，因此每个人要么投给值最大的要么投给值最小的，最终的决定权将落在值中间的那个人。可以将所有人优先按值从小到大排序，若值相同则按编号从小到大排序，最后不断让中间那个来决定淘汰谁即可。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
struct P {
int a, id;
}p[N];
bool cmp(P &A, P &B) {
if (A.a != B.a)
return A.a < B.a;
else
return A.id < B.id;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> p[i].a;
p[i].id = i;
}
sort(p + 1, p + 1 + n, cmp);
int l = 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (abs(p[mid].a - p[l].a) > abs(p[mid].a - p[r].a))
l ++;
else if (abs(p[mid].a - p[l].a) < abs(p[mid].a - p[r].a))
r --;
else {
r --;
}
}
cout << p[l].id;
return 0;
}
J.Qu'est-ce Que C'est?
题意:
给定n和m，求能构造出满足下面条件的序列的数量。
①每个数在[-m, m]的范围内
②任意长度大于等于2的区间和>=0
分析:
考虑dp。
状态定义：f[i][j]表示前i个数中后缀最小值为j的方案数。
状态转移：
①j >= 0，能够转移过来的前一个状态后缀最小值的下限为j - m，因此f[i][j] = \(\sum_{k = j - m}^m f[i - 1][k]\)
②j < 0，由于要满足长度大于2的区间和>=0，所以最小后缀只有可能是第i个数自己，能够转移过来的前一个状态后缀最小值的下限即为-j， 因此f[i][j] = \(\sum_{k = -j}^m f[i - 1][k]\)
答案即为：\(\sum_{j = -m}^m f[n][j]\)
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 5010, M = 10010, mod = 998244353;
int f[N][M], s[N][M]; // s优化求和部分
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 2 * m; i >= 0; i --) {
f[1][i] = 1;
s[1][i] = s[1][i + 1] + 1;
}
for (int i = 2; i <= n; i ++) {
for (int j = -m; j <= m; j ++) {
if (j < 0) {
f[i][j + m] = s[i - 1][-j + m];
} else {
f[i][j + m] = s[i - 1][j - m + m];
}
}
// 优化求和
for (int j = m; j >= -m; j --) {
s[i][j + m] = (s[i][j + m] + s[i][j + m + 1] + f[i][j + m]) % mod;
}
}
cout << s[n][0];
return 0;
}
L.We are the Lights
题意：
n × m的灯阵，初始全灭。每次操作可将某一行或者某一列的灯全开/全关。问q次操作过后有多少台灯亮着。
分析：
可以发现只有最后一步才决定灯的状态，因此我们可以倒着去维护亮着灯的数量。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
bool row[N], col[N];
struct Q {
string s, op;
int idx;
}q[N], q2[N];
LL cnt, cntr, cntc;
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m, t;
cin >> n >> m >> t;
for (int i = 0; i < t; i ++) {
string s, op;
int idx;
cin >> s >> idx >> op;
q[i] = {s, op, idx};
}
for (int i = t - 1; i >= 0; i --) {
string s = q[i].s, op = q[i].op;
int idx = q[i].idx;
if (s == "row" && !row[idx]) {
row[idx] = true;
q2[cnt ++] = {s, op, idx};
} else if (s == "column" && !col[idx]) {
col[idx] = true;
q2[cnt ++] = {s, op, idx};
}
}
LL res = 0;
for (int i = cnt - 1; i >= 0; i --) {
string s = q2[i].s, op = q2[i].op;
int idx = q2[i].idx;
if (s == "row") {
if (op == "on") {
res += (m - cntc);
cntr ++;
} else {
if (res > 0)
res -= cntc;
}
} else if (s == "column") {
if (op == "on") {
res += (n - cntr);
cntc ++;
} else {
if (res > 0)
res -= cntr;
}
}
}
cout << res;
return 0;
}