2019年1月 – Smokey_Days

2019年1月31日

仔细阅读题意，我们发现，这道题本质上就是一个约束类问题：对于每一株植物，都存在一些植物，需要消灭掉它们才能消灭它。
故而，它就变成了一个这样的问题：存在一些植物，其中的一些要消灭了另外一些之后才能消灭，问收益最大化的方法。
如果我们对每一棵植物建点，然后从一棵植物向它的约束植物连边，那么问题就转化为：一张有向图，每个点都有点权，请选中其中的某些点，使得每个点的后继都在这张图中。
这是一类被称为「最大权闭合子图问题」的问题。这种问题的解决方案是，从源点向正权点连权值为点权的边；从负权点向汇点连权值为点权的绝对值的边。原图中的边流量无穷大。
那么，答案就是总权值减去最小割。

下面我们来证明这种建模方式的合法性和最优性。
我们令从源点连出的边被割掉表示不选中这个点，连向汇点的边被割掉表示选中这个点。
那么，最终的结果必然是一个闭合子图。
这是因为，对于这张图的最小割，当你选中一个节点之后，这个点的所有后继负权节点都一定被割掉/选中了（根据割的性质显然）；
这个点的所有后继正权节点都一定不被割/选中了（根据最小割的性质，割掉这些边没有意义）。
并且，任何一个闭合子图的选法都至少可以对应一个割法。
这是因为，对于原图中的某一种连接方法，都可以通过割掉不在其之中的所有负权边和在其之中的所有负权边来使其对应。
同时，根据我们此前的定义，最小割的值意味着没选中的正权点的值与选中的负权点的值的绝对值的和。故而，答案便是正权店的值的和减去最小割的值。
而最小割是要尽量小的，故而最小割可以得到最优答案。

PS:
这一题应当考虑死锁情况，想象一个无限攻击力和攻速的豌豆射手。（不考虑连样例都过不了）（但是尽管这样还是能够拿到80分）
具体处理方法就大力上一个拓扑排序即可。把所有需要缩掉的点打个标记，然后令这些点在网络流中不存在。
然而，如果我们直接写一个拓扑排序的话，还是只能得到80分的好成绩——这是因为这张图需要对反图进行拓扑排序。
细想，因为这张图上每一条有向边的终点一旦被删去，那么它的所有前驱也都是不能存在的。
故而，对反图进行拓扑排序找环并删去才能符合题目的要求。

#include<iostream>
#include<cstdio>
#include<queue>

const int INF=2147483647;
const int VERYBIG=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

int n,m,s,t,nw[1005],dep[1005],val[1005];

struct ee{
	int v;
	int w;
	int nxt;
}e[1000005];
int h[1005],et=-1,in[1005];
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
	++in[U];
}

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		nw[i]=h[i];
		if(dep[i]>-2){		
			dep[i]=INF;
		}
	}
	q.push(s);
	dep[s]=0;
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;;
				q.push(e[i].v); 
			}
		}
	}
//	printf("%d\n",dep[t]);
	return dep[t]<INF;
}

inline int dfs(int X,int V){
	if(!V||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(e[i].w,V));
			if(val){
				V-=val;
				cnt+=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(!V){
					break;
				} 
			}
		}
	}
	return cnt;
}

inline int calc(int X,int Y){
	return X*m+Y+1;
}

inline int dinic(){
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
	}
	return ans;
}
inline int srt(){
	for(int i=1;i<=t;++i){
		if(!in[i]){
			q.push(i);
		}
		dep[i]=-2;
	}
	int RT=0,p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		dep[p]=0;
		if(val[p]>0){
			RT+=val[p];
		}
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(!e[i].w){
				if(!--in[e[i].v]){
					q.push(e[i].v);
				}
			}
		}
	}
	return RT;
}

void init(){
	scanf("%d%d",&n,&m);
	s=n*m+1,t=n*m+2,et=-1;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int x,y,z;
	for(int i=1;i<=n*m;++i){
		scanf("%d",&x);
		val[i]=x;
		x>0?(add(s,i,x),0):(x==0?0:(add(i,t,-x),0));
		scanf("%d",&x);
		for(int j=1;j<=x;++j){
			scanf("%d%d",&y,&z);
			add(calc(y,z),i,VERYBIG);
		}
		if(i%m){
			add(i,i+1,VERYBIG);
		}
	}
	int tot=srt();
	printf("%d\n",tot-dinic());
}

