From The Stupid

n^2的dp可过第一问

第二问只要从左往右贪心的取数就好了 只要当前的数的f[i]>l-top 且大于前一个数 就可以取来

千万要注意 题目中说的字典序最小是下标字典序最小而不是序列的字典序最小！！！！！！！

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=10010;
int f[N],s[N],n,m,q,ans[N],maxdp;
void read(int &x){
	char c;
	while((c=getchar())<'0' || c>'9');x=c-'0';
	while((c=getchar())>='0' && c<='9') x=x*10+c-'0';
}
int main(){
	//freopen("1046.in","r",stdin);freopen("1046.out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++) read(s[i]);s[0]=~0u>>1;
	for(int i=n;i>=1;i--){
		f[i]=1;
		for(int j=i+1;j<=n;j++) if(s[i]<s[j]) f[i]=max(f[i],f[j]+1);
		maxdp=max(maxdp,f[i]);
	}
	read(m);
	while(m--){
		int l;
		read(l);
		if(maxdp>=l){
			int top=0;
			ans[0]=-(~0u>>1);
			for(int i=1;i<=n;i++) if(l-f[i]<=top && s[i]>ans[top]) ans[++top]=s[i];
			for(int i=1;i<l;i++) printf("%d ",ans[i]);printf("%d\n",ans[l]);
		}
		else printf("Impossible\n");
	}
	return 0;
}

网络流裸体 

第一问最大流跑一跑

第二问新建一个点连边到1 容量k费用0 再对所有的边复制一条边出来 容量为inf 费用为w

然后跑最小费用最大流

这题最大流用ek可过

#include <cstdio>
#include <algorithm>
#include <cstring>
#define clr(x) memset(x,0,sizeof(x))
using namespace std;
void read(int &x){
	char c;
	while((c=getchar())<'0' || c>'9');x=c-'0';
	while((c=getchar())>='0' && c<='9') x=x*10+c-'0';
}
const int N=100010,inf=308888888;
struct Ask{
	int u,v,c,w;
	void read2(){read(u),read(v);read(c);read(w);}
}ask[N];
int n,m,c[N],to[N],nxt[N],now[N],cap[N],tail=1,q[N],from[N],dis[N],inq[N],k,ans;
void add(int u,int v,int ci,int capi){
	to[++tail]=v;nxt[tail]=now[u];now[u]=tail;c[tail]=ci;cap[tail]=capi;
	to[++tail]=u;nxt[tail]=now[v];now[v]=tail;c[tail]=-ci;cap[tail]=0;
}
bool spfa(int s,int t){
	int l=0,r=0;
	clr(from);clr(inq);
	for(int i=1;i<=n+2;i++) dis[i]=inf;
	q[++r]=s;dis[s]=0;inq[s]=1;
	while(l<r){
		int u=q[(++l)%N];inq[u]=0;
		for(int i=now[u];i;i=nxt[i]) if(cap[i]>0 && dis[to[i]]>dis[u]+c[i]){
			int v=to[i];
			dis[v]=dis[u]+c[i];
			from[v]=i;
			if(!inq[v]) q[(++r)%N]=v;
		}
	}
	return dis[t]!=inf;
}
int augument(int s,int t,int type){
	int fl=inf,ret=0;
	for(int tmp=t;tmp!=s;){
		int e=from[tmp];
		fl=min(cap[e],fl);
		tmp=to[e^1];
	}
	for(int tmp=t;tmp!=s;){
		int e=from[tmp];
		cap[e]-=fl;cap[e^1]+=fl;
		ret+=fl*c[e];
		tmp=to[e^1];
	}
	return type?ret:fl;
}
int main(){
	//freopen("1834.in","r",stdin);freopen("1834.out","w",stdout);
	read(n);read(m);read(k);
	for(int i=1;i<=m;i++) {
		ask[i].read2();
		add(ask[i].u,ask[i].v,0,ask[i].c);
	}
	while(spfa(1,n)) ans+=augument(1,n,0);
	printf("%d ",ans);ans=0;
	for(int i=1;i<=m;i++) add(ask[i].u,ask[i].v,ask[i].w,inf);
	add(n+1,1,0,k);
	while(spfa(n+1,n)) 	ans+=augument(n+1,n,1);
	printf("%d",ans);
}

