A
题意
数据范围
思路
代码
B Tokitsukaze and Balance String (easy)
题意
定义字符串是平衡的：字符串中01的连续子串的数量和10的连续子串的数量相同。
定义字符串s的val(s)：
- 将字符串
s的某位置i的字符倒置（1变成0，0变成1）后，字符串是平衡的，这样的位置的总数
现在有一个由1、0和?组成的字符串，?可以任意换成1或0，求所有的填写完成的字符串的val(s)的总和，模数是。
数据范围
- 保证单个测试文件的之和不超过
思路
Easy版本的数据范围较小，直接dfs统计即可。
代码
ll val(string t) {
ll n = t.size();
ll ret = 0ll;
for (ll pi = 0; pi < n; pi++) {
t[pi] = '1' - t[pi] + '0';
ll cnt1 = 0, cnt2 = 0;
for (ll i = 1; i < n; i++) {
if (t[i - 1] == '0' && t[i] == '1')
cnt1++;
if (t[i - 1] == '1' && t[i] == '0')
cnt2++;
}
ret += (cnt1 == cnt2);
t[pi] = '1' - t[pi] + '0';
}
return ret;
}
ll ans = 0ll;
void dfs(string s, ll p) {
if (s.find('?') == -1) {
ans += val(s);
return;
}
if (s[p] != '?') {
dfs(s, p + 1);
return;
}
s[p] = '1';
dfs(s, p + 1);
s[p] = '0';
dfs(s, p + 1);
return;
}
void solve() {
ll n;
string s;
cin >> n >> s;
ans = 0ll;
dfs(s, 0);
cout << ans << '\n';
}C
题意
数据范围
思路
代码
D Tokitsukaze and Concatenate Palindrome
题意
有两个字符串a和b。
第一步：对他们分别进行重新排列（也可以保持原状）；
第二步：可以进行若干次替换；
第三步：将a和b链接成一个新字符串s。
求至少进行多少次第二步的替换，可以让s是一个回文串。
数据范围
思路
如果a和b有共同拥有的字符，那么在回文串中要尽量将这些字符用作对称的位置，在组合串s的中线位置，尽量放满a或b中较长的串的剩余部分中的数量大于 1 的字符，剩余的不对称的部分就是不得不替换的字符。
代码
void solve() {
ll n, m;
cin >> n >> m;
string a, b;
cin >> a >> b;
if (n < m) {
swap(n, m);
swap(a, b);
}
vector<ll> v1(26, 0), v2(26, 0);
for (auto c : a) {
v1[c - 'a']++;
}
for (auto c : b) {
v2[c - 'a']++;
}
ll tot = 0ll, sum1 = 0ll, sum2 = 0ll;
for (int i = 0; i < 26; i++) {
if (v1[i] > v2[i])
v1[i] -= v2[i], v2[i] = 0;
else
v2[i] -= v1[i], v1[i] = 0;
sum1 += v1[i], sum2 += v2[i];
tot += v1[i] / 2;
}
ll ans = sum2;
if ((sum1 - sum2) / 2 > tot) {
ans += (sum1 - sum2) / 2 - tot;
}
cout << ans << '\n';
}E Tokitsukaze and Dragon’s Breath
题意
在的表格中，每个位置有一个数字代表此地的怪物数量，当龙的位置在时，火焰会打败坐标的怪物，并向四个斜角方向（左上 ↖，右上 ↗，右下 ↘，左下 ↙）一直拓展，形成一个X形状。
请在地图上选一个作为龙的坐标，并计算可以打败最多怪物的数量。
数据范围
思路
按题意枚举点，模拟攻击，注意需要记忆化算过的斜线，保证合适的复杂度。
代码
ll maz[1200][1200];
vector<pll> dxy = {{1, 1}, {-1, 1}, {1, -1}, {-1, -1}};
void solve() {
ll n, m;
cin >> n >> m;
for (ll i = 1; i <= n; i++) {
for (ll j = 1; j <= m; j++) {
cin >> maz[i][j];
}
}
map<ll, ll> mpc, mpr;
auto fire = [&](ll x, ll y) {
if (mpc.count(x - y) == 0) {
ll sum = -maz[x][y];
ll dx = 1, dy = 1;
ll px = x, py = y;
while (px >= 1 && px <= n && py >= 1 && py <= m) {
sum += maz[px][py];
px += dx, py += dy;
}
dx = -1, dy = -1;
px = x, py = y;
while (px >= 1 && px <= n && py >= 1 && py <= m) {
sum += maz[px][py];
px += dx, py += dy;
}
mpc[x - y] = sum;
}
if (mpr.count(x + y) == 0) {
ll sum = -maz[x][y];
ll dx = 1, dy = -1;
ll px = x, py = y;
while (px >= 1 && px <= n && py >= 1 && py <= m) {
sum += maz[px][py];
px += dx, py += dy;
}
dx = -1, dy = 1;
px = x, py = y;
while (px >= 1 && px <= n && py >= 1 && py <= m) {
sum += maz[px][py];
px += dx, py += dy;
}
mpr[x + y] = sum;
}
return mpc[x - y] + mpr[x + y] - maz[x][y];
};
ll ans = 0ll;
for (ll x = 1; x <= n; x++) {
for (ll y = 1; y <= m; y++) {
ll res = fire(x, y);
ans = max(ans, res);
}
}
cout << ans << '\n';
}I Tokitsukaze and Pajama Party
题意
歌词模式是u*uwawauwa，必须有一个u开头和一个uwawauwa结尾(连续的)，且中间的*至少匹配 1 个任意字符，给出一个字符串，求字符串中有多少符合上述模式的子串。
数据范围
思路
寻找字符串中所有uwawauwa的位置，枚举u的位置，统计总数。
代码
void solve() {
ll n;
string s;
cin >> n >> s;
ll p = 0, ans = 0;
vector<ll> pos, v;
while (s.find("uwawauwa", p) != -1) {
p = s.find("uwawauwa", p);
pos.push_back(p);
p += 1;
}
for (ll i = 0; i < s.size(); i++) {
if (s[i] == 'u') {
v.push_back(i);
}
}
for (auto i : pos) {
ll c = lower_bound(v.begin(), v.end(), i - 1) - v.begin();
ans += c;
}
cout << ans << '\n';
}K Tokitsukaze and Shawarma
题意
客人需要个沙威玛，杯可乐，包薯条。
制作 个沙威玛需要 分钟；让饮料机倒可乐，每一杯可乐需要 分钟；让炸锅自动炸薯条，每一包薯条需要 分钟。这三件事可以同时进行。
请问客人至少需要等待几分钟。
数据范围
思路
三者可以同时进行，取耗时最多的时间。
代码
void solve() {
ll x, y, z, a, b, c;
cin >> x >> y >> z >> a >> b >> c;
ll ans = max(x * a, y * b);
ans = max(ans, c * z);
cout << ans << '\n';
}