int main(){
	init();
	return 0;
}

2019年1月28日2019年1月28日

lp2774 方格取数问题

这是一道最小割转最大流的例题。
首先，我们发现，这一题要求我们求的是所取和。然后容易知道，所取和等于总和减去舍弃和。
故而，我们要使得所取和最大，就只需要使得舍弃和最小。
尝试用所取和来建图并且跑最大流，发现，它并不是那么容易地建成一个可靠的图。
正难则反，我们考虑怎么样才能让舍弃和最小。
于是尝试用舍弃和最小来建图并且跑最小割。观察题目的性质我们发现，所有的坐标和的奇偶性相同的方格，永远是互不影响的。
这启发我们建一个二分图。
我们不妨将奇点建在左侧，偶点建在右侧。然后从源点向奇点连容量为数值的边；从偶点向汇点连容量为数值的边。
于是，很显然，当我们割掉任何一条边的时候，就意味着相应的点是不取的。
接着我们将相邻的黑白点连容量为无穷大的边，这意味着这两个点之间至少有一个不能取。
然后跑最大流得到最小割即可。

#include<iostream>
#include<cstdio>
#include<queue>


const int INF=2147483647;
const int VERYBIG=0x3f3f3f3f; 

inline int Min(int A,int B){
	return A<B?A:B;
}


struct ee{
	int v;
	int w;
	int nxt;
}e[200005];
int h[40005],et=-1;
int dep[40005],nw[40005];

inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}

inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
}

int n,m,s,t;

inline int calc(int X,int Y){
	return (X-1)*m+Y;
}

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
}

inline int dfs(int X,int V){
	if(!V||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(e[i].w,V));
			if(val){
				V-=val;
				cnt+=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(!V){
					break;
				}
			}
			
		}
	}
	return cnt;
}

inline int dinic(){
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
	}
	return ans;
}

void init(){
	scanf("%d%d",&n,&m);
	s=n*m+1,t=n*m+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int x,cnt=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&x);
			cnt+=x;
			if((i+j)&1){
				add(s,calc(i,j),x);
				if(i+1<=n){
					add(calc(i,j),calc(i+1,j),VERYBIG);
				}
				if(i-1>=1){
					add(calc(i,j),calc(i-1,j),VERYBIG);
				}
				if(j+1<=m){
					add(calc(i,j),calc(i,j+1),VERYBIG);
				}
				if(j-1>=1){
					add(calc(i,j),calc(i,j-1),VERYBIG);	
				}
			}else{
				add(calc(i,j),t,x);
			} 
		}
	}
	printf("%d\n",cnt-dinic());
}

int main(){
	init();
	return 0;
}

2019年1月15日

lp3381 【模板】最小费用最大流

首先我们需要掌握网络流的相关知识。
然后，我们仔细观察费用流问题，我们发现，这一类问题的本质上就是让我们求一个带路径长度的最大流。
故而，我们考虑，对于相同的流量，尽可能地从费用小的一条路走过去——这是一种很显然的贪心。
具体的实现似乎也并不难，只需要将原来的朴素求法（EK）稍微更改一下，将反边的花费变成相反数，然后求最短路即可。
考虑到负权边的可能，用SPFA会比较快。当然如果只有正权边显然是可以Dijkstra的。

#include<iostream>
#include<cstdio>
#include<queue>