prufer数列+高精度

http://www.cnblogs.com/zhj5chengfeng/archive/2013/08/23/3278557.html

详细的介绍可以看这篇blog

知道这个之后 只要计算prufer数列的个数就好了

首先将有度数限制的所有点数一下，这些点的度数-1就是在数列中出现的次数，这可以用含有重复元素的排列来解决。剩下来的位置可以用任意一个没有度数限制的点来填，乘法原理一下即可。

注意特判n=1和2的情况。

计算组合数的时候除法除单精度的数即可

#include <cstdio>
#include <algorithm>
using namespace std;
const int MOD=10,N=5010;
struct bigint{int a[N];
	void reset(){for(int i=0;i<N;i++) a[i]=0;a[0]=1;}
	void operator =(int x){
		reset();
		for(;x;x/=MOD,a[0]++) a[a[0]]=x%MOD;
		if(a[0]>1) a[0]--;
	}
	void print(){
		for(int i=a[0];i;i--) putchar(a[i]+'0');
	}
}ans;
int n,s[N],sum,sum2;
bigint operator *(bigint x,int y){
	for(int i=1;i<=x.a[0];i++) x.a[i]*=y;
	for(int i=1;i<x.a[0];i++) x.a[i+1]+=x.a[i]/MOD,x.a[i]%=MOD;
	for(int& i=x.a[0];x.a[i]>=MOD;i++) x.a[i+1]+=x.a[i]/MOD,x.a[i]%=MOD;
	return x;
}
bigint operator /(bigint x,int y){
	bigint z;int tmp=0;
	z=0;z.a[0]=x.a[0];
	for(int i=x.a[0];i;i--) z.a[i]=(tmp*MOD+x.a[i])/y,tmp=(tmp*MOD+x.a[i])%y;
	for(int &i=z.a[0];!z.a[i] && i;) 
		i--;
		if(!z.a[0]) z.a[0]++;
	return z;
}
int main(){
	scanf("%d",&n);
	if(n==1){
		scanf("%d",&s[1]);	
    		printf(s[1]?"0":"1");
       		return 0;
	}
	for(int i=1;i<=n;i++) {
		scanf("%d",&s[i]),s[i]>=1?sum+=s[i]-1:sum2++;
		if(!s[i]) {printf("0");return 0;}
	}
	if(sum>n-2) {printf("0");return 0;}
	ans=1;
	for(int i=n-2;i>=n-2-sum+1;i--) ans=ans*i;
	for(int i=1;i<=n;i++) if(s[i]>1) for(int j=1;j<=s[i]-1;j++) ans=ans/j;
	for(int i=1;i<=n-2-sum;i++) ans=ans*(sum2);
	ans.print();
	return 0;
}

考虑枚举gcd(i,n) =d 那么只要计数有多少个数和N的gcd是d

显然是phi(n/d)个

假设一个数可以表示成$p_{1}^{a1}+p_{2}^{a2}+...$,那么phi的结果就是 $(p_{1}-1)*p_{1}^{a1-1}*(p_{2}-1)*p_{2}^{a2-1}...$每次找到一个约数之后除干净就可以保证每次找到的都是质因数

计算phi是$\sqrt{n}$(枚举约数的复杂度) 枚举公约数$\sqrt{n}$ 时间复杂度$\sqrt{n}$

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
LL n,sq,ans;
LL phi(LL x){
	LL tmp=(LL)sqrt(x),ret=1;
	for(int i=2;i<=tmp;i++){
		if(x%i==0){
			ret*=i-1;x/=i;
			while(x%i==0) x/=i,ret*=i;
		}
	}
	if(x>1)ret=ret*(x-1);
	return ret;
}
int main(){
	scanf("%lld",&n);sq=(LL)sqrt(n);
	for(int i=1;i<=sq;i++){
		if(n%i==0) {
			ans+=i*phi(n/i);
			if(n/i!=i) ans+=(n/i*phi(i));
		}
	}
	printf("%lld",ans);
}

这种限制节点经过次数的估计就是网络流了

新建源汇s t

把一个点拆成两个，中间连接一条容量为经过次数的边

