A
部分分可以分讨/搜索。
这个题长得就很区间 DP。我们假设一个区间被删完，那么最后被删掉的那些数将区间划分为了若干个子区间。每个子区间是独立的，可以直接相加，最终要求剩下的数 and 值不为 $0$ 就行。
于是我们可以定义 $f_{l,r,k}$ 表示区间 $l,r$，最后被删掉的那些数 and 为 $k$ 时的最大操作次数。一种转移方法可以枚举其中第一个最后一次被删的数 $i$，那么 $[l,i-1]$ 是一个子问题，$[i+1.r]$ 是一个子问题。
总复杂度 $O(n^3V)$，看上去存在一个更有复杂度的做法不过出题人没有细想。
#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
re int t=0;re char v=getchar();
while(v<'0')v=getchar();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
return t;
}
int n,m,a[65],f[65][65][65];
inline int calc(re int l,re int r,re int X){
if(~f[l][r][X])return f[l][r][X];
re int s=0,nx=(X==0)?63:X;
for(re int i=l;i<=r;++i)s=max(s,calc(i+1,r,nx&a[i])+calc(l,i-1,63));
return f[l][r][X]=s+(X==0);
}
int main(){
memset(f,-1,sizeof(f)),n=read();
for(re int i=1;i<=n;++i)a[i]=read();
printf("%d",calc(1,n,63));
}B
部分分可以搜索/DP。
我们发现，减小一个数时，当且仅当其比相邻两个数都要小时式子的值才会发生变化，且变化量一定恰好为 $2$，所以，若存在这样的数，直接操作一定最优。
若不存在这样的数，一定存在极长值域相同段满足这个条件。此时使式子变小的方式只能是将这个值域相同连续段中的所有数 $-1$，使答案 $-2$。
可以证明，我们可以每次选择长度最小的满足上述条件的值域连续段。
同时我们发现，删去一个连续段可能产生新的连续段，不过总段数是 $O(n)$ 的，可以直接用优先队列维护。
知道每一段的长度，答案可以看成一个分段函数，直接二分即可。
时间复杂度 $O((n+m)\log n)$。
#include<bits/stdc++.h>
#define re register
#define int long long
using namespace std;
inline int read(){
re int t=0;re char v=getchar();
while(v<'0')v=getchar();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
return t;
}
int n,a[1000002],fa1[1000002],fa2[1000002],tim,W,q,sum;
inline int root1(re int x){return x==fa1[x]?x:fa1[x]=root1(fa1[x]);}
inline int root2(re int x){return x==fa2[x]?x:fa2[x]=root2(fa2[x]);}
inline void Merge(re int x){fa1[root1(x)]=root1(x-1),fa2[root2(x-1)]=root2(x);}
struct node{
int l,r;
bool operator <(const node A)const{return r-l>A.r-A.l;}
};
priority_queue<node>Q;
struct Node{int x,y,z;bool operator <(const Node A)const{return x==A.x?y<A.y:x<A.x;};};
vector<Node>T;
inline void ck(re int x){
re int l=root1(x),r=root2(x);
if(a[l]>a[l-1]&&a[r]>a[r+1])Q.push((node){l,r});
}
inline int Abs(re int x){return x>0?x:-x;}
signed main(){
n=read(),q=read();int ss=0;
for(re int i=1;i<=n;++i)a[i]=read(),ss+=a[i],fa1[i]=fa2[i]=i;fa1[n+1]=fa2[n+1]=n+1;
for(re int i=0;i<=n;++i)sum+=Abs(a[i+1]-a[i]);
a[0]=a[n+1]=-1e18;
for(re int i=2;i<=n;++i)if(a[i]==a[i-1])Merge(i);
for(re int i=1;i<=n;++i)if(root1(i)==i)ck(i);
while(!Q.empty()){
re node tmp=Q.top();Q.pop();
if(tmp.l==1&&tmp.r==n){T.push_back((Node){tim,W,n});break;}
else{
T.push_back((Node){tim,W,tmp.r-tmp.l+1});
re int dlt=max(a[tmp.l-1],a[tmp.r+1]);
tim+=(a[tmp.l]-dlt)*(tmp.r-tmp.l+1),W+=a[tmp.l]-dlt;
a[tmp.l]=a[tmp.r]=dlt;
if(a[tmp.l]==a[tmp.l-1])Merge(tmp.l);
if(a[tmp.r]==a[tmp.r+1])Merge(tmp.r+1);
ck(tmp.l);
}
}
while(q--){
re int x=read(),pos=upper_bound(T.begin(),T.end(),(Node){x,1000000000000000000ll,0})-T.begin()-1;
printf("%lld\n",max(0ll,sum-2*(T[pos].y+(x-T[pos].x)/T[pos].z)));
}
}C
部分分可以树形背包。
先考虑 $f_i=-1$ 的情况，这时我们只需要把这个点所有儿子接到这个点的父亲即可。
所以我们只用考虑 $f_i\neq -1$ 的情况。
可以发现答案可以看成对于每个子树分别求答案，最终乘起来。我们不妨假设 $g_i$ 表示子树 $i$ 恰好有 $1\sim f_i$ 这些颜色的方案书。使用容斥原理，我们钦定 $k$ 种颜色使得最终只出现这 $k$ 种之一的颜色。所以我们有 $g_x=\sum_{i=0}^{f_x}(-1)^{f_x-i}\prod_{y\in son(x)}g_y\dbinom{i}{f_y}$，直接计算复杂度 $O(nm)$。
由于这是 NOIP 模拟肯定不存在多项式。我们得用树的性质来优化。我们发现，上述式子种的 $i$ 实际上只需要从 $f$ 最大的一个儿子开始枚举。否则组合数就为 $0$。
然后我们可以合并相同的 $f$，即有多个相同的 $f$ 我们可以用快速幂计算。
我们可以证明上述算法是 $O(n\sqrt n)$ 的。
首先由于相同的 $f$ 合并后只会有 $O(\sqrt n)$ 种不同的 $f$，所以这部分是 $O(\sqrt n \log n)$ 的，然后这里可以分析到 $O(\sqrt n)$，参见上次 UR 的 T1。
我们每次从最大的 $f$ 的儿子开始枚举，其实可以看作从 size 最大的儿子开始枚举，代价 $f_x-f_y$ 求和可以看成每个点的轻儿子大小之和，是 $O(n\log n)$ 的。
所以这部分是 $O(n\sqrt n\log n)$ 的 ，据 127 称可以分析到 $n\sqrt n$，我也不太会（不过可以发现造不出卡到 $\sqrt n \log n$ 的数据）。
#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
re int t=0,f=0;re char v=getchar();
while(v<'0')f|=(v=='-'),v=getchar();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
return f?-t:t;
}
const int M=1e9+7;
inline int ksm(re int x,re int y){
re int s=1;
while(y){
if(y&1)s=1ll*s*x%M;
x=1ll*x*x%M,y>>=1;
}return s;
}
inline void add(re int&x,re int y){(x+=y)>=M?x-=M:x;}
int n,m,head[200002],fac[200002],inv[200002],f[200002],ans,cnt,fa[200002];
struct edge{int to,next;}e[400002];
inline void addd(re int x,re int y){e[++cnt]=(edge){y,head[x]},head[x]=cnt;}
struct node{int x,y;};
inline int C(re int x,re int y){return 1ll*fac[x]*inv[y]%M*inv[x-y]%M;}
inline void dfs(re int x,re int y){
map<int,int>V;vector<node>tmp;re int mx=0,num=0;
for(re int i=head[x];i;i=e[i].next)dfs(e[i].to,x),++V[f[e[i].to]],mx=max(mx,f[e[i].to]),++num;
++V[1];
for(auto z:V)tmp.push_back((node){z.first,z.second});
if(f[x]==1)return;re int sum=0;
for(re int i=mx;i<=f[x];++i){
re int s=C(f[x],i);if(f[x]-i&1)s=M-s;
for(auto z:tmp)s=1ll*s*ksm(C(i,z.x),z.y)%M;
add(sum,s);
}ans=1ll*ans*sum%M;
}
int main(){
n=read(),m=read(),ans=1;
for(re int i=fac[0]=inv[0]=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%M,inv[i]=ksm(fac[i],M-2);
for(re int i=2;i<=n;++i)fa[i]=read();
for(re int i=1;i<=n;++i)f[i]=read();
for(re int i=2;i<=n;++i)if(f[fa[i]]==-1)fa[i]=fa[fa[i]];
for(re int i=2;i<=n;++i)addd(fa[i],i);
for(re int i=1;i<=n;++i)if(f[i]==-1)f[i]=1;
dfs(1,1),printf("%d",ans);
}D
部分分有一些特判。
核心思路：最短路。
容易发现对于每个 $i$ 是独立的，即令 $s_i$ 表示将一个初始仅有 $i$ 为 $1$ 其余为 $0$ 的序列变为全 $0$ 的最小步数，那答案就是 $\sum a_is_i$。
考虑怎么求 $s_i$，实际上对于一个涉及 $i$ 的转移，可以看成用 $L\sim R$ 中所有 $s$ 的和转移到 $s_i$，暴力实现可以做到 $O(nm)$。
考虑模拟 dij 的过程，每次找出最小的 $s_i$，打上确定的标记，每次找到所有操作 $L,R$ 使得 $L,R$ 中所有的 $s_i$ 都被打上了标记，那么这个操作就是可以转移的。动态判定 $L\sim R$ 是否全部打上了标记可以用线段树。
总复杂度 $O((n+m)\log n)$。
#include<bits/stdc++.h>
#define re register
#define ll long long
using namespace std;
char rbuf[20000002];
int pt=-1;
inline int read(){
re int t=0,f=0;re char v=rbuf[++pt];
while(v<'0')f|=(v=='-'),v=rbuf[++pt];
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=rbuf[++pt];
return f?-t:t;
}
const int M=998244353;
int n,m,a[400002],num[400002],cnt,L[400002],R[400002],X[400002],W[400002],f[400002],sz[1600002],b[400002],head[1600002];
struct edge{int to,next;}e[14400002];
inline void add(re int x,re int y){e[++cnt]=(edge){y,head[x]},head[x]=cnt;}
ll S[1600002],sum[400002],inf=(4e18)+1,ans,inf1=(2e18)+1;
struct node{
int x;ll dis;
bool operator <(const node A)const{return dis>A.dis;}
}h[400002];
inline void gmn(re ll&x,re ll y){y<x&&(x=y);}
priority_queue<node>Q;
inline void Ins(re int p,re int l,re int r,re int x,re int y,re int z){
if(l>=x&&r<=y){
add(p,z),++num[z];
return;
}
re int mid=l+r>>1;
if(x<=mid)Ins(p<<1,l,mid,x,y,z);
if(y>mid)Ins(p<<1|1,mid+1,r,x,y,z);
}
inline void ck(re int x,re ll y){y=min(y,inf1);if(y<h[x].dis)h[x].dis=y,Q.push(h[x]);}
inline void cg(re int p,re int l,re int r,re int x,re ll y){
++sz[p],S[p]+=y,S[p]=min(S[p],inf1);
assert(sz[p]<=r-l+1);
if(sz[p]==r-l+1){
for(re int i=head[p];i;i=e[i].next){
re int z=e[i].to;sum[z]+=S[p];
if(!(--num[z]))ck(X[z],sum[z]+W[z]);
}
}
if(l==r)return;
re int mid=l+r>>1;
if(x<=mid)cg(p<<1,l,mid,x,y);
else cg(p<<1|1,mid+1,r,x,y);
}
int main(){
fread(rbuf,1,20000000,stdin),n=read(),m=read();
for(re int i=1;i<=n;++i)a[i]=read(),h[i]=(node){i,inf};
for(re int i=1;i<=m;++i){
X[i]=read(),L[i]=read(),R[i]=read(),W[i]=read();
Ins(1,1,n,L[i],R[i],i);
}
for(re int i=1;i<=n;++i){
re int x=read();b[i]=x;
if(x>=0)h[i].dis=x;
}
for(re int i=1;i<=n;++i)if(h[i].dis!=inf)Q.push(h[i]);
while(!Q.empty()){
re node x=Q.top();Q.pop();
if(x.dis!=h[x.x].dis)continue;
cg(1,1,n,x.x,x.dis);
}
for(re int i=1;i<=n;++i)if(a[i]&&h[i].dis>=inf1)return puts("-1"),0;
for(re int i=1;i<=n;++i)ans+=h[i].dis*a[i];
printf("%lld",ans);
}