const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
    return A<B?A:B;
}
struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[100005];
int h[5005],et=-1;
inline void Eadd(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int C){
	Eadd(U,V,W,C);Eadd(V,U,0,-C);
}
int n,m,s,t,dis[5005],val[5005],fa[5005],nw[5005];
bool vis[5005];
std::queue<int> q;
inline int spfa(){
	for(int i=1;i<=n;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	while(!q.empty()){
		q.pop();
	}
	vis[s]=1,dis[s]=0,fa[t]=-1;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(val[p],e[i].w);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;
}
void init(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    int u,v,w,c;
    for(int i=1;i<=n;++i){
        h[i]=-1;
    }
    for(int i=1;i<=m;++i){
        scanf("%d%d%d%d",&u,&v,&w,&c);
        add(u,v,w,c);
    }
    int ansW=0,ansC=0,p;
    while(spfa()){
    	p=t;
    	ansW+=val[t];
    	ansC+=val[t]*dis[t];
    	while(p!=s){
    		e[nw[p]].w-=val[t];
    		e[nw[p]^1].w+=val[t];
    		p=fa[p];
		} 
    }
    printf("%d %d\n",ansW,ansC);
}

int main(){
    init();
    return 0; 
}

2019年1月11日2019年3月14日

lp2468 SDOI2010 粟粟的书架

简化题意。
有一个n*m的矩阵，q个询问，求问，在每个矩阵中最少取多少个数，使得和至少为h。
观察数据范围，我们惊讶地发现这一题不可避免地要做两次。
因为，n,m<=200显然不是用普通的数据结构可以维护的。我们考虑使用$cnt_{i,j,k}$表示大于k的数的数量，$sm_{i,j,k}$表示大于k的数的总和。然后二分这个k来求解即可。
对于n==1的情况，我们很容易可以想到维护一棵权值主席树。对于每一个询问，我们在两棵权值线段树上二分然后求差。

#include<iostream>
#include<cstdio>
#define MID ((L+R)>>1)
int n,m,q;
int b[205][205],cnt[205][205][1005],sm[205][205][1005];
//不需要开longlong！！！MLE警告！！！ 

inline long long cntQry(int X1,int Y1,int X2,int Y2,int K){
    return cnt[X2][Y2][K]-cnt[X1-1][Y2][K]-cnt[X2][Y1-1][K]+cnt[X1-1][Y1-1][K];
}
inline long long smQry(int X1,int Y1,int X2,int Y2,int K){
    return sm[X2][Y2][K]-sm[X1-1][Y2][K]-sm[X2][Y1-1][K]+sm[X1-1][Y1-1][K];
}
inline void slv2(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%d",&b[i][j]);
        }
    }
    for(int k=0;k<=1000;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                cnt[i][j][k]=cnt[i-1][j][k]+cnt[i][j-1][k]-cnt[i-1][j-1][k]+(int)(b[i][j]>=k);
                sm[i][j][k]=sm[i-1][j][k]+sm[i][j-1][k]-sm[i-1][j-1][k]+(int)(b[i][j]>=k)*b[i][j];
            }
        }
    }
    long long l,r,mid,h,ans;
    int X1,X2,Y1,Y2;
    while(q--){
        l=0,r=1001,ans=-1;
        scanf("%d%d%d%d%lld",&X1,&Y1,&X2,&Y2,&h);
        while(l<=r){
            mid=(l+r)>>1,smQry(X1,Y1,X2,Y2,mid)>=h?(ans=mid,l=mid+1):r=mid-1;
        }
        (~ans)?(printf("%lld\n",cntQry(X1,Y1,X2,Y2,ans)-(smQry(X1,Y1,X2,Y2,ans)-h)/ans)):(puts("Poor QLW"));
    }
    