对于每一个蜥蜴，从s向这个点的入点连边，容量为1，表示有一条蜥蜴。对于每一个点可达的点从出点连边，容量正无穷，能跳出的向t连边，容量正无穷。跑最大流即可

dinic的时候不要忘记重置cur数组，一直死循环…………

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
//点ij为2*(c*(i-1)+j)入和2*(c*(i-1)+j)+1出 s=r*c*2+2 t=r*c*2+3
const int N=200010,INF=209999999;
int to[N],from[N],fl[N],tail=1,pre[N],now[N],ans,d[N],vis[N],q[N*2],L,R,cur[N],r,c,di,tmp,g[50][50],xiyi;
inline int o(int i,int j){return 2*(c*(i-1)+j);}
void add(int u,int v,int f){
	to[++tail]=v;pre[tail]=now[u];now[u]=tail;fl[tail]=f;
	to[++tail]=u;pre[tail]=now[v];now[v]=tail;fl[tail]=0;
}
bool bfs(int s,int t){
	memset(vis,0,sizeof(vis));
	L=R=0;q[++R]=s;vis[s]=1;d[s]=0;
	for(int x=q[++L];L<=R;x=q[++L])
		for(int i=now[x];i;i=pre[i]) if(fl[i]>0 && !vis[to[i]]) d[to[i]]=d[x]+1,vis[to[i]]=1,q[++R]=to[i];
	return vis[t];
}
int dfs(int x,int t,int a){
	if(x==t || a==0) return a;
	int flow=0,f;
	for(int &i=cur[x];i;i=pre[i]) if(d[to[i]]==d[x]+1 && (f=dfs(to[i],t,min(a,fl[i])))>0){
		fl[i]-=f;fl[i^1]+=f;flow+=f;a-=f;
		if(a==0) break;
	}
	return flow;
}
int main(){
	//freopen("1066.in","r",stdin);freopen("1066.out","w",stdout);
	scanf("%d%d%d\n",&r,&c,&di);
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++) {
			g[i][j]=getchar()-'0';
			if(g[i][j]) add(o(i,j),o(i,j)^1,g[i][j]);
		}
		getchar();
	}
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++) if(g[i][j])
			for(int x=-di;x<=di;x++)
				for(int y=-di;y<=di;y++) if(abs(x)+abs(y)<=di && i+x>0 && i+x<=r && j+y>0 && j+y<=c && g[i+x][j+y] && ((i+x)!=i || (j+y)!=j)) add(o(i,j)^1,o(i+x,j+y),INF);
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			tmp=getchar();
			if(tmp=='L') xiyi++,add(2*r*c+2,o(i,j),1);
		}
		getchar();
	}
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++) if(g[i][j] && min(min(r+1-i,i),min(c+1-j,j)) <= di) 	add(o(i,j)+1,2*r*c+3,INF);
	while(bfs(2*r*c+2,2*r*c+3)) {
		for(int i=1;i<=2*r*c+3;i++) cur[i]=now[i];
		ans+=dfs(2*r*c+2,2*r*c+3,INF);
	}
	ans=xiyi-ans;
	printf("%d",ans);
	return 0;
}

贪心法

一开始以为是取线段问题……结果发现手算的样例过不去，然后才发现是时间可以接上去的...

和取线段问题类似，我们首先把所有的建筑按照结束时间点排序，每次拿到这个建筑，我们看看之前修理的所有建筑的时间和是多少，如果来得及修理就加入到维修的列表里去，但是如果来不及修理的话怎么办呢？由于之前的所有建筑都可以在截止时间前修好，我们可以删掉其中的某些建筑来满足当前考虑的这个点，但是我们显然最多删掉一个（否则的话总数会减少）,那么删除掉哪个呢？当然是完成时间最大的那个啦！（注意这里如果完成时间最大的那个比当前考虑的建筑完成时间要短的话就跳过当前这个建筑，否则的话时间增加而维修的建筑数不变）  

于是我们就得到了一个这样的问题：动态插入一些点，每次寻找其中最大的，采用堆维护即可。

