开始做POI啦...

库

为了效率搞了这么一个库:

现在版本号1.14(一月十四日更新版本囧..)

http://pan.baidu.com/s/1c0SoGfu [source]

http://pan.baidu.com/s/1c0UqCXq [precompiled]

版权之类就随他去吧..WTFPL..

用法:释放在include文件目录里就可以使用#include <poi.h>啦..!(当然对于lemon、cena之类也适用)

或者如果不要求评测..可以用#include "poi.h"

因为现在做了前几题渐渐POI库大了起来...应该不久就会比较完善啦..

效率

实战证明了它的效率(大雾

由于沙茶zball只会卡常数,那么这个库的效率可以参考这张图:

大囧..

POI2007 atr

一句话题意

一张无向图,从第1个点出发到第n个点,其中第2到k+1个点必须经过而且要满足一些形如a要在b之前访问过的条件,求最短路.

题解

最短路+状压DP.

代码

#define frenable

#include <poi.h>

using namespace POI;

#define maxn 20010

#define maxm 400010

int n,m;

graphw<maxn,maxm> gr;

#define maxk 22

int k;

int dis[maxk][maxn];

inline void read_graph(){

	rdu(n),rdu(m),rdu(k);

	int a,b,c;

	fet(i,1,m){

		rdu(a),rdu(b),rdu(c);

		gr.addedge(a,b,c);

		gr.addedge(b,a,c);

	}

}

inline void disgen(){

	fet(i,1,k+1) gr.dijkstra(i,dis[i]);

#ifdef debug

	fet(i,1,k+1){

		fet(j,1,n){

			pru(dis[i][j]);putc(' ');

		}

		putc('\n');

	}

#endif

}

int relation[maxk],relat;

inline void read_relation(){

	rdu(relat);

	int u,v;

	fet(i,1,relat){

		rdu(u),rdu(v);

		relation[v]|=1<<(u-2);

	}

}

int f[1<<20][maxk],vx;

inline void dp(){

	fet(now,0,vx)

	 fet(x,1,k+1)

	  if(~f[now][x])

		fet(i,2,k+1){

			int toState=now|(1<<i-2);

			int dist=f[now][x]+dis[x][i];

			if((now & relation[i])==relation[i])

			 if(f[toState][i]==-1 || f[toState][i]>dist) f[toState][i]=dist;

		}

}

int main(){

	read_graph();

	disgen();

	read_relation();

	memset(f,-1,sizeof(f));

	f[0][1]=0;

	vx=(1<<k)-1;

	dp();

	int ans=0x3f3f3f3f;

	fet(i,1,k+1) if(~f[vx][i]) tensen(ans,f[vx][i]+dis[i][n]);

	printf("%d\n",ans);

	return 0;

}

提醒:这个代码在我的电脑上是可以过的,在lydsy上是过不了的..原因很显然..

POI2007 biu

一句话题意

给出一张图,求它补图的连通块个数.

题解

(因为现在还在做Stage I所以都比较简单吧)

维护一个"当前访问不到"链表,在补图中访问到某个点就删去,然后BFS.

代码

#define frenable

#include <POI.h>

using namespace POI;

#define maxn 100010

#define maxm 4000010

graph<maxn,maxm> gr;

int n,m,k;

int grk[maxn],grl;

#define ll llp

struct llx{

	int lab,l,r;

} ll[maxn];

inline void del(int x){

	ll[ll[x].l].r=ll[x].r;

	ll[ll[x].r].l=ll[x].l;

}

inline int bfs(int f){

	static int queue[maxn],h,t;

	h=t=0;

	queue[t++]=f;

	del(f);

	while(h-t){

		int v=queue[h++];

		for(edge*i=gr.h[v];i;i=i->nxt){

			ll[i->to].lab=1;

		}

		for(int i=ll[0].r;i<=n;i=ll[i].r){

			if(ll[i].lab) ll[i].lab=0;

			else{

				del(i);

				queue[t++]=i;

			}

		}

	}

	return t;

}

int main(){

	rdu(n),rdu(m);

	int a,b;

	fet(i,1,m) rdu(a),rdu(b),gr.addedge(a,b),gr.addedge(b,a);

	fet(i,1,n){

		ll[i].l=i-1;

		ll[i].r=i+1;

	}

	for(int i=1;i<=n;i=ll[0].r) grk[grl++]=bfs(i);

	std::sort(grk,grk+grl);

	pru(grl); putc('\n');

	fet(i,0,grl-1) pru(grk[i]),putc(' ');

	putc('\n',1);

	return 0;

}

POI2007 osi

一句话题意

给你一个多边形,判断它有几条对称轴.

题解

我感觉这个转化思路还是比较有意思的. 将多边形砍断,拉成边和角交互的数组,那么两个一样的数组对应的多边形是相同的,将它的循环串求回文子串,若长度大于n就有一条对称轴了.

将多边形砍断这一部分我觉得挺有用的,就放在POI库里了.

代码

#define frenable

#include <poi.h>

using namespace POI;

polygon<ll,200010> pt;

ll sym[800010],sym2[1600010];

int dist3[1600010];

int main(){

	int n,t,ocr,m;

	rdu(t);

	while(t--){

		pt.clear();

		rdu(n);

		fet(i,1,n) rdi(ocr),rdi(m),pt.push_point(point<ll>(ll(ocr),ll(m)));

		ocr=pt.flatten_symmetric(sym);

		ocr=Manacher_init(sym,sym2,maxll,-maxll-1,ocr);

		Manacher(sym2,dist3,ocr);

		int ans=0;

		fot(i,0,ocr) if(dist3[i]>2*n-1) ++ans;

		printf("%d\n",ans/2);

	}

	return 0;

}

巴特西

开始做POI啦...

库

效率

POI2007 atr

一句话题意

题解

代码

POI2007 biu

一句话题意

题解

代码

POI2007 osi

一句话题意

题解

代码

最新文章

热门文章