//	 对于同一个k可能有多个值，而可能只需要选取部分。 
}
const int MAXN2=10000005;
int a[MAXN2];
//数组大小别算错 
class ChairmanTree{
    private:
        class Node{
            public:
                int l;
                int r;
                int fa;
                int sz;
                int sm;
        };
        Node tr[MAXN2];
        int cnt,rt[MAXN2];
        inline void build(int LST,int &NW,int L,int R,int V){
            NW=++cnt;tr[NW].sz=tr[LST].sz+1;tr[NW].sm=tr[LST].sm+V;
            if(L==R){return;}
            MID>=V?(build(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(build(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
            //如果值小等于MID。那么就更新右边的值；否则更新左边的值。一定要注意判断V==MID时的情况。 
            //如果更新的是右边的值，那么就把右边的节点与上一个版本的右边的节点一并下传，并修改本节点的左节点；否则反之。 
        }
        //从根往下搜索。注意减去的应当是右节点的值。 
        inline int qry(int A,int B,int L,int R,int V){
            int RT=0;
            while(L<R){(tr[tr[B].r].sm-tr[tr[A].r].sm)>V?(L=MID+1,B=tr[B].r,A=tr[A].r):(RT+=tr[tr[B].r].sz-tr[tr[A].r].sz,V-=(tr[tr[B].r].sm-tr[tr[A].r].sm),R=MID,B=tr[B].l,A=tr[A].l);}
            //同理，对于等于的情况也应当特别注意。 
            return RT+(V+L-1)/(L);
            //剩下的部分应该全部由大小为R的这些东西，也就是当前点的值来处理掉。故而要加上(V+L-1)/(L)
        }
    public:
        inline void ADD(int VER,int X){
            build(rt[VER-1],rt[VER],1,1000,X);
        }
        inline int QUREY(int LVER,int RVER,int X){
            return qry(rt[LVER-1],rt[RVER],1,1000,X);
        }
        inline int SUM(int L,int R){
            return tr[rt[R]].sm-tr[rt[L-1]].sm;
        }
        inline void INIT(){
            cnt=0;
        }
};
ChairmanTree T;
inline void slv1(){
    T.INIT();
    for(int i=1;i<=m;++i){
        scanf("%d",&a[i]);
        T.ADD(i,a[i]);
    }
    int l,r,tmp,x;
    while(q--){
        scanf("%d%d%d%d%d",&tmp,&l,&tmp,&r,&x);
        if(T.SUM(l,r)<x){
            puts("Poor QLW");
            continue;
        }
        printf("%d\n",T.QUREY(l,r,x));
    }
}

void init(){
    scanf("%d%d%d",&n,&m,&q);
    n==1?slv1():slv2();
}

int main(){
    init();
    return 0;
}

2019年1月10日

lp1131 ZJOI2007 时态同步

有一棵树，每次将一条边的长度增加1的代价为1，求，使得所有叶节点到根节点距离相同的最小代价。
很显然，对于一棵树来说，贪心地考虑，最终的距离显然是最开始的最远叶节点的距离。
然后，继续贪心地考虑，每一次增加的代价，应当避免那些已经是最远距离的节点。
但是这样做的话复杂度最坏是n^2的。
故而我们考虑树形DP。对于每个节点临时记以这个节点为根的子树完成时态同步需要的代价。然后每一次修改把修改结果记下来即可。

#include<iostream>
#include<cstdio>

inline int Max(int A,int B){
	return A>B?A:B;
}
struct ee{
	int v;
	int w;
	int nxt;
}e[1000005];
int h[500005],et=0;
inline void add(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
int n,s,f[500005];
long long ans=0;
inline void dfs(int X,int FA){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		dfs(e[i].v,X);
	}
	int mx=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		mx=Max(mx,f[e[i].v]+e[i].w);
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		ans+=mx-(f[e[i].v]+e[i].w);
	}
	f[X]=mx;
}
void init(){
	scanf("%d%d",&n,&s);
	int u,v,w;
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	dfs(s,0);
	printf("%lld\n",ans);
}

int main(){
	init();
	return 0;
}

2019年1月9日

lp2150 NOI2015 寿司晚宴

将2~n的整数划分到两个集合，使得两个集合中任意两个元素互质，求方案数。
对于n<=30的情况是很容易想到的，将每个数$i$求出它的质因子集合$K_{i}$。
很容易可以发现，30以内的质数仅有10种。故而我们就有了一个$O(2^{202}n)$的做法。
对于n<=500的情况，似乎用上述的做法并不是十分可行，无论是时间复杂度还是空间复杂度都是不可接受的。
但是我们发现，有且仅有7个质数，在500以内会作为因数出现多次。我们是不是可以用一种奇技淫巧把大于19的质数处理掉呢？
我们惊讶地发现，由于所有较大的质数会且只会出现一次，那么很显然所有最大质因子是较大质数且最大质因子相同的数只能放到一个集合里。
故而我们把所有数按照最大质因子排序，然后从小到大遍历。当最大质因子成为较大质数的时候，不再使用原来的数组，而是将「这个质因子一个都没选」的情况复制到两个新的数组f2[2][1<<7][1<<7]。
每一次更换最大质因子的时候都从原数组继承DP值，然后在这里面对每一个是放在A还是放在B的情况来更新：

$$f_{S_1,S_2} = f2_{0,S_1,S_2} + f2_{1,S_1,S_2} – f_{S_1,S_2}$$

之所以最后还要减去原来的值是因为，两个新数组的最终结果各自都是从原来的「这个质因子一个都没选」的情况复制过来的，因此「这个质因子一个都没选」的情况就会被统计两次。

#include<iostream>
#include<cstdio>
#include<algorithm>
/*

*/ 
const int P[8]={2,3,5,7,11,13,17,19};
const int MAX=1<<8;
long long MOD;
long long f[MAX][MAX],f2[2][MAX][MAX];
struct data{
	int v;
	int big;
	int K;
	inline void init(int X){
		v=X,big=0;
		int nw=v;K=0;
		for(int i=0;i<8;++i){
			if(!(nw%P[i])){
				K|=(1<<i);
			}
			while(!(nw%P[i])){
				nw/=P[i];
			}
		}
		if(nw>1){
			big=nw;
		}
	}
	inline bool operator<(const data &B)const{
		return big<B.big;
	}
}a[505];
int n;
void init(){
	scanf("%d%lld",&n,&MOD);
	--n;
	for(int i=1;i<=n;++i){
		a[i].init(i+1);
	}
	std::sort(a+1,a+1+n);
	int lst=0x3f3f3f3f;
	f[0][0]=1;
	for(int i=1;i<=n;++i){
		if(a[i].big){
			lst=i;
			break;
		}
		for(int j=MAX-1;~j;--j){
//			注意这里要-1 
			for(int k=MAX-1;~k;--k){
				f[j][k|a[i].K]+=f[j][k];f[j|a[i].K][k]+=f[j][k];
				f[j][k|a[i].K]%=MOD;f[j|a[i].K][k]%=MOD;
			}
		}
	}
	for(int i=lst;i<=n;++i){
		if(a[i].big!=a[i-1].big){
			for(int j=0;j<MAX;++j){
				for(int k=0;k<MAX;++k){
					f2[0][j][k]=f2[1][j][k]=f[j][k];
				}
			}
		}
		for(int j=MAX-1;~j;--j){
			for(int k=MAX-1;~k;--k){
				if(j&k){
					continue;
				}
				if(!(k&a[i].K)){
					f2[0][j|a[i].K][k]+=f2[0][j][k];
					f2[0][j|a[i].K][k]%=MOD;
				}
				if(!(j&a[i].K)){
					f2[1][j][k|a[i].K]+=f2[1][j][k];
					f2[1][j][k|a[i].K]%=MOD;
				}
			}
		}
		if(a[i].big!=a[i+1].big){
			for(int j=0;j<MAX;++j){
				for(int k=0;k<MAX;++k){
					f[j][k]=(f2[0][j][k]+f2[1][j][k]+(MOD-f[j][k]))%MOD;
				}
			}
		}
	}
	long long ans=0;
	for(int i=MAX-1;~i;--i){
		for(int j=MAX-1;~j;--j){
			if(i&j){
				continue;
			}
			ans+=f[i][j];
			ans%=MOD;
		}
	}
	printf("%lld\n",ans);
}

int main(){
	init();
	return 0;
}

2019年1月8日

CF1099

一场爆肝场。
如果不是划水划到太晚才不会打呢（大雾）
整体来说难度较低…但是EF都没做出来，丢人。

CF1099A
一道简单题。直接处理贡献即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int w,h;
int d1,w1,d2,w2;
void init(){
	scanf("%d%d%d%d%d%d",&w,&h,&w1,&d1,&w2,&d2);
	int ans=w;
	for(int i=h;i>=0;--i){
		ans+=i;
		if(d1==i){
			ans-=w1;
			ans=std::max(ans,0);
			continue;
		}
		if(d2==i){
			ans-=w2;
			ans=std::max(ans,0);
			continue;
		}
		
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}

CF1099B
找规律题。
解一个二次方程很容易就可以找到最优解。
实际情况当然是大力分类讨论。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
int n;
void init(){
	int ans=0;
	scanf("%d",&n);
	int flr=(floor(sqrt(n)));
	ans=2*flr;
	n-=flr*flr;
	if(n&&n<=flr){
		++ans;
	}else if(n&&n>flr){
		ans+=2;
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}

CF1099C
一道有一定难度的模拟题。
很容易可以想到朴素的贪心做法。就是，能删的全都删；要加的一次加光。
要考虑很多细节。注意对无解情况的判定。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
char base[205];
int len,del,ad,gl;
void init(){
	cin>>base+1;
	scanf("%d",&gl);
	len=strlen(base+1);
	for(int i=1;i<=len;++i){
		if(base[i]=='?'){
			++del;
		}
		if(base[i]=='*'){
			++ad;
		}
	}
	int n=len;
	len-=del;
	len-=ad;
	if(len-del-ad>gl||(!ad&&len<gl)){
		puts("Impossible");
	}else{
		if(len==gl){
			for(int i=1;i<=n;++i){
				if(base[i]!='?'&&base[i]!='*'){
					putchar(base[i]);
				}
			}
		}else if(len>gl){
			int cnt=len-gl;
			for(int i=1;i<=n;++i){
				if(base[i]=='*'){
					base[i]='?';
				}
			}
			for(int i=1;i<=n;++i){
				if(base[i+1]=='?'&&cnt){
					++i;
					--cnt;
				}else if(base[i]=='?'){
					continue;
				}else{
					putchar(base[i]);
				}
			}
			return;
		}else if(len<gl){
			int cnt=gl-len;
			for(int i=1;i<=n;++i){
				if(base[i+1]=='*'&&cnt){
					for(int j=0;j<=cnt;++j){
						putchar(base[i]);
					}
					cnt=0;
				}else if(base[i]=='?'||base[i]=='*'){
					continue;
				}else{
					putchar(base[i]);
				}
			}
		}
	}
}
int main(){
	init();
	return 0;
}

CF1099D
一道有一定思维难度的树形DP。
很容易可以证明，贪心地取子树最小总是更优的；下方只要不比上方大那就始终是有解的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
struct ee{
	int v;
	int nxt;
}e[200005];
int h[100005],et=0,fa[100005],dep[100005];
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int n,s[100005],a[100005];
inline void dfs0(int X){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==fa[X]){
			continue;
		}
		dep[e[i].v]=dep[X]+1;
		dfs0(e[i].v);
	}
}
inline void dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==fa[X]){
			continue;
		}
		dfs(e[i].v);
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==fa[X]){
			continue;
		}
		if(!(dep[X]&1)){
			s[X]=std::min(s[X],s[e[i].v]);
		}
	}
	if(s[X]==0x3f3f3f3f){
		s[X]=s[fa[X]];
	}
}
void init(){
	scanf("%d",&n);
	int v;
	for(int i=2;i<=n;++i){
		scanf("%d",&v);
		fa[i]=v;
		add(i,v);
		add(v,i);
	}
	dep[1]=1,fa[1]=0;
	dfs0(1);
	for(int i=1;i<=n;++i){
		scanf("%d",s+i);
	}
	for(int i=1;i<=n;++i){
		if(s[i]==-1){
			s[i]=0x3f3f3f3f;
		}
	}
	dfs(1);
//	for(int i=1;i<=n;++i){
//		printf("%d ",dep[i]);
//	}
//	puts("");
	long long ans=0;
	for(int i=1;i<=n;++i){
		a[i]=s[i]-s[fa[i]];
		ans+=a[i];
		if(a[i]<0){
			puts("-1");
			return;
		}
	}
	printf("%I64d\n",ans);
}
int main(){
	init();
	return 0;
}

