DP刷题笔记III
xtx1092515503 · · 个人记录
笔记I（1~50题）
笔记II（51~100题）
现在开始！
CI.[IOI2009]salesman
思想非常simple：因为一次从上游往下游的转移，可以被表示成
拆开括号，即可得到两半互不相关的部分。然后直接使用线段树/树状数组进行转移即可。
从下游往上游的转移也可以类似地处理。
现在考虑
3min就能想出的idea，我整整调了3d。主要因为一开始套了两重离散化，后来发现数据范围开的下便删去了离散化；一开始写的是线段树，后来发现线段树debug起来很麻烦，便换成了BIT；一开始也没有想到没有回头路的情形，辅助DP时写的极其憋屈（后来证明就是这个憋屈的DP中有一处
代码：
#include<bits/stdc++.h>
using namespace std;
const int inf=0xc0c0c0c0;
const int N=1001000;
int n,U,D,S,tim[N],pos[N],bon[N],m=500100,ord[N],f[N],g[N],upper[N],lower[N];//upper:the maximal when go against the wave; lower:vice versa
void modify(int P,int val){
for(int x=P;x;x-=x&-x)upper[x]=max(upper[x],val-P*U);
for(int x=P;x<=m;x+=x&-x)lower[x]=max(lower[x],val+P*D);
}
int queryupper(int P){
int ret=inf;
for(int x=P;x<=m;x+=x&-x)ret=max(ret,upper[x]+P*U);
return ret;
}
int querylower(int P){
int ret=inf;
for(int x=P;x;x-=x&-x)ret=max(ret,lower[x]-P*D);
return ret;
}
#define I ord[i]
#define J ord[j]
#define K ord[k]
int main(){
scanf("%d%d%d%d",&n,&U,&D,&S),memset(upper,0xc0,sizeof(upper)),memset(lower,0xc0,sizeof(lower));
for(int i=1;i<=n;i++)scanf("%d%d%d",&tim[i],&pos[i],&bon[i]),ord[i]=i;
sort(ord+1,ord+n+1,[](int x,int y){return tim[x]==tim[y]?pos[x]<pos[y]:tim[x]<tim[y];});
modify(S,0);
for(int i=1,j=1;j<=n;){
while(tim[I]==tim[J])f[J]=g[J]=max(queryupper(pos[J]),querylower(pos[J]))+bon[J],j++;
for(int k=i+1;k<j;k++)f[K]=max(f[K],f[ord[k-1]]-(pos[K]-pos[ord[k-1]])*D+bon[K]);
for(int k=j-2;k>=i;k--)g[K]=max(g[K],g[ord[k+1]]-(pos[ord[k+1]]-pos[K])*U+bon[K]);
while(i<j)modify(pos[I],max(f[I],g[I])),i++;
}
printf("%d\n",max(queryupper(S),querylower(S)));
return 0;
}CII.HDU6212 Zuma
一眼区间DP。
首先，我们将串压缩（即将相同颜色的相邻珠子合并）。记
我们设
则有：
其中，第一条转移是直接补满
时间复杂度
代码：
#include<bits/stdc++.h>
using namespace std;
int T,n,m,sz[210],f[210][210];
bool col[210];
char s[210];
int main(){
scanf("%d",&T);
for(int t=1;t<=T;t++){
scanf("%s",s+1),m=strlen(s+1),n=0;
col[1]=s[1]-'0',sz[1]=1,n++;
for(int i=2;i<=m;i++){
if(s[i]-'0'==col[n])sz[n]++;
else n++,col[n]=s[i]-'0',sz[n]=1;
}
for(int i=1;i<=n;i++)f[i][i]=3-sz[i];
for(int l=2;l<=n;l++)for(int i=1,j=i+l-1;j<=n;i++,j++){
f[i][j]=0x3f3f3f3f;
for(int k=i;k<j;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
if(col[i]!=col[j])continue;
f[i][j]=min(f[i][j],f[i+1][j-1]+max(0,3-sz[i]-sz[j]));
if(sz[i]==2&&sz[j]==2)continue;
for(int k=i+1;k<j;k++)if(col[k]==col[i]&&sz[k]==1)f[i][j]=min(f[i][j],f[i+1][k-1]+f[k+1][j-1]);
}
printf("Case #%d: %d\n",t,f[1][n]);
}
return 0;
} CIII.[APIO2014]连珠线
一般的换根DP题。
明显可以看出，最终的树一定可以通过指定一个根变成一棵有根树，所有的蓝边都可以被分成两两一组，其中每组中两条边深度递增。
于是我们可以设置DP状态。
简单使用multiset维护
然后换个根即可。
代码：
#include<bits/stdc++.h>
using namespace std;
const int inf=0xc0c0c0c0;
int n,f[200100][2],head[200100],cnt,res;
struct node{
int to,next,val;
}edge[400100];
void ae(int u,int v,int w){
edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++;
}
multiset<int>s[200100];
void dfs1(int x,int fa){
for(int i=head[x],y;i!=-1;i=edge[i].next){
if((y=edge[i].to)==fa)continue;
dfs1(y,x);
int tmp=max(f[y][0],f[y][1]+edge[i].val);
f[x][0]+=tmp;
f[x][1]+=tmp,s[x].insert(f[y][0]+edge[i].val-tmp);
}
if(s[x].empty())f[x][1]=inf;
else f[x][1]+=*s[x].rbegin();
// printf("%d:%d %d\n",x,f[x][0],f[x][1]);
}
void dfs2(int x,int fa){
for(int i=head[x],y;i!=-1;i=edge[i].next){
if((y=edge[i].to)==fa)continue;
int tmp=max(f[y][0],f[y][1]+edge[i].val);
int fx0=f[x][0],fx1=f[x][1];
fx0-=tmp;
fx1-=tmp;
fx1-=*s[x].rbegin();
int pmt=f[y][0]+edge[i].val-tmp;
s[x].erase(s[x].find(pmt));
fx1=(s[x].empty()?inf:fx1+*s[x].rbegin());
s[x].insert(pmt);
int qwq=max(fx0,fx1+edge[i].val);
f[y][0]+=qwq;
f[y][1]=(s[y].empty()?0:f[y][1]-*s[y].rbegin());
f[y][1]+=qwq;
s[y].insert(fx0+edge[i].val-qwq);
f[y][1]+=*s[y].rbegin();
dfs2(y,x);
}
}
int main(){
scanf("%d",&n),memset(head,-1,sizeof(head));
for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),ae(x,y,z);
dfs1(1,0),dfs2(1,0);
for(int i=1;i<=n;i++)res=max(res,f[i][0]);
printf("%d\n",res);
return 0;
}CIV.[TopCoder 12519]ScotlandYard
我们考虑一个最原始的DP状态：
然后考虑枚举藏的人下一步给出走了什么颜色的边，然后取
观察可以发现，猜的人最终可以确定藏的人在哪里的前一刻，
-
如果
\geq3 ，显然只判断其中两个亦可； -
如果
=2 ，显然可以根据此两个一路反推回去，即任意时刻|\mathbb{S}| 都可以被缩减到2 。 -
如果
\leq1 ，此状态显然不合法，不可能出现。
故我们发现任意时刻状态中仅需存储
代码（TC的格式）：
#include<bits/stdc++.h>
using namespace std;
class ScotlandYard{
private:
const int inf=0x3f3f3f3f;
int n,f[60][60];
vector<int>g[60][3];
bool in[60][60];
int dfs(int x,int y){
if(in[x][y])return inf;
if(f[x][y]!=-1)return f[x][y];
in[x][y]=true;
f[x][y]=0;
for(int i=0;i<3;i++){
vector<int>v;
for(auto j:g[x][i])v.push_back(j);
for(auto j:g[y][i])v.push_back(j);
sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin());
if(v.size()==0){f[x][y]=max(f[x][y],0);continue;}
if(v.size()==1){f[x][y]=max(f[x][y],1);continue;}
for(int i=0;i<v.size();i++)for(int j=i+1;j<v.size();j++)f[x][y]=max(f[x][y],min(inf,dfs(v[i],v[j])+1));
}
in[x][y]=false;
return f[x][y];
}
public:
int maxMoves(vector<string>taxi,vector<string>bus,vector<string>metro){
n=taxi.size();
for(int i=0;i<n;i++)for(int j=0;j<3;j++)g[i][j].clear();
for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(taxi[i][j]=='Y')g[i][0].push_back(j);
for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(bus[i][j]=='Y')g[i][1].push_back(j);
for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(metro[i][j]=='Y')g[i][2].push_back(j);
// for(int i=0;i<3;i++){for(int j=0;j<n;j++){for(auto k:g[j][i])printf("%d ",k);puts("");}puts("");}
memset(f,-1,sizeof(f));
int res=0;
for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)res=max(res,dfs(i,j));
return res>=inf?-1:res;
}
}my;CV.[ARC067D] Yakiniku Restaurants
明显在最优方案中，行走方式一定是从一条线段的一端走到另一端，不回头。
于是设
我们发现，假设有一张位置
则时间复杂度
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[210][5010],stk[5010],tp,lson[5010],rson[5010];
ll s[5010],f[5010][5010],res;
void solve(int id,int x,int l,int r,int las){
f[l][r]+=a[id][x]-las;
if(l==r)return;
if(lson[x])solve(id,lson[x],l,x-1,a[id][x]);
if(rson[x])solve(id,rson[x],x+1,r,a[id][x]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=2;i<=n;i++)scanf("%lld",&s[i]),s[i]+=s[i-1];
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[j][i]);
for(int i=1;i<=m;i++){
tp=0;
for(int j=1;j<=n;j++){
lson[j]=rson[j]=0;
while(tp&&a[i][stk[tp]]<=a[i][j])lson[j]=stk[tp--];
if(stk[tp])rson[stk[tp]]=j;
stk[++tp]=j;
}
solve(i,stk[1],1,n,0);
}
for(int i=1;i<=n;i++)for(int j=n;j>=i;j--)f[i][j]+=f[i-1][j]+f[i][j+1]-f[i-1][j+1];
for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)res=max(res,f[i][j]-(s[j]-s[i]));
printf("%lld\n",res);
return 0;
}CVI.[CSACADEMY]Root Change
常规换根DP。设
则
于是直接上 multiset 暴力换根即可。时间复杂度
代码：
#include<bits/stdc++.h>
using namespace std;
int n,f[100100],g[100100],sz[100100];
vector<int>v[100100];
multiset<pair<int,int> >s[100100];
multiset<int>t[100100];
void dfs1(int x,int fa){
for(auto y:v[x])if(y!=fa)dfs1(y,x),f[x]=max(f[x],f[y]+1),sz[x]+=sz[y]+1,s[x].insert(make_pair(f[y]+1,g[y]-(sz[y]+1))),t[x].insert(f[y]+1);
g[x]=sz[x];
if(s[x].size()==1||s[x].size()>=2&&s[x].rbegin()->first!=(++s[x].rbegin())->first)g[x]+=s[x].rbegin()->second;
}
void dfs2(int x,int fa){
for(auto y:v[x]){
if(y==fa)continue;
int fx=0,szx=sz[x]-sz[y]-1;
t[x].erase(t[x].find(f[y]+1));
if(!t[x].empty())fx=*t[x].rbegin();
t[x].insert(f[y]+1);
int gx=szx;
s[x].erase(s[x].find(make_pair(f[y]+1,g[y]-(sz[y]+1))));
if(s[x].size()==1||s[x].size()>=2&&s[x].rbegin()->first!=(++s[x].rbegin())->first)gx+=s[x].rbegin()->second;
s[x].insert(make_pair(f[y]+1,g[y]-(sz[y]+1)));
t[y].insert(fx+1);
s[y].insert(make_pair(fx+1,gx-(szx+1)));
sz[y]+=szx+1;
f[y]=*t[y].rbegin();
g[y]=sz[y];
if(s[y].size()==1||s[y].size()>=2&&s[y].rbegin()->first!=(++s[y].rbegin())->first)g[y]+=s[y].rbegin()->second;
dfs2(y,x);
}
}
int main(){
scanf("%d",&n);
for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
dfs1(1,0),dfs2(1,0);
for(int i=1;i<=n;i++)printf("%d\n",g[i]);
return 0;
}CVII.[NOI2009]二叉查找树
首先该树的中序遍历是唯一可以确定的（直接按照数据值排序即可）。
然后，因为权值可以被修改成一切实数，故我们完全可以把权值离散化掉。
于是我们现在可以设置一个DP状态
区间
然后就枚举根转移即可。转移的时候就可以看作是子树内所有东西被整体提高了一层，所以直接增加
则时间复杂度
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,sum[110],f[110][110][110];
struct dat{
int val,key,lam;
}a[100];
int dfs(int l,int r,int lim){
if(l>r)return 0;
if(f[l][r][lim]!=-1)return f[l][r][lim];
int &now=f[l][r][lim];now=0x3f3f3f3f;
for(int i=l;i<=r;i++){//assume that i is the root in the section [l,r].
if(a[i].key>=lim)now=min(now,dfs(l,i-1,a[i].key)+dfs(i+1,r,a[i].key)+sum[r]-sum[l-1]);//do not modify, the height simply increased by one.
now=min(now,dfs(l,i-1,lim)+dfs(i+1,r,lim)+m+sum[r]-sum[l-1]);//modify i to any real number a little greater than lim.
}
return now;
}
int main(){
scanf("%d%d",&n,&m),memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++)scanf("%d",&a[i].val);
for(int i=1;i<=n;i++)scanf("%d",&a[i].key);
for(int i=1;i<=n;i++)scanf("%d",&a[i].lam);
sort(a+1,a+n+1,[](dat u,dat v){return u.key<v.key;});
for(int i=1;i<=n;i++)a[i].key=i;
sort(a+1,a+n+1,[](dat u,dat v){return u.val<v.val;});
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i].lam;
printf("%d\n",dfs(1,n,1));
return 0;
}CVIII.[POI2014]MRO-Ant colony
根据下取整除法的性质（
这个可以直接一遍dfs就出来了（可以把它当成DP）。注意，当一段路径的分母已经爆
然后，对于一个分母
时间复杂度
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LIM=1e9;
int n,m,k,sp[1001000],U,V;
ll dif[1001000],res;
vector<int>v[1001000],u;
void dfs(int x,int fa,int lam){
if(v[x].size()==1){u.push_back(lam);return;}
if(1ll*lam*(v[x].size()-1)>LIM)return;
lam*=(v[x].size()-1);
for(auto y:v[x])if(y!=fa)dfs(y,x,lam);
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++)scanf("%d",&sp[i]);
scanf("%d%d",&U,&V),v[U].push_back(V),v[V].push_back(U);
for(int i=1,x,y;i+1<n;i++)scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
dfs(U,V,1),dfs(V,U,1);
sort(sp+1,sp+m+1);
for(auto i:u){
ll l=1ll*k*i,r=1ll*(k+1)*i;
if(l>LIM)continue;
dif[lower_bound(sp+1,sp+m+1,l)-sp]++;
dif[lower_bound(sp+1,sp+m+1,r)-sp]--;
}
for(int i=1;i<=m;i++)dif[i]+=dif[i-1],res+=dif[i];
printf("%lld\n",res*k);
return 0;
}CIX.[NOI Online #1 入门组]魔法
我们可以构造出原图的转移矩阵
我们还可以构造出魔法的转移矩阵
则，可以想到，答案一定是
这种样子。
故我们用
时间复杂度
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,p;
struct Matrix{
ll a[110][110];
void init(){memset(a,0x3f,sizeof(a));for(int i=1;i<=n;i++)a[i][i]=0;}
ll* operator[](int x){return a[x];}
friend Matrix operator *(Matrix &u,Matrix &v){
Matrix w;w.init();
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)w[i][j]=min(w[i][j],u[i][k]+v[k][j]);
return w;
}
}a,b;
int main(){
scanf("%d%d%d",&n,&m,&p);
a.init(),b.init();
for(int i=1,x,y,z;i<=m;i++)scanf("%d%d%d",&x,&y,&z),a[x][y]=min(a[x][y],1ll*z),b[x][y]=min(b[x][y],-1ll*z);
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
// for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%d ",a[i][j]);puts("");}
b=b*a;
// for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%d ",b[i][j]);puts("");}
for(;p;p>>=1,b=b*b)if(p&1)a=a*b;
printf("%lld\n",a[1][n]);
return 0;
}CX.[POI2015]MOD
比较恶心的题目。
首先，有一个结论，即如果把两棵树通过某种方式连接起来，新树的直径的端点一定来自于原本两棵树的直径端点集合。
则考虑新树的最大直径，明显就是把两棵树的直径直接连一块，就是两棵树的直径之和再加一。
考虑新树的最小直径，则应该选择两树直径的中点（如果直径长度为奇数则随便选一个）连一块，这样新树的直径就是
于是我们就用换根DP求出multiset维护，但是会莫名其妙MLE。故最后不得不全面换成vector才不出问题）。然后两个拼一块就能找出所有新树的直径的最大值/最小值。
代码（非常丑陋）：
#include<bits/stdc++.h>
using namespace std;
int n,f[500100],g[500100],h[500100],FA[500100],mx,mn=0x3f3f3f3f;
//f[i]:the maximal length starting from i; g[i]: the maximal length in i's subtree; h[i]:the maximal length outside that.
vector<int>v[500100],s[500100],t[500100];
void dfs1(int x,int fa){
for(auto y:v[x]){
if(y==fa)continue;
FA[y]=x;
dfs1(y,x);
f[x]=max(f[x],f[y]+1);
s[x].push_back(f[y]+1);
t[x].push_back(g[y]);
g[x]=max(g[x],g[y]);
}
sort(s[x].rbegin(),s[x].rend());while(s[x].size()>3)s[x].pop_back();
sort(t[x].rbegin(),t[x].rend());while(t[x].size()>2)t[x].pop_back();
if(s[x].size()>=2)g[x]=max(g[x],s[x][0]+s[x][1]);
else if(s[x].size()>=1)g[x]=max(g[x],s[x][0]);
}
void dfs2(int x,int fa){
int alls=0;
for(auto i:s[x])alls+=i;
// printf("%dS",x);for(auto i:s[x])printf("%d ",i);puts("");
// printf("%dT",x);for(auto i:t[x])printf("%d ",i);puts("");
for(auto y:v[x]){
if(y==fa)continue;
if(f[y]+1>=s[x].back())h[y]=alls-(f[y]+1);
else if(s[x].size()<=2)h[y]=alls;
else h[y]=s[x][0]+s[x][1];
if(t[x][0]!=g[y])h[y]=max(h[y],t[x][0]);
else if(t[x].size()>=2)h[y]=max(h[y],t[x][1]);
t[y].push_back(h[y]);
sort(t[y].rbegin(),t[y].rend());while(t[y].size()>2)t[y].pop_back();
if(s[x][0]!=f[y]+1)s[y].push_back(s[x][0]+1);
else if(s[x].size()>=2)s[y].push_back(s[x][1]+1);
else s[y].push_back(1);
sort(s[y].rbegin(),s[y].rend());while(s[y].size()>3)s[y].pop_back();
dfs2(y,x);
}
}
int S,dp,inva,nd,rt;
void dfs3(int x,int fa,int dep){
if(dep>dp)S=x,dp=dep;
for(auto y:v[x])if(y!=fa&&y!=inva)dfs3(y,x,dep+1);
}
bool dfs4(int x,int fa){
if(x==S){
nd--;
if(nd==0)rt=x;
return true;
}
for(auto y:v[x]){
if(y==fa)continue;
if(!dfs4(y,x))continue;
nd--;
if(nd==0)rt=x;
return true;
}
return false;
}
int main(){
scanf("%d",&n);
for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
dfs1(1,0),dfs2(1,0);
// for(int i=1;i<=n;i++)printf("%d:%d %d %d\n",i,f[i],g[i],h[i]);
for(int i=2;i<=n;i++)mx=max(mx,g[i]+h[i]+1),mn=min(mn,max({(g[i]+1)/2+(h[i]+1)/2+1,g[i],h[i]}));
for(int i=2;i<=n;i++){
if(mn!=max({(g[i]+1)/2+(h[i]+1)/2+1,g[i],h[i]}))continue;
printf("%d %d %d ",mn,i,FA[i]);
inva=FA[i];
S=0,dp=-1;
dfs3(i,FA[i],0);
int T=S;
S=0,dp=-1;
dfs3(T,0,0);
nd=(g[i]+2)/2;
dfs4(T,0);
printf("%d ",rt);
inva=i;
S=0,dp=-1;
dfs3(FA[i],i,0);
T=S;
S=0,dp=-1;
dfs3(T,0,0);
nd=(h[i]+2)/2,dfs4(T,0);
printf("%d\n",rt);
break;
}
for(int i=2;i<=n;i++){
if(mx!=g[i]+h[i]+1)continue;
inva=0;
printf("%d %d %d ",mx,i,FA[i]);
S=0,dp=-1;
dfs3(i,FA[i],0);
printf("%d ",S);
S=0,dp=-1;
dfs3(FA[i],i,0);
printf("%d\n",S);
break;
}
return 0;
}CXI.[九省联考2018]一双木棋chess
一下子就想到了LXX.[USACO5.5]贰五语言Two Five（可见刷题笔记II），因为同是阶梯型的图样。然后稍微想一想就发现总方案数可以用隔板法证得是
首先先用爆搜搜出所有图案的分布（实现从编号到图案的映射），然后再预处理一个辅助的DP来实现从图案到编号的映射。然后就直接分当前是谁操作进行不同的转移即可。
时间复杂度，如上所述，是
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,f[20][20],a[20][20],b[20][20],g[200000];
vector<int>v[200100];
vector<int>u;
void dfs(int pos,int lim){
if(pos==n){v[++cnt]=u;return;}
for(int i=0;i<=lim;i++){
u.push_back(i);
dfs(pos+1,i);
u.pop_back();
}
}
int deco(vector<int>&ip){
int ret=1;
for(int i=0;i<n;i++)if(ip[i])ret+=f[i][ip[i]-1];
return ret;
}
int dp(int ip,bool sd){
if(ip==cnt)return 0;
if(g[ip]!=-1)return g[ip];
if(sd==0){//first player
g[ip]=0xc0c0c0c0;
vector<int>tmp=v[ip];
for(int i=0;i<n;i++){
if(i==0&&tmp[i]==m||i>0&&tmp[i]==tmp[i-1])continue;
tmp[i]++;
g[ip]=max(g[ip],dp(deco(tmp),sd^1)+a[i][tmp[i]]);
tmp[i]--;
}
return g[ip];
}else{
g[ip]=0x3f3f3f3f;
vector<int>tmp=v[ip];
for(int i=0;i<n;i++){
if(i==0&&tmp[i]==m||i>0&&tmp[i]==tmp[i-1])continue;
tmp[i]++;
g[ip]=min(g[ip],dp(deco(tmp),sd^1)-b[i][tmp[i]]);
tmp[i]--;
}
return g[ip];
}
}
int main(){
scanf("%d%d",&n,&m),memset(g,-1,sizeof(g));
dfs(0,m);
for(int i=0;i<=m;i++)f[n-1][i]=i+1;
for(int i=n-2;i>=0;i--)for(int j=0;j<=m;j++)for(int k=0;k<=j;k++)f[i][j]+=f[i+1][k];
for(int i=0;i<n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
for(int i=0;i<n;i++)for(int j=1;j<=m;j++)scanf("%d",&b[i][j]);
printf("%d\n",dp(1,0));
return 0;
} CXII.[CEOI2007]树的匹配Treasury
题解
CXIII.[JLOI2016/SHOI2016]侦察守卫
神题。
见代码即可。
#include<bits/stdc++.h>
using namespace std;
int n,m,p,a[500100],f[500100][25],g[500100][25],res=0x3f3f3f3f;
//f[i,j]:minimum cost when there're at most j layers left uncovered
//g[i,j]:minimum cost when there're at least j layers outside the subtree covered
bool sp[500100];
vector<int>v[500100];
void dfs(int x,int fa){
if(sp[x])f[x][0]=g[x][0]=a[x];//at special points, empty state still need a guard; at normal points, empty state doesn't need a guard.
for(int i=1;i<=m;i++)g[x][i]=a[x];//at whatever points, a state which can spread outside the subtree need a guard.
g[x][m+1]=0x3f3f3f3f;//avoiding transferring outside bounds
for(auto y:v[x]){
if(y==fa)continue;
dfs(y,x);
for(int i=m;i>=0;i--)g[x][i]=min(g[x][i]+f[y][i],f[x][i+1]+g[y][i+1]);
//in this case transferring order doesn't matter.
//but g's transferring must take place before f since it needs f in transferring.
//case 1:guards in x spread into y, where there are i layers downwards y is covered from x.
//case 2:guards in y spread into x, where there are i+1 layers downward x is covered from y, and y can also cover upper levels.
for(int i=m;i>=0;i--)g[x][i]=min(g[x][i],g[x][i+1]);
//in this case it is getting a suffix minimum, where transferring order matters.
f[x][0]=g[x][0];//in fact f[x][0] and g[x][0] have the same meaning(which is a full subtree covered and nothing more)
for(int i=1;i<=m;i++)f[x][i]+=f[y][i-1];
//if there are at most i layers downwards, there should be at most i-1 layers downwards.
for(int i=1;i<=m;i++)f[x][i]=min(f[x][i],f[x][i-1]);
//getting a prefix minimum.
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
scanf("%d",&p);
for(int i=1,x;i<=p;i++)scanf("%d",&x),sp[x]=true;
for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
dfs(1,0);
printf("%d\n",f[1][0]);
return 0;
}CXIV.[POI2014]ZAL-Freight
题解
CXV.[COCI2019]Mobitel
如果正着来DP的话，状态是
这时，我们就要应用一些数论知识了：
若
则
然后，整除又有如下性质：
同时，依据整除分块的性质，
因此我们可以保存上述下取整的结果作为DP状态。此时复杂度就来到了
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,lim,p,a[310][310],f[2][310][2010],deco[2010],code[1001000];
int main(){
scanf("%d%d%d",&n,&m,&lim),lim--;
deco[1]=lim,code[lim]=1,p=1;
for(int i=2;i<=lim;i++)if(lim/i!=deco[p])p++,deco[p]=lim/i,code[lim/i]=p;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
// for(int i=1;i<=p;i++)printf("%d ",deco[i]);puts("");
f[n&1][m][code[lim/a[n][m]]]=1;
for(int i=n;i;i--){
memset(f[!(i&1)],0,sizeof(f[!(i&1)]));
for(int j=m;j;j--)for(int k=0;k<=p;k++){
if(i-1)(f[!(i&1)][j][code[deco[k]/a[i-1][j]]]+=f[i&1][j][k])%=mod;
if(j-1)(f[i&1][j-1][code[deco[k]/a[i][j-1]]]+=f[i&1][j][k])%=mod;
}
}
printf("%d\n",f[1][1][0]);
return 0;
}CXVI.[COCI2014-2015#1] Kamp
一看题面，突然感觉很弱智，不就是求出以每个点为根到其它所有特殊点的距离之和吗？这不是随随便便换个根就完事了吗？
然后兴冲冲敲出来，一测样例全挂。
后来发现并不是这样的，因为车上可以同时搭载多人，且车最后可以就停在某个地方不回去了。
稍微想想可以发现，最终停着的位置，一定是离起点最远的特殊点；故我们直接使用 multiset 维护一下就可以换根了。求出每个节点离其最远的特殊点的距离后，以它为根的答案就是
然后，因为车上可以搭载多人，所以实际上上述最短距离就是二倍以当前点和所有特殊点构成的虚树大小。这个可以直接通过求虚树大小的做法（按照dfs序排序再求出两两相邻点间距离）或者干脆直接再来一发换根解决。
时间复杂度
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,head[500100],cnt,g[500100];
ll f[500100],h[500100];
bool sp[500100];
struct node{
int to,next,val;
}edge[1001000];
void ae(int u,int v,int w){
edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++;
}
multiset<ll>s[500100];
void dfs1(int x,int fa){
if(sp[x])g[x]++,h[x]=0,s[x].insert(0);
for(int i=head[x],y;i!=-1;i=edge[i].next){
if((y=edge[i].to)==fa)continue;
dfs1(y,x),f[x]+=f[y]+1ll*!!g[y]*edge[i].val,g[x]+=g[y];
h[x]=max(h[x],h[y]+edge[i].val),s[x].insert(h[y]+edge[i].val);
}
}
void dfs2(int x,int fa){
for(int i=head[x],y;i!=-1;i=edge[i].next){
if((y=edge[i].to)==fa)continue;
ll fx=f[x]-f[y]-1ll*!!g[y]*edge[i].val;
int gx=g[x]-g[y];
f[y]+=fx+1ll*!!gx*edge[i].val;
g[y]+=gx;
s[x].erase(s[x].find(h[y]+edge[i].val));
if(!s[x].empty())s[y].insert(*s[x].rbegin()+edge[i].val);
s[x].insert(h[y]+edge[i].val);
h[y]=*s[y].rbegin();
dfs2(y,x);
}
}
int main(){
scanf("%d%d",&n,&m),memset(head,-1,sizeof(head)),memset(h,0xc0,sizeof(h));
for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),ae(x,y,z);
for(int i=1,x;i<=m;i++)scanf("%d",&x),sp[x]=true;
dfs1(1,0),dfs2(1,0);
// for(int i=1;i<=n;i++)printf("%lld %d %lld\n",f[i],g[i],h[i]);
for(int i=1;i<=n;i++)printf("%lld\n",2*f[i]-h[i]);
return 0;
}CXVII.[清华集训2012]串珠子
如果直接暴力上状压进行计数是会重复计算的；那么怎样不重不漏地计数呢？
我们发现，要求出连通图的数量是比较难的；但是要求出非联通图的数量是比较简单的，因为我们可以祭出套路。
我们设
则显然，必有
首先，lowbit所在的连通块，然后就把它拆成一个
则时间复杂度
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,a[20][20],f[1<<20],g[1<<20],h[1<<20];
//f:all possible situations
//g:all invalid situations
//h:all valid situations
int main(){
scanf("%d",&n),m=1<<n;
for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%d",&a[i][j]);
f[0]=1;
for(int i=1;i<m;i++){
f[i]=f[i^(i&-i)];
for(int j=__builtin_ctz(i)+1;j<n;j++)if(i&(1<<j))f[i]=1ll*f[i]*(a[j][__builtin_ctz(i)]+1)%mod;
}
for(int i=1;i<m;i++){
for(int U=i^(i&-i),V=U;V;V=(V-1)&U)(g[i]+=1ll*h[i^V]*f[V]%mod)%=mod;
h[i]=(f[i]-g[i]+mod)%mod;
}
printf("%d\n",h[m-1]);
return 0;
}CXVIII.[BJOI2017]机动训练
这题的瓶颈，在于把
但需要注意的是，平行于坐标轴的方向会被重复计算，所以我们应该容斥一下。
代码：
#include<bits/stdc++.h>
using namespace std;
#define y1 _19260817
#define y2 _17680321
const int mod=1e9+9;
int n,m,f[31][31][31][31],dx[8]={1,1,0,-1,-1,-1,0,1},dy[8]={0,1,1,1,0,-1,-1,-1},res,d1,d2,lim;
int dx1[31],dy1[31],dx2[31],dy2[31];
char s[32][32];
int dfs(int x1,int y1,int x2,int y2){
int &now=f[x1][y1][x2][y2];
if(now!=-1)return now;
if(s[x1][y1]!=s[x2][y2])return now=0;
now=1;
for(int i=1;i<=lim;i++){
int X1=x1+dx1[i],Y1=y1+dy1[i],X2=x2+dx2[i],Y2=y2+dy2[i];
if(X1>=1&&X1<=n&&Y1>=1&&Y1<=m&&X2>=1&&X2<=n&&Y2>=1&&Y2<=m)(now+=dfs(X1,Y1,X2,Y2))%=mod;
}
return now;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
for(int d1=0;d1<8;d1++)for(int d2=0;d2<8;d2++){
memset(f,-1,sizeof(f)),lim=0;
for(int i=(d1&1?(d1+7)%8:d1);(i+7)%8!=(d1&1?(d1+1)%8:d1);i++,i%=8)for(int j=(d2&1?(d2+7)%8:d2);(j+7)%8!=(d2&1?(d2+1)%8:d2);j++,j%=8){
lim++;
dx1[lim]=dx[i],dy1[lim]=dy[i];
dx2[lim]=dx[j],dy2[lim]=dy[j];
}
int lam=((d1&1)^(d2&1))?-1:1;
for(int x1=1;x1<=n;x1++)for(int y1=1;y1<=m;y1++)for(int x2=1;x2<=n;x2++)for(int y2=1;y2<=m;y2++)(res+=(mod+lam*dfs(x1,y1,x2,y2))%mod)%=mod;
}
printf("%d\n",res);
return 0;
}CXIX.[SHOI2009]舞会
之前一直在往二项式反演去想，没想到最后居然成了……
我们考虑将男生和女生全部按照高度递减排序，则对于第
然后，我们考虑设
我们考虑DP。设
考虑第
于是就有
然后，最终得到
套上高精度，时间复杂度
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,a[310],b[310],num[310];
struct Wint:vector<int>{
Wint(){clear();}
Wint(int x){clear();while(x)push_back(x%10),x/=10;}
void operator ~(){
for(int i=0;i+1<size();i++){
(*this)[i+1]+=(*this)[i]/10,(*this)[i]%=10;
while((*this)[i]<0)(*this)[i]+=10,(*this)[i+1]--;
}
while(!empty()&&back()>9){
int tmp=back()/10;
back()%=10;
push_back(tmp);
}
while(!empty()&&!back())pop_back();
}
void operator +=(const Wint &x){
if(size()<x.size())resize(x.size());
for(int i=0;i<x.size();i++)(*this)[i]+=x[i];
~*this;
}
void operator -=(const Wint &x){
for(int i=0;i<x.size();i++)(*this)[i]-=x[i];
~*this;
}
friend Wint operator +(Wint x,const Wint &y){
x+=y;
return x;
}
friend Wint operator *(const Wint &x,const Wint &y){
Wint z;
if(!x.size()||!y.size())return z;
z.resize(x.size()+y.size()-1);
for(int i=0;i<x.size();i++)for(int j=0;j<y.size();j++)z[i+j]+=x[i]*y[j];
~z;
return z;
}
void print()const{
if(empty()){putchar('0');return;}
for(int i=size()-1;i>=0;i--)putchar('0'+(*this)[i]);
}
}C[310][310],f[310][310],fac[310];
signed main(){
scanf("%d%d",&n,&m);
fac[0]=1;
for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i;
for(int i=0;i<=n;i++)C[i][0]=1;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)C[i][j]=C[i-1][j-1]+C[i-1][j];
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1),reverse(a+1,a+n+1);
for(int i=1;i<=n;i++)scanf("%d",&b[i]);
sort(b+1,b+n+1),reverse(b+1,b+n+1);
for(int i=1,j=1;i<=n;i++){
while(j<=n&&b[j]>a[i])j++;
num[i]=j-1;
}
f[0][0]=1;
for(int i=0;i<n;i++)for(int j=0;j<=i;j++){
if(j<=num[i+1])f[i+1][j+1]+=f[i][j]*(num[i+1]-j);
f[i+1][j]+=f[i][j];
}
for(int i=0;i<=n;i++)f[n][i]=f[n][i]*fac[n-i];
for(int i=n;i>=0;i--)for(int j=i+1;j<=n;j++)f[n][i]-=C[j][i]*f[n][j];
// for(int i=0;i<=n;i++)printf("%d ",f[n][i]);puts("");
for(int i=1;i<=n;i++)f[n][i]+=f[n][i-1];
f[n][m].print();
return 0;
}CXX.CF917D Stranger Trees
这里是本题的DP解法。矩阵树定理解法详见矩阵树定理学习笔记中重题III.TopCoder13369-TreeDistance。
首先，一个基础结论是，如果一张
然后，考虑二项式反演。设
时间复杂度
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,f[110][110][110],g[110],sz[110],h[110][110],fac[110],inv[110];
vector<int>v[110];
int ksm(int x,int y=mod-2){
int z=1;
for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;
return z;
}
void dfs(int x,int fa){
sz[x]=1,f[x][1][1]=1;
for(auto y:v[x]){
if(y==fa)continue;
dfs(y,x);
for(int i=1;i<=sz[x];i++)for(int I=1;I<=sz[y];I++)for(int j=1;j<=sz[x];j++)for(int J=1;J<=sz[y];J++){
(h[i+I][j]+=1ll*f[x][i][j]*f[y][I][J]%mod*J%mod)%=mod;
(h[i+I-1][j+J]+=1ll*f[x][i][j]*f[y][I][J]%mod)%=mod;
}
for(int i=1;i<=sz[x]+sz[y];i++)for(int j=1;j<=sz[x]+sz[y];j++)f[x][i][j]=h[i][j],h[i][j]=0;
sz[x]+=sz[y];
}
}
int C(int x,int y){return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;}
int main(){
scanf("%d",&n);
for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=ksm(fac[n]);for(int i=n-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
dfs(1,0);
for(int i=0,k=ksm(n);i<n;i++,k=1ll*k*n%mod){
for(int j=1;j<=n;j++)(g[i]+=1ll*f[1][i+1][j]*j%mod)%=mod;
g[i]=1ll*g[i]*k%mod;
}
for(int i=0;i<n;i++)for(int j=0;j<i;j++)(g[i]+=mod-1ll*g[j]*C(n-j-1,i-j)%mod)%=mod;
for(int i=0;i<n;i++)printf("%d ",g[n-i-1]);
return 0;
}CXXI.[GYM100134I][NEERC2012]Identification of Protein
debug5h，精神崩溃。
首先，很容易想到把所有东西都乘上 P 和 Q”的表达形式。因此，整条字符串中所具有的 P 数和 Q 数也就确定了。分别设其为
然后，一条前缀就唯一对应了一条后缀，反之亦然。于是我们便可以建出一张矩阵，P 和 Q（当然，作为前缀和后缀）。此时，一条字符串就对应了一条
但是，一个值如果同时作为前缀和后缀出现，是不能被计算两遍的。所以我们设计DP状态时，要同时记录下正着的和反着的位置，以在上述情况时及时判断出来。我们设 P，后缀里已经填了 Q 的最优收益。采取记忆化搜索进行DP，复杂度
要注意一堆细节，例如实际上当总串长度为奇或偶时，前后缀相遇处时的处理是不一样的。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P=9705276;
const int Q=12805858;
const int inf=-0x3f3f3f3f;
int q,n,m,s,g[410][410],f[210][210][210],opt[210][210][210];
ll a[100100],mx;
double db;
pair<int,int>pr;
pair<int,int>pt(ll ip){
for(int i=0;ip>=0;ip-=P,i++)if(!(ip%Q))return make_pair(i,ip/Q);
return make_pair(-1,-1);
}
int dfs(int stp,int x1,int x2){
int &now=f[stp][x1][x2];
if(now!=-1)return now;
if((x1+x2-(s&1)>n||stp-x1+stp-x2-(s&1)>m)||!(x1<=n&&x2<=n&&stp-x1<=m&&stp-x2<=m))return now=inf;
now=g[x1][stp-x1];
if(x1!=x2&&(x1!=n-x2||stp-x1!=m-(stp-x2)))now+=g[x2][stp-x2];
if(stp==((s+1)>>1))return now;
if(x1+x2>n||stp-x1+stp-x2>m)return now=inf;
int A=dfs(stp+1,x1,x2);
int B=((s&1)&&(stp==(s>>1)))?inf:dfs(stp+1,x1+1,x2);
int C=((s&1)&&(stp==(s>>1)))?inf:dfs(stp+1,x1,x2+1);
int D=dfs(stp+1,x1+1,x2+1);
int M=max({A,B,C,D});
now+=M;
if(A==M)opt[stp][x1][x2]=1;
else if(B==M)opt[stp][x1][x2]=2;
else if(C==M)opt[stp][x1][x2]=3;
else if(D==M)opt[stp][x1][x2]=4;
return now;
}
char res[410];
int main(){
freopen("identification.in","r",stdin);
freopen("identification.out","w",stdout);
scanf("%d",&q),memset(f,-1,sizeof(f));
for(int i=1;i<=q;i++){
scanf("%lf",&db);
a[i]=db*100000+0.1;
mx=max(mx,a[i]);
}
pr=pt(mx),n=pr.first,m=pr.second,s=n+m;
for(int i=1;i<=q;i++){
pr=pt(a[i]);
if(pr==make_pair(-1,-1))continue;
if(pr.first>n||pr.second>m)continue;
g[pr.first][pr.second]++;
if((pr.first<<1)!=n||(pr.second<<1)!=m)g[n-pr.first][m-pr.second]++;
}
dfs(0,0,0);
for(int stp=0,x1=0,x2=0;stp+1<=s-stp;stp++){
if(opt[stp][x1][x2]==1)res[stp+1]='Q',res[s-stp]='Q';
else if(opt[stp][x1][x2]==2)res[stp+1]='P',res[s-stp]='Q',x1++;
else if(opt[stp][x1][x2]==3)res[stp+1]='Q',res[s-stp]='P',x2++;
else if(opt[stp][x1][x2]==4)res[stp+1]='P',res[s-stp]='P',x1++,x2++;
}
printf("%s\n",res+1);
return 0;
}CXXII.CF913E Logical Expression
题解
CXXIII.CF612F Simba on the Circle
题解
CXXIV.[GYM102155J]stairways
首先，考虑暴力
然后，观察到
设前缀
考虑
于是我们考虑全程只使用一个
然后，
于是我们现在要解决两个问题，一是区间加定值
我们对于每个位置
在前缀加
可以使用线段树，但这样就没法很方便地维护单调性；无论是分块还是平衡树维护都可以起到简单维护单调性的功效，直接上即可。
时间复杂度
代码：
/*
f[i]=f[j] (j is the maximal element smaller than i
f[j]=f[j]+s-i (j<i)
f[j]=f[j]+j-i (j>i)
tms=upper[(f[k]-f[j])/(j-k)] where k<j.
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[100100],rt,cnt;
#define lson t[x].ch[0]
#define rson t[x].ch[1]
struct Treap{
int key,rd,ch[2],sz;
ll f,tagf,tagt,tms,mn;
}t[100100];
void pushup(int x){
t[x].mn=t[x].tms,t[x].sz=1;
if(lson)t[x].mn=min(t[x].mn,t[lson].mn),t[x].sz+=t[lson].sz;
if(rson)t[x].mn=min(t[x].mn,t[rson].mn),t[x].sz+=t[rson].sz;
}
void ADDF(int x,ll y){if(x)t[x].tagf+=y,t[x].f+=y;}
void ADDT(int x,ll y=1){if(x)t[x].tagt+=y,t[x].tms-=y,t[x].mn-=y,t[x].f+=1ll*y*t[x].key;}
void pushdown(int x){
ADDF(lson,t[x].tagf),ADDT(lson,t[x].tagt);
ADDF(rson,t[x].tagf),ADDT(rson,t[x].tagt);
t[x].tagf=t[x].tagt=0;
}
int merge(int x,int y){
if(!x||!y)return x+y;
if(t[x].rd>t[y].rd){pushdown(x),t[x].ch[1]=merge(t[x].ch[1],y),pushup(x);return x;}
else{pushdown(y),t[y].ch[0]=merge(x,t[y].ch[0]),pushup(y);return y;}
}
void splitbykey(int x,int k,int &u,int &v){//u:<k.
if(!x){u=v=0;return;}
pushdown(x);
if(t[x].key<k)u=x,splitbykey(rson,k,rson,v);
else v=x,splitbykey(lson,k,u,lson);
pushup(x);
}
void splitbysize(int x,int k,int &u,int &v){
if(!x){u=v=0;return;}
pushdown(x);
if(t[lson].sz>=k)v=x,splitbysize(lson,k,u,lson);
else u=x,splitbysize(rson,k-t[lson].sz-1,rson,v);
pushup(x);
}
int Newnode(int key,ll f){
int x=++cnt;
t[x].f=f,t[x].key=key,t[x].rd=rand()*rand();
pushup(x);
return x;
}
ll flor(ll x,ll y){//the floor-rounded of x/y.
if(x<=0)return 0;
return (x-1)/y+1;
}
void func(int k,int pre){
int a,b,c,d,e;
splitbykey(rt,k,b,c);
ADDF(b,pre);
splitbysize(b,t[b].sz-1,a,b);
splitbykey(c,k+1,c,d);
if(!c)c=Newnode(k,0),t[c].f=t[b].f+k-pre;//because f[b] has already been added by pre.
else t[c].f+=k;
t[c].tms=flor(t[b].f-t[c].f,t[c].key-t[b].key);
pushup(c);
ADDT(d);
splitbysize(d,1,d,e);
if(d)t[d].tms=flor(t[c].f-t[d].f,t[d].key-t[c].key),pushup(d);
rt=merge(merge(merge(merge(a,b),c),d),e);
}
int getmn(int x){
pushdown(x);
if(lson&&t[lson].mn<=0)return getmn(lson);
if(t[x].tms<=0)return t[x].key;
return getmn(rson);
}
void reset(){
while(rt&&t[rt].mn<=0){
int k=getmn(rt);
int a,b,c,d,e;
splitbykey(rt,k,b,c);
splitbysize(b,t[b].sz-1,a,b);
splitbykey(c,k+1,c,d);
splitbysize(d,1,d,e);
if(d)t[d].tms=flor(t[b].f-t[d].f,t[d].key-t[b].key),pushup(d);
rt=merge(merge(a,b),merge(d,e));
}
}
ll getres(){
int a,b;
splitbysize(rt,t[rt].sz-1,a,b);
ll tmp=t[b].f;
rt=merge(a,b);
return tmp;
}
void iterate(int x){
if(!x)return;
pushdown(x);
iterate(lson);
printf("%d:(F:%d TMS:%d MN:%d)\n",t[x].key,t[x].f,t[x].tms,t[x].mn);
iterate(rson);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
rt=Newnode(0,a[1]),t[rt].tms=0x3f3f3f3f;
for(int i=2,j=a[1];i<=n;i++){
j=max(j,a[i]);
func(a[i],j);
// puts("BEF:");iterate(rt);
reset();
// puts("AFT:");iterate(rt);puts("");
}
ll res=getres();
for(int i=1;i<=n;i++)res-=a[i];
printf("%lld\n",res);
return 0;
}
/*
9
44 43 42 41 33 66 32 11 5
*/CXXV.[Topcoder16346]TwoPerLine
跟一年半以前就刷过的经典老题[AHOI2009]中国象棋完全一致，道理非常simple，设
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
class TwoPerLine{
private:
int f[210][210][210];
void add(int &x,int y){x+=y;if(x>=mod)x-=mod;}
int sqr(int x){return (1ll*x*(x-1)/2)%mod;}
public:
int count(int n,int m){
f[0][0][0]=1;
for(int i=0;i<n;i++)for(int j=0;j<=n;j++)for(int k=0;j+k<=n;k++)if(j*2+k<=m){
add(f[i+1][j][k],f[i][j][k]);//put nothing on this colomn
if(k)add(f[i+1][j+1][k-1],1ll*f[i][j][k]*k%mod);//put one chess on an 1-row
if(k>=2)add(f[i+1][j+2][k-2],1ll*f[i][j][k]*sqr(k)%mod);//put both chesses on 1-rows
if(j+k+1<=n)add(f[i+1][j][k+1],1ll*f[i][j][k]*(n-j-k)%mod);//put one chess on a 0-row
if(j+k+2<=n)add(f[i+1][j][k+2],1ll*f[i][j][k]*sqr(n-j-k)%mod);//put both chesses on 0-rows
if(k&&j+k+1<=n)add(f[i+1][j+1][k],1ll*f[i][j][k]*k%mod*(n-j-k)%mod);//put one chess on an 1-row, the other on a 0-row
}
int res=0;
for(int j=0;j<=n;j++)for(int k=0;j+k<=n;k++)if(j*2+k==m)add(res,f[n][j][k]);
return res;
}
}my;
/*
int main(){
// printf("%d\n",my.count(3,6));
// printf("%d\n",my.count(7,0));
// printf("%d\n",my.count(100,3));
// printf("%d\n",my.count(6,4));
return 0;
}
*/CXXVI.[GYM102832J]Abstract Painting
考虑将一个圆心为
因为所有的圆半径很小（
总复杂度
（附，通过子集枚举等trick可以将复杂度优化到
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,mus[1010],f[1010][1<<9],all=(1<<0)|(1<<2)|(1<<4)|(1<<6)|(1<<8),res;
int fob(int ip){
int lim=1;
while(lim<=ip)lim<<=1;
return lim-1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),mus[x+y]|=(1<<((y-1)<<1));
f[0][0]=1;
for(int i=1;i<=n;i++)for(int j=all;;j=(j-1)&all){
if((j&mus[i])==mus[i]&&j<(1<<min(i-1,9))){
int J=fob(j);
// printf("%d:%d:%d\n",i,j,J);
for(int k=0;k<(1<<min(i-1,9));k++){
if(k&j)continue;
(f[i][((k<<1)&((1<<9)-1))|J]+=f[i-1][k])%=mod;
}
}
if(!j)break;
}
for(int i=0;i<(1<<9);i++)(res+=f[n][i])%=mod;
printf("%d\n",res);
return 0;
} CXXVII.[GYM102822I]Invaluable Assets
引理1.最优解法下我们会尽量选取效果为
考虑每袋肥料单位效果所需费用——此为
引理2.最优解法中不会使用效果大于等于
显然，对于一个效果大于等于
引理3.至多使用两种不同肥料。
考虑假设我们有两包肥料
引理4.不存在若干个和为
这很显然，因为你明显可以用很多包
引理5.选择的非
结合引理2、3、4，我们会发现，我们最多选择
则我们考虑暴力背包求出需要肥料总量不大于
现在，考虑回答询问。假设对于一次询问，有一棵树需要生长
考虑将所有询问按照模
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m,q,p,f[30100],h[100100],lim[100100],equ[110],cost;
ll res[100100];
vector<int>v[10100];
ll query(int now,int las){
ll ret=0;
int l1=lower_bound(h+1,h+n+1,now)-h;
int l2=lower_bound(h+1,h+n+1,las-2*m)-h;
for(int i=l2;i<l1;i++){
int tmp=now-h[i];
if(tmp<=3*m)ret+=f[tmp];
else ret+=f[equ[tmp%p]]+1ll*(tmp-equ[tmp%p])/p*cost;
if(h[i]<=las)ret-=f[las-h[i]];
}
ret+=1ll*((now-las)/p)*cost*(l2-1);
return ret;
}
int main(){
scanf("%d",&T);
for(int tt=1;tt<=T;tt++){
scanf("%d%d%d",&n,&m,&q),p=sqrt(m);
if((p*p+m)*(p+1)>((p+1)*(p+1)+m)*p)p++;
// printf("%d\n",p);
cost=p*p+m;
memset(f,0x3f,sizeof(f)),f[0]=0;
for(int i=1;i<=2*p;i++)for(int j=i;j<=3*m;j++)f[j]=min(f[j],f[j-i]+i*i+m);
// for(int i=0;i<=3*m;i++)printf("%d ",f[i]);puts("");
for(int i=1;i<=n;i++)scanf("%d",&h[i]);sort(h+1,h+n+1);
// for(int i=1;i<=n;i++)printf("%d ",h[i]);puts("");
for(int i=1;i<=q;i++)scanf("%d",&lim[i]),v[lim[i]%p].push_back(i);
for(int i=m-p+1;i<=m;i++)equ[i%p]=i;
for(int i=0;i<p;i++){
if(v[i].empty())continue;
sort(v[i].begin(),v[i].end(),[](int x,int y){return lim[x]<lim[y];});
res[v[i][0]]=query(lim[v[i][0]],0);
for(int j=1;j<v[i].size();j++)res[v[i][j]]=res[v[i][j-1]]+query(lim[v[i][j]],lim[v[i][j-1]]);
v[i].clear();
}
printf("Case #%d:\n",tt);
for(int i=1;i<=q;i++)printf("%lld\n",res[i]);
}
return 0;
}CXXVIII.[AGC020E] Encoding Subsets
这种“压缩”题可以考虑区间DP。但是若考虑标准的区间的话它“子集”等定义又不好处理。
于是我们考虑对字符串作DP。设
显然，其有两种转移方式：一种是
于是我们枚举循环节长度以及循环次数，找到这所有循环串的交集（仍是一个串），然后转移即可。
使用 map 维护DP状态，复杂度玄学，但能过。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
string s;
void merge(string &s,string t){//merge string t into s
for(int i=0;i<s.size();i++)if(t[i]=='0')s[i]='0';
}
map<string,int>mp;
int dfs(string s){
if(s.empty())return 1;
if(s.size()==1)return s[0]=='0'?1:2;
if(mp.find(s)!=mp.end())return mp[s];
int ret=1ll*dfs(s.substr(0,1))*dfs(s.substr(1))%mod;//encoding the leading character separately
for(int i=1;(i<<1)<=s.size();i++){//encoding i charactets together as a permutation chapter
string t=s.substr(0,i);
for(int j=i;j+i<=s.size();j+=i)merge(t,s.substr(j,i)),(ret+=1ll*dfs(t)*dfs(s.substr(j+i))%mod)%=mod;
}
return mp[s]=ret;
}
int main(){
cin>>s;
printf("%d\n",dfs(s));
return 0;
}CXXIX.CF559E Gerald and Path
考虑将所有线段按照固定的那一端从小往大排序，并且对线段的端点离散化。
这之后，设
我们考虑，假设我们放了一根线段
于是我们现在考虑处理第
首先，其有可能在接下来（或者在
其次，考虑其向右摆。向右摆，就意味着最右位置一定是
则有
但是这也意味着，我们的线段
然后就考虑其向左摆了。向左摆，就意味着最右位置不一定是
首先，最右位是
然后，对于最右位不是
设所有
时间复杂度
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,f[110][310];
pair<int,int>p[110];
vector<int>v;
int L[110],P[110],R[110],res;
#define bs(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&p[i].first,&p[i].second),v.push_back(p[i].first),v.push_back(p[i].first-p[i].second),v.push_back(p[i].first+p[i].second);
sort(p+1,p+n+1),sort(v.begin(),v.end()),v.resize(m=unique(v.begin(),v.end())-v.begin());
for(int i=1;i<=n;i++)L[i]=bs(p[i].first-p[i].second),P[i]=bs(p[i].first),R[i]=bs(p[i].first+p[i].second);
for(int i=1;i<=n;i++){
memcpy(f[i],f[i-1],sizeof(f[i]));
for(int j=P[i];j<=R[i];j++)f[i][j]=max(f[i][j],f[i-1][P[i]]+v[j-1]-v[P[i]-1]);
for(int j=i;j;j--){
int Rmax=(j==i?P[j]:R[j]);
if(Rmax<P[i])continue;
int Lmin=(j==i?L[j]:P[j]);
for(int k=j+1;k<=i;k++)Lmin=min(Lmin,L[k]);
for(int k=Lmin;k<=Rmax;k++)f[i][k]=max(f[i][k],f[j-1][Lmin]+v[k-1]-v[Lmin-1]);
}
for(int j=1;j<=m;j++)f[i][j]=max(f[i][j],f[i][j-1]);
}
for(int i=1;i<=m;i++)res=max(res,f[n][i]);
printf("%d\n",res);
return 0;
}CXXX.[GYM102904B]Dispatch Money
考虑设
区间逆序对数不好处理，但是我们考虑像莫队一样处理，则其可以轻松地使用树状数组，从任何一个
类莫队转移是分治优化DP的配套。但是分治优化DP要求转移具有单调性，此处明显
分治优化还得有一个前提，即转移分层，形式化来说就是转移形如
但是，在分治的外面再套一个CDQ分治，即可使得转移分层——总是左子区间的
于是复杂度
但我们还不满足。现在考虑优化。
明显优化只能从树状数组下手。于是问题转换为能否
考虑分块预处理。我们在值域上每
但是这样的查询是离线的。只需要对其可持久化即可做到在线询问。因为每次加入一个数，只会变动
这里因为笔者不会
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[300100],t[300100];
void ADD(int x,int tp){while(x)t[x]+=tp,x-=x&-x;}
int SUM(int x){int ret=0;while(x<=n)ret+=t[x],x+=x&-x;return ret;}
int LL=1,RR;
ll sum,f[300100];
void PushL(int x){
sum+=SUM(1)-SUM(a[x]);
ADD(a[x],1);
}
void PopL(int x){
ADD(a[x],-1);
sum-=SUM(1)-SUM(a[x]);
}
void PushR(int x){
sum+=SUM(a[x]);
ADD(a[x],1);
}
void PopR(int x){
ADD(a[x],-1);
sum-=SUM(a[x]);
}
ll CALC(int L,int R){
// printf("BEF:%d\n",sum);
while(LL>L)PushL(--LL);
while(RR<R)PushR(++RR);
// printf("BEF:%d\n",sum);
while(LL<L)PopL(LL++);
while(RR>R)PopR(RR--);
// printf("[%d,%d]:%d\n",L,R,sum);
return sum;
}
void solve(int l,int r,int L,int R){
if(l>r)return;
// printf("[%d,%d]:[%d,%d]\n",l,r,L,R);
int mid=(l+r)>>1,MID=L;
ll mn=CALC(L+1,mid)+f[L];
for(int i=L+1;i<=R;i++)if(CALC(i+1,mid)+f[i]<mn)mn=CALC(i+1,mid)+f[i],MID=i;
f[mid]=min(f[mid],mn+m);
solve(l,mid-1,L,MID),solve(mid+1,r,MID,R);
}
void CDQ(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
CDQ(l,mid);
solve(mid+1,r,l,mid);
CDQ(mid+1,r);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),f[i]=CALC(1,i)+m;
// for(int i=1;i<=n;i++)printf("%d ",f[i]);puts("");
CDQ(1,n);
// for(int i=1;i<=n;i++)printf("%d ",f[i]);puts("");
printf("%lld\n",f[n]);
return 0;
}CXXXI.[GYM102331J]Jiry Matchings
首先，不难想到一个
我们知道一个结论——对于任意带权网络流图，随着总流量的增加，最大费用是凸函数，即差分不增的函数。这可以被这样证明：我们在
显然，最大带权匹配也是带权网络流模型，也因此
我们考虑合并一条边连接着的两个子树（也即一对父子），不妨设父亲为
下面我们来考虑如何定义卷积。明显，数组间的卷积，不妨设为
这个卷积对于普通的
现在考虑数组与整数间卷积，明显就直接背包即可，也可
于是我们合并一条边连接的子树的复杂度就是
下面考虑祭出一些奇奇怪怪的合并方式。考虑对这棵树重链剖分。
现在，我们考虑先求出每个点仅考虑其所有轻儿子的子树时，其此时的
明显，对于点
现在要求出其所有轻儿子转移上来的东西的卷积。如果直接按顺序一个一个乘的话，复杂度是
但是，如果我们对其分治地进行合并的话，复杂度就是
显然，每个轻儿子仅会被转移一次，所以处理这个轻儿子的复杂度就是
下面我们考虑重链部分的转移。显然，如果仍考虑归并地转移的话——显然，这里归并的状态就需要四个数组，即区间顶有/无被匹配、区间底有/无被匹配，且当归并到长度为
总复杂度 vector 模拟每个函数。不必担心空间、时间等常数问题，因为我写的非常随便的代码都没卡常过去了，事实上大概也跑不满。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=0x8080808080808080;
int n,head[200100],cnt;
struct node{int to,next,val;}edge[400100];
void ae(int u,int v,int w){
edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++;
}
struct Array:vector<ll>{
Array(){resize(1);}
friend Array operator +(const Array &u,const Array &v){
Array w;
w.resize(u.size()+v.size()-1);
for(int i=1,j=1,k=1;k<w.size();k++){
if(i==u.size()){w[k]=w[k-1]+v[j]-v[j-1],j++;continue;}
if(j==v.size()){w[k]=w[k-1]+u[i]-u[i-1],i++;continue;}
if(u[i]-u[i-1]>v[j]-v[j-1])w[k]=w[k-1]+u[i]-u[i-1],i++;
else w[k]=w[k-1]+v[j]-v[j-1],j++;
}
return w;
}
friend Array operator +(const Array &u,const int &v){
Array w=u;w.push_back(inf);
for(int i=1;i<w.size();i++)w[i]=max(w[i],u[i-1]+v);
return w;
}
friend Array operator |(const Array &u,const Array &v){
Array w;w.assign(max(u.size(),v.size()),inf);
for(int i=0;i<w.size();i++){
if(i<u.size())w[i]=max(w[i],u[i]);
if(i<v.size())w[i]=max(w[i],v[i]);
}
return w;
}
void print()const{for(auto i:*this)printf("%d ",i);puts("");}
};
struct Paira{
Array f,g;//f is the array for self matched-or-not, while g is the self not matched
Paira(){f=Array(),g=Array();}
Paira(Array F,Array G){f=F,g=G;}
friend Paira operator +(const Paira &u,const Paira &v){
Paira w;
w.f=(u.f+v.g)|(u.g+v.f);
w.g=u.g+v.g;
w.f=w.f|w.g;
// puts("U");u.print();
// puts("V");v.print();
// puts("W");w.print();
return w;
}
void print()const{printf("[1]"),f.print();printf("[0]"),g.print();}
}a[200100];
struct Quada{
Paira f,g;//f for upper matched-or-not, g for upper not matched
Quada(){f=Paira(),g=Paira();}
Quada(Paira F,Paira G){f=F,g=G;}
friend Quada merge(const Quada &u,const int &v,const Quada &w,bool U,bool W){
Quada r;
r.f.f=(u.f.f+w.f.f)|((u.f.g+w.g.f)+v);
r.f.g=(u.f.f+w.f.g);
if(W)r.f.g=r.f.g|((u.f.g+w.g.g)+v);
r.g.f=(u.g.f+w.f.f);
if(U)r.g.f=r.g.f|((u.g.g+w.g.f)+v);
r.g.g=(u.g.f+w.f.g);
if(U&&W)r.g.g=r.g.g|((u.g.g+w.g.g)+v);
r.f.g=r.f.g|r.g.g,r.g.f=r.g.f|r.g.g;
r.f.f=r.f.f|r.f.g|r.g.f;
// puts("U"),u.print();
// puts("W"),w.print();
// puts("R"),r.print();puts("");
return r;
}
void print()const{puts("[[F]]"),f.print();puts("[[G]]"),g.print();}
};
int fa[200100],son[201000],top[200100],sz[200100],val[200100];
void dfs1(int x){
sz[x]=1;
for(int i=head[x],y;i!=-1;i=edge[i].next){
if((y=edge[i].to)==fa[x])continue;
fa[y]=x,val[y]=edge[i].val,dfs1(y),sz[x]+=sz[y];
if(sz[y]>sz[son[x]])son[x]=y;
}
}
vector<int>v;
Paira lightsonsolve(int l,int r){
if(l==r-1)return Paira(a[v[l]].g+val[v[l]],a[v[l]].f);
int mid=(l+r)>>1;
return lightsonsolve(l,mid)+lightsonsolve(mid,r);
}
Quada heavysonsolve(int l,int r){
if(l==r)return Quada(Paira(a[v[l]].f,a[v[l]].g),Paira(a[v[l]].g,a[v[l]].g));
int mid=(l+r)>>1;
// printf("(%d,%d]:(%d,%d]+(%d,%d]\n",l,r,l,mid,mid,r);
return merge(heavysonsolve(l,mid),val[v[mid+1]],heavysonsolve(mid+1,r),l!=mid,mid+1!=r);
}
void dfs2(int x){
if(!top[x])top[x]=x;
if(son[x])top[son[x]]=top[x],dfs2(son[x]);
for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=fa[x]&&edge[i].to!=son[x])dfs2(edge[i].to);
v.clear();for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=fa[x]&&edge[i].to!=son[x])v.push_back(edge[i].to);
// printf("LIT%d:",x);for(auto i:v)printf("%d ",i);puts("");
if(!v.empty())a[x]=lightsonsolve(0,v.size());
// a[x].print();puts("");
if(top[x]!=x)return;
v.clear();for(int i=x;i;i=son[i])v.push_back(i);
// printf("CHA%d:",x);for(auto i:v)printf("%d ",i);puts("");
Quada tmp=heavysonsolve(0,v.size()-1);
a[x]=Paira(tmp.f.f,tmp.g.f);
}
int main(){
scanf("%d",&n),memset(head,-1,sizeof(head));
for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),ae(x,y,z);
dfs1(1),dfs2(1);
// for(int i=1;i<=n;i++)printf("%d %d %d %d %d\n",fa[i],son[i],top[i],sz[i],val[i]);
// for(int i=1;i<=n;i++)printf("%d:%d\n",i,a[i].f.size());
for(int i=1;i<n;i++)if(i<a[1].f.size())printf("%lld ",a[1].f[i]);else printf("? ");puts("");
return 0;
} CXXXII.[GYM102268J]Jealous Split
wqs二分。
首先，先讲一下wqs二分的应用条件：
对于某个函数
具体来说，明显
明显我们可以二分
但需要注意的是，对于某些
我们回到本题。
先从简单的情形想起：假如仅能切一刀，应该怎么切？
明显我们可以初始令最左方的元素单独成段，然后剩下元素再成一段。之后，不断向右移动切点，直到再往右移动会使得左段元素和大于右端元素和。这时，明显一定满足题目要求，因为当且仅当切点将要跨越的那个元素比当前的差要大才会停止移动，而这本身就表明已经有一个元素大于当前差的绝对值。
当能切更多刀时，明显我们可以通过逐步调整法使得每一刀都符合上述要求，也即解一定存在。
我们发现，这种情形下，对于任意实数
于是我们现在就要找到一种分成
但是，我们发现平方和，随着段数的越分越多，肯定是递减的；不仅如此，其还是下凸的，因为否则我们一定可以更早地分开一段使答案更优。
考虑套上wqs二分。于是我们就变成了每切一段需要额外的代价
但是依据我们上文对wqs二分的分析，其好像并不能很好地求出方案来（因为不能保证切线刚好就切到我们需要的点上）。事实上，对于大多数的wqs二分题，我们都无法找到一种方案。
但是，注意到这里说的是大多数！事实上，对于本题这种“区间划分”wqs二分问题，的确是有一种构造方案的。具体而言，当求出的区间包含目标位置时，我们可以求出分段最少的方法以及最多的方法——可以通过斜率优化时当队首首个和次个元素的斜率与所需斜率相等时，出不出队来分别求出。明显我们的目标介于两种方法之间。
考虑用一种方法的一段前缀与另一种方法的一段后缀拼成完整的分段方案。考虑如何拼接。
首先，若两者方法出现了相同的分割点，明显在分割点处拼接前一半和后一半是一种合法的方案，因为最小方法和最大方法本质相当于从初始状态到终止状态的两条不同的最短路，一条从起点到终点的最短路，对于路径上所有节点，也必是最短路，故拼接合法。
我们还有一种拼接方法。考虑最少方案中，出现了一段区间
可以被证明的是，一定存在一种拼接方案满足长度恰好为任何
于是我们现在已经知道如何二分、如何构造方式了。是不是就结束了呢？
稍等！我们还没有讨论
然后就是一些具体实现的问题了。一开始我wqs二分写的是实数二分，因为考虑到斜率可能为一切实数。但是后来思考发现，只需整数二分，得到的直线就可以切到所有点，于是就换成了整数二分。
实际上，还有一个原因是本题数据范围就非常尴尬（序列中所有数之和最大为 int，平方后就爆了 long long），即使使用long double，也会被卡精度 WA 71。用实数二分就无法避免地用 long double 存状态，因此会挂。
但是爆 long long 也意为着我们不能使用 long long 储存。我尝试使用了压 13 个 bit 的 int 来模拟 __int128，但是被卡常了。所以最后索性直接上了 __int128（第一次知道 CF 开 C++17(64) 就能用 __int128 的），才卡过。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 ii;
int n,m,F[100100],G[100100];
ii f[100100],g[100100];
ll s[100100];
ii sqr(ll x){return (ii)x*x;}
int read(){
int x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
int q[100100],l,r;
int che(ll ip){
// printf("%lld:\n",ip);
l=r=0;
for(int i=1;i<=n;i++){
if(s[i]==s[i-1]){f[i]=f[i-1],F[i]=F[i-1];continue;}
// if(r-l>=1)(2*BigNum(s[i])*(s[q[l+1]]-s[q[l]])).print(),(f[q[l+1]]-f[q[l]]+sqr(s[q[l+1]])-sqr(s[q[l]])).print(),puts("");
while(r-l>=1&&f[q[l+1]]-f[q[l]]+sqr(s[q[l+1]])-sqr(s[q[l]])<(ii)2*s[i]*(s[q[l+1]]-s[q[l]]))l++;
F[i]=q[l],f[i]=f[q[l]]+sqr(s[i]-s[q[l]])+ip;
while(r-l>=1&&(f[q[r]]-f[q[r-1]]+sqr(s[q[r]])-sqr(s[q[r-1]]))*(s[i]-s[q[r]])>(f[i]-f[q[r]]+sqr(s[i])-sqr(s[q[r]]))*(s[q[r]]-s[q[r-1]]))r--;
q[++r]=i;
}
// for(int i=1;i<=n;i++)f[i].print();puts("");
// for(int i=1;i<=n;i++)printf("%d ",F[i]);puts("");
l=r=0;
for(int i=1;i<=n;i++){
if(s[i]==s[i-1]){g[i]=g[i-1],G[i]=G[i-1];continue;}
// if(r-l>=1)printf("%d:%d,%d\n",i,q[l],q[l+1]),(2*BigNum(s[i])*(s[q[l+1]]-s[q[l]])).print(),(g[q[l+1]]-g[q[l]]+sqr(s[q[l+1]])-sqr(s[q[l]])).print(),puts("");
while(r-l>=1&&g[q[l+1]]-g[q[l]]+sqr(s[q[l+1]])-sqr(s[q[l]])<=(ii)2*s[i]*(s[q[l+1]]-s[q[l]]))l++;
G[i]=q[l],g[i]=g[q[l]]+sqr(s[i]-s[q[l]])+ip;
while(r-l>=1&&(g[q[r]]-g[q[r-1]]+sqr(s[q[r]])-sqr(s[q[r-1]]))*(s[i]-s[q[r]])>=(g[i]-g[q[r]]+sqr(s[i])-sqr(s[q[r]]))*(s[q[r]]-s[q[r-1]]))r--;
q[++r]=i;
}
// for(int i=1;i<=n;i++)g[i].print();puts("");
// for(int i=1;i<=n;i++)printf("%d ",G[i]);puts("");
l=0;for(int i=n;i;i=F[i])l++;
r=0;for(int i=n;i;i=G[i])r++;
// printf("[%d %d]\n",l,r);
if(l>m)return -1;
if(r<m)return 1;
return 0;
}
vector<int>u,v;
int tot;
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)s[i]=s[i-1]+read(),tot+=(s[i]!=s[i-1]);
puts("Yes");
if(tot<m){//cases when there have to be single 0 sections
for(int i=1;i<n;i++){
if(tot<m&&s[i]==s[i-1])tot++,printf("%d ",i);
if(s[i]!=s[i-1])printf("%d ",i);
}puts("");return 0;
}
// for(int i=1;i<=n;i++)printf("%Lf ",s[i]);puts("");
ll L=0,R=0x3f3f3f3f3f3f3f3f,mid;
while(true){
// printf("%lld %lld\n",L,R);
int tmp=che(mid=(L+R)>>1);
if(tmp==-1)L=mid+1;
if(tmp==1)R=mid-1;
if(!tmp)break;
}
// printf("%d %d\n",l,r);
for(int i=n;i;i=F[i])u.push_back(i);u.push_back(0),reverse(u.begin(),u.end());
for(int i=n;i;i=G[i])v.push_back(i);v.push_back(0),reverse(v.begin(),v.end());
// for(auto i:u)printf("%d ",i);puts("");
// for(auto i:v)printf("%d ",i);puts("");
// if(l==m){for(int i=1;i+1<u.size();i++)printf("%d ",u[i]);puts("");return 0;}
// if(r==m){for(int i=1;i+1<v.size();i++)printf("%d ",v[i]);puts("");return 0;}
for(int i=1,j=0;i<u.size();i++){
for(;j<v.size()&&v[j]<u[i];j++){
if(!j||v[j-1]<=u[i-1])continue;
if(i+v.size()-j-1==m){for(int k=1;k<i;k++)printf("%d ",u[k]);for(int k=j;k+1<v.size();k++)printf("%d ",v[k]);puts("");return 0;}
if(j+u.size()-i-1==m){for(int k=1;k<j;k++)printf("%d ",v[k]);for(int k=i;k+1<u.size();k++)printf("%d ",u[k]);puts("");return 0;}
}
if(j==v.size()||v[j]!=u[i])continue;
if(i+v.size()-j-1==m){for(int k=1;k<i;k++)printf("%d ",u[k]);for(int k=j;k+1<v.size();k++)printf("%d ",v[k]);puts("");return 0;}
if(j+u.size()-i-1==m){for(int k=1;k<j;k++)printf("%d ",v[k]);for(int k=i;k+1<u.size();k++)printf("%d ",u[k]);puts("");return 0;}
}
return 0;
}CXXXIII.[HDU6094]Rikka with K-Match
依旧wqs二分。
首先，依据我们之前提到过的一个性质，“凡是可以表示成费用流模型的东西都有凹凸性”，本题也不例外，关于匹配个数的函数是凹的。
凹的就可以wqs二分。于是问题转换为最小权任意匹配。因为
需要注意的是本题二分的边界。或许会认为仅仅是 long long，同时还能求出答案。
时间复杂度
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m,q,X[40100][4],Y[40100][4],F[40100][4][1<<4],G[40100][4][1<<4],lim;
ll f[40100][4][1<<4];
void chmn(int i,int j,int k,int K,ll bon,bool mat){
int I=i-!j,J=(!j?m:j)-1;
if(f[i][j][k]>f[I][J][K]+bon)f[i][j][k]=f[I][J][K]+bon,F[i][j][k]=F[I][J][K]+mat,G[i][j][k]=G[I][J][K]+mat;
else if(f[i][j][k]==f[I][J][K]+bon)F[i][j][k]=min(F[i][j][k],F[I][J][K]+mat),G[i][j][k]=max(G[i][j][k],G[I][J][K]+mat);
}
int che(ll ip){
// printf("%d\n",ip);
for(int i=0;i<n;i++)for(int j=0;j<m;j++){
if(!i&&!j){for(int k=0;k<lim;k++)f[i][j][k]=0;continue;}
for(int k=0;k<lim;k++)f[i][j][k]=0x3f3f3f3f3f3f3f3f;
for(int k=0;k<lim;k++){
if(i&&!(k&(1<<j)))chmn(i,j,k|(1<<j),k,X[i][j]-ip,true);
if(j&&!(k&(1<<(j-1))))chmn(i,j,k|(1<<(j-1))|(1<<j),k,Y[i][j]-ip,true);
chmn(i,j,k&(lim-1-(1<<j)),k,0,false);
}
}
ll mn=0x3f3f3f3f3f3f3f3f;
for(int k=0;k<lim;k++)mn=min(mn,f[n-1][m-1][k]);
int L=0x3f3f3f3f,R=0;
for(int k=0;k<lim;k++)if(mn==f[n-1][m-1][k])L=min(L,F[n-1][m-1][k]),R=max(R,G[n-1][m-1][k]);
if(L>q)return -1;
if(R<q)return 1;
printf("%lld\n",mn+ip*q);
return 0;
}
void read(int &x){
x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
int main(){
read(T);
while(T--){
read(n),read(m),read(q),lim=1<<m;
for(int i=1;i<n;i++)for(int j=0;j<m;j++)read(X[i][j]);
for(int i=0;i<n;i++)for(int j=1;j<m;j++)read(Y[i][j]);
ll l=0,r=1e14,mid;
while(true){
int tp=che(mid=(l+r)>>1);
if(tp==-1)r=mid-1;
if(tp==1)l=mid+1;
if(!tp)break;
}
}
return 0;
}CXXXIV.[BZOJ3864]Hero meet devil
我们不妨从最trival的LCS问题上想起：暴力的LCS求法是什么？
设
因为
明显，对于 A,G,C,T 四个字符会分别到达哪个新状态即可。然后直接DP就行了。
这种手法被称作“DP on DP”，因为DP状态中储存了另一种更简单的DP的数组。可以发现，简单DP的数组压缩后得到了一张自动姬。
时间复杂度
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int T,n,m,f[2][1<<15],lim,t[20],a[20],b[20],res[20],trans[1<<15][4];
char s[20];
int main(){
scanf("%d",&T);
while(T--){
scanf("%s%d",s+1,&m),n=strlen(s+1),lim=1<<n;
for(int i=1;i<=n;i++){
if(s[i]=='A')t[i]=0;
if(s[i]=='G')t[i]=1;
if(s[i]=='C')t[i]=2;
if(s[i]=='T')t[i]=3;
}
for(int j=0;j<lim;j++){
for(int k=0;k<n;k++)a[k+1]=a[k]+((j>>k)&1);
for(int c=0;c<4;c++){
for(int k=1;k<=n;k++)b[k]=max({a[k-1]+(t[k]==c),a[k],b[k-1]});
trans[j][c]=0;
for(int k=0;k<n;k++)trans[j][c]|=(b[k+1]-b[k])<<k;
}
}
memset(f,0,sizeof(f)),f[0][0]=1;
for(int i=0;i<m;i++){
memset(f[!(i&1)],0,sizeof(f[!(i&1)]));
for(int j=0;j<lim;j++)for(int k=0;k<4;k++)(f[!(i&1)][trans[j][k]]+=f[i&1][j])%=mod;
}
// for(int i=0;i<=m;i++){for(int j=0;j<lim;j++)printf("%d ",f[i][j]);puts("");}
for(int i=0;i<lim;i++)(res[__builtin_popcount(i)]+=f[m&1][i])%=mod;
for(int i=0;i<=n;i++)printf("%d\n",res[i]),res[i]=0;
}
return 0;
}CXXXV.[ZOJ3989]Triangulation
神题。
这个数据范围很难不让人想到状压DP。于是我们考虑应该怎么设计状态。
考虑一组三角剖分的形态：其必定是在所有点所构成的凸包内部划分出很多三角形。这也就表明，任何一组三角剖分一定包含所有凸包上的边。
我们可以想到一个比较简洁的DP：设
于是我们另辟蹊径。我们令初始三角剖分上的边仅包含所有点集的下凸壳上的所有边。之后，维护当前剖分的上边界，每次往上边界上添加一个新的三角形，得到新的上边界，这样持续不断直到填成了整个点集的上凸壳。
但是，出于不重复计数的考虑，我们必须对该上边界做出限制。
我们强制该上边界上的点的
同时，为了处理有点
接着考虑如何添加三角形。
我们发现，其可以分为两种情形：
-
对于边界上连续的三个点
A,B,C ，满足B 在AC 下方，且\triangle_{ABC} 内部无点，此时便可以连边AC ，将B 从边界上删除。 -
对于边界上连续的两个点
A,B ，存在一个C 在AB 上方，且C 的x 坐标介于A,B 之间，且\triangle_{ABC} 内部无点，此时便可以连边AC,BC ，并将C 插入上边界。
为了不重复计算，我们每次仅加入上边界上最左的三角形。也就是说，如果一条边
这样，我们便可以设
需要注意的是，因为
通过预处理一大坨东西（三角形内部有没有点啦、情形2的哪些
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,ord[20],a[20][20],rev[20],f[1<<16][17],in[1<<16],b[20];
ll g[1<<16][17];
const double eps=1e-13;
const double pi=acos(-1);
int cmp(double x){
if(x>eps)return 1;
if(x<-eps)return -1;
return 0;
}
struct Vector{
double x,y;
Vector(){}
Vector(double X,double Y){x=X,y=Y;}
friend Vector operator +(const Vector &u,const Vector &v){return Vector(u.x+v.x,u.y+v.y);}
friend Vector operator -(const Vector &u,const Vector &v){return Vector(u.x-v.x,u.y-v.y);}
friend Vector operator *(const Vector &u,const double &v){return Vector(u.x*v,u.y*v);}
friend Vector operator /(const Vector &u,const double &v){return Vector(u.x/v,u.y/v);}
friend double operator &(const Vector &u,const Vector &v){return u.x*v.y-u.y*v.x;}//cross times
friend double operator |(const Vector &u,const Vector &v){return u.x*v.x+u.y*v.y;}//point times
friend bool operator <(const Vector &u,const Vector &v){return u.x<v.x;}
double operator ~()const{return sqrt(x*x+y*y);}//the modulo of a vector
double operator !()const{return atan2(y,x);}//the angle of a vector
void print(){printf("(%lf,%lf)",x,y);}
void rotate(double ang){
double modu=~*this;
double angl=!*this;
angl+=ang;
x=cos(angl)*modu,y=sin(angl)*modu;
}
}p[20];
typedef Vector Point;
struct Line{
Point x,y;
Vector z;
Line(){}
Line(Point X,Point Y){x=X,y=Y,z=Y-X;}
friend Point operator &(const Line &u,const Line &v){return u.x+u.z*((v.z&(u.x-v.x))/(u.z&v.z));}
};
typedef Line Segment;
bool CMP(int u,int v){return p[u].x<p[v].x;}
bool lower[20],upper[20];
int stk[20],tp,LO,UP;
queue<int>q;
void trans(int i,int j,int I,int J,int k){
if(!--in[I])q.push(I);
if(f[I][J]>k)f[I][J]=k,g[I][J]=g[i][j];
else if(f[I][J]==k)g[I][J]+=g[i][j];
}
vector<int>v[20][20];
bool abv[20][20][20],ins[20][20][20];//if above, true.
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n),LO=UP=0,memset(f,0x3f,sizeof(f)),memset(in,0,sizeof(in)),memset(ins,true,sizeof(ins));
for(int i=0;i<n;i++)scanf("%lf%lf",&p[i].x,&p[i].y),ord[i]=i,lower[i]=upper[i]=false;
while(true){
double ang=(1.0*rand()/RAND_MAX)*2*pi;
for(int i=0;i<n;i++)p[i].rotate(ang);
sort(ord,ord+n,CMP);
bool ok=true;
for(int i=1;i<n;i++)if(!cmp(p[i].x-p[i-1].x)){ok=false;break;}
if(ok)break;
}
for(int i=0;i<n;i++)rev[ord[i]]=i;
for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%d",&a[rev[i]][rev[j]]);
sort(p,p+n);
// for(int i=0;i<n;i++)p[i].print();puts("");
for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)for(int k=i+1;k<j;k++)abv[i][j][k]=(cmp((p[i]-p[k])&(p[j]-p[k]))==1);
stk[++tp]=0;
for(int i=1;i<n;i++){
while(tp>=2&&cmp((p[stk[tp-1]]-p[stk[tp]])&(p[i]-p[stk[tp]]))!=-1)tp--;
stk[++tp]=i;
}
for(int i=1;i<=tp;i++)lower[stk[i]]=true,LO|=1<<stk[i];
LO=(LO^(1<<(n-1)))>>1,f[LO][0]=0,g[LO][0]=1;
for(int i=1;i<tp;i++)f[LO][0]+=a[stk[i]][stk[i+1]];
tp=0;
stk[++tp]=0;
for(int i=1;i<n;i++){
while(tp>=2&&cmp((p[stk[tp-1]]-p[stk[tp]])&(p[i]-p[stk[tp]]))!=1)tp--;
stk[++tp]=i;
}
for(int i=1;i<=tp;i++)upper[stk[i]]=true,UP|=1<<stk[i];
UP=(UP^(1<<(n-1)))>>1;
tp=0;
// printf("STA:%d %d\n",LO,UP);
// for(int i=0;i<n;i++)printf("(%d %d)",lower[i],upper[i]);puts("");
for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){
for(int k=i+1;k<j;k++){
if(abv[i][j][k]){
bool ok=true;
for(int l=i+1;l<k;l++)if(abv[i][j][l]&&!abv[i][k][l]){ok=false;break;}
if(!ok)continue;
for(int l=k+1;l<j;l++)if(abv[i][j][l]&&!abv[k][j][l]){ok=false;break;}
if(!ok)continue;
v[i][j].push_back(k);
}else{
ins[i][j][k]=false;
for(int l=i+1;l<k;l++)if(!abv[i][j][l]&&abv[i][k][l]){ins[i][j][k]=true;break;}
for(int l=k+1;l<j;l++)if(!abv[i][j][l]&&abv[k][j][l]){ins[i][j][k]=true;break;}
}
}
}
for(int i=0;i<(1<<(n-2));i++){
int len=0;b[len++]=0;
for(int j=0;j<n-2;j++)if(i&(1<<j))b[len++]=j+1;
b[len++]=n-1;
// printf("%d:",i);for(int j=0;j<len;j++)printf("%d ",b[j]);puts("");
for(int j=0;j<len;j++){
if(j&&j+1<len&&!ins[b[j-1]][b[j+1]][b[j]])in[i^(1<<(b[j]-1))]++;
if(j)for(auto k:v[b[j-1]][b[j]])in[i|(1<<(k-1))]++;
}
}
q.push(LO);
while(!q.empty()){
int i=q.front();q.pop();
// printf("SS:%d\n",i);
int len=0;b[len++]=0;
for(int j=0;j<n-2;j++)if(i&(1<<j))b[len++]=j+1;
b[len++]=n-1;
for(int j=0;j<len;j++){
if(j&&j+1<len&&!ins[b[j-1]][b[j+1]][b[j]])trans(i,j,i^(1<<(b[j]-1)),j-1,f[i][j]+a[b[j-1]][b[j+1]]);
if(j)for(auto k:v[b[j-1]][b[j]])trans(i,j-1,i|(1<<(k-1)),j-1,f[i][j-1]+a[b[j-1]][k]+a[b[j]][k]);
if(j+2<len)trans(i,j,i,j+1,f[i][j]);
}
}
printf("%d %lld\n",f[UP][__builtin_popcount(UP)],g[UP][__builtin_popcount(UP)]);
for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)v[i][j].clear();
}
return 0;
}CXXXVI.[[IOI2000] 邮局 加强版]()
Observation 1. 若一段村庄中设一个邮局，则邮局一定设在其中位数（若是偶数则任一中位数）的位置。
Observation 2. 若令
Observation 3. 显然全段中修几个邮局的函数有凹性，可以wqs二分。
考虑check二分的
当转移分层时，因为四边形不等式得出的决策单调性，可以分治解决；不分层时，一种解法是使用CDQ分治，正如CXXX.[GYM102904B]Dispatch Money。但是那题囿于逆序对没有
考虑我们当前已经求出了
显然，此时
明显，
这样，内层DP的复杂度就是
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[500100],F[500100],G[500100],pos[500100],trs[500100],l,r;
ll s[500100],f[500100],g[500100];
ll calc(int l,int r){return s[l-1]+s[r]-s[(l+r)/2]-s[(l+r-1)/2];}
void read(int &x){
x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
int che(ll ip){
// printf("%lld\n",ip);
l=r=1,trs[l]=0;
for(int i=1;i<=n;i++){
if(l<r&&pos[l]==i)l++;
f[i]=f[trs[l]]+calc(trs[l]+1,i)+ip,F[i]=F[trs[l]]+1;
if(i==n)break;
pos[l-1]=i+1,pos[r]=n+1;
while(true){
if(r<l){trs[++r]=i;break;}
if(f[i]+calc(i+1,pos[r-1])<=f[trs[r]]+calc(trs[r]+1,pos[r-1])){r--;continue;}
int L=pos[r-1],R=pos[r];
while(L+1<R){
int mid=(L+R)>>1;
if(f[i]+calc(i+1,mid)<=f[trs[r]]+calc(trs[r]+1,mid))R=mid;
else L=mid;
}
if(R<=n)r++,pos[r-1]=R,trs[r]=i;
break;
}
}
// for(int i=1;i<=n;i++)printf("%lld ",f[i]);puts("");
// for(int i=1;i<=n;i++)printf("%d ",F[i]);puts("");
l=r=1,trs[l]=0;
for(int i=1;i<=n;i++){
if(l<r&&pos[l]==i)l++;
g[i]=g[trs[l]]+calc(trs[l]+1,i)+ip,G[i]=G[trs[l]]+1;
if(i==n)break;
pos[l-1]=i+1,pos[r]=n+1;
while(true){
if(r<l){trs[++r]=i;break;}
if(g[i]+calc(i+1,pos[r-1])<g[trs[r]]+calc(trs[r]+1,pos[r-1])){r--;continue;}
int L=pos[r-1],R=pos[r];
while(L+1<R){
int mid=(L+R)>>1;
if(g[i]+calc(i+1,mid)<g[trs[r]]+calc(trs[r]+1,mid))R=mid;
else L=mid;
}
if(R<=n)r++,pos[r-1]=R,trs[r]=i;
break;
}
}
int R=F[n],L=G[n];
// printf("%d %d\n",L,R);
if(L>m)return 1;
if(R<m)return -1;
printf("%lld\n",f[n]-ip*m);
return 0;
}
int main(){
read(n),read(m);
for(int i=1;i<=n;i++)read(a[i]);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
ll l=0,r=1e12,mid;
while(true){
int tp=che(mid=(l+r)>>1);
if(tp==-1)r=mid-1;
if(tp==1)l=mid+1;
if(!tp)break;
}
return 0;
}CXXXVII.[国家集训队]Tree I
两年前刚学MST时做这题WA了，然后两年后才把它补上……
明显直接wqs二分就行了。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,q,dsu[50100],ip;
int read(){
int x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
struct dat{
int u,v,w,c;
void READ(){u=read()+1,v=read()+1,w=read(),c=!read();}
int calc()const{return c?ip+w:w;}
friend bool operator<(const dat&u,const dat&v){return u.calc()==v.calc()?u.c<v.c:u.calc()<v.calc();}
}p[100100];
vector<dat>v[2];
int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);}
bool merge(int x,int y){x=find(x),y=find(y);if(x==y)return false;dsu[x]=y;return true;}
int che(){
// printf("%lld:\n",ip);
for(int i=0,j=0;i<v[0].size()||j<v[1].size();)if(i!=v[0].size()&&(j==v[1].size()||v[0][i]<v[1][j]))p[i+j+1]=v[0][i],i++;else p[i+j+1]=v[1][j],j++;
int f=0,F=0;
for(int i=1;i<=n;i++)dsu[i]=i;
for(int i=1,j=1;i<=m;i=j){
while(j<=m&&p[i].calc()==p[j].calc())j++;
for(int k=i;k<j;k++)if(merge(p[k].u,p[k].v))f+=p[k].calc(),F+=p[k].c;
}
int g=0,G=0;
for(int i=1;i<=n;i++)dsu[i]=i;
for(int i=1,j=1;i<=m;i=j){
while(j<=m&&p[i].calc()==p[j].calc())j++;
for(int k=j-1;k>=i;k--)if(merge(p[k].u,p[k].v))g+=p[k].calc(),G+=p[k].c;
}
if(F>q)return 1;
if(G<q)return -1;
printf("%d\n",f-ip*q);
return 0;
}
int main(){
// freopen("P2619_10.in","r",stdin);
n=read(),m=read(),q=read();
for(int i=1;i<=m;i++)p[i].READ(),v[p[i].c].push_back(p[i]);
for(int i=0;i<2;i++)sort(v[i].begin(),v[i].end());
int l=-100,r=100;
while(true){
ip=(l+r)>>1;
int tp=che();
if(tp==-1)r=ip-1;
if(tp==1)l=ip+1;
if(!tp)return 0;
}
return 0;
} CXXXVIII.CF739E Gosha is hunting
因为
时间复杂度
需要注意的是，在wqs二分
代码：
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-9;
int n,a,b,F[2010][2010],G[2010][2010];
double p[2010],q[2010],f[2010][2010];
int cmp(double ip){
if(ip>eps)return 1;
if(ip<-eps)return -1;
return 0;
}
void trans(int i,int j,int I,int J,double k,int K){
if(cmp(f[I][J]-k)==-1)f[I][J]=k,F[I][J]=F[i][j]+K,G[I][J]=G[i][j]+K;
else if(cmp(f[I][J]-k)==0)F[I][J]=min(F[I][J],F[i][j]+K),G[I][J]=max(G[I][J],G[i][j]+K);
}
int che(double ip){
for(int i=1;i<=n;i++)for(int j=0;j<=min(i,a);j++)f[i][j]=-n;
for(int i=0;i<n;i++)for(int j=0;j<=min(i,a);j++){
if(j+1<=a){
trans(i,j,i+1,j+1,f[i][j]+p[i+1],0);
trans(i,j,i+1,j+1,f[i][j]+1-(1-p[i+1])*(1-q[i+1])-ip,1);
}
trans(i,j,i+1,j,f[i][j],0);
trans(i,j,i+1,j,f[i][j]+q[i+1]-ip,1);
}
if(F[n][a]>b)return 1;
if(G[n][a]<b)return -1;
printf("%lf\n",f[n][a]+ip*b);
return 0;
}
int main(){
scanf("%d%d%d",&n,&a,&b);
for(int i=1;i<=n;i++)scanf("%lf",&p[i]);
for(int i=1;i<=n;i++)scanf("%lf",&q[i]);
double l=0,r=1,mid;
while(true){
int tp=che(mid=(l+r)/2);
if(tp==1)l=mid;
if(tp==-1)r=mid;
if(!tp)break;
}
return 0;
}CXXXIX.[AGC030F] Permutation and Minimum
看到
为方便，我们将
因为是两个位置取
考虑当前填入一个数。这个数有两种可能：一是与比它小的数匹配——此时最小值已经确定了，是那个更小的数，而更小数已经被填入序列，所以当前数与哪个比它小的数匹配根本不影响。二是与比它大的数匹配——此时最小值不确定，因此与不同的比它大的数在不同位置匹配会有不同结果。
于是我们便依次设出了剩余两维的意义：前
我们考虑分情况从
情形1. 若数
情形1.1. 若数
则此时显然其已被唯一确定，直接划归
情形1.2. 若数
有两种情形：其与比它小的东西匹配，或者与比它大的东西匹配。
情形1.2.1. 与比它小的东西匹配。
则依照定义，其应与
情形1.2.2. 与比它大的东西匹配。
则依照定义，其应划归
情形2. 若数
情形2.1. 作为
则此时与
情形2.2. 作为
则直接划归即可，因为方案数已在1.2.1中被计算。故
情形2.3. 作为
依照定义，
显然，总序列中，若我们设
显然转移
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,a[610],p[610],f[2][610][610],sig[610],mat[610],sur[610];
int main(){
scanf("%d",&n),n<<=1;
for(int i=1;i<=n;i++)mat[i]=((i-1)^1)+1;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),p[a[i]]=i;
for(int i=1;i<=n;i++)if(a[i]!=-1&&a[mat[i]]==-1)sig[a[i]-1]++;
for(int i=n;i>=0;i--)sig[i]+=sig[i+1];
for(int i=1;i<=n;i++)if(a[i]!=-1&&a[mat[i]]!=-1)sur[a[i]-1]++;
for(int i=n;i>=0;i--)sur[i]+=sur[i+1];
// for(int i=1;i<=n;i++)printf("%d ",sur[i]);puts("");
// for(int i=1;i<=n;i++)printf("%d ",mat[i]);puts("");
// for(int i=1;i<=n;i++)printf("%d ",p[i]);puts("");
f[0][0][0]=1;
for(int i=0;i<n;i++){
memset(f[!(i&1)],0,sizeof(f[!(i&1)]));
for(int j=0;j<=i;j++)for(int k=0;j+k<=i;k++){
if(n-(j+sur[i])-k*2-sig[i]*2<0)continue;
if(!f[i&1][j][k])continue;
// if(j+k!=i)continue;
// printf("%d %d %d:%d\n",i,j,k,f[i&1][j][k]);
if(p[i+1]){
if(a[mat[p[i+1]]]!=-1){f[!(i&1)][j+1][k]=f[i&1][j][k];continue;}
(f[!(i&1)][j][k+1]+=f[i&1][j][k])%=mod;//we left i+1 unmatched, which should be considered as k.
// printf("I-J-K:%d\n",i-j-k);
(f[!(i&1)][j+2][k]+=1ll*(i-j-k)*f[i&1][j][k]%mod)%=mod;//we match something unsure position
}else{
if(k)(f[!(i&1)][j+2][k-1]+=f[i&1][j][k])%=mod;//we match something of sure position
(f[!(i&1)][j][k]+=f[i&1][j][k])%=mod;//match it with an element in [i+2,n]
(f[!(i&1)][j][k+1]+=1ll*(n-(j+sur[i])-k*2-sig[i]*2)/2*f[i&1][j][k]%mod)%=mod;//put it in any empty space.
}
}
}
printf("%d\n",f[n&1][n][0]);
return 0;
}CXL.忘情
wqs二分水题，明显那个式子可以被化成
需要注意的是，因为二分上界是 __int128。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 ii;
int n,m,s[100100],F[100100],q[100100],l,r;
ii f[100100];
inline void print(ii x){
if(x<=9)putchar('0'+x);
else print(x/10),putchar('0'+x%10);
}
ll sqr(int x){return 1ll*x*x;}
int che(ll ip){
// printf("%lld\n",ip);
l=r=0;
for(int i=1;i<=n;i++){
while(l<r&&f[q[l]]-f[q[l+1]]+sqr(s[q[l]])-sqr(s[q[l+1]])-2*(s[q[l]]-s[q[l+1]])>2ll*s[i]*(s[q[l]]-s[q[l+1]]))l++;
// printf("%d:%d\n",i,q[l]);
f[i]=f[q[l]]+sqr(s[i]-s[q[l]]+1)+ip,F[i]=F[q[l]]+1;
while(l<r&&(f[q[r-1]]-f[q[r]]+sqr(s[q[r-1]])-sqr(s[q[r]]))*(s[q[r]]-s[i])>(f[q[r]]-f[i]+sqr(s[q[r]])-sqr(s[i]))*(s[q[r-1]]-s[q[r]]))r--;
q[++r]=i;
}
// for(int i=1;i<=n;i++)printf("%lld ",f[i]);puts("");
// for(int i=1;i<=n;i++)printf("%d ",F[i]);puts("");
int L=F[n];
l=r=0;
for(int i=1;i<=n;i++){
while(l<r&&f[q[l]]-f[q[l+1]]+sqr(s[q[l]])-sqr(s[q[l+1]])-2*(s[q[l]]-s[q[l+1]])>=2ll*s[i]*(s[q[l]]-s[q[l+1]]))l++;
f[i]=f[q[l]]+sqr(s[i]-s[q[l]]+1)+ip,F[i]=F[q[l]]+1;
while(l<r&&(f[q[r-1]]-f[q[r]]+sqr(s[q[r-1]])-sqr(s[q[r]]))*(s[q[r]]-s[i])>=(f[q[r]]-f[i]+sqr(s[q[r]])-sqr(s[i]))*(s[q[r-1]]-s[q[r]]))r--;
q[++r]=i;
}
int R=F[n];
// printf("[%d,%d]\n",L,R);
if(L>m)return 1;
if(R<m)return -1;
print(f[n]-(ii)ip*m);
return 0;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&s[i]),s[i]+=s[i-1];
ll L=0,R=1e18,mid;
while(true){
int tp=che(mid=(L+R)>>1);
if(tp==-1)R=mid-1;
if(tp==1)L=mid+1;
if(!tp)break;
}
return 0;
}CXLI.[八省联考2018]林克卡特树
一眼发现函数是凸的。然后思考发现直接一个树形DP就能进行二分的check：设
为什么二分边界要开到
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,g[300100][3],head[300100],cnt;
ll f[300100][3],ip;//0:x is on nothing 1:x is currently on a path 2:x's path has been matched
struct node{int to,next,val;}edge[600100];
void ae(int u,int v,int w){
edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++;
}
void trans(ll &F,int &G,ll ff,int gg){
if(F<ff)F=ff,G=gg;
else if(F==ff)G=min(G,gg);
}
void dfs(int x,int fa){
f[x][0]=f[x][1]=f[x][2]=0,g[x][0]=g[x][1]=g[x][2]=0;
for(int i=head[x],y,z;i!=-1;i=edge[i].next){
y=edge[i].to,z=edge[i].val;
if(y==fa)continue;
dfs(y,x);
f[x][2]+=f[y][2],g[x][2]+=g[y][2];
// printf("%d,%d:%d,%d,%d,%d\n",x,y,f[x][1],f[y][1],z,-ip);
trans(f[x][2],g[x][2],f[x][1]+f[y][1]+z-ip,g[x][1]+g[y][1]+1);
f[x][1]+=f[y][2],g[x][1]+=g[y][2];
trans(f[x][1],g[x][1],f[x][0]+f[y][1]+z,g[x][0]+g[y][1]);
f[x][0]+=f[y][2],g[x][0]+=g[y][2];
}
trans(f[x][2],g[x][2],f[x][1]-ip,g[x][1]+1);
trans(f[x][2],g[x][2],f[x][0],g[x][0]);
// printf("%d:\n%d %d %d\n%d %d %d\n",x,f[x][0],f[x][1],f[x][2],g[x][0],g[x][1],g[x][2]);
}
int main(){
scanf("%d%d",&n,&m),m++,memset(head,-1,sizeof(head));
for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),ae(x,y,z);
ll l=-1e12,r=1e12;
while(l<r){
ip=(l+r)>>1;
// printf("%d------------\n",ip);
dfs(1,0);
if(g[1][2]<=m)r=ip;
else l=ip+1;
}
ip=l,dfs(1,0);
printf("%lld\n",f[1][2]+1ll*l*m);
return 0;
}CXLII.CF1158F Density of subarrays
题解
CXLIII.[AGC013E] Placing Squares
关键是将问题从抽象的“正方形面积”转为具象的形式：一段长度为
于是我们可以设计DP：设
常规的位置可以直接矩阵快速幂解决；然而对于题目中给出的特殊位置，需要用特殊的矩阵处理。
因此复杂度
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100100];
const int mod=1e9+7;
struct Matrix{
int g[3][3];
int*operator[](int x){return g[x];}
Matrix(){memset(g,0,sizeof(g));}
friend Matrix operator*(Matrix x,Matrix y){
Matrix z;
for(int i=0;i<3;i++)for(int j=0;j<3;j++)for(int k=0;k<3;k++)(z[i][j]+=1ll*x[i][k]*y[k][j]%mod)%=mod;
return z;
}
}A,B,R;
Matrix ksm(Matrix x,int y){
Matrix z;
z[0][0]=z[1][1]=z[2][2]=1;
for(;y;y>>=1,x=x*x)if(y&1)z=z*x;
return z;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d",&a[i]);a[m+1]=n;
A[0][1]=2,A[0][2]=1,A[1][2]=1;
A[2][0]=1,A[2][1]=2,A[2][2]=2;
A[0][0]=A[1][1]=1;
B[0][1]=2,B[0][2]=1,B[1][2]=1;
B[0][0]=B[1][1]=B[2][2]=1;
R=ksm(A,a[1]);
for(int i=1;i<=m;i++)R=R*B,R=R*ksm(A,a[i+1]-a[i]-1);
printf("%d\n",R[0][2]);
return 0;
} CXLIV.[IOI2018] meetings 会议
被人坑了说这题是CDQ分治的题，一小时想不出来开了题解发现是道DP
大概不会有人像我一样一开始想了极其诡异的DP，然后发现可以用莫队+树剖优化到
扯远了，下面是正解。
一个主流的想法是设
考虑找到区间中的
（当然，对于
发现这两边形式一致，就可以只考虑一半东西，然后另一半直接将序列翻转再做一遍即可得到。但需要注意的是，两边转移的
我们不妨只考虑
因为转移多次涉及到区间
然后发现，所有的
于是我们考虑求出从所有
因为我们明显不能显式地求出所有
然后我们发现，用线段树维护简直是一个天才般的想法，因为我们发现，
这就意味着
于是我们现在考虑求出如何求出
我们蓦然发现，实际上已经有了一半的值，因为
于是现在考虑应该如何在
祭出最上头的DP式，我们发现其有两种方式：一是左儿子中所有东西到右儿子去，右儿子中所有东西的DP值都要增加
但是我们悲哀地发现，要执行的是区间与等差数列取
但是，转机来了：因为
因此，采取等差数列的部分一定是从
时间复杂度
需要多说一句的是，这里的笛卡尔树没必要显式地搞出来，只需要求出每个节点所对应的区间就行了，直接用ST表即可。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[750010],st[750010][20],LG[750010],ql[750010],qr[750010];
bool sec;//if we are executing the second round
ll res[750010];
int MAX(int x,int y){if(!sec)return a[x]>a[y]?x:y;else return a[x]>=a[y]?x:y;}
int RMQ(int x,int y){int k=LG[y-x+1];return MAX(st[x][k],st[y-(1<<k)+1][k]);}
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
#define X x,l,r
#define LSON lson,l,mid
#define RSON rson,mid+1,r
struct SegTree{ll tagl,tagadd,lval,rval;int tagdelta;}seg[3001000];
void SETSEQ(int x,int l,int r,ll lval,int delta){seg[x].tagl=seg[x].lval=lval,seg[x].rval=lval+1ll*(r-l)*delta,seg[x].tagdelta=delta,seg[x].tagadd=0;}
void ADD(int x,ll val){if(seg[x].tagl!=-1)seg[x].tagl+=val;else seg[x].tagadd+=val;seg[x].lval+=val,seg[x].rval+=val;}
void pushup(int x){seg[x].lval=seg[lson].lval,seg[x].rval=seg[rson].rval;}
void pushdown(int x,int l,int r){
if(seg[x].tagl!=-1){
SETSEQ(LSON,seg[x].tagl,seg[x].tagdelta);
SETSEQ(RSON,seg[x].tagl+1ll*seg[x].tagdelta*(mid-l+1),seg[x].tagdelta);
seg[x].tagl=seg[x].tagdelta=-1;
}else ADD(lson,seg[x].tagadd),ADD(rson,seg[x].tagadd),seg[x].tagadd=0;
}
void modifysequence(int x,int l,int r,int L,int R,ll leftval,int delta){
if(l>R||r<L)return;
if(L<=l&&r<=R){SETSEQ(X,leftval+1ll*(l-L)*delta,delta);return;}
pushdown(X),modifysequence(LSON,L,R,leftval,delta),modifysequence(RSON,L,R,leftval,delta),pushup(x);
}
void modifyadd(int x,int l,int r,int L,int R,ll val){
if(l>R||r<L)return;
if(L<=l&&r<=R){ADD(x,val);return;}
pushdown(X),modifyadd(LSON,L,R,val),modifyadd(RSON,L,R,val),pushup(x);
}
ll query(int x,int l,int r,int P){
if(l==r)return seg[x].lval;
pushdown(X);
if(P<=mid)return query(LSON,P);else return query(RSON,P);
}
int innerbinaryonseg(int x,int l,int r,ll lval,int delta){
if(l==r)return l;
pushdown(X);
if(seg[rson].lval<=lval+1ll*(mid+1-l)*delta)return innerbinaryonseg(LSON,lval,delta);
else return innerbinaryonseg(RSON,lval+1ll*(mid+1-l)*delta,delta);
}
int outerbinaryonseg(int x,int l,int r,int L,int R,ll lval,int delta){
if(l>R||r<L)return -1;
if(L<=l&&r<=R){
// printf("(%d,%d):%lld %lld\n",l,r,seg[x].lval,lval+1ll*(l-L)*delta);
// printf("(%d,%d):%lld %lld\n",l,r,seg[x].rval,lval+1ll*(r-L)*delta);
if(seg[x].rval>lval+1ll*(r-L)*delta)return -1;
if(seg[x].lval<=lval+1ll*(l-L)*delta)return l-1;
return innerbinaryonseg(X,lval+1ll*(l-L)*delta,delta);
}
pushdown(X);
int tmp=outerbinaryonseg(LSON,L,R,lval,delta);if(tmp!=-1)return tmp;
return outerbinaryonseg(RSON,L,R,lval,delta);
}
vector<int>v[750010];
void iterate(int x,int l,int r){
if(l==r){printf("%lld ",seg[x].lval);return;}
pushdown(X),iterate(LSON),iterate(RSON);
}
void solve(int l,int r){
if(l==r){modifysequence(1,1,n,l,r,a[l],0);return;}
int o=RMQ(l,r);
if(l!=o)solve(l,o-1);
if(r!=o)solve(o+1,r);
// printf("[%d,%d]:%d\n",l,r,o);
for(auto i:v[o])res[i]=min(res[i],query(1,1,n,qr[i])+1ll*(o-ql[i]+1)*a[o])/*,printf("QQ:%d\n",query(1,1,n,qr[i])+1ll*(o-ql[i]+1)*a[o])*/;
ll FO;modifysequence(1,1,n,o,o,FO=(l==o?a[o]:query(1,1,n,o-1)+a[o]),0);
if(r!=o)modifyadd(1,1,n,o+1,r,1ll*(o-l+1)*a[o]);
// iterate(1,1,n),puts("");
if(r!=o){
int P=outerbinaryonseg(1,1,n,o+1,r,FO+a[o],a[o]);if(P==-1)P=r;//printf("%d\n",P);
if(P>=o+1)modifysequence(1,1,n,o+1,P,FO+a[o],a[o]);
}
// iterate(1,1,n),puts("");
}
void calc(){
for(int i=1;i<=n;i++)st[i][0]=i,v[i].clear();
for(int j=1;j<=LG[n];j++)for(int i=1;i+(1<<j)-1<=n;i++)st[i][j]=MAX(st[i][j-1],st[i+(1<<(j-1))][j-1]);
for(int i=1;i<=m;i++){int o=RMQ(ql[i],qr[i]);if(o!=qr[i])v[o].push_back(i);}
// for(int i=1;i<=n;i++)printf("%d ",a[i]);puts("");
solve(1,n);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=2;i<=n;i++)LG[i]=LG[i>>1]+1;
for(int i=1,l,r;i<=m;i++){
scanf("%d%d",&ql[i],&qr[i]),ql[i]++,qr[i]++;
if(ql[i]!=qr[i])res[i]=0x3f3f3f3f3f3f3f3f;else res[i]=a[ql[i]];
}
calc();
sec=true,reverse(a+1,a+n+1);for(int i=1;i<=m;i++)ql[i]=n-ql[i]+1,qr[i]=n-qr[i]+1,swap(ql[i],qr[i]);calc();
for(int i=1;i<=m;i++)printf("%lld\n",res[i]);
return 0;
}CXLV.[九省联考2018]秘密袭击coat
首先先讲一种暴力但能过的方法。
很容易就会往每个值各被计算几次的方向去想。于是我们枚举每个节点，计算有多少种可能下该节点是目标节点。
为了避免相同的值的影响，我们在值相同的点间也决出一种顺序，即，若两个值相同的点在作比较，依照上文定下的那种顺序决定。
于是我们考虑从该枚举的点
看上去复杂度是
-
第二维最大只枚举到
m （这里的m 即题面中的k ，因为k 这个字母我们接下来还要用） -
第二维最大只枚举到子树大小
sz 。
然后就过了，跑的还比正解都要快。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=64123;
int n,m,W,d[2010],f[2010][2010],p[2010],q[2010],res,sz[2010];
vector<int>v[2010];
void dfs(int x,int fa,int lim){
for(int i=0;i<=sz[x];i++)f[x][i]=0;
f[x][sz[x]=(q[x]>=lim)]=1;
for(auto y:v[x]){
if(y==fa)continue;
dfs(y,x,lim);
// printf("%d:",x);for(int i=0;i<=m;i++)printf("%d ",f[x][i]);puts("");
// printf("%d:",y);for(int i=0;i<=m;i++)printf("%d ",f[y][i]);puts("");
for(int i=sz[x];i>=0;i--)for(int j=min(m-i,sz[y]);j>=0;j--)(f[x][i+j]+=1ll*f[x][i]*f[y][j]%mod)%=mod;
sz[x]=min(sz[x]+sz[y],m);
// printf("%d:",x);for(int i=0;i<=m;i++)printf("%d ",f[x][i]);puts("\n");
}
}
int main(){
scanf("%d%d%d",&n,&m,&W);
for(int i=1;i<=n;i++)scanf("%d",&d[i]),p[i]=i;
sort(p+1,p+n+1,[](int u,int v){return d[u]<d[v];});
for(int i=1;i<=n;i++)q[p[i]]=i;
for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
for(int i=1;i<=n;i++){
// printf("%d\n",q[i]);
if(q[i]>n-m+1)continue;
dfs(i,0,q[i]);
(res+=1ll*d[i]*f[i][m]%mod)%=mod;
}
printf("%d\n",res);
return 0;
}然后是正解。
我们要求
考虑枚举该
考虑让每个
考虑令
考虑对于每个连通块，在树上最高处计算它的贡献。设
考虑如何求答案。因为我们是在最高处计算贡献，所以就要求
因为我们是卷积，所以考虑FFT转移。又因为它一直在卷，所以我们干脆考虑压根不把它复原成系数式，就纯粹用点集表示。
更准确地说，因为
则，在合并父亲
但是就算有了这么伟大的思路，我们算算复杂度，还是
我们发现，最终要对所有
我们思考当合并
在全体结束后，再有
同时，为了便于合并，我们采用线段树合并来维护DP数组。（这种操作被称作整体DP）
我们考虑初始化，发现假如我们最外层枚举的点值是
明显这个初始状态大体是区间的，非常适合线段树合并。
但是，就算这样，暴力合并的复杂度仍然
于是，一个天才般的想法诞生了：
观察到每次的变换都是
而这个变换，可以用四元组
同时，展开式子，就会发现这个变换具有结合律（虽然很遗憾的是，大部分情形下它不具有交换律）。
假如我们初始令
于是，我们把它看作区间的 tag，然后线段树合并就非常简单了。
同时，要注意的是，其单位元是
我们来总结一下操作：当合并的时候，我们希望 tag 解决，当然这里不需要额外增加其它的 tag，我们发现 tag 即可（需要注意的是，
最后合并
需要注意的是，这里并不能标记永久化，主要是因为从四元组中抽出 tag 上去，在线段树合并的时候要先一路下传到某一方已经没有叶子了再合并。
同时，使用 unsigned int 可以刚好把 64123 卡进一次乘法内不爆。
代码（一些比较疑惑的地方已经加了注释）：
#include<bits/stdc++.h>
using namespace std;
#define int unsigned int
const int mod=64123;
int n,m,W,d[2010],X,cnt,bin[5010000],tp,rt[2010],a[2010];
struct dat{//(f,g)->(af+b,cf+d+g)
int a,b,c,d;
dat(){a=1,b=c=d=0;}
dat(int A,int B,int C,int D){a=A,b=B,c=C,d=D;}
friend dat operator*(const dat&u,const dat&v){return dat((u.a*v.a)%mod,(u.b*v.a+v.b)%mod,(u.a*v.c+u.c)%mod,(u.b*v.c+u.d+v.d)%mod);}
void operator*=(const dat&v){(*this)=(*this)*v;}
void print()const{printf("(%u %u %u %u)\n",a,b,c,d);}
};
#define mid ((l+r)>>1)
int newnode(){return tp?bin[tp--]:++cnt;}
struct SegTree{
int lson,rson;
dat tag;
}seg[5010000];
void erase(int &x){if(x)seg[x].tag=dat(),erase(seg[x].lson),erase(seg[x].rson),bin[++tp]=x,x=0;}//erase all the subtree of x.
void pushdown(int x){
if(!seg[x].lson)seg[x].lson=newnode();
if(!seg[x].rson)seg[x].rson=newnode();
seg[seg[x].lson].tag*=seg[x].tag,seg[seg[x].rson].tag*=seg[x].tag,seg[x].tag=dat();
}
void modify(int &x,int l,int r,int L,int R,dat val){
if(l>R||r<L)return;
if(!x)x=newnode();
if(L<=l&&r<=R){seg[x].tag*=val;return;}
pushdown(x),modify(seg[x].lson,l,mid,L,R,val),modify(seg[x].rson,mid+1,r,L,R,val);
}
void merge(int &x,int &y){
if(!seg[x].lson&&!seg[x].rson)swap(x,y);
if(!seg[y].lson&&!seg[y].rson){seg[x].tag*=dat(seg[y].tag.b,0,0,seg[y].tag.d);return;}
pushdown(x),pushdown(y),merge(seg[x].lson,seg[y].lson),merge(seg[x].rson,seg[y].rson);
}
int query(int x,int l,int r){
if(l==r)return seg[x].tag.d;
pushdown(x);
return (query(seg[x].lson,l,mid)+query(seg[x].rson,mid+1,r))%mod;
}
void iterate(int x,int l,int r){
if(!x)return;
printf("%u:[%u,%u]\n",x,l,r);seg[x].tag.print();
iterate(seg[x].lson,l,mid),iterate(seg[x].rson,mid+1,r);
}
vector<int>v[2010];
void dfs(int x,int fa){
modify(rt[x],1,W,1,W,dat(0,1,0,0));//set all into (0,1,0,0),which means only f=1.
for(auto y:v[x])if(y!=fa)dfs(y,x),merge(rt[x],rt[y]),erase(rt[y]);
modify(rt[x],1,W,1,d[x],dat(X,0,0,0));//those <=d[x] are multiplied by an X
modify(rt[x],1,W,1,W,dat(1,1,1,0));
//product of (1,0,1,0) and (1,1,0,0), first means add f to g(to calculate the real g), second means add 1 to f (stands for x itself not chosen at x's father)
}
int all[2010],tmp[2010],res;
int ksm(int x,int y=mod-2){int z=1;for(;y;y>>=1,x=x*x%mod)if(y&1)z=z*x%mod;return z;}
void Lagrange(){
all[0]=1;
for(int i=1;i<=n+1;i++)for(int j=i-1;j<=i;j--)(all[j+1]+=all[j])%=mod,(all[j]*=mod-i)%=mod;//note that j is unsigned!!!
// for(int i=0;i<=n+1;i++)printf("%u ",all[i]);puts("");
for(int i=1;i<=n+1;i++){
int inv=ksm(mod-i),sum=0;
for(int j=0;j<=n;j++)tmp[j]=all[j];
for(int j=0;j<=n;j++)(tmp[j]*=inv)%=mod,(tmp[j+1]+=mod-tmp[j])%=mod;
// if(i>=1410){for(int j=0;j<=n;j++)printf("%u ",tmp[j]);puts("");}
for(int j=m;j<=n;j++)sum+=tmp[j];sum%=mod;
for(int j=1;j<=n+1;j++)if(j!=i)(sum*=ksm((i-j+mod)%mod))%=mod;
res+=sum*a[i]%mod;
}
res%=mod;
}
signed main(){
scanf("%u%u%u",&n,&m,&W);
for(int i=1;i<=n;i++)scanf("%u",&d[i]);
for(int i=1,x,y;i<n;i++)scanf("%u%u",&x,&y),v[x].push_back(y),v[y].push_back(x);
for(X=1;X<=n+1;X++)dfs(1,0),a[X]=query(rt[1],1,W),erase(rt[1]);
// for(int i=1;i<=n+1;i++)printf("%u ",a[i]);puts("");
Lagrange();printf("%u\n",res);
return 0;
}CXLVI.[十二省联考 2019]皮配
题解里”豌豆“的比喻实在太精妙了。
先重新描述一遍题意：有
首先，”重量和有上界“，想到背包问题。于是我们设计一种DP，
然后，我们发现，大部分时候，
于是我们设
因为
最后就拼接
需要注意存在空豆荚。
代码：
/*
Mendel's peas are Awesome!
*/
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int T,n,m,q,yel,gre,rou,smo,id[1010],wei[1010],fob[1010],WEI[1010],f[2510],g[2510],h[2510][310],hh[2510][310],all,res;//yellow,green,rough,smooth
vector<int>v[1010];
bool FOB[1010];
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m),memset(fob,-1,sizeof(fob));
scanf("%d%d%d%d",&yel,&gre,&rou,&smo);
for(int i=1;i<=n;i++)scanf("%d%d",&id[i],&wei[i]),WEI[id[i]]+=wei[i],v[id[i]].push_back(i),all+=wei[i];
scanf("%d",&q);
for(int i=1,x,y;i<=q;i++){
scanf("%d%d",&x,&y);
fob[x]=y,FOB[id[x]]=true;
}
f[0]=1;
for(int i=1;i<=m;i++){
if(FOB[i]||v[i].empty())continue;
for(int j=yel-WEI[i];j>=0;j--)(f[j+WEI[i]]+=f[j])%=mod;
}
g[0]=1;
for(int i=1;i<=n;i++){
if(fob[i]!=-1)continue;
for(int j=rou-wei[i];j>=0;j--)(g[j+wei[i]]+=g[j])%=mod;
}
for(int i=1;i<=yel;i++)(f[i]+=f[i-1])%=mod;
for(int i=1;i<=rou;i++)(g[i]+=g[i-1])%=mod;
h[0][0]=1;
for(int i=1;i<=m;i++){
if(!FOB[i]||v[i].empty())continue;
memcpy(hh,h,sizeof(h));
for(auto x:v[i]){
if(fob[x]==-1)continue;
if(fob[x]>1)for(int j=0;j<=yel;j++)for(int k=min(rou,300);k>=wei[x];k--)(hh[j][k]+=hh[j][k-wei[x]])%=mod;
else if(fob[x]==1)for(int j=0;j<=yel;j++)for(int k=min(rou,300);k>=0;k--)hh[j][k]=(k>=wei[x]?hh[j][k-wei[x]]:0);
if(fob[x]<=1)for(int j=0;j<=yel;j++)for(int k=min(rou,300);k>=wei[x];k--)(h[j][k]+=h[j][k-wei[x]])%=mod;
else if(fob[x]==3)for(int j=0;j<=yel;j++)for(int k=min(rou,300);k>=0;k--)h[j][k]=(k>=wei[x]?h[j][k-wei[x]]:0);
}
for(int j=0;j<=yel;j++)for(int k=min(rou,300);k>=0;k--)if(j>=WEI[i])(h[j][k]+=hh[j-WEI[i]][k])%=mod;
}
gre=all-gre,smo=all-smo;
for(int i=0;i<=yel;i++)for(int j=0;j<=min(rou,300);j++){
int F=f[yel-i];
if(i<gre)(F+=mod-f[gre-i-1])%=mod;
int G=g[rou-j];
if(j<smo)(G+=mod-g[smo-j-1])%=mod;
(res+=1ll*h[i][j]*F%mod*G%mod)%=mod;
}
printf("%d\n",res);
memset(f,0,sizeof(f)),memset(g,0,sizeof(g)),memset(h,0,sizeof(h));
for(int i=1;i<=m;i++)WEI[i]=0,FOB[i]=false,v[i].clear();
all=res=0;
}
return 0;
}CXLVII.[NOI2016] 国王饮水记
首先，我们一定可以舍去那些高度比
我们不妨从三座城市想起。假如可以合并两次，应该怎么合并？
先合并
由此我们得出了第一个Obeservation：越早合并的城市，高度越低。这也就意味着，我们每次合并的城市，必定是高度递增的一段，且前一次合并的所有城市的水量都低于后一次合并的城市。
那如果只能合并一次呢？
首先，
于是我们得到了用一次合并来合并城市
有了这两个观察，我们就可以开始DP了：设
同时，为了处理上面“合并
这种“合并
则式子修改为
这时候，如果再观察到“合并次数 double 暴力DP了。
可以取得
#include<bits/stdc++.h>
using namespace std;
int n,m,p,h[8010];
double f[8010],g[8010],s[8010];
void solve(){
for(int i=1;i<=n;i++)f[i]=-0x3f3f3f3f3f3f3f3f;
for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)f[i]=max(f[i],(g[j]+s[i]-s[j])/(i-j+1));
for(int i=1;i<=n;i++)f[i]=max(f[i],f[i-1]);
}
int main(){
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++)scanf("%d",&h[i]);
sort(h+2,h+n+1),reverse(h+2,h+n+1);
while(h[n]<=h[1])n--;
reverse(h+2,h+n+1);
// for(int i=1;i<=n;i++)printf("%d ",h[i]);puts("");
for(int i=1;i<=n;i++)s[i]=s[i-1]+h[i];
m=min(m,n-1);
for(int i=1;i<=n;i++)f[i]=h[1];
while(m--){
for(int i=1;i<=n;i++)g[i]=f[i];
solve();
}
printf("%lf\n",f[n]);
return 0;
}然后，有一个推论是“合并
这之后，我们掏出转移式
它可以被解释为
因为我们已经将
尽管
具体而言，发现最优决策点
明显单次复杂度就做到了 double 暴力转移，复杂度是
代码：
#include<bits/stdc++.h>
using namespace std;
typedef pair<double,double> pdd;
int n,m,p,h[8010],l,r;
double f[8010],g[8010],s[8010];
pdd dat[8010];
int q[8010];
double slope(pdd x,pdd y){return (x.second-y.second)/(x.first-y.first);}
void solve(){
l=r=0;
for(int i=1;i<=n;i++){
dat[i]=make_pair(i,s[i]-g[i]);
while(r-l>=2&&slope(dat[q[r-2]],dat[q[r-1]])>slope(dat[q[r-1]],dat[i]))--r;
q[r++]=i;
pdd I=make_pair(i+1,s[i]);
while(r-l>=2&&slope(dat[q[l]],I)<slope(dat[q[l+1]],I))l++;
f[i]=(g[q[l]]+s[i]-s[q[l]])/(i-q[l]+1);
}
for(int i=1;i<=n;i++)f[i]=max(f[i],f[i-1]);
}
int main(){
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++)scanf("%d",&h[i]);
sort(h+2,h+n+1),reverse(h+2,h+n+1);
while(h[n]<=h[1])n--;
reverse(h+2,h+n+1);
// for(int i=1;i<=n;i++)printf("%d ",h[i]);puts("");
for(int i=1;i<=n;i++)s[i]=s[i-1]+h[i];
m=min(m,n-1);
for(int i=1;i<=n;i++)f[i]=h[1];
while(m--){
for(int i=1;i<=n;i++)g[i]=f[i];
solve();
}
printf("%lf\n",f[n]);
return 0;
}到这里，优化似乎已经到头了——单次DP已经压到底线
因为水量互不相等，所以肯定是越晚合并的区间长度越短，不然我们一定可以将一个原本在后面合并的元素移到前面并使得答案增加。
依据这个结论，有个性质是若
于是我们只需DP
（证明？打表就行了！）
还有一个由“互不相同”带来的结论是，比较大小关系时精度只需要十几位就行了，这是显然的。于是我们DP时直接用普通 double 存，然后记录转移点，在DP结束后再用高精度小数按图索骥复原出完整的精度即可。
时间复杂度
代码（省略模板部分）：
#include<bits/stdc++.h>
using namespace std;
typedef pair<double,double> pdd;
int n,m,p,h[8010],l,r,las[17][8010];
double f[8010],g[8010],s[8010];
pdd dat[8010];
int q[8010];
double slope(pdd x,pdd y){return (x.second-y.second)/(x.first-y.first);}
void solve(int ID){
l=r=0;
for(int i=1;i<=n;i++){
dat[i]=make_pair(i,s[i]-g[i]);
while(r-l>=2&&slope(dat[q[r-2]],dat[q[r-1]])>slope(dat[q[r-1]],dat[i]))--r;
q[r++]=i;
pdd I=make_pair(i+1,s[i]);
while(r-l>=2&&slope(dat[q[l]],I)<slope(dat[q[l+1]],I))l++;
f[i]=(g[q[l]]+s[i]-s[q[l]])/(i-q[l]+1),las[ID][i]=q[l];
}
for(int i=1;i<=n;i++)if(f[i]<f[i-1])f[i]=f[i-1],las[ID][i]=-1;
}
Decimal calc(int i,int j){
if(!i)return h[1];
if(las[i][j]==-1)return calc(i,j-1);
return (calc(i-1,las[i][j])+s[j]-s[las[i][j]])/(j-las[i][j]+1);
}
int main(){
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++)scanf("%d",&h[i]);
sort(h+2,h+n+1),reverse(h+2,h+n+1);
while(h[n]<=h[1])n--;
reverse(h+2,h+n+1);
// for(int i=1;i<=n;i++)printf("%d ",h[i]);puts("");
for(int i=1;i<=n;i++)s[i]=s[i-1]+h[i];
m=min(m,n-1);
int lim=min(m,14);
for(int i=1;i<=n;i++)f[i]=h[1];
for(int j=1;j<=lim;j++){
for(int i=1;i<=n;i++)g[i]=f[i];
solve(j);
}
Decimal res=calc(lim,n-m+lim);
for(int i=n-m+lim+1;i<=n;i++)res=(res+h[i])/2;
cout<<res.to_string(p<<1)<<endl;
return 0;
}CXLVIII.[NOI2019] 机器人
首先发现每个点向左向右能到达的位置就类似笛卡尔树上一个点的代表区间，不同的是这里有多个最大值时选取最右的一个。于是我们可以想到一个DP，
我们有转移式
满分做法要猜一个结论：假如把所有
证明也很简单。首先，对于
为了方便转移，我们需要维护前缀和（这里就与一开始设的不大于
我们显然可以取
对于段
我们来计算复杂度。首先，我们要顺序DP每一段
然后就是卡常了。注意到拉插时，对于同一个
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int ksm(int x,int y=mod-2){int z=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;return z;}
int n,a[310],b[310],fac[310],inv[310],tmp[310],lim;
void ADD(int &x,int y){x+=y;if(x>mod)x-=mod;}
int g[2210][310],pre[2210][610],vis[3010],tot,id[310][310];
void Lagrange(int D,int L,int R){
if(L+n>=R){for(int i=1;i<=tot;i++)pre[i][D]=g[i][lim];return;}
tmp[0]=1;for(int i=1;i<=lim;i++)tmp[i]=1ll*tmp[i-1]*(R-(L+i-1))%mod;
for(int j=1;j<=tot;j++)pre[j][D]=0;
for(int i=lim,j=1;i;j=1ll*j*(R-(L+--i))%mod){
int pmt=1ll*tmp[i-1]*j%mod*inv[i-1]%mod*inv[lim-i]%mod;
if((lim-i)&1)for(int j=1;j<=tot;j++)ADD(pre[j][D],mod-1ll*pmt*g[j][i]%mod);
else for(int j=1;j<=tot;j++)ADD(pre[j][D],1ll*pmt*g[j][i]%mod);
}
}
vector<int>v;
void name(int l,int r){if(l>r||id[l][r])return;id[l][r]=++tot;if(l!=r)for(int i=(l+r-1)/2;i<=(l+r)/2+1;i++)name(l,i-1),name(i+1,r);}
int dfs(int l,int r,int D){
if(l>r)return 0;
int ID=id[l][r];
if(vis[ID]==D)return ID;vis[ID]=D;
if(l==r){
if(D<a[l]||D>=b[l]){for(int i=0;i<=lim;i++)g[ID][i]=pre[ID][D-1];pre[ID][D]=pre[ID][D-1];}
else{for(int i=0;i<=lim;i++)g[ID][i]=i+pre[ID][D-1];pre[ID][D]=v[D]-v[a[l]-1];}
return ID;
}
for(int i=1;i<=lim;i++)g[ID][i]=0;g[ID][0]=pre[ID][D-1];
for(int i=(l+r-1)/2;i<=(l+r)/2+1;i++){
if(D<a[i]||D>=b[i])continue;
int A=dfs(l,i-1,D),B=dfs(i+1,r,D);
for(int j=1;j<=lim;j++)ADD(g[ID][j],1ll*g[A][j]*g[B][j-1]%mod);
}
for(int j=1;j<=lim;j++)ADD(g[ID][j],g[ID][j-1]);
return ID;
}
int main(){
// freopen("robot.in","r",stdin);
// freopen("robot.out","w",stdout);
scanf("%d",&n);
fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=ksm(fac[n]);for(int i=n-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]),b[i]++,v.push_back(a[i]),v.push_back(b[i]);
sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin());
for(int i=1;i<=n;i++)a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1,b[i]=lower_bound(v.begin(),v.end(),b[i])-v.begin()+1;
// for(auto i:v)printf("%d ",i);puts("");
// for(int i=1;i<=n;i++)printf("[%d,%d)\n",a[i],b[i]);
name(1,n);
for(int i=0;i<=n+1;i++)g[0][i]=1;
for(int i=1;i<v.size();i++){
// printf("%d\n",i);
lim=min(n+1,v[i]-v[i-1]);
for(int l=1;l<=n;l++)for(int r=l;r<=n;r++)if(id[l][r])dfs(l,r,i);
Lagrange(i,v[i-1],v[i]-1);
// for(int l=1;l<=n;l++)for(int r=l;r<=n;r++)if(id[l][r]){printf("[%d,%d]",l,r);for(int j=0;j<lim;j++)printf("%d ",g[id[l][r]][j]);puts("");}
// puts("");
}
printf("%d\n",pre[id[1][n]][v.size()-1]);
return 0;
} CIL.[NOI2020] 制作菜品
本题有三个难点：留意到题面中的 bitset 优化。
首先，在很隐蔽的角落，有一句话
结论1.
m\geq n-1 时一定有解。
要证明这个结论，我们要分成三部分。
结论1.1.
m=n-1 时一定有解。
不妨将
同时，我们也能发现，
结论1.2.
m=n 时一定有解。
不妨仍将
若
结论1.3.
m>n 时一定有解。
递增排序后，
结论2.
m=n-2 时，当且仅当其能被分成两个非空集合\mathbb{U,V} 使得\sum\limits_{u\in\mathbb U}a_u=\Big(|\mathbb U|-1\Big)k 时，有解。
首先，其是充分的，因为对于
其次，其是必要的，因为
这样，我们就可以背包出一组解来了。具体而言，有经典套路是在上式中把 bool 数组，所以可以使用 bitset 优化至
（可能因为 bitset 开太大的缘故，本代码在 Windows 下会 RE，可以使用 CF 的 Custom Test 编译）
代码：
#include<bits/stdc++.h>
using namespace std;
int T,n,m,p,a[510],ord[510];
vector<vector<int> >v;
bool cmp(int u,int v){return a[u]<a[v];}
bitset<5000010>bs[502];
const int half=2500002;
bool sd[510];
void SOLVE(int M,int N,int *dro){
while(M){
sort(dro+1,dro+N+1,cmp);
v.push_back({dro[1],a[dro[1]],dro[N],p-a[dro[1]]});
a[dro[N]]-=p-a[dro[1]];
dro[1]=dro[N--],M--;
}
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&p),v.clear();
for(int i=1;i<=n;i++)scanf("%d",&a[i]),ord[i]=i;
while(m>n){
sort(ord+1,ord+n+1,cmp);
v.push_back({ord[n],p}),a[ord[n]]-=p;
m--;
}
while(n&&m==n){
sort(ord+1,ord+n+1,cmp);
v.push_back({ord[n],p}),a[ord[n]]-=p;
m--;
if(!a[ord[n]])n--;
}
if(m==n-1)SOLVE(m,n,ord);else if(n){
bs[0].reset(),bs[0].set(half);
for(int i=1;i<=n;i++){
// printf("%d\n",i);
if(a[i]==p)bs[i]=bs[i-1];
if(a[i]>p)bs[i]=bs[i-1]|(bs[i-1]<<(a[i]-p));
if(a[i]<p)bs[i]=bs[i-1]|(bs[i-1]>>(p-a[i]));
}
if(!bs[n].test(half-p)){puts("-1");continue;}
for(int i=n,now=half-p;i;i--){
if(bs[i-1].test(now-a[i]+p))sd[i]=true,now=now-a[i]+p;
else sd[i]=false;
}
// for(int i=1;i<=n;i++)printf("%d ",sd[i]);puts("");
sort(ord+1,ord+n+1,[](int x,int y){return sd[x]<sd[y];});
for(int i=1;i<n;i++)if(!sd[ord[i]]&&sd[ord[i+1]])SOLVE(i-1,i,ord),SOLVE(n-i-1,n-i,ord+i);
}
for(auto i:v){for(auto j:i)printf("%d ",j);puts("");}
}
return 0;
} CL.[[NOI2018] 冒泡排序]()
结论1.交换次数压到下界，当且仅当不存在长度大于
2 的下降子序列。
证明很简单。众所周知的是，冒泡排序的交换次数等于序列逆序对数。要压到下界，与每个点有关的逆序对数都只能为
不存在长度大于
要求出所有字典序
首先，我们可以判一下
如果在矩阵上画出来的话，会发现这转移的位置是一条斜线，不好处理；但是我们可以转变DP状态：设新的
下面我们考虑用此DP值来求答案。枚举前缀长度
发现，就算
发现，无论是转移式还是求值式，我们都需要用到DP数组的后缀和。于是我们设
好耶！是大家daisuki的推式子时间！
OK！这样我们就得出了简单的后缀和公式！
现在考虑其实际意义：从
因为这个“不越过
发现只有一种操作在
发现现在是裸的卡特兰数模型。于是就直接得到
因为我们之前强制令
时间复杂度可以做到
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int N=1200000;
int T,n,q[1201000],fac[1201000],inv[1201000],premax,secmax,res,k,sufmin[1201000];
int ksm(int x,int y=mod-2){int z=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;return z;}
int binom(int x,int y){if(x<y||y<0)return 0;return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;}
int S(int x,int y){if(y>x)return 0;return(binom(2*x-y+1,x-y)-binom(2*x-y+1,x-y-1)+mod)%mod;}
int main(){
fac[0]=1;for(int i=1;i<=N;i++)fac[i]=1ll*fac[i-1]*i%mod;
inv[N]=ksm(fac[N]);for(int i=N;i;i--)inv[i-1]=1ll*inv[i]*i%mod;
scanf("%d",&T);
while(T--){
scanf("%d",&n),premax=secmax=res=k=0;
for(int i=1;i<=n;i++)scanf("%d",&q[i]);sufmin[n+1]=0x3f3f3f3f;
for(int i=n;i;i--)sufmin[i]=min(sufmin[i+1],q[i]);
for(int i=1;i<=n;i++){
if(secmax>sufmin[i])break;
if(q[i]>premax)k+=q[i]-premax-1,premax=q[i];else secmax=max(secmax,q[i]),k--;
(res+=S(n-i,k+1))%=mod;
}
printf("%d\n",res);
}
return 0;
}到这里，又是50题结束了。敬请收看DP刷题笔记IV。