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++;elsema--;}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]++;elseb[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;elsecout << 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];elsedd[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;
}
