Codeforces Round 910 (Div. 2)
A. Milica and String
解题思路:
统计给定字符串\(s\)中的\(B\)的数量，记录为\(cnt\)。
如果\(cnt == k\):输出0；
如果\(cnt < k\):从左往右数，将第\(cnt - k\)个\(A\)的位置前的数全部变成\(B\).
如果\(cnt > k\):从左往右数，将第\(k - cnt\)个\(B\)的位置前的数全部变成\(A\).
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n,k;
cin >> n >> k;
string s;
cin >> s;
int cnt = 0;
for(auto c : s)
{
if(c == 'B')
{
cnt ++;
}
}
if(cnt == k)
{
puts("0");
}
else
{
puts("1");
if(cnt > k)
{
int dist = cnt - k;
int num = 0;
for(int i = 0;i < n;i++)
{
if(s[i] == 'B')
{
num ++;
}
if(num == dist)
{
printf("%d A\n",i + 1);
return;
}
}
}
else
{
int dist = k - cnt;
int num = 0;
for(int i = 0;i < n;i++)
{
if(s[i] == 'A')
{
num ++;
}
if(num == dist)
{
printf("%d B\n",i + 1);
return;
}
}
}
}
}
int main()
{
int t = 1;
cin >> t;
while(t--)
{
solve();
}
return 0;
}
B. Milena and Admirer
解题思路:
首先，每个数字只会变小不会变大。所以，如果\(a[i] > a[j],(j > i)\)。那么我们只能将\(a[i]\)进行拆分。所以考虑后面的数对前面的数的限制。
同时，为了让拆分出来的数对更前面的数限制尽量小，我们要是的被拆分出的数中的最小值尽量的大。
由于我们要求最小操作次数，所以每次拆分出来的数的个数要尽可能少。\(len = (a[i] + a[j] - 1) / a[j]\)。上取整。
要让拆分出的数的最小值尽量的大，那就是尽量均分下去整。\(res = a[i] / len\)。
根据上述思路，从后往前更新即可。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n;
cin >> n;
vector<ll> a(n + 1);
for(int i = 1;i <= n;i++)
{
cin >> a[i];
}
ll ans = 0;
ll t = a[n];
for(int i = n - 1;i;i --)
{
t = min(a[i+1],t);
if(a[i] > t)
{
int len = (a[i] + t - 1) / t;
t = a[i] / len;
ans += len - 1;
}
}
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while(t--)
{
solve();
}
return 0;
}
C. Colorful Grid
解题思路:
简单观察可以发现，从\((1,1) \to (n,m)\)最少要\(n + m - 2\)步。同时，存在的可行解步数\(k\)一定和\(n + m - 2\)奇偶性相同。
\(num = k \% (n + m - 2)\)。
若\(num \% 4 == 2\):我们需要一次转弯。
若\(num \% 4 == 0\):我们原地绕圈即可。
注意：这里转圈位置和转弯位置不能是重合位置，性质原因，二者路线奇偶性有冲突。
所以，我们可以在\((1,1)\)出构造转圈，在\((n,m)\)附近构造转弯。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
ll n,m,k;
cin >> n >> m >> k;
ll a = n + m - 2;
if(k < a)
{
puts("NO");
}
else
{
if((a & 1) != (k & 1))
{
puts("NO");
}
else
{
puts("YES");
{
vector<char> c(3);
c[0] = 'R';
c[1] = 'B';
int vis = 0;
int row = 0;
int col = 0;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m - 1;j++)
{
if(i == 1)
{
if(j == 1)
{
row = vis;
}
if(j == m - 1)
{
col = vis;
}
if(vis)
{
printf("%c ",c[vis]);
}
else
{
printf("%c ",c[vis]);
}
vis ^= 1;
}
else if(i == 2 && j == 1)
{
printf("%c ",c[row]);
}
else if((i >= n - 1) && j == m - 1)
{
if(n & 1)
{
printf("%c ",c[col]);
}
else
{
printf("%c ",c[col ^ 1]);
}
}
else
{
printf("R ");
}
}
printf("\n");
}
for(int i = 1;i<=n - 1;i ++)
{
for(int j = 1;j<=m;j++)
{
if(j == m)
{
if(vis)
{
printf("%c ",c[vis]);
}
else
{
printf("%c ",c[vis]);
}
vis ^= 1;
}
else if(i == 1 && j <= 2)
{
printf("%c ",c[row ^ 1]);
}
else if(i == n - 1 && j == m - 1)
{
printf("%c ",c[vis ^ 1]);
}
else
{
printf("B ");
}
}
printf("\n");
}
}
}
}
}
int main()
{
int t = 1;
cin >> t;
while(t--)
{
solve();
}
return 0;
}
D. Absolute Beauty
解题思路:
本题强烈建议画图理解！！！
略微读题，不难发现本题似曾相识。
本题和2023牛客熟悉多校的题目\(Match\)几乎一样。
我们将\((a[i],b[i])\)看作一个线段。当然，当\(a[i] > b[i]\)时，二元组为\((b[i],a[i])\)。即这是有序二元组。
我们开始讨论一共有几种交换形式。
若\((a[i],b[i]),(a[j],b[j])\)，我们称这两个二元组之间为正序关系。\((a[i],b[i]),(b[j],a[j])\)为反序关系。
若两个二元组表示的线段值域完全不相交，我们称为二者不交。若有相交部分，但并未有一个线段的值域完全包含另外一个线段的值域，称之为相交。若存在完全包含关系，称之为包络关系。
我们考虑交换\(b\)所带来的影响。
正序相交 $\to $ 正序包络，正序包络 $\to $ 正序相交。二者交换前后线段长度之和不变。
正序不交 $\to $ 反序包络，交换后线段长度之和增加。反序包络 $\to $正序不交。交换后线段长度之和减小。
反序不交 $\to $ 反序相交，交换后线段长度之和增加。反序相交 $\to $反序不交。交换后线段长度之和减小。
我们根据长度之和会增加的情况排序遍历，枚举端点计算即可。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
typedef pair<int,int> pii;
void solve()
{
ll n;
cin >> n;
vector<ll> a(n + 1),b(n + 1);
for(int i = 1;i<=n;i++)
{
cin >> a[i];
}
for(int i = 1;i<=n;i++)
{
cin >> b[i];
}
vector<pair<int,int>> v;
ll ans = 0;
for(int i = 1;i <= n;i++)
{
int l = min(a[i],b[i]);
int r = max(a[i],b[i]);
v.push_back({l,r});
ans += abs(l - r);
}
sort(v.begin(),v.end());
ll rs = 1e9 + 10;
ll res = 0;
for(int i = 0;i<n;i++)
{
ll l = v[i].fi;
ll r = v[i].se;
if(rs < l)
{
res = max(res,2 * (l - rs));
}
rs = min(rs,r);
}
cout << ans + res << endl;
}
int main()
{
int t = 1;
cin >> t;
while(t--)
{
solve();
}
return 0;
}
E. Sofia and Strings
解题思路:
\(t\)串应当是\(s\)串操作完后的最终串，所以我们遍历\(t\)串判断\(s\)串能否一步步转移过去即可。
首先，对于排序操作，能实现的作用是将字典序较小的字符转移到一个区域最前面，当该字符时该区域字典序最小时，否则我们只有将该区域中字典序更小的字符删除干净才可以 。
对于\(t\)位置\(idx\)，我们想让\(s[idx] == t[idx]\)，只能从\(idx\)开始往后找，找到\(s[j] == t[idx]\)，然后将他向前面移动。移动方案如上。根据如上移动方案，如果\(s[j] == s[k],(j<k)\)，移动\(s[k]\)一定不会比移动\(s[j]\)更优。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
typedef pair<int,int> pii;
void solve()
{
int n,m;
cin >> n >> m;
set<int> s[27];
string a,b;
cin >> a >> b;
for(int i = 0;i < n;i ++)
{
char c = a[i];
s[c - 'a'].insert(i);
}
for(int i = 0;i < m;i ++)
{
int x = b[i] - 'a';
if(s[x].empty())
{
puts("NO");
return;
}
auto idx = *s[x].begin();
for(int j = 0;j < x;j++)
{
while((!s[j].empty()) && (*s[j].begin()) <= idx)
{
s[j].erase(s[j].begin());
}
}
s[x].erase(s[x].begin());
}
puts("YES");
}
int main()
{
int t = 1;
cin >> t;
while(t--)
{
solve();
}
return 0;
}