Codeforces Round 932 (Div. 2)
A - Entertainment in MAC
解题思路:
如果翻转字符小于原字符，那么一直翻转即可。
否则，翻转\(n - 1\)次，然后添加一次。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
typedef double db;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
const int N = 6010;
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
string rs = s;
reverse(rs.begin(), rs.end());
if (s <= rs)
{
cout << s << endl;
}
else
{
rs += s;
cout << rs << endl;
}
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
B - Informatics in MAC
解题思路:
如果有解，一定能只划分为两个区间。
从左向右遍历，实时维护前后缀的\(mex\)。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
typedef double db;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
const int N = 6010;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1), cl(n + 1), cr(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
cr[a[i]]++;
}
int l = 0;
int r = 0;
while (cr[r] > 0)
{
r++;
}
for (int i = 1; i < n; i++)
{
cl[a[i]]++;
cr[a[i]]--;
if (cr[a[i]] == 0)
{
if (r > a[i])
{
r = a[i] + 1;
}
}
while (cl[l] > 0)
{
l++;
}
while (r > 0 && cr[r - 1] == 0)
{
r--;
}
if (l == r)
{
cout << 2 << endl;
cout << 1 << ' ' << i << endl;
cout << i + 1 << ' ' << n << endl;
return;
}
}
cout << -1 << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
C - Messenger in MAC
解题思路:
同样的元素集合，一定是按照\(b\)升序排列花费最小。
按\(b\)进行升序排序，枚举左右两个端点，\(b\)的总和就确定了。取区间中尽量多的最小的\(a\)，使得花费小于等于\(l\)。
所以我们就是要维护区间中的\(a\)有序，然后尽量多取较小的\(a[i]\)。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
typedef double db;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
const int N = 6010;
void solve()
{
ll n, m;
cin >> n >> m;
vector<pii> v(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> v[i].fi >> v[i].se;
}
sort(v.begin(), v.end(), [&](auto a, auto b)
{ return a.se < b.se; });
ll ans = 0;
for (int i = 1; i <= n; i++)
{
// cost 维护了[l,r]的a的和减去一个b[i]
ll cost = -v[i].se;
priority_queue<int> q;
for (int j = i; j <= n; j++)
{
q.push(v[j].fi);
cost += v[j].fi;
if (!q.empty() && cost + v[j].se > m)
{
cost -= q.top();
q.pop();
}
ans = max(ans, (ll)q.size());
}
}
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
D - Exam in MAC
解题思路:
考虑容斥：总对数 - 通过\(a[i]\)单个排除的对数 + 重复减去的对数。
对于\(a[i]:\)
- 考虑\(x + y = a[i]\):\((0,a_i),(1, a_i-1),...,(\frac{a_i}{2},a_i -\frac{a_i}{2})\)。
- 考虑\(y - x = a_i:\)\((0,a_i),(1,a_i + 1),...,(c - a_i,c)\)。
自身排除对数时有一个重复对。
不同\(a\)之间会重复的只有较小\(a_i\)的\(y_i -x_i = a_i\)，\(y_i + x_i = a_j\)这种情况。
如果\(a_i\)为奇数，那么\(y_i + x_i\)一定为奇数；如果\(a_i\)为偶数，那么\(y_i + x_i\)一定为偶数；
所以，较小的奇数一定会对较大的奇数造成一次对数删除重复，遍历记录奇偶个数即可。
举例:\(3 - 1= 2,3 + 1 = 4，4 - 2= 2， 4 +2 = 6\)。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
typedef double db;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
const int N = 6010;
void solve()
{
ll n, c;
cin >> n >> c;
vector<ll> a(n + 1);
// 计算总对数
ll ans = (c + 2) * (c + 1) / 2;
// 减去非法对
for (int i = 1; i <= n; i++)
{
cin >> a[i];
// x + y == a[i]
ans -= a[i] / 2 + 1;
// y - x == a[i]
ans -= c - a[i] + 1;
}
// 加上重复减去的对
vector<int> cnt(2);
for (int i = 1; i <= n; i++)
{
cnt[a[i] % 2]++;
ans += cnt[a[i] % 2];
}
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}