Codeforces Round 860 (Div. 2)
Date: 04/08/2023
A|Showstopper
Brief: 两组数 \(\{a_i\}\) 和 \(\{b_i\}\)，长度都为 \(n\). \(\forall i\) , 可以交换 \(a_i\) 和 \(b_i\), 问是否可以使得 \(a_n = \max(a_i)\), \(b_n = \max(b_i)\).
Data: \(T\leq 200\), \(n\leq 100\).
Solution: 【简单思维题】
发现只需考虑当把大的放在一边，小的放在另一边时的可行性。
题解提到一个比较重要的思想：交换操作大于等于 \(2\) 时是无效的。
Complexity: \(\mathcal{O}(Tn)\).
Review: -
State: AC.
Code:
#define Justanaaaaame
#include <cstdio>
#include <iostream>
using namespace std;
#define MAXN 110
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
int a[MAXN], b[MAXN];
for (int i = 1 ; i <= n ; ++i)
cin >> a[i];
for (int i = 1 ; i <= n ; ++i)
cin >> b[i];
for (int i = 1 ; i <= n ; ++i)
if (a[i] < b[i])
swap(a[i], b[i]);
bool flag = true;
for (int i = 1 ; i < n ; ++i)
if (a[i] > a[n] || b[i] > b[n])
{
flag = false;
break;
}
if (flag)
cout << "Yes\n";
else
cout << "No\n";
}
}
B|Three Sevens
Brief: \(m\) 天，每天 \(n_i\) 人参加比赛，编号分别为 \(a_{i,j}\). 每天有一个胜者，胜者在之后的比赛中不出现。构造出一个可能的胜者序列。
Data: \(T\leq 50000\), \(m\leq 50000\), \(\sum n_i\leq 50000\).
Solution: 【简单思维题】【构造】
一个比较重要的思想：倒序考虑。
倒序维护出现过的人，在每一天找一个没出现过的人即可。
Review: 实现时在循环里声明大数组TLE，放全局变量AC：声明有复杂度QAQ（滚去学 cpp 惹~
State: AC.
Code:
#define Justanaaaaame
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define MAXN 50010
vector <int> v[MAXN];
bool vis[MAXN];
int ans[MAXN];
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
{
int m;
cin >> m;
for (int i = 1 ; i <= m ; ++i)
{
v[i].clear();
int n;
cin >> n;
for (int j = 1 ; j <= n ; ++j)
{
int t;
cin >> t;
v[i].push_back(t);
vis[t] = false;
}
}
bool flag;
for (int i = m ; i ; --i)
{
flag = false;
for (const auto &x : v[i])
if (!vis[x])
{
vis[x] = true;
ans[i] = x;
flag = true;
}
if (!flag)
break;
}
if (flag)
{
for (int i = 1 ; i <= m ; ++i)
cout << ans[i] << ' ';
cout << "\n";
}
else
{
cout << "-1\n";
}
}
return 0;
}
C|Candy Store
Brief: \(n\) 种糖，第 \(i\) 种有 \(a_i\) 颗，每颗 \(b_i\) 元。现在把第 \(i\) 种糖分成 \(a_i/d_i\) 袋，每袋 \(d_i\) 颗，那么一袋 \(c = b_i \cdot d_i\) 元。一个标签可以覆盖相邻价格一样的糖果袋，求在不改变糖的顺序的前提下，最少的标签数量。
Data: \(T\leq 100000\), \(2 \leq n\leq 200000\), \(\sum n_i\leq 20000\).
Solution: 【数学】
Observation 1: 贪心地让当前的标签覆盖更多的袋子最优；
Observation 2: \(b_i\mid c\). 对于一个标签覆盖的，\(\text{lcm}(b_i)\mid c\);
Observation 3: \(c \mid a_i\cdot b_i\) (由于 \(c \cdot (a_i/d_i) = a_i\cdot b_i\)). 对于一个标签覆盖的，\(c\mid\gcd(a_i\cdot b_i)\);
综上，只需从前往后判断新加入的是否满足 \(\text{lcm}(b_i)\mid\gcd(a_i\cdot b_i)\), 不满足则新加一个标签。
Review: 实际上离结论已经很近了，然而……
State: -> AC.
Code:
#define Justanaaaaame
#include <iostream>
using namespace std;
#define int long long
int gcd(int a, int b)
{
while(a ^= b ^= a ^= b %= a);
return b;
}
int lcm(int a, int b)
{
return a * b / gcd(a, b);
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
int ans = 1;
int a1, b1;
cin >> a1 >> b1;
int g = a1 * b1, l = b1;
for (int i = 2 ; i <= n ; ++i)
{
int a, b;
cin >> a >> b;
g = gcd(g, a * b);
l = lcm(l, b);
if (g % l)
{
++ans;
g = a * b;
l = b;
}
}
cout << ans << '\n';
}
}
D|Shocking Arrangement
Brief: 给定整数序列，满足和为 \(0\)。需要构造一个排列，使得 \(\max\limits_{1\leq l\leq r\leq n}|a_l+a_{l+1}+\cdots+a_r|<\max(a) - \min(a)\).
Data: \(T\leq 50000\), \(1 \leq n\leq 300000\), \(\sum n_i\leq 30000\).
Solution: 【构造】【dp】
Observation 1: 左式可以写成 \(maxPrefSum - minPrefSum\)；
Observation 2: 只需满足 \(maxPrefSum\leq\max(a)\) and \(minPrefSum\geq\min(a)\) 且不能同时取等。
综上，只需当前缀和 \(> 0\) 时，放一个小于 \(0\) 的数；在前缀和 \(\leq 0\) 时，放一个 \(\geq 0\) 的数。如此构造前缀和一定在最大值和最小值之间。
另外，注意到全为 \(0\) 时取等，无解。
Review: 关键在于公式的转换。注意max和min的性质。复健基本模型。
State: AC.
Code:
#define Justanaaaaame
#include <iostream>
using namespace std;
#define MAXN 300010
int np, pos[MAXN];
int nn, neg[MAXN];
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
{
nn = 0;
np = 0;
int n;
cin >> n;
for (int i = 1 ; i <= n ; ++i)
{
int t;
cin >> t;
if (t >= 0) pos[++np] = t;
else neg[++nn] = t;
}
if (nn == 0)
{
cout << "No\n";
continue;
}
cout << "YES\n";
long long prefsum = 0;
for (int i = 1 ; i <= n ; ++i)
{
if (prefsum > 0)
{
prefsum += neg[nn];
cout << neg[nn--] << ' ';
}
else
{
prefsum += pos[np];
cout << pos[np--] << ' ';
}
}
cout << '\n';
}
return 0;
}
E|Multitest Generator
Brief: 定义test: 数列的第一个数是长度-1，multitest: 数列第一个数是能将后面的数划分成test的数量。给出一列数，问对于 \(i\in[1, n-1]\) ，最少修改多少个数使得数列 \(\{a_i, a_{i+1},\dots, a_n\}\) 为 multitest.
Data: \(T\leq 300000\), \(2 \leq n\leq 300000\), \(\sum n_i\leq 30000\).
Solution: 【dp】
Observation 1: 答案只可能是 \(0,1,2\), 这一点可以从样例得到启发。原因是只需要修改第一个数为 \(1\), 第二个数为 \(n-2\) 则一定可以使其成为 multitest;
Observation 2: 判断为 \(0\) 是容易的，从后往前考虑，同时维护链（test）是否能覆盖完整个序列，如果可以，计算链的长度。假如可以覆盖并且 \(a_i\) 等于test的个数, 那么答案为 \(0\).
Observation 3: 现在只需要考虑何时为 \(1\).
(1) 可以覆盖，则只需更改第一个数为test数量；
(2) 不能覆盖，那么只需求出最大可能的test数，小于该值的也一定可行，因为可以修改第二个值，使得其多覆盖任意多个test。那么问题变为如何计算修改一次后最大可能的test数。考虑 dp，如果修改第二个数，test数量为之后可覆盖的最长链+1；如果不修改第二个数，答案为 dp[a[i] + i + 1] + 1.取 max 即可。和第一个数比较大小，若第一个数小于等于这个数，那么答案为 \(1\),否则为 \(2\).
Review: -
State: AC.
Code:
#define Justanaaaaame
#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 300010
int a[MAXN];
int go[MAXN];
bool able[MAXN];
int len[MAXN];
int dp[MAXN]; // 第 i 位后修改1次的最长链
int ans[MAXN];
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
memset(able, 0, sizeof(bool) * (n+5));
memset(len, 0, sizeof(int) * (n+5));
memset(dp, 0, sizeof(int) * (n+5));
for (int i = 1 ; i <= n ; ++i)
{
cin >> a[i];
go[i] = i + a[i] + 1;
if (go[i] > n + 1)
go[i] = n + 2;
}
able[n + 1] = true;
int maxlen = 0;
for (int i = n ; i ; --i)
{
able[i] = able[go[i]];
len[i] = len[go[i]] + 1;
if (able[i])
maxlen = max(maxlen, len[i]);
dp[i] = max(dp[go[i]] + 1, maxlen + 1);
}
for (int i = n - 1 ; i ; --i)
{
if (able[i + 1])
{
if (a[i] == len[i + 1])
ans[i] = 0;
else
ans[i] = 1;
}
else
{
if (dp[i + 1] >= a[i])
ans[i] = 1;
else
ans[i] = 2;
}
}
for (int i = 1 ; i < n ; ++i)
cout << ans[i] << ' ';
cout << '\n';
}
}
F|Gifts from Grandfather Ahmed
State: 咕咕咕