Codeforces Round 862 (Div. 2) A-E
题目链接：https://codeforces.com/contest/1805
A - We Need the Zero
解题思路：异或没啥好说的
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
using ull = unsigned long long;
const int mx = 3e5 + 10;
const int mod = 1e9 + 7;int a[mx], ans[mx];
int vis[mx], ma[mx];
int n;int main() {int t;scanf("%d", &t);auto solve = [](vector <int> &ans, int m) {};while (t--) {scanf("%d", &n);int sum = 0;for (int i=1;i<=n;i++) {scanf("%d", a + i);sum ^= a[i];}if (n&1)printf("%d\\n", sum);else {puts(sum==0?"0":"-1");}}return 0;
}B - The String Has a Target
解题思路：贪心找到最后一个最小的数交换即可
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
using ull = unsigned long long;
const int mx = 3e5 + 10;
const int mod = 1e9 + 7;char a[mx];
int n;int main() {int t;scanf("%d", &t);auto solve = [](vector <int> &ans, int m) {};while (t--) {scanf("%d", &n);scanf("%s", a+1);int mi = 200, p;for (int i=1;i<=n;i++) {if (a[i] <= mi) {p = i;mi = a[i];}}printf("%c", a[p]);for (int i=1;i<p;i++)printf("%c", a[i]);for (int i=p+1;i<=n;i++)printf("%c", a[i]);puts("");}return 0;
}C - Place for a Selfie
解题思路：合并两式就得到 a*x^2 + (b-k)*x + c = 0，那么根据求根公式，直线和抛物线没有交点的情况就是没有跟的情况，也就是(b-k)^2 < 4ac。abc都知道，去掉平方讨论一下然后就二分找一下k就可以了。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
using ull = unsigned long long;
const int mx = 3e5 + 10;
const int mod = 1e9 + 7;char a[mx];
int n, m;
set <int> st;int main() {int t;scanf("%d", &t);auto solve = [](vector <int> &ans, int m) {};while (t--) {scanf("%d%d", &n, &m);st.clear();for (int i=1;i<=n;i++) {int v;scanf("%d", &v);st.insert(v);}for (int i=1;i<=m;i++) {int a,b,c;scanf("%d%d%d", &a, &b, &c);if (c <= 0) {puts("no");continue;}int val = ceil(sqrt(4.0 * a * c));auto it1 = st.upper_bound(b - val);if (it1 != st.end() && *it1 <= b) {puts("yes");printf("%d\\n", *it1);continue;}auto it2 = st.lower_bound(b);if (it2 != st.end() && *it2 < val + b) {puts("yes");printf("%d\\n", *it2);continue;}puts("no");}}return 0;
}D - A Wide, Wide Graph
解题思路：首先需要证明，最大长度大于等于K的点一定会是联通的，最大长度小于K的点一定是个孤立的点。这个看似不好证明，实际用图的直径就可以证明，假设我们已经知道了图的直径的两个端点u,v，那么任意一点x他的最长长度一定是到达u或者v的路径，因为如果不是，那么u,v就不是图直径的两个端点，可以自己画图证明一下。那么就证明了大于等于K的点一定会是联通的。所以我们求图的直径后就知道了每个点的最长长度是多少，那么每个K的结果自然也就知道了。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
using ull = unsigned long long;
const int mx = 1e5 + 10;
const int mod = 1e9 + 7;char a[mx];
int n, m;
vector <int> vec[mx], link;
int ma = 0, x, y;
int dep[mx], loof[mx];
int dis[mx];
bool vis[mx];void find_max(int u, int fa)
{loof[u] = u;int temp_ma = 0, temp_x= u;for (int v: vec[u]) {if (v == fa)continue;find_max(v, u);if (dep[u] < dep[v] + 1) {dep[u] = dep[v] + 1;loof[u] = loof[v];}int new_val = dep[v] + temp_ma + 1 + (temp_x != u);if (new_val > ma) {ma = new_val;x = loof[v];y = temp_x;}if (dep[v] > temp_ma) {temp_ma = dep[v];temp_x = loof[v];}}
}bool find_link(int u, int fa)
{if (u == y)return 1;for (int v: vec[u]) {if (v == fa)continue;if (find_link(v, u)) {link.push_back(v);return 1;}}return 0;
} void dfs(int u, int v)
{vis[u] = 1;dis[u] = v;for (int son: vec[u]) {if (vis[son])continue;dfs(son, v + 1);}
}int main() {auto solve = [](vector <int> &ans, int m) {};int n;scanf("%d", &n);for (int i=1;i<n;i++) {int u,v;scanf("%d%d", &u, &v);vec[u].push_back(v);vec[v].push_back(u);}find_max(1, -1);find_link(x, -1);link.push_back(x);for (int i=0; i<link.size(); i++) {dis[link[i]] = max(i, (int)link.size() - 1 - i);vis[link[i]] = 1;//cout << link[i] << " ";}//cout << endl;for (int v: link) {dfs(v, dis[v]);}sort(dis + 1, dis + 1 + n);for (int i=1;i<=n;i++) {int d = lower_bound(dis+1, dis+1+n, i) - dis - 1;printf("%d ", d + (d != n));}return 0;
}E - There Should Be a Lot of Maximums
解题思路：这就是启发式合并暴力拆分求答案，时间复杂度O(n*logn*logn)，可以优化常数或者到n*logn但是也能过，没必要。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
using ull = unsigned long long;
const int mx = 1e5 + 10;
const int mod = 1e9 + 7;vector <int> vec[mx];
map <int,int> mp[mx], mp1[2];
set <int> st[2] = {{0}, {0}};
int siz[mx], son[mx];
int a[mx], ans[mx];void dfs(int u,int fa)
{siz[u] = 1;for (int v: vec[u]) {if (v == fa)continue;dfs(v, u);siz[u] += siz[v];if (siz[son[u]] < siz[v])son[u] = v;}
}void update(int u, int fa, bool val)
{mp1[val][a[u]]++;mp1[val^1][a[u]]--;if (mp1[val][a[u]] == 2)st[val].insert(a[u]);if (mp1[val^1][a[u]] == 1)st[val^1].erase(a[u]);for (int v: vec[u]) {if (v == fa)continue;update(v, u, val);}
}void dsu(int u, int fa, bool fl)
{for (int v: vec[u]) {if (v == fa || v == son[u])continue;dsu(v, u, 0);}if (son[u]) dsu(son[u], u, 1);for (int v: vec[u]) {if (v == fa || v == son[u])continue;update(v, u, 1);}mp1[1][a[u]]++;mp1[0][a[u]]--;if (mp1[1][a[u]] == 2)st[1].insert(a[u]);if (mp1[0][a[u]] == 1)st[0].erase(a[u]);ans[mp[u][fa]] = max(*(--st[0].end()), *(--st[1].end()));if (!fl) update(u, fa, 0);
}int main() {auto solve = [](vector <int> &ans, int m) {};int n;scanf("%d", &n);for (int i=1;i<n;i++) {int u,v;scanf("%d%d", &u, &v);vec[u].push_back(v);vec[v].push_back(u);mp[u][v] = mp[v][u] = i;}for (int i=1;i<=n;i++) {scanf("%d", a+i);mp1[0][a[i]]++;if (mp1[0][a[i]] == 2)st[0].insert(a[i]);}dfs(1, 0);dsu(1, 0, 1);for (int i=1;i<n;i++)printf("%d\\n", ans[i]);return 0;
}