A. 欧几里得的噩梦
首先发现第一问所询问的异或值数量就是所求的第二问的最小集合的元素个数次方
因为除去集合里的任一一个元素，其中若干个元素异或之后的集合就不可能为原来的集合（否则不满足最小条件）
然后对线性基的插入过程进行一个模拟
\(\cdots\cdots\) 扑街是肯定的
注意到
给定的集合的二进制表示下最多只有两位为 1。
考虑并查集，假如只有 \(x\) 位为 \(1\) ，那么就和虚点 \(m+1\) 连边，否则给 \(x\) 和 \(y\) 连边
容易发现此时并查集内所维护的其实就是目前的连通块中选若干个数能表示出的集合，当发现此时 x 和 y 已经联通，那么就不插入。由于要维护字典序最小，那么其实边读边插就可以了。
贺一下BE的
#include <set>
#include <cstdio>
#include <algorithm>
#define Reg register
#define ll long long
using namespace std;
const int maxn=500100,mod=1e9+7;
int n,m,tot,f[maxn];
int ans[maxn];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s*w;
}
inline ll qpow(ll A,ll B){
ll Ass=1;
while(B){
if(B&1) Ass=A*Ass%mod;
A=A*A%mod;
B>>=1;
}
return Ass;
}
inline int finds(int x){
if(x!=f[x]) f[x]=finds(f[x]);
return f[x];
}
inline void Merge(int x,int y){
x=finds(x),y=finds(y);
f[y]=x;
}
int main(){
n=read(),m=read();
for(Reg int i=1;i<=m+1;++i) f[i]=i;
for(Reg int i=1;i<=n;++i){
int opt=read(),x=read();
if(opt==1){
if(finds(x)!=finds(m+1)){
Merge(x,m+1);
ans[++tot]=i;
}
}else{
int y=read();
if(finds(x)!=finds(y)){
Merge(x,y);
ans[++tot]=i;
}
}
}
printf("%lld %d\n",qpow(2,tot),tot);
for(Reg int i=1;i<=tot;++i) printf("%d ",ans[i]);
return 0;
}
B. 清扫
设某一颗子树中的根节点为 \(u\) ，子树权值和为 \(sum\) ，子树最大权值为 \(maxx\) ，那么稍微推导即可知以下三个合法条件：
\[\begin{cases} sum\geqslant a_u\\ sum\leqslant 2a_u\\ maxx\leqslant a_u \end{cases}\]不满足其中之一即可输出无解，满足的话就需要再考虑 \(a_u\) 在子树删除完之后应该是什么。
设子树之间删除次数为 \(x\) ，子树之外删除次数为 \(y\) ，稍微推导即可知以下一个二元一次方程组：
所以能推出来 \(a_u=2a_u−sum\)
最后判断 $a_{root} 是否为 \(0\) 即可。
注意为避免漏掉叶节点，应选择度大于 \(1\) 的点作为根节点，但此时 \(n=2\) 的情况下需要一个小小的特判。
点击查看代码
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000;
struct Edge{
int pre,to;
}edge[WR<<1];
int head[WR],tot;
int n,rt;
int a[WR],dp[WR];
int ipt[WR];
bool leaf[WR],flag=true;
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<1)+(s<<3)+ch-'0';
ch=getchar();
}
return s*w;
}
void add(int u,int v){
edge[++tot].pre=head[u];
edge[tot].to=v;
head[u]=tot;
}
void dfs(int u,int root){
for(int i=head[u];i;i=edge[i].pre){
int v=edge[i].to;
if(v==root) continue;
dfs(v,u);
if(!flag) return;
if(dp[v]>a[u]){
flag=false;
return;
}
dp[u]-=dp[v];
if(dp[u]<0){
flag=false;
return;
}
}
if(dp[u]>a[u]||dp[u]<0){
flag=false;
return;
}
}
signed main(){
n=read();
for(int i=1;i<=n;i++) a[i]=read();
if(n==2){
if(a[1]==a[2]) printf("YES\n");
else printf("NO\n");
return 0;
}
for(int i=1;i<n;i++){
int u=read(),v=read();
add(u,v);add(v,u);
ipt[u]++,ipt[v]++;
}
for(int i=1;i<=n;i++){
if(ipt[i]==1) leaf[i]=true,dp[i]=a[i];
else rt=i,dp[i]=a[i]*2;
}
dfs(rt,0);
if(!flag||dp[rt]!=0) printf("NO\n");
else printf("YES\n");
return 0;
}
C. 购物
代码不超过 \(40\) 行
结论：将 \(a_i\) 从小到大排序之后，求出序列中的前缀和 \(sum_i\) ，若存在 \(\large\lceil \frac{a_i}{2} \rceil > sum_{i−1}\)，那么 \([sum_{i−1},\lceil \frac{a_i}{2}\rceil ]\) 的范围内无贡献。
首先我们显然不能用大于 \(a_i\) 的数来找属于这一范围的价值和，那样只会比 \(\lceil \frac{a_i}{2}\rceil\) 更大，此时找小于 \(a_i\) 的数也只会比 \(\lceil \frac{a_i}{2}\rceil\) 更小——这段区间不会产生贡献
相应的，也能证明 \(\large sum_i>\lceil \frac{a_i}{2}\rceil\) 的情况下的答案区间一定是连续的
那么实现就比较显然了，先判断是否存在上述无贡献的区间，之后将区间拓展到 \(sum_i\) 即可
点击查看代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000;
int n;
int a[WR];
int sum;
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<1)+(s<<3)+ch-'0';
ch=getchar();
}
return s*w;
}
signed main(){
n=read();
for(int i=1;i<=n;i++) a[i]=read(),sum+=a[i];
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
int l=a[i-1],r=ceil(a[i]/2.0);
if(l<r) sum-=r-l-1;
a[i]+=a[i-1];
}
printf("%lld\n",sum);
return 0;
}
D. ants
回滚莫队板子
然鹅我还不会回滚莫队
放个 \(50\) 分的跑路
点击查看代码
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<cmath>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=101000;
struct SegmentTree{
int lson,rson;
int l,r,len,val;
}tree[WR<<3];
struct Ask{
int l,r,num;
}query[WR];
int n,m,l,r;
int a[WR],BL;
int cnt[WR],blng[WR];
int ans[WR];
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-48;
ch=getchar();
}
return s*w;
}
void pushup(int k){
tree[k].l=tree[k<<1].l;
tree[k].r=tree[k<<1|1].r;
if(tree[k<<1].l==tree[k<<1].len) tree[k].l+=tree[k<<1|1].l;
if(tree[k<<1|1].r==tree[k<<1|1].len) tree[k].r+=tree[k<<1].r;
tree[k].val=max(tree[k<<1].r+tree[k<<1|1].l,max(tree[k<<1].val,tree[k<<1|1].val));
}
void build(int k,int l,int r){
tree[k].lson=l,tree[k].rson=r;
if(l==r){
tree[k].len=1;
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
tree[k].len=tree[k<<1].len+tree[k<<1|1].len;
}
void modify(int k,int pos,int val){
if(tree[k].lson==tree[k].rson){
tree[k].l=val;
tree[k].r=val;
tree[k].val=val;
return;
}
int mid=(tree[k].lson+tree[k].rson)>>1;
if(pos<=mid) modify(k<<1,pos,val);
else modify(k<<1|1,pos,val);
pushup(k);
}
bool cmp(Ask x,Ask y){
if(blng[x.l]==blng[y.l]) return x.r<y.r;
return blng[x.l]<blng[y.l];
}
signed main(){
n=read(),m=read();
BL=n/sqrt(m)+1;
for(int i=1;i<=n;i++) a[i]=read(),blng[i]=(i-1)/BL+1;
build(1,1,n);
for(int i=1;i<=m;i++){
query[i].l=read(),query[i].r=read();
query[i].num=i;
}
sort(query+1,query+1+m,cmp);
l=1,r=0;
for(int i=1;i<=m;i++){
while(l<query[i].l){cnt[a[l]]--;if(!cnt[a[l]]) modify(1,a[l],0);l++;}
while(l>query[i].l){l--;cnt[a[l]]++;if(cnt[a[l]]==1) modify(1,a[l],1);}
while(r<query[i].r){r++;cnt[a[r]]++;if(cnt[a[r]]==1) modify(1,a[r],1);}
while(r>query[i].r){cnt[a[r]]--;if(!cnt[a[r]]) modify(1,a[r],0);r--;}
ans[query[i].num]=tree[1].val;
}
for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
return 0;
}