Codeforces Round 969 (Div. 2)题解A-E
Codeforces Round 969 (Div. 2)
神奇的一场，感觉整体不是很难，狠狠的上了一波大分。
这场也算是这个暑假的最后一场了
整个暑假不是在渡劫就是在渡劫的路上，中间那个紫名还是回滚给加上的，神奇的比赛，每次都能很快打到渡劫的分数，然后不出意料的渡劫失败。不懂
再接再励吧，总会渡劫成功的。
A. Dora's Set
呃，每次在l-r的范围内删除互相互质的三个数，不难发现相连的奇数偶数奇数 互相互质，似乎是最好的选取方式，因为每次最多选一个偶数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define debug(x) cout<<#x<<" = "<<x<<endl
#define sz(a) ((int)a.size())
const int mod = 998244353, N = 505, G = 3;
void solve() {
ll l, r,ans=0;
cin >> l >> r;
if(l%2==1)
l--;
cout << ans+(r - l+1) / 4 << endl;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0),cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
B. Index and Maximum Value
呃，这个题一开是看错了，以为是让l<=i<=r的数操作，然后白忙活半天搞了个线段树样例错了才发现。
言归正转，给一个数组，每次可以选l,r 然后让\(a_i\)的数+1或-1，然后每次操作，输出当前数组最大值。
不难发现，只有最大值+1或者-1，这个数组的最大值才会变化。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define debug(x) cout<<#x<<" = "<<x<<endl
#define sz(a) ((int)a.size())
const int mod = 998244353, N = 505, G = 3;
void solve() {
ll n,ma=0,m;
cin >> n>>m;
for (ll i = 1,x; i <= n;i++){
cin >> x;
ma = max(ma, x);
}
for (int i = 1; i<= m;i++){
char op;
ll l, r;
cin >> op >> l >> r;
if(ma>=l&&ma<=r){
if(op=='+')
ma++;
else
ma--;
}
cout << ma << ' ';
}
cout << endl;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0),cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
C. Dora and C++
呃，可以任意次的将\(a_i\)+a或者+b,让最小化数组最大值和最小值的差。
呃老生常谈了，牛客多校好像也有类似的。
先说结论，如果对于一个数字+a,-a,+b,-b任意次我们可以得到\(a_i+kgcd(a,b)\)，虽然这个题只能+a,+b但是让求的是数组最大值-最小值，我们让其他的数字相加，就等于相对来说让剩下的数字相减。
所以数组可以化简成\(a_i\%gcd(a,b)\)
然后贪心一下，就可以了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define debug(x) cout << #x << " = " << x << endl
#define sz(a) ((int)a.size())
const int mod = 998244353, N = 2e5 + 10, G = 3;
ll A[N];
void solve()
{
ll n, a, b;
cin >> n >> a >> b;
ll cc = __gcd(a, b);
for (int i = 1; i <= n; i++)
{
cin >> A[i];
A[i] %= cc;
}
sort(A + 1, A + 1 + n);
n = unique(A + 1, A + 1 + n) - A - 1;
ll ans = A[n] - A[1];
for (int i = 2; i <= n; i++)
{
ans = min(A[i - 1] + cc - A[i] , ans);
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
D. Iris and Game on the Tree
这个题猛地一看会很难，但是细推一下还是挺简单的
我们可以发现对于010和101和1001或者0010000都是01串和10串一样，可以看到连续的01和单独的01一个效果，我们考虑将01压缩，0010001111就变成了0101这样子，发现中间的1 0 的贡献为0，1 0在边界有贡献，
然后左边的0和右边界的1都是贡献01，而左1和右0是10
然后答案就变成 根和叶子不一样的答案数目了。
然后随便码一下
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define debug(x) cout << #x << " = " << x << endl
#define sz(a) ((int)a.size())
const int mod = 998244353, N = 4e5 + 10, G = 3;
vector<int> edge[N];
char a[N];
ll b[2], ans, res;//b[1]是叶子为1的数量，b[0]是叶子为0的数目，ans是叶子为'?'的数目，res是除了叶子和根的其他的可以转移先手的选择
void dfs(int u, int father)
{
int sum = 0;
for (int i = 0; i < edge[u].size(); i++)
{
int v = edge[u][i];
if (v == father)
{
continue;
}
dfs(v, u);
sum++;
}
if (sum == 0)
{
if (a[u] == '?')
ans++;
else if (a[u] == '0')
b[0]++;
else
b[1]++;
}
else
{
if (u != 1 && a[u] == '?')
{
res++;
}
}
}
void solve()
{
int n;
cin >> n;
ans = b[1] = b[0] = res = 0;
for (int i = 1; i <= n; i++)
edge[i].clear();
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
edge[u].pb(v);
edge[v].pb(u);
}
for (int i = 1; i <= n; i++)
cin >> a[i];
dfs(1, 0);
if (a[1] == '?')
{
ll ma = 0;
if (b[1] < b[0])
swap(b[1], b[0]);
ma = max(b[1] + ans / 2, ma);
ma = max(min(b[1], b[0] + 1) + (ans) / 2, ma);
if (res & 1)
ma = max(ma, b[1] + b[0] + ans - ma);
cout << ma << endl;
}
else
{
if (a[1] == '1')
cout << b[0] + (ans + 1) / 2 << endl;
else
cout << b[1] + (ans + 1) / 2 << endl;
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
E. Iris and the Tree
本来速开4题我都准备下班了，E就过了几十个人，然后才知道这场分12，感觉应该是是高手没写才过题人少的，然后进行了一个快速的码，然后发现也不是很难。
呃，我们可以发现他让求\(\sum_{i=1}^{n}Dist(i,(i+1)\%n)\)Dist(i,(i+1)%n),为i到（i+1）%n之间路程最大可能和。
假设如果i到(i+1)%n中间的边都有值了，我们叫这个为活距离，反之叫死距离
然后可以发现加入我们让一个边\(t_x=y\),那么的话，就会让其他不含\(t_x\)的活距离都少y，然后如果x和(x+1)%n之间都有值就放入死距离里面，(x-1+n)%n和x之间都有值就放入死距离里面。
然后我们只需要预处理处理x到(x+1)%n之间有多少个边就可以了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define debug(x) cout << #x << " = " << x << endl
#define sz(a) ((int)a.size())
const int mod = 998244353, N = 2e5+10, G = 3;
vector<int> edge[N];
ll s = 0, ans = 0;
ll dd[N], sum[N], sumw;
void dfs(int u)
{
sum[dd[u]]++;
for (int i = 0; i < edge[u].size(); i++)
{
int v = edge[u][i];
if (i + 1 < edge[u].size())
dd[v] = edge[u][i + 1];
else
dd[v] = dd[u];
dfs(v);
}
}
void solve()
{
ll n, w;
cin >> n >> w;
s = n;
ans = n * w;
sumw = w;
for (int i = 1; i <= n; i++)
{
sum[i] = 1;
dd[i] = 1;
edge[i].clear();
}
for (int i = 2; i <= n; i++)
{
ll x;
cin >> x;
edge[x].pb(i);
}
dfs(1);
sum[1] -= 2;
// debug(sum[1]);
for (int i = 1; i < n; i++)
{
ll x, y;
cin >> x >> y;
sumw -= y;
ans -= (s - 2) * y;
sum[dd[x]]--;
sum[x]--;
if (sum[x] == 0)
{
ans -= sumw;
s--;
}
if (sum[dd[x]] == 0)
{
ans -= sumw;
s--;
}
cout << ans << ' ';
}
cout << endl;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}