传送门:CF

前提提要:本场中的E题是个线段树合并的板子题,或者可以使用莫队来维护,但是近期思维题打多了导致这些ds问题根本打不来了,留着以后复建之后再补吧

A题:A. We Need the Zero

因为异或是会相互抵消的.所以偶数次异或等于0,奇数次异或才会产生作用.所以当我们的n为偶数时,我们无论怎么操作,对原数列的异或和是不会产生影响的.所以此时看原数列是否是0即可.当n为奇数时,我们n次异或之后会剩下来一个x,此时我们只要满足这个x和我们原数列的异或和相等即可.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int a[maxn];
int main() {int T=read();while(T--) {int n=read();int sum_xor;for(int i=1;i<=n;i++){a[i]=read();if(i==1) sum_xor=a[i];else sum_xor^=a[i];} if(n&1) {cout<<sum_xor<<endl;}else {if(sum_xor==0) {cout<<"0"<<endl;}else {cout<<-1<<endl;}}}return 0;
}

B题:The String Has a Target

发现我们必须进行一次操作,那么我们这道题就变得很简单了.我们只要挑出原字符串中最小的那一个字符,然后将其放在一个位即可.注意我们也可以挑第一位的字符.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int main() {int T=read();while(T--) {int n=read();string s;cin>>s;char maxx='z';for(int i=0;i<s.length();i++) maxx=min(maxx,s[i]);cout<<maxx;int pos;for(int i=s.length()-1;i>=0;i--) {if(s[i]==maxx) {pos=i;break;}}for(int i=0;i<s.length();i++) {if(i!=pos) {cout<<s[i];}}cout<<endl;}return 0;
}

C题:C. Place for a Selfie

算是一道简单的计算几何的题目了.
考虑抛物线和直线相交,使用高中数学的知识,我们发现$k=(a{x}^2+bx+c)/x$有解,也就是$k=ax+b+c/x$有交点,我们将左式看做一个函数(也就是一条横线),右式看做一个函数,因为a是大于0的所以右式的图像与c的正负有关.当$c<=0$时,我们发现无论如何都有交点.当$c>0$时,我们只需要找到一个k,满足$(\sqrt{2ac}+b)>k>(-\sqrt{2ac}+b)$即可,对于这个,我们可以使用二分来进行查找.在二分的时候注意边界问题(具体可以参考下列代码)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
vector<int>k;
struct Quxian{double a,b,c;
}qx[maxn];
int ans[maxn];
int main() {int T=read();while(T--) {int n=read(),m=read();k.clear();for(int i=1;i<=n;i++) {int K=read();k.push_back(K);}sort(k.begin(),k.end());for(int i=1;i<=m;i++) {qx[i].a=read();qx[i].b=read();qx[i].c=read();}for(int i=1;i<=m;i++) {if(qx[i].c<=0) {cout<<"NO"<<endl;}else {double num1=2*__builtin_sqrt((double)qx[i].a*qx[i].c)+(double)qx[i].b;double num2=-2*__builtin_sqrt((double)qx[i].a*qx[i].c)+(double)qx[i].b;auto pos=lower_bound(k.begin(),k.end(),num1);if(pos==k.end()) {if(k.back()>num2) {cout<<"YES"<<endl;cout<<k.back()<<endl;}else {cout<<"NO"<<endl;}continue;}if(pos==k.begin()) {cout<<"NO"<<endl;continue;}if(*(pos-1)>num2) {cout<<"YES"<<endl;cout<<*(pos-1)<<endl;}else {cout<<"NO"<<endl;}}}}return 0;
}

D题:A Wide, Wide Graph

诶,算是一道思维题吧.找找规律,我们就会发现这道题和树的直径有关.然后我们猜想一下就与树的直径有关.
关于树的直径:与树上任意一点x最远的点一定是直径的两端
诶此时我们就会发现,假设一个点可能与另外一个点联通,那么因为它到直径上的点的距离是最远的,**所以这个点必然和直径的一端是相连的.**又因为直径上的两端点的距离必然是树上两点之间距离最长的.所以只要还有点相互联通,这两个点必然是联通的.此时我们就会发现,只要有点联通,那么这些点必然是与直径两端点联通成为一个联通分量
此时本题也就不难解决了,对于每一个点,考虑记录这个点单独存在的最小k值,这个k值显然就是到直径上两个端点的距离最大值.然后我们枚举每一个k值,计算出当前k值有多少个点单独存在,那么剩下的点显然是相互联通的(因为他们都与直径端点联通).所以此时答案就是单独存在的点+1.当然当所有点都单独存在时,答案为n

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
vector<int>tree[maxn];int dep[maxn],dep1[maxn],dep2[maxn];
void dfs(int u,int per_u,int Dep[]) {for(int i=0;i<tree[u].size();i++) {int v=tree[u][i];if(v==per_u) continue;Dep[v]=Dep[u]+1;dfs(v,u,Dep);}
}
int max_dis[maxn];int sum[maxn];
int main() {int n=read();for(int i=1;i<=n-1;i++) {int u=read();int v=read();tree[u].push_back(v);tree[v].push_back(u);}dfs(1,0,dep);int maxx=-int_INF;for(int i=1;i<=n;i++) {maxx=max(maxx,dep[i]);}int node1;for(int i=1;i<=n;i++) {if(maxx==dep[i]) {node1=i;break;}}dfs(node1,0,dep1);maxx=-int_INF;for(int i=1;i<=n;i++) {maxx=max(maxx,dep1[i]);} int node2;for(int i=1;i<=n;i++) {if(maxx==dep1[i]) {node2=i;break;}}dfs(node2,0,dep2);for(int i=1;i<=n;i++) {max_dis[i]=max(dep1[i],dep2[i]);sum[max_dis[i]]++;}for(int i=1;i<=n;i++) sum[i]+=sum[i-1];for(int i=1;i<=n;i++) {cout<<min(sum[i-1]+1,n)<<" ";}return 0;
}