Codeforces Round 897 (Div. 2)
A. green_gold_dog, array and permutation
分析:
由题意:
\[c_i = a_i - b_i
\]
\(c_i\)种类最多就是\(n\)个数都不同。
若\(a_i\)不断变大，\(b_i\)不断变小，那么\(c_i\)会不断变大。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
typedef pair<pair<ll, ll>, ll> piii;
#define fi first
#define se second
using i128 = __int128;
int n, m;
int lowbit(int x)
{
return x & -x;
}
void solve()
{
scanf("%d", &n);
vector<pii> a(n + 1);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i].fi);
a[i].se = i;
}
sort(a.begin() + 1, a.end());
vector<int> b(n + 1);
int cnt = n;
for (int i = 1; i <= n; i++)
{
b[a[i].se] = cnt--;
}
for (int i = 1; i <= n; i++)
{
printf("%d ", b[i]);
}
printf("\n");
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}
B. XOR Palindromes
分析:
如何获得回文串：
- 对半分，通过操作使左右两侧一样。
- 全部变成1或0
注意，如果总字符数为奇数，那么每个左右两边一样后，我们还可以将中间的字符进行一次翻转操作。
使得左右两边一样，除了将两边不同的变成相同的，还可以将两边相同的同时翻转。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
typedef pair<pair<ll, ll>, ll> piii;
#define fi first
#define se second
using i128 = __int128;
int n, m;
int lowbit(int x)
{
return x & -x;
}
void solve()
{
scanf("%d", &n);
string s;
cin >> s;
int l = 0;
int r = s.size() - 1;
int cnt = 0;
while (l < r)
{
if (s[l] != s[r])
{
cnt++;
}
l++;
r--;
}
unordered_map<int, int> q;
for (int i = 0; i < n; i++)
{
int x = s[i] - '0';
q[x]++;
}
string ans;
for (int i = 0; i <= n; i++)
{
ans += '0';
}
for (int i = cnt; i <= n / 2; i++)
{
if (i == cnt)
{
ans[i] = '1';
}
else
{
int t = i - cnt;
ans[cnt + t * 2] = '1';
}
}
if (n & 1)
{
for (int i = n - 1; i >= 0; i--)
{
if (ans[i] == '1')
{
ans[i + 1] = '1';
}
}
}
ans[q[0]] = '1';
ans[q[1]] = '1';
cout << ans << endl;
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}
C. Salyg1n and the MEX Game
分析:
直接贪心了，第一次添加\(MEX(S)\),之后删了啥加啥。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
typedef pair<pair<ll, ll>, ll> piii;
#define fi first
#define se second
using i128 = __int128;
int n, m;
int lowbit(int x)
{
return x & -x;
}
void solve()
{
scanf("%d", &n);
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
int cur = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] == cur)
{
cur++;
}
else
{
break;
}
}
while (true)
{
printf("%d\n", cur);
fflush(stdout);
scanf("%d", &cur);
if (cur == -1)
{
return;
}
}
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}