Codeforces Round 960 (Div. 2)(A - D)
A - Submission Bait
解题思路:
假设直接选最大数，如果最大数有奇数个，\(Alice\)必胜，反之必败。
根据这个思路，从大到小看数字，找到第一个出现奇数次的数，从它开始选，就能保证每次\(Alice\)选的时候还剩奇数个选项。
代码:
#include <bits/stdc++.h>
#include <cxxabi.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
using ull = unsigned long long;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
#define fi first
#define se second
const int N = 2e5 + 10;
const int M = 60;
const ll inf = 1ll << 30;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) { return rng() % (r - l + 1) + l; }
void solve()
{
int n;
cin >> n;
vector<int> cnt(n + 10);
for (int i = 1; i <= n; i++)
{
int t;
cin >> t;
cnt[t]++;
}
for (int i = n; i; i--)
{
cnt[i] += cnt[i + 1];
if (cnt[i] & 1)
{
cout << "YES\n";
return;
}
}
cout << "NO\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
B - Array Craft
解题思路:
整个序列分为三段\([1, y + 1],[y, x],[x + 1, n]\)。
\([x,y]\)全部填正数，这样只要加上这一段一定比不加要更大。
对于最大前缀和来说，\([x + 1, n]\)区间中\(sum(x + 1,... ,k)\in [x + 1, n]\)一定得小于等于\(0\)。先考虑能否取尽量小？不方便构造，因为如果尽量往小取，我们还要反过来考虑\(suf[y, ...,n] >suf[x - 1, ...n]\)。所以，考虑使得后缀和为零。
如果\(n - (x + 1)\)为偶数，我们按\(-1, 1\)的规律一定能让其最后和为零。
如果\(n - (x + 1)\)是奇数，我们可以最终让区间和为\(-1\)。发现\([x,y]\)区间全部取\(1\)区间和都有\(2\)，一定大于\(-1\),满足后缀和条件，所以可以这么构造。
对于区间\([1, y + 1]\)同理考虑。
代码:
#include <bits/stdc++.h>
#include <cxxabi.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
using ull = unsigned long long;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
#define fi first
#define se second
const int N = 2e5 + 10;
const int M = 60;
const ll inf = 1ll << 30;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) { return rng() % (r - l + 1) + l; }
void solve()
{
int n, x, y;
cin >> n >> x >> y;
vector<int> a(n + 1);
int l = 1;
int r = y - 1;
int len = r - l + 1;
if (len & 1)
{
int cur = -1;
for (int i = l; i <= r; i++)
{
a[i] = cur;
cur *= -1;
}
}
else
{
int cur = 1;
for (int i = l; i <= r; i++)
{
a[i] = cur;
cur *= -1;
}
}
for (int i = y; i <= x; i++)
{
a[i] = 1;
}
l = x + 1;
r = n;
int cur = -1;
for (int i = l; i <= r; i++)
{
a[i] = cur;
cur *= -1;
}
for (int i = 1; i <= n; i++)
{
cout << a[i] << " \n"[i == n];
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
C - Mad MAD Sum
解题思路：
举例\((1,1,1,2,2,2)\rightarrow (0,1,1,1,2,2) \rightarrow (0,0,1,1,1,2) \rightarrow (0,0,0,1,1,1)\)。
像这样玩一下，不难发现，变化后的序列一定是一个单调递增的序列，且每一段相同数字的变化都是有迹可循的。
比如，最大数段会不断变短，前面数段会不断右移。
考虑到初始序列不具备这样的性质，所以可以先对原序列进行两次操作，然后对第二次操作后的单调序列按照上述性质模拟即可。
两次操作后，出了最大数段，不可能出现数段长度为\(1\)的情况。这个情况处理起来麻烦且会出现在前两次操作中，所以直接操作掉即可。
代码:
#include <bits/stdc++.h>
#include <cxxabi.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
using ull = unsigned long long;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
#define fi first
#define se second
const int N = 2e5 + 10;
const int M = 60;
const ll inf = 1ll << 30;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) { return rng() % (r - l + 1) + l; }
void solve()
{
ll n;
cin >> n;
ll ans = 0;
vector<ll> a(n + 1), pos(n + 1), cnt(n + 1);
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
a[i] = x;
ans += x;
}
ll mx = 0;
for (int i = 1; i <= n; i++)
{
cnt[a[i]]++;
if (cnt[a[i]] == 2)
{
pos[a[i]] = i;
}
if (a[i] > mx && cnt[a[i]] >= 2)
{
mx = a[i];
}
a[i] = mx;
ans += a[i];
// cout << i << ' ' << a[i] << endl;
}
for (int i = 1; i <= n; i++)
{
cnt[i] = pos[i] = 0;
}
for (int i = 1; i <= n; i++)
{
cnt[a[i]]++;
if (cnt[a[i]] == 2)
{
pos[a[i]] = i;
}
}
ll r = n;
for (ll i = n; i; i--)
{
if (cnt[i] < 2 || pos[i] > r)
{
continue;
}
ll m = r - pos[i] + 1;
ans += (m * (m + 1)) / 2 * i;
if (r != n && m > 1)
{
ans += (n - 1 - r + 1) * m * i;
}
r = pos[i] - 1;
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
D - Grid Puzzle
解题思路:
操作次数上限为\(n\)，就是一行一行地变白。尝试用\(2 \times 2\)涂白优化。
举例：
- \((1, 1),(1, 2),(2, 1),(2, 2)\)：都可以一次涂白两行，操作数为一。由此也可见，这里\(1\)和\(2\)其实是等价的，少的那个\(1\)并无优化空间。
- \((2, 4, 4, 4,4, 2)\)：这种两端\(2\)中间连续的\(4\)，操作数都可以优化到行数减一。同理，把中间连续的\(4\)部分换成\(3\)也行，\(3,4\)在这里也是等价的。
- 这样我们就还可以把\((2, 2)\)这种看作中间连续的\(4\)数量为\(0\)的情况。
枚举下标，只有当前\(a_i = 2\)时，我们可以尝试优化操作数。其中\((1, 2)\)等价\((3, 4)\)等价。其余操作，都是直接将当前行涂白最优。
注意：手画一下就能发现，中间\(4\)的个数一定得是偶数个才能尝试优化。
代码:
#include <bits/stdc++.h>
#include <cxxabi.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
using ull = unsigned long long;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
#define fi first
#define se second
const int N = 2e5 + 10;
const int M = 60;
const ll inf = 1ll << 30;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) { return rng() % (r - l + 1) + l; }
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1), dp(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
// 等价
if (a[i] == 1)
{
a[i] = 2;
}
// 等价
if (a[i] == 3)
{
a[i] = 4;
}
}
int len = 0;
for (int i = 1; i <= n; i++)
{
dp[i] = dp[i - 1] + (a[i] == 0 ? 0 : 1);
// 只有2结尾有可能优化操作次数
if (a[i] == 2 && a[i - len - 1] == 2 && len % 2 == 0)
{
dp[i] = min(dp[i], dp[i - len - 2] + len + 1);
}
if (a[i] == 4)
{
len++;
}
else
{
len = 0;
}
}
cout << dp[n] << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}