C:HSI
期望模型，不想说。
#include<cstdio>
using namespace std;
typedef long long ll;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
printf("%lld\n",(ll)((n-m)*+m*)*(<<m));
return ;
}
D:ABS
f[i][j]表示第i轮，X在i，Y在j，玩到最后的差绝对值。下一次由Y先手，取所有可以的转移中的最小值。
g[i][j]表示第i轮，Y在i，X在j，玩到最后的差绝对值。下一次由X先手，取所有可以的转移中的最大值。
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=;
int n,z,w,a[N],ans,Mn_g[N],Mx_f[N],f[N][N],g[N][N];
int main()
{
scanf("%d%d%d",&n,&z,&w);
for (int i=;i<=n;i++) scanf("%d",&a[i]);
a[]=w;
for (int i=;i<n;i++) f[n][i]=g[n][i]=Mx_f[i]=Mn_g[i]=abs(a[n]-a[i]);
for (int i=n-;i>=;i--)
for (int j=;j<i;j++)
{
if (i) f[i][j]=Mn_g[i],Mx_f[j]=max(Mx_f[j],f[i][j]);
if (j) g[i][j]=Mx_f[i],Mn_g[j]=min(Mn_g[j],g[i][j]);
}
for (int i=;i<=n;i++) ans=max(ans,f[i][]);
printf("%d\n",ans);
return ;
}
E：MUL
题意：n个宝石，有价值ai，可以为负。你可以打碎若干宝石和其所有标号有倍数关系的宝石。问剩下的宝石最大价值和？
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=;
const ll inf=1ll<<;
int cnt=,head[N],Head[N],n,dis[N],S,T,x;
ll ans,tmp;
queue<int> q;
struct node{int to,next;ll w;}num[N*N*];
void add(int x,int y,ll w)
{num[++cnt].to=y;num[cnt].next=head[x];num[cnt].w=w;head[x]=cnt;
num[++cnt].to=x;num[cnt].next=head[y];num[cnt].w=;head[y]=cnt;}
int bfs()
{
memset(dis,,sizeof(dis));dis[S]=;
q.push(S);
while (!q.empty())
{
int now=q.front();q.pop();
for (int i=head[now];i;i=num[i].next)
if (num[i].w&&!dis[num[i].to])
q.push(num[i].to),dis[num[i].to]=dis[now]+;
}
return dis[T];
}
ll dfs(int x,ll mm)
{
ll tmp=mm;
if (x==T) return mm;
for (int &i=Head[x];i&&tmp;i=num[i].next)
if (dis[num[i].to]==dis[x]+)
{
ll t=dfs(num[i].to,min(num[i].w,tmp));
tmp-=t;num[i].w-=t;num[i^].w+=t;
}
return mm-tmp;
}
void dinic()
{
while (bfs())
{
memcpy(Head,head,sizeof(head));
while (tmp=dfs(S,inf)) ans-=tmp;
}
}
int main()
{
scanf("%d",&n);S=n+;T=S+;
for (int i=;i<=n;i++)
{
scanf("%d",&x);
if (x<) add(S,i,-x);else add(i,T,x),ans+=x;
}
for (int i=;i<=n;i++)
for (int j=i+i;j<=n;j+=i) add(i,j,inf);
dinic();
printf("%lld\n",ans);
return ;
}
最小割建模（又忘记套路了真是该打）
S部设为不选，T部为选。权值为负的点向S连容量为-w的边，权值为正的点向T连容量为w的边。这里的容量相当于是割掉这条边的代价。
对于所有有倍数关系的点，小的向大的连inf的边。ans一开始为所有正权边的权值和。
比如对于i和2i，S-i，i-2i，2i-T。那么割掉i-2i，就是不选i而选2i，不可能。割掉S-i，就是都保留，那么ans-=w[i]。割掉2i-T，就是都不保留，那么ans-=w[2i]。所以最大权值也就是一个最小割的问题啦。
建模方法：分为选和不选两部分点，把边的容量设为代价，通过正负的约束来使得要求的是最小割，ans一开始统计全部保留和T点（保留点）连边的价值和。
F：NRE
题意：给你若干个区间，你可以从中选取部分来使得一整个区间变成1。
初始序列为A，问进行一些操作后，和B的最少不同位？
n<=20W。
#include<bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
const int inf=0x3f3f3f3f;
const int N=;
int T[N<<],tag[N<<],n,a[N],sum0[N],sum1[N],Q,head;
struct node{int l,r;}q[N];
bool operator < (const node &A,const node &B)
{return A.l<B.l||A.l==B.l&&A.r<B.r;}
void down(int k)
{
if (tag[k])
{
tag[k<<]+=tag[k];tag[k<<|]+=tag[k];
T[k<<]+=tag[k];T[k<<|]+=tag[k];
tag[k]=;
}
}
void ins(int k,int l,int r,int x,int y)
{
if (l==r) {T[k]=min(T[k],y);return;}
down(k);
if (x<=mid) ins(k<<,l,mid,x,y);
else ins(k<<|,mid+,r,x,y);
T[k]=min(T[k<<],T[k<<|]);
}
void add(int k,int l,int r,int L,int R,int x)
{
if (L<=l&&r<=R) {T[k]+=x;tag[k]+=x;return;}
down(k);
if (L<=mid) add(k<<,l,mid,L,R,x);
if (R>mid) add(k<<|,mid+,r,L,R,x);
T[k]=min(T[k<<],T[k<<|]);
}
int qry(int k,int l,int r,int L,int R)
{
if (L<=l&&r<=R) return T[k];
down(k);int ans=inf;
if (L<=mid) ans=min(ans,qry(k<<,l,mid,L,R));
if (R>mid) ans=min(ans,qry(k<<|,mid+,r,L,R));
return ans;
}
int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++)
{
scanf("%d",&a[i]);sum0[i]=sum0[i-];sum1[i]=sum1[i-];
if (!a[i]) sum0[i]++;else sum1[i]++;
}
scanf("%d",&Q);
for (int i=;i<=Q;i++) scanf("%d%d",&q[i].l,&q[i].r);
sort(q+,q+Q+);
head=;memset(T,inf,sizeof(T));
ins(,,n,,);
for (int i=;i<=n;i++)
{
while (head<=Q&&q[head].l==i) ins(,,n,q[head].r,qry(,,n,,q[head].r)),head++;
if (a[i]) add(,,n,,i-,);else add(,,n,,i-,-);
}
printf("%d\n",qry(,,n,,n)+sum0[n]);
return ;
}
线段树优化dp
我们要求的是(0,1)+(1,0)的数量，也就是(0,1)+(0/1,0)-(0,0)。那么(0/1,0)是固定的，即要使得(0,1)-(0,0)最小。1的覆盖也就是不计算一些位置的贡献。
哇这个dp思路超级巧妙。dp[i][j]表示前i个数确定，当前最后一个1在j的最小(0,1)-(0,0)。
从小到大枚举i，对于一条左端点在i的线段[i,r]，dp[i][r]=min(dp[i-1][k]),k<=r。（因为i之后都是1，相当于只有前i-1位确定即可。而且如果k>r，那么之前那条线段一定包含[i,r]，dp[i][r]的更新跟它就没有什么关系了，况且根据定义最后一个1就出界了），其他没有更改的和dp[i-1]一样。
此时落点>=i的线段一定覆盖了i点（因为线段的左端点<=i），因而我们需要对于所有dp[i][0~i-1]都更改为前i个数确定的状态，由第i个数的0/1决定-1/+1。区间最小值和区间加用线段树实现。时间复杂度O(nlogn)。