感觉贪心题的证明还是比较重要的，个人感觉自己的贪心是很弱的……

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int N=150010;
typedef long long LL;
LL n,s,t,last;
struct ar{LL t1,t2;friend bool operator <(ar a,ar b){return a.t1<b.t1;}}b[N];
priority_queue<ar> q;
bool cmp(ar a,ar b){return a.t2<b.t2;}
void read(LL &x){char c;while((c=getchar())<'0'||c>'9');x=c-'0';while((c=getchar())>='0'&& c<='9') x=x*10+c-'0';}
int main(){
	//freopen("1029.in","r",stdin);freopen("1029.out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++) read(b[i].t1),read(b[i].t2);
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++)
		if(t+b[i].t1<=b[i].t2) q.push(b[i]),s++,t+=b[i].t1;
		else if(!q.empty()){
			ar a=q.top();
			if(b[i].t1<a.t1) q.pop(),q.push(b[i]),t=t-a.t1+b[i].t1;
		}
	printf("%lld",s);
	return 0;
}

最小生成树求一下就好了……

其实相当于是二分一个答案然后把所有小于这个权值的边都连上然后判断连通性，但是这个过程其实就是kruscal的过程所以只要最小生成树就可以了

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100010;
struct edge{int a,b,v;}e[N];
int n,m,cnt,ans,f[N];
int find(int a){return f[a]==a?a:f[a]=find(f[a]);}
void Union(int a,int b){f[find(a)]=find(b);}
bool cmp(edge a,edge b){return a.v<b.v;}
int main(){
	//freopen("1083.in","r",stdin);freopen("1083.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].v);
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		if(find(e[i].a)!=find(e[i].b)) cnt++,Union(e[i].a,e[i].b),ans=e[i].v;
		if(cnt==n-1) break;
	}
	printf("%d %d",cnt,ans);
	return 0;
}

离线莫队算法

预处理出每个位置i 前一个和这个颜色相同的位置pre[i]和下一个颜色相同的位置nxt[i]

莫队转移的时候看一下区间里面还有没有这个颜色就可以转移了