2019年1月6日

lp2766 网络流24题-最长不下降子序列问题

这是一道看起来很简单的麻题。
很显然可以发现第一问就是直接n^2DP求一个答案。
第二问模拟寻找最长不下降子序列的过程。
第三问改几条边再跑一遍。
但是要注意很多很多细节。
比如说，建模的时候应该反着建。
再比如说，对于最长长度只有1的情况应当格外注意，因为这可能会导致各种错误。
写起来还是有点烦心的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>

const int INF=0x3f3f3f3f;
const int BIG=19260817;
inline int Min(int A,int B){
	return A<B?A:B;
}

inline int Max(int A,int B){
	return A>B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[250005];
int h[2005],et=-1;

inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et; 
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
}

int dep[2005],nw[2005],a[505];
int n,s,t,len;
std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF,nw[i]=h[i];
	}
	dep[s]=1;
	while(!q.empty()){
		q.pop();
	}
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
//	for(int i=1;i<=t;++i){
//		printf("%d ",dep[i]);
//	}
//	puts("");
	return dep[t]^INF;
}

inline int dfs(int X,int V){
	if(!V||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(V,e[i].w));
			if(val){
				cnt+=val;
				V-=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(!V){
					break;
				}
			}
		}
	}
	return cnt;
}
int f[505];
inline void slv1(){
	for(int i=1;i<=n;++i){
		f[i]=1;
		for(int j=1;j<i;++j){
			if(a[i]>=a[j]){
				f[i]=Max(f[i],f[j]+1);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		ans=Max(ans,f[i]);
	}
	len=ans;
	printf("%d\n",ans);
}

inline int dinic(){
	int RT=0;
	while(bfs()){
		RT+=dfs(s,INF);
	}
	return RT;
}

inline void slv2(){
	s=2*n+1,t=2*n+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	et=-1;
	for(int i=1;i<=n;++i){
		if(f[i]==len){
			add(i+n,t,1);
		}
		if(f[i]==1){
			add(s,i,1);
		}
		add(i,i+n,1);
		for(int j=1;j<i;++j){
			if(a[i]>=a[j]&&f[j]+1==f[i]){
				add(j+n,i,1);
			}
		}
	}
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
	}
	printf("%d\n",ans);
	add(1,n+1,BIG),add(s,1,BIG);
	if(f[n]==len){
		add(n,2*n,BIG),add(2*n,t,BIG);
	}
	while(bfs()){
		ans+=dfs(s,INF);
	}
	printf("%d\n",ans);
}

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	slv1();
	slv2();
}
int main(){
	init();
	return 0;
}

