咕咕咕
C：普及组难度的题
D：给定$a_{1\cdots n}$，求有多少$1\leq l\leq r\leq n$满足$x_l+\cdots+x_r=x_l\text^\cdots\text^x_r$
因为异或是不进位加法，所以枚举左端点暴力拓展右端点即可，一旦发生进位就break即可，对$0$要特殊处理
#includetypedef long long ll;int a[200010],len[200010];int main(){ int n,i,j; ll ans,x; scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",a+i); for(i=n;i>0;i--){ if(a[i]==0)len[i]=len[i+1]+1; } ans=0; for(i=1;i<=n;i++){ x=0; for(j=i;j<=n;){ if(a[j]==0){ ans+=len[j]; j+=len[j]; }else{ if(x&a[j])break; x^=a[j]; ans++; j++; } } } printf("%lld",ans);}
E：给定$a_{1\cdots n},k,q$，你要进行$q$次操作，每次操作可以选择一个长度为$k$的区间并删掉区间最小值，最小化删掉的数的极差
枚举删掉的最小值$x$，那么可以删掉的数必须处在连续$k$个$\geq x$的数中，对每个长度为$l(l\geq k)$的所有数都$\geq x$的极长区间排序后取前$l-k+1$小的数，最后把这些数选出来排序取第$q$小作为删除的最大值更新答案即可
#include#include using namespace std;const int inf=2147483647;int a[2010],t[2010],al[2010],n,k,q;int work(int x){ int i,j,s,M; s=M=0; for(i=1;i<=n+1;i++){ if(a[i]>=a[x]){ if(s==0)s=i; }else if(s){ if(i-s>=k){ for(j=s;j
F：给定一个简单连通无向图，每个点有$a_i,b_i$，一个人可以带$w$的钱从任意$w\geq a_x$的$x$开始走，每走一条边要求目标节点$v$满足$w\geq a_v$，他也可以选择在$x$捐赠$b_i$，问捐赠完所有节点至少要多少钱
首先我们把$a_i$变成$\max(a_i-b_i,0)$并加一条限制：在$x$捐赠后也要满足$w\geq a_x$，容易看出这是不会改变答案的
存在一个最优解使得任意节点在被捐赠后不会再被经过，因为如果这样我们可以延迟捐赠，这并不会让答案变大
假设$x$有最大的$a_x$且删掉$x$后原图被分成许多连通块$G_{1\cdots k}$，那么存在这样一种最优解：先捐$G_{1\cdots i-1},G_{i+1\cdots k}$，再捐$x$，再进入$G_i$捐赠且以后都不再走出$G_i$
假如存在$w\in G_i$且先捐$w$后捐$x$，那么我们可以先不捐$w$而是在捐$x$后立刻走到$w$并捐$w$，因为$x$有最大的$a_x$，所以这总是能实现的，并且不会让答案变大
到这里思路就很清晰了，我们每次找出最大的$a_x$，把$x$作为根并递归进$G_{1\cdots k}$建出一棵树，在这棵树上的最优解就对应着原图的最优解
考虑DP，因为答案肯定$\geq\sum b_i$，不妨设$s_i=\sum\limits_{j\in\text{subtree}(i)}b_j$，$f_i$表示要比$s_i$多带多少钱，那么转移就是$f_x\mathop\longleftarrow\limits^\min\max(f_y,a_x-s_y)$
首先在$x$捐完除了$y$以外的所有子树后，带的钱肯定要$\geq a_x$
如果$f_y+s_y\gt a_x$，那么要带更多钱（这同时保证了即将从$x$到$y$的时候带的钱$\geq a_x$），也就是直接按$y$的限制，所以一开始要带$s_x+f_y$的钱，这样到$y$就有$s_y+f_y$的钱，而这也是捐完子树$y$的最小值
否则不需要考虑$y$的限制，因为剩下的钱肯定够了，所以要带$s_x+a_x-s_y$的钱，这样捐完$x$后刚好剩下$a_x$，是足够捐完子树$y$的
#include#include using namespace std;typedef long long ll;struct node{ int x,v; node(int a=0,int b=0){x=a;v=b;}}p[100010];int h[100010],nex[200010],to[200010],a[100010],b[100010],fa[100010],M;ll s[100010],f[100010];bool v[100010];void add(int a,int b){ M++; to[M]=b; nex[M]=h[a]; h[a]=M;}bool operator<(node a,node b){return a.v
咕咕咕
