补题链接：Codeforces Round 1050 (Div. 4)
文章目录
A. Sublime Sequence
如果 n n n 为奇数，输出 x x x；否则输出 0 0 0.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010, M = N * 2, mod = 1e9 + 7;
ll n, x;
void solve()
{
cin >> x >> n;
if (n & 1) cout << x << endl;
else cout << 0 << endl;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
ll Case = 1;
cin >> Case;
while (Case--) solve();
return 0;
}
B. Lasers
输出 n + m n + m n+m.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010, M = N * 2, mod = 1e9 + 7;
ll n, m, x, y;
ll a[N], b[N];
void solve()
{
cin >> n >> m >> x >> y;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i];
cout << n + m << endl;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
ll Case = 1;
cin >> Case;
while (Case--) solve();
return 0;
}
C. Pacer
记录前一次的位置 p r e pre pre 和时间点 c u r cur cur，设 d d d 为 a − c u r a - cur a−cur，对答案的贡献最大为 d d d 或 d − 1 d - 1 d−1，取值取决于状态的改变和 d d d 的奇偶性。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010, M = N * 2, mod = 1e9 + 7;
ll n, m;
void solve()
{
cin >> n >> m;
ll res = 0, cur = 0, pre = 0, a, b;
while (n--)
{
cin >> a >> b;
ll d = a - cur;
if (b != pre) res += (d & 1) ? d : d - 1;
else res += (d & 1) ? d - 1 : d;
cur = a;
pre = b;
}
res += m - a;
cout << res << endl;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
ll Case = 1;
cin >> Case;
while (Case--) solve();
return 0;
}
D. Destruction of the Dandelion Fields
如果存在奇数，加上所有偶数，并从大到小加上一半的奇数；否则输出 0 0 0.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010, M = N * 2, mod = 1e9 + 7;
ll n;
void solve()
{
cin >> n;
vector<ll> even, odd;
for (int i = 1; i <= n; i++)
{
ll t;
cin >> t;
if (t & 1) odd.push_back(t);
else even.push_back(t);
}
if (odd.size() == 0)
{
cout << 0 << endl;
return;
}
ll res = 0;
for (auto i : even) res += i;
sort(odd.begin(), odd.end());
for (int i = odd.size() - 1; i >= (int)(odd.size() / 2); i--)
res += odd[i];
cout << res << endl;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
ll Case = 1;
cin >> Case;
while (Case--) solve();
return 0;
}
E. Split
使用双指针，从 1 1 1 到 n n n 枚举右指针 r r r，同时记录最小的左指针，满足 [ l , r ] [l, r] [l,r] 区间内每个数的数量不超过上界，每次在答案上加上 r − l + 1 r - l + 1 r−l+1.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010, M = N * 2, mod = 1e9 + 7;
ll n, k;
ll a[N];
ll up[N], cnt[N];
void solve()
{
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i], up[i] = cnt[i] = 0;
bool flag = true;
for (int i = 1; i <= n; i++) up[a[i]]++;
for (int i = 1; i <= n; i++)
if (up[i] % k != 0)
{
flag = false;
break;
}
else up[i] /= k;
if (!flag)
{
cout << 0 << endl;
return;
}
ll l = 1, res = 0;
for (int i = 1; i <= n; i++)
{
if (cnt[a[i]] + 1 > up[a[i]])
{
while (l < i && a[l] != a[i]) cnt[a[l]]--, l++;
cnt[a[l]]--, l++;
}
cnt[a[i]]++;
res += i - l + 1;
}
cout << res << endl;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
ll Case = 1;
cin >> Case;
while (Case--) solve();
return 0;
}
F. Gravity Falls
每次从第 k k k 个位置找到字典序最小的数组，然后将该数组的所有数加入答案，更新 k k k 为数组长度 + 1.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010, M = N * 2, mod = 1e9 + 7;
ll n;
ll s[N];
void solve()
{
cin >> n;
vector<vector<ll>> a(n + 1);
set<ll> have;
for (int i = 1; i <= n; i++) have.insert(i);
ll mx = 0;
for (int i = 1; i <= n; i++)
{
cin >> s[i];
for (int j = 0; j < s[i]; j++)
{
ll t;
cin >> t;
a[i].push_back(t);
}
mx = max(mx, s[i]);
}
vector<ll> res;
for (int i = 0; i < mx; i++)
{
auto tmp = have;
ll id, mn = LLONG_MAX;
for (auto j : tmp)
{
if (s[j] < i + 1) have.erase(j);
else if (a[j][i] < mn)
{
mn = a[j][i];
id = j;
}
else if (a[j][i] == mn)
{
bool flag = true, Equal = true;
for (int k = i; k < min(s[j], s[id]); k++)
{
if (a[j][k] != a[id][k]) Equal = false;
if (a[j][k] > a[id][k])
{
flag = false;
break;
}
else if (a[j][k] < a[id][k]) break;
}
if (Equal && s[j] > s[id]) flag = false;
if (flag) id = j;
}
}
for (int j = i; j < s[id]; j++) res.push_back(a[id][j]);
have.erase(id);
i = s[id] - 1;
}
for (auto i : res) cout << i << ' ';
cout << endl;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
ll Case = 1;
cin >> Case;
while (Case--) solve();
return 0;
}
G. Farmer John’s Last Wish
在 O ( n n ) O(n \sqrt n) O(nn) 的时间复杂度内求出第 i i i 个位置前所有数的所有因子的个数，该位置的答案是数量小于 i i i 的因子的数量最大值。使用 s e t set set 的时间复杂度会达到 O ( n n l o g n ) O(n \sqrt n log n) O(nnlogn)，会超时。
技巧：第 i i i 个位置的答案一定大于等于前一个位置的答案，如果答案比前一个位置大，取到答案的因子一定是 a [ i − 1 ] a[i - 1] a[i−1] 或 a [ i ] a[i] a[i] 的因子。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 200010, M = N * 2, mod = 1e9 + 7;
int n;
int a[N];
int mp[N];
vector<int> fac[N + 10];
void init()
{
for (int i = 1; i <= N; i++)
for (int j = 1; j * j <= i; j++)
if (i % j == 0)
{
if (j != 1) fac[i].push_back(j);
if (j * j != i) fac[i].push_back(i / j);
}
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], mp[i] = 0;
vector<int> res;
int mx = 0;
for (int i = 1; i <= n; i++)
{
for (auto j : fac[a[i]]) mp[j]++;
for (auto j : fac[a[i]])
if (mp[j] != i)
mx = max(mx, mp[j]);
for (auto j : fac[a[i - 1]])
if (mp[j] != i)
mx = max(mx, mp[j]);
res.push_back(mx);
}
for (auto i : res) cout << i << ' ';
cout << endl;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
init();
int Case = 1;
cin >> Case;
while (Case--) solve();
return 0;
}