cf补题
Educational Codeforces Round 135 (Rated for Div. 2)
C. Digital Logarithm
题意
给定两个长度为n的序列a，b；给定一种操作为，令ai=leng（ai）（bi=leng（bi）），其中leng（n）表示十进制数n的位数。求最少几次操作可以使a和b中出现的相同元素的个数相同。
解
对题给操作观察可以发现，有三种值：1(最终值），2~9（过渡值），其他（初始值）。因为使得一个值等于它的长度，而长度最长为9，最短为1。故经过最多两次转化就可以使一个数为1。
本题可以对数组进行三次处理，1.先去除重复数（初始重复值）；2.因为上一步已经去除了两数组公共元素，故本步将ab中所有非1~9数进行题给操作，再次去重（过渡重复值）；3.经过前两步操作可以使数组中只剩下1~9区间内的数，故只要再将非1数处理既可。
代码
void solve()
{
int n;
cin >> n;
multiset<string> a, b;
for (int i = 0; i < n; i++)
{
string x;
cin >> x;
a.insert(x);
}
for (int i = 0; i < n; i++)
{
string x;
cin >> x;
if (a.find(x) != a.end())
a.erase(a.find(x));
else
b.insert(x);
}
int cnt = 0;
multiset<string> t;
for (auto c : a)
{
if (c.size() > 1 || c == "0")
t.insert(to_string(c.size())), cnt++;
else
t.insert(c);
}
a = t;
t.clear();
for (auto c : b)
{
string p = c;
if (c.size() > 1 || c == "0")
p = to_string(c.size()), cnt++;
if (a.find(p) != a.end())
a.erase(a.find(p));
else
t.insert(p);
}
for (auto c : a)
if (c != "1")
cnt++;
for (auto c : t)
if (c != "1")
cnt++;
cout << cnt << endl;
}D. Letter Picking
题意
给定一个字符串s，有A，B两人各有一个空的字符串a，b；从A开始，依次从s的两端不放回的取字符，头插入自己的字符串中，在最优决策下谁的字符串字典序排序较小谁胜，反之则平局。
解
可以发现在长度为2的字符串中，只存在两种情况，A胜或平局。将其推广至L，R的情况时，可以发现：当A选L，B选R，若L+1~R-1是A赢，则现在仍是A赢，若是平局，则当sL<sR是A赢；同理写出其他三种情况即可转换为状态转移方程。
代码
void solve()
{
string s;
cin >> s;
int n = s.size();
s = "1" + s;
memset(f, 0, sizeof f);
for (int i = 1; i < n; i++)
{
f[i][i + 1] = (s[i] != s[i + 1] ? 1 : 0);
}
for (int len = 3; len < n; len += 2)
{
for (int i = 1; i + len <= n; i++)
{
int j = i + len;
if (f[i + 1][j - 1] && f[i + 2][j])
f[i][j] = 1;
else
{
if (!f[i + 1][j - 1] && (!f[i + 2][j]))
{
if (s[i] < s[j] && s[i] < s[i + 1])
f[i][j] = 1;
}
else if (!f[i + 1][j - 1])
{
if (s[i] < s[j])
f[i][j] = 1;
}
else if (!f[i + 2][j])
{
if (s[i] < s[i + 1])
f[i][j] = 1;
}
}
if (f[i + 1][j - 1] && f[i][j - 2])
f[i][j] = 1;
else
{
if (!f[i + 1][j - 1] && (!f[i][j - 2]))
{
if (s[i] > s[j] && s[j - 1] > s[j])
f[i][j] = 1;
}
else if (!f[i + 1][j - 1])
{
if (s[i] > s[j])
f[i][j] = 1;
}
else if (!f[i][j - 2])
{
if (s[j - 1] > s[j])
f[i][j] = 1;
}
}
}
}
if (f[1][n])
cout << "Alice" << endl;
else
cout << "Draw" << endl;
}
Codeforces Round #819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022
C. Jatayu's Balanced Bracket Sequence
题意
给一个长度为2n的合法括号序列s，让建一个有2n个点的图，建图方式为取任意i，j大于等于1，小于等于2n，若区间ij内对应s为合法括号序列则连接结点ij。求有几个联通块。
解
经过观察可以发现（）（）...（）这样的括号序列形成一个连通块，当（（...（）...））这样的有匹配括号数-1个联通块，（（）（（）））（）这样的有3个连通块等价于（（（））），故可以看出当（）与其他括号序列相连时奉献为0，（（...（）...））与其他括号序列相连时奉献为n-1。
故只要求出每一部分的奉献即可。
代码
void solve()
{
int n;
string s;
cin >> n >> s;
int cnt = -1;
int res = 0;
for (auto c : s)
{
if (c == '(')
cnt++;
if (c == ')')
res += max(0, cnt), cnt = -1;
}
cout << res + 1 << endl;
}Codeforces Round #822 (Div. 2)
C. Removing Smallest Multiples
题意
给一个从1到n的数组排列S，和一个数组T给定一个操作：选择一个k,1<=k<=n，然后清除目前排列S中存在的k的最小倍数，此次操作的代价为k。保证S可以变为K，问最小代价是多少。
解
可以暴力的去解本题，将k从1开始向上递增，判断当前k可以清除多少个需要处理的元素，当k要清除到需要保留的元素时，结束这个k的递增。
代码
void solve()
{
int n;
string s;
cin>>n>>s;
s="!"+s;
vector<int> a(n+1,1);
int cnt=0,tar=count(s.begin(),s.end(),'0');
ll res=0;
for(int i=1;i<=n&&cnt<tar;i++){
for(int j=1;j*i<=n&&cnt<tar;j++){
int t=j*i;
if(a[t]){
if(s[t]=='1')break;
cnt++;
res+=i;
a[t]=0;
}
}
}
cout<<res<<endl;
}D - Slime Escape
题意
给一长度为n的数组a和一个下标k，可以从a[k]开始向右或向左移动并且用a[k],加上目标位置上的数，之后该位置上数变为0，需要保证在移动过程中，值始终不小于0。能否找到一条路径可以到达a[0]或a[n+1]。
解
每次可以向一个方向移动直到不能移动并且记录移动过程中出现的最大值，再向另一方向移动，用上该最大值，重复上述步骤直到不能再向外移动或完成目标。
代码
void solve()
{
int n, k;
cin >> n >> k;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
ll l = k - 1, r = k + 1, lc = 0, rc = 0, lm = 0, rm = 0;
while (l >= 1 && r <= n)
{
bool f = 1;
while (l >= 1 && a[k] + a[l] + lc + rm >= 0)
{
lc += a[l--];
lm = max(lm, lc);
f = 0;
}
while (r <= n && a[k] + a[r] + rc + lm >= 0)
{
rc += a[r++];
rm = max(rm, rc);
f = 0;
}
if (f)
{
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}Codeforces Round #821 (Div. 2)
C. Parity Shuffle Sorting
题意
给一个长度为n的非负整数数组a，给定一个操作：选择两个下标l和r，当(al+ar)%2==1时，ar=al;反之al=ar。进行最多n次操作使得数组非递减。
解
因为最多n此操作，我们可以考虑把整个数组都变一下，变成相等的。再看给定操作，我们可以发现，第一个数和最后一个数非常好用，只要他们相同，那无论是奇偶情况都可以做到我们想做到的。
代码
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
if (n == 1)
{
cout << 0 << endl;
return;
}
if ((a[1] + a[n]) % 2)
{
vector<pair<int, int>> b(n);
int tt = 0;
b[tt++] = {1, n};
for (int i = 2; i < n; i++)
{
if ((a[i] + a[1] )% 2)
{
b[tt++] = {1, i};
}
else
b[tt++] = {i, n};
}
cout << tt << endl;
for (int i = 0; i < tt; i++)
cout << b[i].first << ' ' << b[i].second << endl;
}
else
{
vector<pair<int, int>> b(n);
int tt = 0;
b[tt++] = {1, n};
for (int i = 2; i < n; i++)
{
if ((a[i] + a[n]) % 2)
{
b[tt++] = {1, i};
}
else
b[tt++] = {i, n};
}
cout << tt << endl;
for (int i = 0; i < tt; i++)
cout << b[i].first << ' ' << b[i].second << endl;
}
}D1. Zero-One (Easy Version)
题意
给两个长度为n的字符串a，b，和一种作用于字符串a的操作：选择两个不相同的下标l，r，使a[l]和a[r]上的元素反转，0<l<r<=n。对于该操作，当l+1=r时，花费为x，反之花费为y。保证x>y。
解
每次都是变化两个元素，故如果想让a变成b需要，必须的操作数必然是偶数。故所需的变化数就是ab不同元素的个数/2，当只改变下标满足l+1=r的时候，当x>=2*y时，可以多操作一次，以获得更优解。
代码
void solve()
{
int n, x, y;
string a, b;
cin >> n >> x >> y >> a >> b;
int t = count(a.begin(), a.end(), '0') - count(b.begin(), b.end(), '0');
if (t % 2)
{
cout << -1 << endl;
return;
}
ll cnt = 0;
int l = 0, r = a.size() - 1;
bool f = 0;
while (l < r)
{
while (l < r && a[l] == b[l])
l++;
while (l < r && a[r] == b[r])
r--;
if (l < r)
{
cnt += y;
if (l + 1 == r)
f = 1;
l++,r--;
}
}
if (f && cnt == y){
if(y<=x/2)cnt+=y;
else cnt=x;
}
cout << cnt << endl;
}Codeforces Round #823 (Div. 2)
B. Meeting on the Line
题意
给一个数轴，数轴上有n个人，在不同的位置，他们想聚一聚，但他们出发之前都有一定的准备时间,你需要找到数轴上一点使得所有人从同时开始准备到到达该点的时间最少，第i个人在x[i]上，出门所需准备时间为t[i]。位置x到达点y所需时间为|x-y|。
解
根据题目很容易可以感觉到本题需要使用二分，但常规的二分位置不具有明显的单调性。故可以尝试二分时间，即最短时间。
代码
bool check(double mid)
{
double L = -2e18, R = 2e18;
for (int i = 0; i < n; i++)
{
if (mid < t[i])
{
return false;
}
L = max(L, x[i] - mid + t[i]);
R = min(R, x[i] + mid - t[i]);
}
ans=L;
if (L - 1e-8 <= R)
return 1;
else
return 0;
}
void solve()
{
cin >> n;
for (int i = 0; i < n; i++)
cin >> x[i];
for (int i = 0; i < n; i++)
cin >> t[i];
double l = 0, r = 2e18;
for(int i = 1 ; i <= 100 ; i ++ )
{
double mid = (l + r) / 2;
if (check(mid))
r = mid;
else
l = mid;
}
check(r);
printf("%.10lf\n", fabs(ans));
}
C. Minimum Notation
题意
给一个包含0~9的字符串，给一个操作：可以选择一个其中一个字符c将其变为min(c+1,9)然后插入字符串的任意位置。问通过上述不限次数的操作后，可得最小字典序字符串是？
解
可以对该字符串，倒着处理，维护一个目前最小值，当遍历到的值是小于该值的时候，更新该值；反之则将值进行处理后备用。
代码
void solve()
{
string s;
cin >> s;
int num[10] = {0};
char cur = '9';
for (int i = s.size() - 1; i >= 0; i--)
{
if (s[i] <= cur)
num[s[i] - '0']++, cur = s[i];
else
num[min(s[i] - '0' + 1, 9)]++;
}
for (int i = 0; i <= 9; i++)
{
while (num[i]--)
cout << i;
}
cout << endl;
}
