Codeforces Round 909 (Div. 3)
A. Game with Integers
题意：
给定一个数\(x\),\(A,B\)两人轮流进行操作，\(A\)先操作。每次给\(x\)加一或者减一，操作完后\(x \% 3 == 0\)者获胜。判断获胜者。
解题思路:
判断\(A\)操作完是否能获胜，如果不能，那么一定是\(B\)获胜。
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n;
cin >> n;
int a = n + 1;
int b = n - 1;
if ((a % 3 == 0) || (b % 3 == 0))
{
puts("First");
}
else
{
puts("Second");
}
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}
B. 250 Thousand Tons of TNT
题意：
将一个数列\(a\)从左到右每\(k\)个相加得到一个和，使得这些和中最小和与最大和的差值最大。
解题思路:
直接暴力。
\(k\)一定是数列长度\(n\)的因子，用前缀和计算这\(k\)个数的和是\(O(1)\)的。
那么对于每个\(k\)的遍历时间复杂度就是\(\frac{n}{k}\)。
遍历\(k\)的时间复杂度是\(O(\sqrt{n})\)。
总体时间复杂度是\(O(n\sqrt{n} \times ln(n))\).调和级数。由于是因子，内层循环大小远小于\(O(nlnn)\)实际时间小这个很多。
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
vector<ll> s(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
ll ans = 0;
for (int i = 1; i <= n / i; i++)
{
if (n % i == 0)
{
ll x = i;
ll y = n / i;
ll minx = 1e18 + 10;
ll maxx = 0;
for (ll l = 1, r = 1 + x; l <= n; l += x, r += x)
{
ll t = s[r - 1] - s[l - 1];
// cout << t << endl;
minx = min(minx, t);
maxx = max(maxx, t);
}
// cout << maxx << ' ' << minx << endl;
ans = max(ans, maxx - minx);
minx = 1e18 + 10;
maxx = 0;
for (ll l = 1, r = 1 + y; l <= n; l += y, r += y)
{
ll t = s[r - 1] - s[l - 1];
minx = min(minx, t);
maxx = max(maxx, t);
}
ans = max(ans, maxx - minx);
}
}
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}
C. Yarik and Array
题意：
给定一个数列，求最大连续子段和，要求子段和中相邻两数奇偶性不能相同。
解题思路:
\(dp\)求解最大子段和板子，加个相邻数奇偶性要不同的转移判断即可。
代码：
#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];
}
vector<ll> f(n + 1);
ll ans = -1e18;
for (int i = 1; i <= n; i++)
{
if (i == 1)
{
f[i] = a[i];
ans = f[i];
continue;
}
int x = (a[i] & 1);
int y = (a[i - 1] & 1);
if (x != y)
{
f[i] = max(f[i - 1] + a[i], a[i]);
}
else
{
f[i] = a[i];
}
ans = max(ans, f[i]);
}
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}
D. Yarik and Musical Notes
题意：
给定数组\(a\)，计算\(pair(i,j)(i < j )\)使得\((2^{a_{i}})^{a_j} == (2^{a_{j}})^{a_i}\)的个数。
解题思路:
首先我们会发现，如果\(a[i] == a[j]\)那么一定是对的。
对于\(a[i] \neq a[j]\)，我们会发现，只有\((1,2),(2,1)\)这种数对是符合的。
统计计数即可。
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n;
cin >> n;
map<int, ll> cnt;
for (int i = 1; i <= n; i++)
{
ll x;
cin >> x;
cnt[x]++;
}
ll ans = 0;
for (auto v : cnt)
{
ll num = v.second;
ans += ((num) * (num - 1)) / 2;
// cout << v.first << ' ' << num << ' ' << ans << endl;
}
ans += cnt[1] * cnt[2];
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}
E. Queue Sort
题意：
给定一个循环数组，问最少进行多少次操作后，数组完全升序。如果无论怎样都无法完全升序，那么输出\(-1\)。
操作为：将第一个数字移到最右端，一直和前一个数字比大小，直到遇到严格小于他的数才停下来，否则就一个一个地向前移动。
解题思路:
如果最终可以升序，那么最多操作\(n\)次。即所有数都操作一遍。
我们会发现，当不存在\(a[i] > a[j],(i < j)\)时，即后面的数都比我大了，那么该位置其实就不用操作了。
所以，我们从右往左找到第一个符合上述条件的位置，就是我们理论上的最小操作次数\(cnt\)。
然后，我们遍历前\(cnt\)个一定要操作的数，如果对于该操作数，整个数组中没有能让他停下来的数，即没有严格小于他的数，那么他就会一直循环，也就是无解。
若对于所有数都存在严格小于他的数，那么答案就是\(cnt\)。
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
int mina = 1e9 + 19;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
};
ll ans = 0;
for (int i = n; i; i--)
{
if (i == n)
{
mina = min(mina, a[i]);
continue;
}
if (a[i] > mina)
{
ans = max((ll)i, ans);
}
mina = min(mina, a[i]);
}
for (int i = 1; i <= ans; i++)
{
if (a[i] <= mina)
{
ans = -1;
break;
}
}
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}
F. Alex's whims
题意：
开始构造一棵树。然后我们有\(q\)次询问。每次询问给定一个\(d\),我们可以删去一条边，然后加上一条边，保证他仍然是一颗树的情况下，使得存在两个叶子间的距离为\(d\),输出操作方案，当然，如果树此时状态就存在\(d\)，也可以不操作。
删边，加边操作为\((u,v_1,v_2)\)，即删去边\((u,v_1)\)，加上边\((u,v_2)\)。\(d_i\)每次询问给定。
解题思路:
开始构造一个\(1 \sim n\)的链。\(d\)是多少，就将\(n\)与当前链接的边断开\((当然，是通向结点1的方向的边)\)，连到\(d\)点上。
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n, q;
cin >> n >> q;
for (int i = 1; i < n; i++)
{
cout << i << ' ' << i + 1 << endl;
}
int last = n - 1;
int idx = 0;
int dist = n - 1;
while (q--)
{
int d;
cin >> d;
int u, v1, v2;
if (dist == d)
{
u = -1;
v1 = -1;
v2 = -1;
}
else
{
u = n;
v1 = last;
v2 = d;
last = v2;
dist = d;
}
cout << u << ' ' << v1 << ' ' << v2 << endl;
}
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}