2019年1月4日

lp1963 NOI2009 变换序列

如果知道这道题是一个二分图匹配，就显得非常简单了。
首先我们对原序列和变换序列各自建一个点。
然后，对于每一组约束条件$D_{i}$，我们向所有到$i$的距离为$D_{i}$的点连一条边。
然后先跑一遍二分图最大匹配。如果全部都能匹配上就说明有解。

但是题目要求字典序输出这组解，怎么办呢？
这么做的意思就是，对于一个尽可能小的数$i$，它匹配的数$T_{i}$也要尽可能小。
故而，搜索的时候从大往小即可。

#include<iostream>
#include<cstdio>
int n,D[10005];
int vis[10005],dep=0;
int usd[10005];

inline bool dfs(int X){
	int up=(X+D[X]-1)%n+1,dw=(X-D[X]+n-1)%n+1;
	if(up<dw){
		std::swap(up,dw);
	}
//	printf("%d %d\n",up,dw);
	if(!usd[dw]&&vis[dw]!=dep){
		vis[dw]=dep;
		usd[dw]=X;
		return 1;
	}
	if(vis[dw]!=dep){
		vis[dw]=dep;
		if(dfs(usd[dw])){
			usd[dw]=X;
			return 1;
		}
	}
	if(!usd[up]&&vis[up]!=dep){
		vis[up]=dep;
		usd[up]=X;
		return 1;
	}
	if(vis[up]!=dep){
		vis[up]=dep;
		if(dfs(usd[up])){
			usd[up]=X;
			return 1;
		}
	}
	
	return 0;
}
int Ans[10005];
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&D[i]);
	}
	int ans=0;
	for(int i=n;i>=1;--i){
		++dep;
		if(dfs(i)){
			++ans;
		}else{
			break;
		}
	}
	if(ans<n){
		puts("No Answer");
	}else{
		for(int i=1;i<=n;++i){
			Ans[usd[i]]=i;
		}
		for(int i=1;i<=n;++i){
			printf("%d ",Ans[i]-1);
		}
	}
}

int main(){
	init();
	return 0;
}

月度归档： 2019年1月

lp2153 SDOI2009 晨跑

lp2805 NOI2009 植物大战僵尸