0610
Cap1taL
·
·
个人记录
NFLS T2
大好题啊，属于是应该会做的题了。还是脑子没转过来那个思路
转化前的题意很抽象，写个暴力 n! 就能发现真实题意是：
- 给定长度为 n 数组 a_i，要求计数有多少 n 的排列 P，满足对于每个最长连续 +1 段和连续 -1 段 [l,r]，有 r-l+1\ge\min_{i\in[l,r]}a_{P_i}+1
- 说人话就是，把排列画在坐标系里，每个 y 有个限制 a，要求对于每个最长斜率为 1 的线段，它的长度不能超过涵盖的 y 的 a 而已
-
n\le 5000
考试的时候唐到家了啊，一直想不出来 poly(n) 的做法。一直在思考基于最后序列的 DP。其实也不是，就是思路没转变过来吧
会注意到，这个形式非常好看，每个连续段在值域上是一个连续段
这提示我们在值域上 DP，而不去考虑每个位置放什么东西。
做过这么多划分区间的题，容易有个模糊的思路是，枚举到 i，就钦定 i 是最后一段的末尾，尝试枚举左端点 j，看看能不能转移。a_i 的限制在这里可以解决。
如果能想到这一步，应该就能想到，先不考虑、也没法考虑这些段在最终序列的位置关系，应该能发现最后乘个阶乘就能大概解决问题
于是记录段数就必不可少了，多了一维，没关系，n\le 5000
然后就又发现了一些小问题：
- 我们在划分值域，但每一段在最终的序列里，有可能是升序的，也有可能是降序的
- 最后如果直接乘段数的阶乘，有可能某些段会连在一起，这就爆炸了，我们的判断全失效了
直觉会告诉我们第一个问题应该好解决，可能有个 2 之类的系数而已，或者得讨论讨论，先暂时不去深究它
对于第二个问题，会发现从阶乘里直接扣掉非法情况这种思路非常完蛋，这太困难了，得记录 O(想想就要炸) 的信息
于是这个时候应该考虑容斥！！
于是这个时候应该考虑容斥！！
于是这个时候应该考虑容斥！！
唉，容斥。唉，容斥。唉，容斥。唉，容斥。
我们想要的是没有任何两段接起来的情况，即重排后值域段的连接数为 0
于是我们可以钦定某些值域段的衔接处必须连接。考虑暴力做法，再开一个维度记录钦定了多少位置就可以了。然后按套路立马发现这个东西很蠢，我们只关心奇偶性来判断 (-1)^N，可以在 转移的时候直接取负，也可以开个 01 状态啥的，这个无所谓了。
现在要解决第一个问题，会发现我们实际上是在思考一些转移细节。一开始想的是对于转移时枚举的每个段，如果长度大于 1 就有个 2 的系数，代表翻还是不翻。然后能察觉，因为我们钦定了一些位置相接，每一段各自翻似乎变得特别抽象，有可能出现值域上不可能相接的情况。第二维度的状态定义还出了问题，如果钦定了连接，重排阶乘数就变了
然后重新理一下思路，会发现，钦定的连接构成了很多 "大段"，可能包含很多小段。小段是真的分段，大段则是容斥的产物。对 a 的限制是小段内的，但翻转与否是整个大段的问题，因为连接之后一翻都得翻。只有大段长度超过 1 才有 2 的系数。最后的阶乘是对大段数做的。
再之后就简单了。分配一些贡献：让翻转 2 的系数在大段末尾结算，这是合理的；大段的累计在段首或段尾都可以，选择和翻转一起在段尾处理
然后会发现，转移时炸了，我们从前面的某个小段尾转移过来，如果我们希望我们开启一个新的大段，那就需要给上一段结算——翻转系数是必须在段尾结算的，但我们发现我们不知道上一个大段有多长，得再记录一个维度表示所处大段的长度。
再仔细想一下，会发现我们的翻转系数很特殊，几乎都为 2，只有大段长度为 1 时才为 1。于是可以把记录大段长度的维度改为 O(1) 的，毕竟我们只关心它是不是 1。现在状态数就是 O(n^2) 的了。转移容易优化到 O(1)
一个更优雅但似乎不自然的办法是记录当前段是否是大段尾，好做很多。但本质上来说只是让贡献结算提前了而已，应该没什么区别。而且如果翻转系数不那么简单（长度为 1 才是 1）这个办法就炸了，还是得考虑有多少大段长有用。
int n;
int a[MAXN];
int f[5005][5005][2];
int fac[5005];
int gmin(int l,int r){
int ret=INT_MAX;
foru(i,l,r){
chkmin(ret,a[i]);
}
return ret;
}
void solve(bool SPE){
n=RIN;
foru(i,1,n){
a[i]=RIN;
}
fac[0]=1;
foru(i,1,n){
fac[i]=mul(fac[i-1],i);
}
static int s[5005][5005];
f[0][0][1]=1;
s[0][0]=1;
foru(i,1,n){
int mn=a[i];
int l=i;
ford(k,i-1,1){
chkmin(mn,a[k]);
if(i-k+1>=mn+1) break;
l=k;
}
foru(j,0,i){
if(i-2>=0){
if(j>0){
mdd(f[i][j][1],mul(s[i-2][j-1],2));
}
mdd(f[i][j][0],s[i-2][j]);
if(l-2>=0){
if(j>0){
mmv(f[i][j][1],mul(s[l-2][j-1],2));
}
mmv(f[i][j][0],s[l-2][j]);
}
}
// foru(k,l-1,i-2){
// if(j>0){
// mdd(f[i][j][1],mul(rmv(f[k][j-1][1],f[k][j-1][0]),2));
// }
// mdd(f[i][j][0],rmv(f[k][j][1],f[k][j][0]));
// }
if(j>0){
mmv(f[i][j][1],mul(f[i-1][j-1][0],2));
mdd(f[i][j][1],mul(f[i-1][j-1][1],1));
}
mmv(f[i][j][0],f[i-1][j][0]);
mdd(f[i][j][0],f[i-1][j][1]);
s[i][j]=add(s[i-1][j],rmv(f[i][j][1],f[i][j][0]));
}
}
int ans=0;
foru(i,0,n){
mdd(ans,mul(f[n][i][1],fac[i]));
}
cout<<ans;
return ;
}
NFLS T3 (AT_codefestival_2016_final_j)
一轮省集原题。当时没补。
有一个 N 行， N 列的正方形，共 N\ \times\ N 个空格。
可以从上下左右四个方向推入方块，共 4\ \times\ N 个插入口，编号为：
- 上侧从左到右 U1,\ U2,\ ...,\ UN
- 下侧从左到右: D1,\ D2,\ ...,\ DN
- 左侧从上到下: L1,\ L2,\ ...,\ LN
- 右侧从上到下： R1,\ R2,\ ...,\ RN
如图是插入口的编号，方块可以推动其他方块，使其往推入方向移动一格，但不能把方块推出正方形外。
你有 N × N 个方块，全部都要推入正方形内。每个插入口的推入次数有一定的限制， U_i只能推入U_i次， D_i只能推入D_i次，L_i只能推入L_i次，R_i只能推入R_i次。
你需要判断这样推入是否可行，如果可行请输出一种方案
n\le 300
题解
没啥好解的。首先只要写暴力就会意识到，推箱子很唐，改称每次在最近空位上放一个更对。容易发现这样做之后有大好处，每个箱子一经放置一定固定。
于是每个箱子都会来自一个方向，考虑先为每个箱子分配一个方向，用网络流实现，最大流必须是 n^2 不然当场炸了。
现在来构造方案。唯一的限制就是，对于一个箱子，它来的方向的箱子必须都比他早放。把限制关系建边，如果是DAG就结束了。问题在如果不是DAG怎么办。
考虑一个环，发现可以通过公式化调整使得这个环爆炸。具体的，让环上每个点指向的方向变成访问它的方向。
但复杂度呢？会注意到调整一个环一定会使得 \sum_u(u到它对应方向边界的距离) 减小一个环长。而这个东西最大就是 n^3 的，这就对了。
于是只要能每次都快速找环就行了，或者说，找环的代价和环长同级别就行了，直接 dfs 找环。容易验证一个点如果不在环里，那它之后不会再参与到新环里。转出来的点也是有可能成环的，这个需要保留
```
int n;
int U[MAXN];
int D[MAXN];
int L[MAXN];
int R[MAXN];
ISAP<500*500+500*5,500*500*10,int,INT_MAX> g;
int gid(int x,int y){
return n*(x-1)+y;
}
int goid(char dr,int i){
switch (dr)
{
case 'U':
return n*n+i;
case 'D':
return n*n+n+i;
case 'R':
return n*n+n*2+i;
case 'L':
return n*n+n*3+i;
}
exit(1);
}
int to[505][505];
void out(int id){
int x=(id-1)/n+1;
int y=id-(x-1)*n;
// cerr<<' '<<x<<' '<<y<<endl;
cout<<"UDRL"[to[x][y]];
if(to[x][y]==0 || to[x][y]==1){
cout<<y;
}else{
cout<<x;
}
cout<<'\n';
}
vector<int> dp[505*505];
void solve(bool SPE){
n=RIN;
foru(i,1,n){
U[i]=RIN;
}
foru(i,1,n){
D[i]=RIN;
}
foru(i,1,n){
L[i]=RIN;
}
foru(i,1,n){
R[i]=RIN;
}
g.set(n*n+4*n+2,n*n+4*n+1,n*n+4*n+2);
static int id[505][505][4];
foru(i,1,n){
foru(j,1,n){
g.add_edge(g.S(),gid(i,j),1);
id[i][j][0]=g.add_edge(gid(i,j),goid('U',j),1);
id[i][j][1]=g.add_edge(gid(i,j),goid('D',j),1);
id[i][j][2]=g.add_edge(gid(i,j),goid('R',i),1);
id[i][j][3]=g.add_edge(gid(i,j),goid('L',i),1);
}
}
foru(i,1,n){
g.add_edge(goid('U',i),g.T(),U[i]);
g.add_edge(goid('D',i),g.T(),D[i]);
g.add_edge(goid('R',i),g.T(),R[i]);
g.add_edge(goid('L',i),g.T(),L[i]);
}
int num=g.maxflow();
if(num!=n*n){
cout<<"NO";
return ;
}
foru(i,1,n){
foru(j,1,n){
foru(c,0,3){
if(g.qry_w(id[i][j][c])!=1){
to[i][j]=c;
break;
}
}
// cout<<to[i][j];
}
// HH;
}
static bool vis[505][505];
static stack<pair<pair<int,int>,int>> st;
static bool in[505][505];
auto dfs=[](auto& dfs,int u,int v,int come)->void {
in[u][v]=1;
st+=mkp(mkp(u,v),come);
// cein<<"pushed "<<mkp(mkp(u,v),come)<<endl;
auto tryout=[&u,&v,&dfs](int x,int y)->bool {
if(vis[x][y]) return false;
// cerr<<u<<' '<<v<<" tryout "<<x<<' '<<y<<endl;
if(in[x][y]){
// cerr<<u<<' '<<v<<" boom "<<x<<' '<<y<<endl;
// cerr<<"change "<<x<<" "<<y<<" from "<<to[x][y]<<" to "<<to[u][v]<<endl;
to[x][y]=to[u][v];
while(1){
auto [p,q]=st.top().fi;
int dr=st.top().se;
// cerr<<"take out "<<p<<' '<<q<<' '<<dr<<endl;
st.pop();
in[p][q]=0;
if(p==x && q==y){
break;
}else{
// cerr<<"change "<<p<<" "<<q<<" from "<<to[p][q]<<" to "<<dr<<endl;
to[p][q]=dr;
}
}
return true;
}
while(!vis[x][y]){
dfs(dfs,x,y,to[u][v]);
if(in[u][v]==0) return true;
}
return false;
};
switch (to[u][v])
{
case 0:
foru(i,1,u-1){
if(tryout(i,v)) return ;
}
break;
case 1:
foru(i,u+1,n){
if(tryout(i,v)) return ;
}
break;
case 2:
foru(i,v+1,n){
if(tryout(u,i)) return ;
}
break;
case 3:
foru(i,1,v-1){
if(tryout(u,i)) return ;
}
break;
}
assert(in[u][v]==1);
in[u][v]=0;
vis[u][v]=1;
// cerr<<"exit "<<u<<' '<<v<<endl;
// cein<<"exitpop "<<st.top()<<endl;
st.pop();
};
foru(i,1,n){
foru(j,1,n){
if(vis[i][j]) continue;
while(!vis[i][j]){
dfs(dfs,i,j,-1);
}
}
}
// dfs(dfs,3,2,1);
// foru(i,1,n){
// foru(j,1,n){
// cout<<to[i][j];
// }
// HH;
// }
// exit(0);
foru(i,1,n){
foru(j,1,n){
switch (to[i][j])
{
case 0:
foru(k,1,i-1){
dp[gid(k,j)]+=gid(i,j);
}
break;
case 1:
foru(k,i+1,n){
dp[gid(k,j)]+=gid(i,j);
}
break;
case 2:
foru(k,j+1,n){
dp[gid(i,k)]+=gid(i,j);
}
break;
case 3:
foru(k,1,j-1){
dp[gid(i,k)]+=gid(i,j);
}
break;
}
}
}
static queue<int> q;
static int d[505*505];
foru(u,1,n*n){
for(auto v:dp[u]){
d[v]++;
}
}
foru(u,1,n*n){
if(d[u]==0){
q.push(u);
}
}
while(!q.empty()){
int u=q.front();
q.pop();
out(u);
for(auto v:dp[u]){
d[v]--;
if(d[v]==0){
q.push(v);
}
}
}
return ;
}
```
### ISAP
感觉各种算法都应该模板化一点，自己简单备一个 ISAP 的板子
只有我觉得 ISAP 比 Dinic 更符合人类直觉吗
首先从 $t$ 到 $s$ 给图分层，之后只在不同层之间跑流量
那又要说了，这不炸了吗，同层的边不都没了？所以如果一个点出边流量都跑完了，把它往更高层上提一个单位
```
gap[dep[u]]--;
if(gap[dep[u]]==0) dep[s]=n+1; //断层了炸了，不用流了
dep[u]++;
gap[dep[u]]++;
```
这使得它可以继续流同层的流量了，对的不能再对了，这有哪里不对吗
跑的还快还好写，拿来求最大流很对了
```
template<int N,int M,class D,D INF>
class ISAP{
struct edge{
int v;
int nxt;
D w;
}e[M*2+5];
int ecnt=1;
int head[N+5],cur[N+5],dep[N+5],gap[N+5];
int n,s,t;
void add_e(int u,int v,D w){
e[++ecnt]={v,head[u],w};
head[u]=ecnt;
}
void bfs(){
static queue<int> q;
while(!q.empty()) q.pop();
foru(i,1,n) dep[i]=-1,gap[i]=0;
dep[t]=0,gap[0]=1;
q.push(t);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[i];i;i=e[i].nxt){
int v=e[i].v;
if(dep[v]!=-1) continue;
dep[v]=dep[u]+1;
gap[dep[v]]++;
q.push(v);
}
}
}
D dfs(int u,D flow){
if(u==t) return flow;
D used=0;
for(int &i=cur[u];i;i=e[i].nxt){
int v=e[i].v;
if(e[i].w==0 || dep[u]!=dep[v]+1) continue;
D x=dfs(v,min(flow-used,e[i].w));
e[i].w-=x;
e[i^1].w+=x;
used+=x;
if(used==flow) return used;
}
gap[dep[u]]--;
if(gap[dep[u]]==0) dep[s]=n+1;
dep[u]++;
gap[dep[u]]++;
return used;
}
public:
void clear(){
foru(i,1,n) head[i]=dep[i]=gap[i]=0;
n=s=t=0;
ecnt=1;
}
void set(int _n,int _s,int _t){
n=_n,s=_s,t=_t;
}
int add_edge(int u,int v,D w){
add_e(u,v,w);
add_e(v,u,0);
return ecnt-1;
}
int S()const{
return s;
}
int T()const{
return t;
}
D qry_w(int id)const{
return e[id].w;
}
D maxflow(){
bfs();
D flow=0;
while(dep[s]<n){
foru(i,1,n) cur[i]=head[i];
flow+=dfs(s,INF);
}
return flow;
}
};
ISAP<500,100000,LL,1e18> g;
g.set(N,S,T)
int edgeid=g.add_edge(g.S(),x,1);
g.add_edge(x,g.T(),1);
cout<<g.maxflow()<<endl;
cout<<g.qry_w(edgeid)<<endl;
```
这很好了