最后统计的时候我用了一个分块- -其实不用也可以的，或者用了分块可以不用预处理上面的东西，分块记录和然后颜色减到0的时候该块的和减1就可以了

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=50010;
struct ask{int l,r,id;}q[200010];
int pre[N],nxt[N],n,c[N],tmp[1000010],sqrn,sqrc=1010,bit[2000],ans[200010],l,r,m,mx;
bool cmp(ask a,ask b){return a.l/sqrn==b.l/sqrn?a.r<b.r:a.l/sqrn<b.l/sqrn;}
void read(int &x){
	char c;
	while((c=getchar())<'0' || c>'9');x=c-'0';
	while((c=getchar())>='0' && c<='9') x=x*10+c-'0';
}
int main(){
	//freopen("1878.in","r",stdin);freopen("1878.out","w",stdout);
	read(n);sqrn=(int)sqrt(n);
	for(int i=1;i<=n;i++) read(c[i]),mx=max(c[i]+10,mx);sqrc=(int)sqrt(mx);
	read(m);
	for(int i=1;i<=m;i++) read(q[i].l),read(q[i].r),q[i].id=i;
	for(int i=1;i<=n;i++) pre[i]=tmp[c[i]],tmp[c[i]]=i;
	for(int i=0;i<=1000000;i++) tmp[i]=50010;
	for(int i=n;i>=1;i--) nxt[i]=tmp[c[i]],tmp[c[i]]=i;//预处理pre和nxt
	sort(q+1,q+m+1,cmp);l=r=1;bit[c[1]/sqrc]=1;
	for(int i=1;i<=m;i++){
		int ret=0;
		for(;l<q[i].l;l++) if(nxt[l]>r) bit[c[l]/sqrc]--;
		for(;l>q[i].l;l--) if(nxt[l-1]>r) bit[c[l-1]/sqrc]++;
		for(;r<q[i].r;r++) if(pre[r+1]<l) bit[c[r+1]/sqrc]++;
		for(;r>q[i].r;r--) if(pre[r]<l) bit[c[r]/sqrc]--;
		for(int j=0;j<sqrc+10;j++) ret+=bit[j];
		ans[q[i].id]=ret;
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

二分图匹配问题

属性为一边，装备为另一边，每一个装备连2条边，枚举属性进行匈牙利算法 

但是这题有一个优化 因为flag每次都重置的话需要花很长时间，我们采用一个时间戳，每次进行匹配的时候T++，flag就用T来代替

注意不能直接输出T-1，因为如果匹配完全的话，就是输出T了

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1000010;
int to[N*2],pre[N*2],now[N],from[N],flag[N],T,tail,n,a,b;
void add(int u,int v){to[++tail]=v;pre[tail]=now[u];now[u]=tail;}
bool hungary(int a){
	for(int i=now[a];i;i=pre[i]) if(flag[to[i]]!=T){
		flag[to[i]]=T;
		if(!from[to[i]] || hungary(from[to[i]])){from[to[i]]=a;return true;}
	}
	return false;
}
void read(int &x){
	char c;
	while((c=getchar())<'0'||c>'9');x=c-'0';
	while((c=getchar())>='0'&&c<='9') x=x*10+c-'0';
}
int main(){
	//freopen("1854.in","r",stdin);freopen("1854.out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++) read(a),read(b),add(a,i),add(b,i);
	for(int i=1;i<=10000;i++){
		T++;
		if(!hungary(i)) {T--;break;}
	}
	printf("%d",T);
	return 0;
}

推dp方程

首先将所有的工厂按距离排序

定义f[i]表示前i个工厂的所有货都能够保存下来的最小费用，cost[i][j]为把所有i到j的货物运到j的费用，那么显然

$f[i]=min{ f[j]+cost[j+1][i]+c[i]} (0\leq j \leq i-1)$

考虑如何计算cost[i][j]，定义sum[i]表示前i个工厂的物品个数之和,d[i]表示工厂i到第一个工厂的距离 那么可以得到

$cost[i][j]=cost[1][j]-cost[1][i]-sum[j]*(d[j]-d[i])$

于是只要预处理出cost[1][i]和sum[i]就可以O(1)计算cost[i][j]。下面用cost[i]表示cost[1][i]

看到n这么大，我们试一试斜率优化

假设j>k,且决策j比k优

那么有

$f[j]+cost[i]-cost[j]-sum[j]*(d[i]-d[j])+c[i] < f[k]+cost[i]-cost[k]-sum[k]*(d[i]-d[k])+c[i]$

将所有有关i的移项到右边其他移到左边可以得到

$(f[j]-cost[j])-(f[k]-cost[k])+sum[j]*d[j]-sum[k]*d[k] < d[i]*(sum[j]-sum[k])$

由于sum[j]>sum[k]，可以除过来，否则要考虑不等号变向问题 则

$\frac{(f[j]-cost[j])-(f[k]-cost[k])+sum[j]*d[j]-sum[k]*d[k]}{(sum[j]-sum[k])} < d[i]$ d[i]递增可以斜率优化

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=1000010;
struct Fact{LL c,d,p;}fa[N];
LL n,cost[N],f[N],sum[N],q[N*3],l,r;
bool cmp(Fact a,Fact b){return a.d<b.d;}
double slop(int k,int j){return (f[j]-cost[j]-(f[k]-cost[k])+sum[j]*fa[j].d-sum[k]*fa[k].d)/(double)(sum[j]-sum[k]);}
void read(LL &x){
	char c;
	while((c=getchar())<'0' || c>'9');x=c-'0';
	while((c=getchar())>='0' && c<='9') x=x*10+c-'0';
}
int main(){
	//freopen("1096.in","r",stdin);freopen("1096.out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++) read(fa[i].d),read(fa[i].p),read(fa[i].c);
	sort(fa+1,fa+n+1,cmp);
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+fa[i].p,cost[i]=cost[i-1]+sum[i-1]*(fa[i].d-fa[i-1].d);
	for(int i=1;i<=n;i++){
		while(l<r && slop(q[l],q[l+1])<fa[i].d) l++;
		int j=q[l];
		f[i]=f[j]+cost[i]-cost[j]-sum[j]*(fa[i].d-fa[j].d)+fa[i].c;
		while(l<r && slop(q[r-1],q[r])>slop(q[r],i)) r--;
		q[++r]=i;
	}
	printf("%lld",f[n]);
	return 0;
}