4
1
2016
0

[坑]POI补完计划#1

跟着金主席的步伐,一步两步,一步两步,一步两步似poi~

嘿嘿嘿, 看着 金主席做$poi$,然后看了看我以前做过的$poi$,想想把能做的做完好辣

现在做了 几道:   19/20

$4.6$ $qiancl:$一半辣一半辣

$4.7$ $qiancl:$拿了一血好开心啊


$2938: [Poi2000]病毒$
询问是否无限就应该先想到有没有合法的环,先构出$AC$自动机,再把$fail$建好,然后就$dfs$找一不经过病毒环,有就有解

#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define N 30030
int i,j,k,m,l,r,n,x,y,cnt,f;char s[N];bool vis[N],mrk[N];
struct node{node*ch[2],*f;int ed;}C[N],*c=C,Null,*null=&Null,*q[N];
inline void insert(char*s){node*o=C;for(o->f=C;*s;o=o->ch[*s-48],o->f=C,++s)if(o->ch[*s-48]==NULL)o->ch[*s-48]=++c;o->ed=1;}
inline void build(){
	node*o=C;
	for(l=1,i=0;i<=1;++i)if(o->ch[i]!=NULL)q[++r]=o->ch[i];
	while(l<=r){
		node*x=q[l++];
		for(i=0;i<2;++i)if(x->ch[i]==NULL)x->ch[i]=x->f->ch[i];
		else x->ch[i]->f=x->f->ch[i],x->ch[i]->ed|=x->f->ch[i]->ed,q[++r]=x->ch[i];
	}
}
void dfs(node*o){
	if(f)return;if(o!=C)vis[o-C]=1;
	for(int i=0;i<2;++i){
		node*x=o->ch[i];if(vis[x-C]){f=1;return;}
		if(mrk[x-C]||x->ed)continue;
		mrk[x-C]=1,dfs(x);
	}
	vis[o-C]=0;
}
int main(){
	for(scanf("%d",&n),i=1;i<=n;++i)scanf("%s",s),insert(s);
	(build(),dfs(C),f)?puts("TAK"):puts("NIE");
}

$3053: The Closest M Points$

$KDtree$模板题,不能$1A$就会显得有些奇怪,别问我为什么不释放空间,你应该出门右转找金主席,比我写的短到不知道哪里去了

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0,f=1;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc());
	if(ch=='-')f=-1,ch=nc();for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x*f;
}
#define N 100010
const int oo=1<<29;
int i,j,k,m,n,f,x,y,t,cnt,z;
struct poi{int p[5];}P,a[N],ans[N];
priority_queue<poi>q;
inline void Mx(int&a,int b){if(b>a)a=b;}
inline void Mn(int&a,int b){if(b<a)a=b;}
inline double dist(const poi&a,const poi&b){double ret=0;for(int i=0;i<k;++i)ret+=(a.p[i]-b.p[i])*(a.p[i]-b.p[i]);return ret;}
struct kd{
	kd*ch[2];int mx[5],mn[5];poi p;
	inline void up(){for(int i=0,j;i<k;++i)for(mx[i]=mn[i]=p.p[i],j=0;j<2;++j)if(ch[j]!=NULL)Mx(mx[i],ch[j]->mx[i]),Mn(mn[i],ch[j]->mn[i]);}
	inline double dis(const poi&x){
		double ret=0.;
		for(int i=0;i<k;++i)if(x.p[i]<mn[i])ret+=(x.p[i]-mn[i])*(x.p[i]-mn[i]);
		else if(x.p[i]>mx[i])ret+=(x.p[i]-mx[i])*(x.p[i]-mx[i]);
		return ret;
	}
}C[N<<4],*c=C;
inline bool cmp(const poi&a,const poi&b){return a.p[f]<b.p[f];}
inline bool operator<(const poi&a,const poi&b){return dist(a,P)<dist(b,P);}
void build(kd**o,int l,int r,int flg){
	if(l>r)return;*o=c++;
	if(l==r){(*o)->p=a[l];for(int i=0;i<k;++i)(*o)->mx[i]=(*o)->mn[i]=a[l].p[i];return;}
	int m=l+r>>1;f=flg,nth_element(a+l,a+m,a+r+1,cmp),(*o)->p=a[m];
	build(&(*o)->ch[0],l,m-1,(flg+1)%k),build(&(*o)->ch[1],m+1,r,(flg+1)%k),(*o)->up();
}
void ask(kd*o){
	double ds=dist(o->p,P),Ds[2]={oo,oo};
	if(q.size()<m)q.push(o->p);else if(dist(q.top(),P)>ds)q.pop(),q.push(o->p);
	for(int i=0;i<2;++i)if(o->ch[i]!=NULL)Ds[i]=o->ch[i]->dis(P);
	bool fl=Ds[0]>Ds[1];
	if((q.size()<m||Ds[fl]<dist(q.top(),P))&&o->ch[fl]!=NULL)ask(o->ch[fl]);fl^=1;
	if((q.size()<m||Ds[fl]<dist(q.top(),P))&&o->ch[fl]!=NULL)ask(o->ch[fl]);
}
int main(){
	while(~scanf("%d%d",&n,&k)){
		for(i=1;i<=n;++i)for(j=0;j<k;++j)a[i].p[j]=read();
		kd*root;for(build(&root,1,n,0),t=read(),i=1;i<=t;++i){
			for(j=0;j<k;++j)P.p[j]=read();
			for(m=read();!q.empty();)q.pop();
			for(ask(root),cnt=0;!q.empty();ans[++cnt]=q.top(),q.pop());
			printf("the closest %d points are:\n",m);
			for(j=cnt;j>=1;--j)for(z=0;z<k;++z)printf("%d%c",ans[j].p[z],z==k-1?'\n':' ');
		}
	}
}

出了点小差错...这题不是$poi$的题_(:зゝ∠)_,是我搜$poi$搜到的..不用在意这些细节辣


$2066: [Poi2004]Gra$

谁都不想移到$m$-$1$,也就是移到$m-1$是必败的,把连续有棋子的格子当做石子,连续的空格数-$1$就是空位的个数,转化成阶梯博弈,然后就可以上$nim$了!奇数位异或起来为$c$,如果$c$=$0$就表示先手必败(以$m$-$1$做终点)

获胜的方案数,对于奇数位异或上$c$小于这一位,就是可行的;

偶数位$(c$ $xor$ $nim[i-1])>nim[i-1]$ $and$ $(nim[i-1]$ $xor$ $c)<=nim[i]+nim[i-1]$那就是可行的

我不知道发生了什么,运行速度似乎出了一点偏差

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 1000010
int i,j,k,m,n,lc[N],ans,l,nim[N],c;
int main(){
	for(m=read(),n=read(),i=1;i<=n;++i)lc[i]=read();
	if(lc[n]==m-1){for(i=n;i>1&&lc[i]-lc[i-1]==1;--i)++ans;return printf("%d\n",ans+1),0;}
	for(lc[n+1]=m-1,i=n;i>=1;--i)if(lc[i+1]-lc[i]==1)++nim[l];
	else if(lc[i+1]-lc[i]==2)nim[++l]=1;else if((lc[i+1]-lc[i]-1)&1)nim[l+=3]=1;else nim[l+=2]=1;
	for(i=1;i<=l;i+=2)c^=nim[i];
	if(!c)return puts("0"),0;
	else{
		for(i=1;i<=l;i+=2)if((c^nim[i])<nim[i])++ans;
		for(i=2;i<=l;i+=2)if((c^nim[i-1])>nim[i-1]&&(nim[i-1]^c)<=nim[i]+nim[i-1])++ans;
	}
	printf("%d\n",ans);
}

$2216: [Poi2011]Lightning Conductor$

$f_{i}=max(a_{j}+\sqrt{\left | i-j \right |})-a_{i}$,然后因为单调吓几拔搞一下就行了

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 500050
int i,j,k,m,n,x,y,t,a[N],l,r;double f[N],g[N];
struct node{int id,l,r;}q[N];
inline double dis(int x,int y){return a[y]+sqrt(abs(x-y));}
inline int ef(int l,int r,int x,int y){for(int m;l<r;m=l+r>>1,(dis(m,x)<dis(m,y)?l=m+1:r=m));return l;}
inline void Dp(double*o){
	for(l=1,r=0,i=1;i<=n;++i){
		if(l<=r&&++q[l].l>q[l].r)++l;
		if(l>r||dis(n,i)>dis(n,q[r].id)){
			while(l<=r&&dis(q[r].l,i)>dis(q[r].l,q[r].id))--r;
			if(l>r)q[++r]=(node){i,i,n};
			else q[r].r=(t=ef(q[r].l,q[r].r,i,q[r].id))-1,q[++r]=(node){i,t,n};
		}
		*(o+i)=dis(i,q[l].id);
	}
}
int main(){
	for(n=read(),i=1;i<=n;++i)a[i]=read();
	Dp(f),reverse(a+1,a+n+1),Dp(g),reverse(a+1,a+n+1),reverse(g+1,g+n+1);
	for(i=1;i<=n;++i)printf("%d\n",(int)ceil(max(f[i],g[i])-a[i]));
}

$2095: [Poi2010]Bridges$

二分是很明显的,但是怎么判二分后构出的图存不存在欧拉回路呢。。首先随便定向无向边,如果出入度的差是奇数,那显然不存在,建一个源$s$,对于出大于入的点,$s$向这个点连容量为出入度差除以二的边,建出汇$t$就反一反,剩下的图里把有向边省去,无向边就按定向的连,看是不是满流就行了,嘛比较显然

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 100010
const int oo=1<<30;
int i,j,k,m,n,x,y,S,T,cnt=1,sum,l=oo,p[N],flow,d[N],r=-oo,last[N],in[N],ot[N],ans;
struct edge{int to,next,s;}e[N];
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
struct bridge{
	int a,b,c,d;
	inline void in(){
		a=read(),b=read(),c=read(),d=read();
		if(c>d)swap(c,d),swap(a,b);l=min(l,c),r=max(r,d);
	}
}q[N<<1];
inline void add(int u,int v,int w){
	e[++cnt]=(edge){v,last[u],w},last[u]=cnt;
	e[++cnt]=(edge){u,last[v],0},last[v]=cnt;
}
inline bool build(){
	for(int i=1;i<=T;++i)d[i]=-1;
	p[1]=S,d[S]=0;
	for(int x,y,l=1,r=1;l<=r;){
		x=p[l++];
		for(int i=last[x];i;i=e[i].next)if(e[i].s&&d[y=e[i].to]==-1){
			d[y]=d[x]+1,p[++r]=y;if(y==T)return 1;
		}
	}return 0;
}
int find(int now,int flow){
	int ret,y,w=0;
	if(now==T)return flow;
	for(int i=last[now];i&&w<flow;i=e[i].next)
		if(e[i].s&&d[y=e[i].to]==d[now]+1&&(ret=find(y,min(flow-w,e[i].s))))e[i].s-=ret,e[i^1].s+=ret,w+=ret;
	if(!w)d[now]=-1;return w;
}
inline bool check(int x){
	for(memset(last,0,sizeof last),i=1;i<=n;++i)in[i]=ot[i]=0;
	for(cnt=1,S=n+1,T=S+1,i=1;i<=m;++i){
		if(q[i].c<=x)++ot[q[i].a],++in[q[i].b];
		if(q[i].d<=x)add(q[i].b,q[i].a,1);
	}
	for(i=1;i<=n;++i)if(abs(in[i]-ot[i])&1)return 0;
	for(sum=ans=0,i=1;i<=n;++i){
		y=in[i]-ot[i],sum+=y>0?y>>1:0;
		if(y>0)add(S,i,y>>1);if(y<0)add(i,T,(-y)>>1);
	}
	while(build())while(1){flow=find(S,oo);if(!flow)break;ans+=flow;}
	return sum==ans;
}
int main(){
	for(n=read(),m=read(),i=1;i<=m;++i)q[i].in();
	for(int mid;l<=r;check(mid=l+r>>1)?r=mid-1:l=mid+1);
	if(!check(l))puts("NIE");else printf("%d\n",l);
}

$1100: [POI2007]对称轴osi$

因为 是对称轴。。 复制一份_(:зゝ∠)_找回文串。。然后就没了_(:зゝ∠)_,什么$kmp$,好高深啊。。一时冲动刷了rank

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int f=1,x=0;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc());
	if(ch=='-')ch=nc(),f=-1;for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x*f;
}
#define N 400400
const int oo=1<<30;int i,j,k,m,n,x,y,f[N],T,o,mx,ans;
struct point{int x,y;}p[N];struct sgl{double p,x;}c[N];
inline point operator-(const point&a,const point&b){return(point){a.x-b.x,a.y-b.y};}
inline bool operator==(const sgl&a,const sgl&b){return(fabs(a.p-b.p)<1e-8)&&(fabs(a.x-b.x)<1e-8);}
inline double poix(const point&a,const point&b){return a.x*b.x+a.y*b.y;}
inline double Xx(const point&a,const point&b){return a.x*b.y-a.y*b.x;}
int main(){
	for(T=read();T--;){
		for(ans=0,memset(f,0,sizeof f),memset(c,0,sizeof c),n=read(),i=1;i<=n;++i)p[i].x=read(),p[i].y=read();
		for(p[0]=p[n],p[n+1]=p[1],c[0].p=c[0].x=oo,i=1;i<=n;++i){
			c[(i<<1)-1].p=poix(p[i-1]-p[i],p[i+1]-p[i]);
			c[(i<<1)-1].x=Xx(p[i-1]-p[i],p[i+1]-p[i]),c[(i<<1)-1+(n<<1)]=c[(i<<1)-1];
		}
		for(f[1]=o=mx=i=1,m=(n<<2)-1;i<=m;++i){
			for(mx>i?f[i]=min(f[(o<<1)-i],mx-i):f[i]=1;c[i+f[i]]==c[i-f[i]];++f[i]);
			if(f[i]+i>mx)mx=f[i]+i,o=i;
		}
		for(i=n+1;i<=n*3;++i)if(f[i]>=n-(!(n&1)))++ans;
		printf("%d\n",ans>>1);		
	}
}

$1104: [POI2007]洪水pow$

辣鸡题目毁我青春

一定是建在城市里,一定从低往高造,直接$bfs$就行了,我$vector$一个$pop$写晚害我足足多调了半小时

#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int f=1,x=0;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc());
	if(ch=='-')f=-1,ch=nc();for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x*f;
}
#define N 1010
#define pb push_back
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int i,j,k,m,n,x,y,a[N][N],b[N][N],mx,ans;
struct node{int x,y;};vector<node>q1[N],q2[N];
#define max(a,b) ((a)>(b)?(a):(b))
inline void bfs(int x,int y){
	for(int i=0;i<4;++i){
		int xx=x+dx[i],yy=y+dy[i];
		if(xx<1||yy<1||xx>n||yy>m||b[xx][yy]!=-1)continue;
		b[xx][yy]=max(b[x][y],a[xx][yy]),q2[b[xx][yy]].pb((node){xx,yy});
	}
}
int main(){
	for(n=read(),m=read(),i=1;i<=n;++i)for(j=1;j<=m;++j)a[i][j]=read(),b[i][j]=-1,a[i][j]>0?(q1[a[i][j]].pb((node){i,j}),mx=max(mx,a[i][j])):(a[i][j]=-a[i][j]);
	for(i=1;i<=mx;++i)if(q2[i].size())x=q2[i].back().x,y=q2[i].back().y,q2[i].pop_back(),bfs(x,y),--i;
	else if(q1[i].size()){
		x=q1[i].back().x,y=q1[i].back().y,q1[i].pop_back();
		if(~b[x][y]){--i;continue;}
		++ans,b[x][y]=a[x][y],bfs(x,y),--i;
	}
	printf("%d\n",ans);
}

$2942: [Poi2000]同构$

金主席:没题面的题都能A

题面可以看这-->点这说明金主席很强

很显然可以得到级别是$n^2$的边,把边当做元素,排列$p_{i}$给出了$n^2$级别的等式$i->j=p_{i}->p_{j}$,然后把相同的缩掉剩下$k$条边,$Ans=2^k$

然而这样做是$n^2$的,需要优化,把$i$向$p_{i}$连边,连完后的图一定是由若干个环构成的,假设第$i$个环的大小为$l_{i}$,如果环的大小是偶数那显然就不合法了,否则

$K=\sum \frac{l_{i}}{2}+\sum gcd(l_{i},l_{j})(i<j)$

因为大小不同的环最多是$\sqrt{n}$级别的,所以复杂度是$O(n)$

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 10010
#define mo 1000
int i,j,k,m,n,x,y,cnt,fa[N],last[N],len[N],l,h[N],vis[N],now,p[N],ans;
struct edge{int to,next;}e[N];
inline void add(int u,int v){e[++cnt]=(edge){v,last[u]},last[u]=cnt;}
inline int dfs(int x,int d){vis[x]=1;for(int i=last[x],y;i;i=e[i].next)if(!vis[y=e[i].to])d+=dfs(y,1);return d;}
inline int power(int a,int b){int ret=1;for(;b;a=a*a%mo,b>>=1)if(b&1)ret=ret*a%mo;return ret;}
int main(){
	for(n=read(),i=1;i<=n;++i)x=read(),add(i,x),fa[x]=i;
	for(i=1;i<=n;++i)if(!vis[i])h[++l]=dfs(i,1);
	for(i=1;i<=l;++i)if(!(h[i]&1))return puts("0"),0;
	for(i=1;i<=l;++i)++len[h[i]],ans+=h[i]>>1;
	for(sort(h+1,h+l+1),p[m=1]=h[1],i=2;i<=l;++i)if(h[i]!=h[i-1])p[++m]=h[i];
	for(i=1;i<m;++i)for(j=i+1;j<=m;++j)ans+=__gcd(p[i],p[j])*len[p[i]]*len[p[j]];
	for(i=1;i<=m;++i)ans+=((len[p[i]])*(len[p[i]]-1)>>1)*p[i];
	printf("%d\n",power(2,ans));
}

$2936: [Poi1999]降 水$

考虑从低往高,找相同联通块周围最低那个,然后填满,不能填了就停下

复杂度$O(能过)$   其实是我不会算

#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 10010
#define pb push_back
int i,j,k,m,n,x,y,mp[110][110],ans,now,vis[110][110],mx,p;
struct node{int x,y;}q[N];vector<node>o,h[N];
const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
inline void bfs(int x,int y){
	int l=1,r=1;q[r]=(node){x,y},o.pb(q[r]),vis[x][y]=i,p=N;
	while(l<=r){
		int xx=q[l].x,yy=q[l++].y;
		for(int i=0;i<4;++i){
			int fx=xx+dx[i],fy=yy+dy[i];
			if(fx<0||fx>n+1||fy<0||fy>m+1)continue;
			if(vis[fx][fy]==::i)continue;
			if(mp[fx][fy]!=mp[x][y])p=min(p,mp[fx][fy]);else q[++r]=(node){fx,fy},o.pb(q[r]),vis[fx][fy]=::i;
		}
	}
	if(p>mp[x][y]){
		ans+=o.size()*(p-mp[x][y]);
		while(o.size()){
			int xx=o.back().x,yy=o.back().y;
			h[p].pb(o.back()),mp[xx][yy]=p,o.pop_back();
		}
	}else while(o.size())o.pop_back();
}
int main(){
	for(n=read(),m=read(),i=1;i<=n;++i)for(j=1;j<=m;++j)mp[i][j]=read(),mx=max(mp[i][j],mx),h[mp[i][j]].pb((node){i,j});
	for(i=1;i<=mx;++i)while(h[i].size()){
		x=h[i].back().x,y=h[i].back().y;h[i].pop_back();
		if(vis[x][y]==i)continue;bfs(x,y);
	}
	printf("%d\n",ans);
}

$2935: [Poi1999]原始生物$

波兰人这么喜欢出欧拉回路这让我有一些惊方

显然是连边,从前往后连有向边,然后问题就是最少加几条边形成一条欧拉路,考虑欧拉回路,减一可以得到欧拉路,形成欧拉回路的话就是入度$-$出度$/2$,但是原图不一定是连通的,所以还得加上原图里存在欧拉回路的联通块数量

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 1010
int i,j,k,m,n,x,y,fa[N],in[N],ot[N],ans,a[N];bool vis[N],mk[N],b[N];
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;	
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
	for(i=1;i<=1000;++i)fa[i]=i;
	for(n=read(),i=1;i<=n;++i){
		x=read(),y=read(),++ot[x],++in[y],mk[x]=mk[y]=1;
		int p=find(x),q=find(y);if(p!=q)fa[q]=p;
	}
	for(i=1;i<=1000;++i)if(mk[i])a[++k]=i,fa[i]=find(fa[i]);
	for(i=1;i<=k;++i)if(in[fa[a[i]]]!=ot[fa[a[i]]])vis[fa[a[i]]]=1;
	for(i=1;i<=k;++i)if(!b[fa[a[i]]])if(!vis[fa[a[i]]])++m,b[fa[a[i]]]=1;
	for(i=1;i<=k;++i)ans+=abs(in[a[i]]-ot[a[i]]);
	printf("%d\n",(ans>>1)+m+n);
}

$2934: [Poi1999]祭坛问题$

为什么这题没人去做,难道是懒的写吗?

要我说,题解就两个字:硬上

对于每个矩形,其他矩形都贡献了一个小小的扇形角度,求个并看看是否覆盖完全就行了

代码越写越长

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}inline void read(char&c){for(c=nc();c==' '||c=='\n';c=nc());}
#define N 1010
#define pi M_PI
#define eps 0
int i,j,k,m,n,x,y,cnt,Flag=1;char ch;double mx,now;
struct Poi{double x,y;inline void in(){x=read(),y=read();}}h[N],no;
inline double dis(const Poi&a,const Poi&b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
inline Poi midpoi(const Poi&a,const Poi&b){return(Poi){(a.x+b.x)/2,(a.y+b.y)/2};}
struct ju{
	Poi a,b,c,d,o,p,L,R;int f;double l,r;
	inline double mklen(){
		if(f==1)return p=midpoi(b,d),dis(b,d)/2;
		if(f==2)return p=midpoi(a,c),dis(a,c)/2;
		if(f==3)return p=midpoi(c,d),dis(c,d)/2;
		return p=midpoi(a,b),dis(a,b)/2;
	}
	inline void get(){
		double len=mklen()/2;o=midpoi(a,d);
		if(f==1){
			L.x=p.x,L.y=p.y+len,l=atan2(L.x-o.x,L.y-o.y)*180/pi;
			R.x=p.x,R.y=p.y-len,r=atan2(R.x-o.x,R.y-o.y)*180/pi;
		}
		if(f==2){
			L.x=p.x,L.y=p.y-len,l=atan2(L.x-o.x,L.y-o.y)*180/pi;
			R.x=p.x,R.y=p.y+len,r=atan2(R.x-o.x,R.y-o.y)*180/pi;
		}
		if(f==3){
			L.x=p.x+len,L.y=p.y,l=atan2(L.x-o.x,L.y-o.y)*180/pi;
			R.x=p.x-len,R.y=p.y,r=atan2(R.x-o.x,R.y-o.y)*180/pi;
		}
		if(f==4){
			L.x=p.x-len,L.y=p.y,l=atan2(L.x-o.x,L.y-o.y)*180/pi;
			R.x=p.x+len,R.y=p.y,r=atan2(R.x-o.x,R.y-o.y)*180/pi;
		}
	}
}M[N];
inline int path(char c){
	if(c=='E')return 1;if(c=='W')return 2;
	if(c=='S')return 3;if(c=='N')return 4;
}
inline double disx(const Poi&a,const Poi&b){return a.x-b.x;}
inline double disy(const Poi&a,const Poi&b){return a.y-b.y;}
inline Poi interval(const ju&o,const ju&p){
	double v[4]={atan2(disx(p.a,o.o),disy(p.a,o.o))*180/pi,
		atan2(disx(p.b,o.o),disy(p.b,o.o))*180/pi,
		atan2(disx(p.c,o.o),disy(p.c,o.o))*180/pi,
		atan2(disx(p.d,o.o),disy(p.d,o.o))*180/pi
	};
	int tot=0;
	if(o.f==1){
		for(int i=0;i<4;++i)if(v[i]>0)++tot;
		if(!tot)return(Poi){-181,-181};
		for(int i=0;i<4;++i)if(v[i]>=-90+eps&&v[i]<0)v[i]=0;
		else if(v[i]<=-90-eps)v[i]=180;
		return sort(v,v+4),(Poi){v[0],v[3]};
	}
	if(o.f==2){
		for(int i=0;i<4;++i)if(v[i]<0)++tot;
		if(!tot)return(Poi){-181,-181};
		for(int i=0;i<4;++i)if(v[i]<90-eps&&v[i]>0)v[i]=0;
		else if(v[i]>90+eps)v[i]=-180;
		return sort(v,v+4),(Poi){v[0],v[3]};
	}
	if(o.f==3){
		for(int i=0;i<4;++i)if(v[i]>90+eps||v[i]<-90-eps)++tot;
		if(!tot)return(Poi){-181,-181};
		for(int i=0;i<4;++i)if(v[i]>-90+eps&&v[i]<0-eps)v[i]=-90;
		else if(v[i]>0+eps&&v[i]<90-eps)v[i]=90;
		double zz[5],ff[5];int l=0,r=0;
		for(int i=0;i<4;++i)if(fabs(v[i])==v[i])zz[++l]=v[i];else ff[++r]=v[i];
		sort(zz+1,zz+l+1),sort(ff+1,ff+r+1);
		if(l&&r)return(Poi){zz[1],ff[r]};
		else if(l)return(Poi){zz[1],zz[l]};
		else if(r)return(Poi){ff[1],ff[r]};
	}
	if(o.f==4){
		for(int i=0;i<4;++i)if(v[i]>-90+eps&&v[i]<90-eps)++tot;
		if(!tot)return(Poi){-181,-181};
		for(int i=0;i<4;++i)if(v[i]<-90-eps)v[i]=-90;
		else if(v[i]>90+eps)v[i]=90;
		double zz[5],ff[5];int l=0,r=0;
		for(int i=0;i<4;++i)if(fabs(v[i])==v[i])zz[++l]=v[i];else ff[++r]=v[i];
		sort(zz+1,zz+l+1),sort(ff+1,ff+r+1);
		if(l&&r)return(Poi){ff[1],zz[l]};
		else if(l)return(Poi){zz[1],zz[l]};
		else if(r)return(Poi){ff[1],ff[r]};
	}
}
inline bool cmp1(const Poi&a,const Poi&b){if(fabs(a.x-b.x)<eps)return a.y<b.y;return a.x<b.x;}
inline void jover(double&x){
	if(fabs(x)==x)x=x-90;
	else x=180-(fabs(x-90)-180);
}
inline void rover(double&x){x+=90;}
int main(){
	for(n=read(),i=1;i<=n;++i){
		M[i].a.in(),M[i].d.in();
		M[i].b.x=M[i].d.x,M[i].b.y=M[i].a.y;
		M[i].c.x=M[i].a.x,M[i].c.y=M[i].d.y;
		read(ch),M[i].f=path(ch),M[i].get();
	}
	for(i=1;i<=n;++i){
		for(cnt=0,mx=now=-181,j=1;j<=n;++j)if(i!=j){
			no=interval(M[i],M[j]);
			if(no.x==-181||no.y==-181)continue;
			if(M[i].f==1||M[i].f==2)if(no.x<=M[i].r+eps&&no.y>=M[i].l-eps)h[++cnt]=no;
			if(M[i].f==3)if((no.y>=M[i].l-eps||no.y<=-90+eps)&&(no.x<=M[i].r+eps||no.x>=90-eps))h[++cnt]=no;
			if(M[i].f==4)if((no.x<=M[i].r+eps&&no.x>=-90-eps)&&(no.y>=M[i].l-eps&&no.y<=90+eps))h[++cnt]=no;
		}
		if(M[i].f==1||M[i].f==2){
			sort(h+1,h+cnt+1,cmp1);bool flg=1;
			if(h[1].x>M[i].l+eps)flg=0;
			for(j=1;j<=cnt;++j)mx=max(mx,h[j].y);
			if(mx<M[i].r-eps)flg=0;
			for(now=h[1].y,j=2;j<=cnt&&flg;++j)if(h[j].x>now-eps)flg=0;else now=max(now,h[j].y);
			if(!flg)printf("%d\n",i),Flag=0;
		}
		if(M[i].f==3){
			bool flg=1;for(j=1;j<=cnt;++j)jover(h[j].x),jover(h[j].y);
			jover(M[i].l),jover(M[i].r),sort(h+1,h+cnt+1,cmp1);
			if(h[1].x>M[i].l+eps)flg=0;
			for(j=1;j<=cnt;++j)mx=max(mx,h[j].y);
			if(mx<M[i].r-eps)flg=0;
			for(now=h[1].y,j=2;j<=cnt&&flg;++j)if(h[j].x>now-eps)flg=0;else now=max(now,h[j].y);
			if(!flg)printf("%d\n",i),Flag=0;
		}
		if(M[i].f==4){
			bool flg=1;for(j=1;j<=cnt;++j)rover(h[j].x),rover(h[j].y);
			rover(M[i].l),rover(M[i].r),sort(h+1,h+cnt+1,cmp1);
			if(h[1].x>M[i].l+eps)flg=0;
			for(j=1;j<=cnt;++j)mx=max(mx,h[j].y);
			if(mx<M[i].r-eps)flg=0;
			for(now=h[1].y,j=2;j<=cnt&&flg;++j)if(h[j].x>now-eps)flg=0;else now=max(now,h[j].y);
			if(!flg)printf("%d\n",i),Flag=0;
		}
	}
	if(Flag)puts("BRAK");
}

$2932: [Poi1999]树的染色问题$

先$dfs$构树,然后就是一个裸的树形$DP$

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){char ch=nc();for(;ch==' '||ch=='\n';ch=nc());return ch-48;}
#define N 10010
int i,j,k,m,n,x,y,cnt,last[N],tot,du[N],f[N][4],z[N][4];
struct edge{int to,next;}e[N];
inline void add(int u,int v){e[++cnt]=(edge){v,last[u]},last[u]=cnt;}
void dfsbuild(int x){
	if(du[x]==1)add(x,++tot),du[tot]=read(),dfsbuild(tot);
	if(du[x]==2)add(x,++tot),du[tot]=read(),dfsbuild(tot),add(x,++tot),du[tot]=read(),dfsbuild(tot);
}
#define oo 0x7f7f7f7f
void Dp(int x){
	f[x][1]=f[x][3]=z[x][1]=z[x][3]=0,f[x][2]=z[x][2]=1;
	for(int i=last[x];i;i=e[i].next)Dp(e[i].to);
	if(du[x]==1){
		int v=e[last[x]].to,mx=0,mn=oo;
		for(int i=1;i<=3;++i){
			mx=0,mn=0x7f7f7f7f;
			for(int j=1;j<=3;++j)if(i!=j)mn=min(mn,z[v][j]),mx=max(f[v][j],mx);
			f[x][i]+=mx,z[x][i]+=mn;
		}
	}
	if(du[x]==2){
		int son[3]={0,0,0},g[4]={0,0,0,0},h[4]={oo,oo,oo,oo};
		for(int i=last[x];i;i=e[i].next)son[++*son]=e[i].to;
		for(int i=1;i<=3;++i)for(int j=1;j<=3;++j)
			if(i!=j)g[6-i-j]=max(g[6-i-j],f[son[1]][i]+f[son[2]][j]),h[6-i-j]=min(h[6-i-j],z[son[1]][i]+z[son[2]][j]);
		for(int i=1;i<=3;++i)f[x][i]+=g[i],z[x][i]+=h[i];
	}
}
int main(){
	du[1]=read(),dfsbuild(++tot),Dp(1),printf("%d %d\n",max(max(f[1][3],f[1][1]),f[1][2]),min(min(z[1][3],z[1][2]),z[1][1]));
}

$2927: [Poi1999]多边形之战$

首先 如果$n$是偶数那先手是必胜的,为什么呢,设和黑色三角相邻的三角形个数有$k$个,那么当$k=1||abs(n-k-3-k)mod$ $2$先手是必胜的,即$n$为偶数

#include<cstdio>
int i,j,n,tot,a,b,c,x,y,z,cnt;
int main(){
	for(scanf("%d%d%d%d",&n,&a,&b,&c),i=2;i<n-1;++i){
		tot=0,scanf("%d%d%d",&x,&y,&z);
		if(x==a||x==b||x==c)++tot;
		if(y==a||y==b||y==c)++tot;
		if(z==a||z==b||z==c)++tot;
		if(tot>=2)++cnt;if(cnt>1)break;
	}
	if(!(n&1)||(cnt==1))puts("TAK");else puts("NIE");
}

$2574: [Poi1999]Store-Keeper$

这道题十分有趣,我强烈推荐_(:зゝ∠)_

题目意思也就是传说中的推箱子,要求最小步数,最小步数问题显然就是$bfs$喽,$bfs$的状态显然存的是箱子的位置和人推的方向

但是存在一个问题,扩展的时候会改方向,但是并不知道人能不能走到那个要推方向的格子上,最简单的做法是再$bfs$一遍

然而时间复杂度是$O(n^4*4)$,显然是会$T$的

那有什么快速的办法来判连通性呢?

考虑双连通分量,如果箱子不在割点上,那么只要连通怎样都是能到的,如果箱子在割点上,那么只要通过判断是否在同个双连通分量上,就能得知连通性

在同个双联通分量上的话,箱子挡掉其中一条路,还是有另一条可以走的,于是就先把图中的割点和块都预处理出来就可以$O(1)$判连通辣!

感觉这题实在是很优美,有一些要注意的地方,就是割点是会被多个双联通分量包含的,所以要都记下来

过了之后我还发现了一些 有趣的东西:

$《推箱子游戏的一个箱子推动路径搜索算法》$

$《推箱子游戏的一个箱子推动路径搜索算法(二)》$

#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define N 110
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
char mp[N][N];int i,j,l,r,top,ans,Po[N][N],Now,stx,ex,now,ey,bx,by,sty,k,m,n,x,y,po[N][N],bcc,clock,pre[N][N];
bool cut[N][N],mk[N][N][4];vector<int>bl[N][N];
inline void add(int x,int y,int bcc){
	for(int i=0;i<bl[x][y].size();++i)if(bl[x][y][i]==bcc)return;
	bl[x][y].push_back(bcc);
}
struct edge{int x1,y1,x2,y2;}S[N*N];
struct node{int x,y,d;}q[N*N*4];
int dfs(int x,int y,int fx,int fy){
	int lw=pre[x][y]=++clock,cld=0;Po[x][y]=Now;
	for(int i=0;i<4;++i){
		int xx=x+dx[i],yy=y+dy[i];
		if(mp[xx][yy]=='S'||xx<1||xx>n||yy<1||yy>m||(xx==fx&&yy==fy))continue;
		edge e=(edge){x,y,xx,yy};
		if(!pre[xx][yy]){
			S[++top]=e,++cld;int lv=dfs(xx,yy,x,y);
			lw=min(lw,lv);
			if(lv>=pre[x][y]){
				cut[x][y]=1,++bcc;
				for(;;){
					edge o=S[top--];
					add(o.x1,o.y1,bcc),add(o.x2,o.y2,bcc);
					if(o.x1==x&&o.y1==y&&o.x2==xx&&o.y2==yy)break;
				}
			}
		}else if(pre[xx][yy]<pre[x][y])S[++top]=e,lw=min(lw,pre[xx][yy]);
	}
	if(fx<0&&fy<0&&cld==1)cut[x][y]=0;
	return lw;
}
void dfs1(int x,int y){
	po[x][y]=now;for(int i=0;i<4;++i){
		int xx=x+dx[i],yy=y+dy[i];
		if(po[xx][yy]||mp[xx][yy]=='S'||xx<1||xx>n||yy<1||yy>m||mp[xx][yy]=='P')continue;
		dfs1(xx,yy);
	}
}
int main(){
	for(scanf("%d%d",&n,&m),i=1;i<=n;++i)scanf("%s",mp[i]+1);
	for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(!pre[i][j]&&mp[i][j]!='S')++Now,dfs(i,j,-1,-1);
	for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(!po[i][j]&&mp[i][j]!='S'&&mp[i][j]!='P')++now,dfs1(i,j);
	for(i=1;i<=n;++i)for(j=1;j<=m;++j)
		if(mp[i][j]=='M')stx=i,sty=j;
		else if(mp[i][j]=='P')bx=i,by=j;
		else if(mp[i][j]=='K')ex=i,ey=j;
	for(l=1,i=0;i<4;++i)if(po[stx][sty]==po[bx+dx[i]][by+dy[i]])q[++r]=((node){bx,by,i}),mk[bx][by][i]=1;
	for(;l<=r;++ans){
		int k=r-l+1;
		for(j=1;j<=k;++j){
			int x=q[l].x,y=q[l].y,d=q[l++].d,xx,yy;
			if(x==ex&&y==ey)return printf("%d",ans),0;
			for(i=0;i<4;++i){
				if(cut[x][y]){
					bool flag=0;
					for(int p=0;p<bl[x+dx[i]][y+dy[i]].size()&&flag==0;++p)
						for(int q=0;q<bl[x+dx[d]][y+dy[d]].size()&&flag==0;++q)if(bl[x+dx[i]][y+dy[i]][p]==bl[x+dx[d]][y+dy[d]][q])flag=1;
					if(flag&&mp[xx=x-dx[i]][yy=y-dy[i]]!='S'&&xx>=1&&xx<=n&&yy>=1&&yy<=m)
						if(!mk[xx][yy][i])q[++r]=(node){xx,yy,i},mk[xx][yy][i]=1;
				}else if((!mk[xx=x-dx[i]][yy=y-dy[i]][i])&&(mp[xx][yy]!='S')&&xx>=1&&xx<=n&&yy>=1&&yy<=m&&Po[x+dx[i]][y+dy[i]]==Po[x+dx[d]][y+dy[d]])q[++r]=(node){xx,yy,i},mk[xx][yy][i]=1;
			}
		}
	}
	puts("NO");
}

$3749: [POI2015]Łasuchy$

就$4$种么,对于一碗菜,被左边次,被右边次,被同时次,不被次,然后就转移好辣

#include<bits/stdc++.h>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 1000010
int i,j,k,m,n,x,y,a[N],f[N][5],ans[N];
inline void work(int x){
	for(i=1;i<=n;++i)for(k=1;k<=4;++k)f[i][k]=0;
	for(f[1][x]=1,i=2;i<=n;++i){
		if(f[i-1][1]&&(a[i-1]<=(a[i]<<1)))f[i][1]=1;
		if(f[i-1][4]&&(a[i-1]<=a[i]))f[i][1]=4;
		if(f[i-1][2]&&((a[i-1]<<1)>=a[i]))f[i][2]=2;
		if(f[i-1][3]&&(a[i-1]>=a[i]))f[i][2]=3;
		if(f[i-1][1]&&(a[i-1]<=a[i]))f[i][3]=1;
		if(f[i-1][4]&&((a[i-1]<<1)<=a[i]))f[i][3]=4;
		if(f[i-1][2]&&(a[i-1]>=a[i]))f[i][4]=2;
		if(f[i-1][3]&&(a[i-1]>=(a[i]<<1)))f[i][4]=3;
	}
	if(f[n][x]==0)return;
	for(i=n;i>=1;--i){
		if(x==1)ans[i-1]=(i-1)%(n-1)+1;
		if(x==2)ans[i]=(i-1)%(n-1)+1;
		if(x==3)ans[i-1]=ans[i]=(i-1)%(n-1)+1;
		x=f[i][x];
	}
	for(--n,i=1;i<n;++i)printf("%d ",ans[i]);
	printf("%d\n",ans[n]),exit(0);
}
int main(){
	for(n=read(),i=1;i<=n;++i)a[i]=read();a[++n]=a[1];
	for(j=1;j<=4;++j)work(j);puts("NIE");
}

$1136: [POI2009]Arc$

这是一道思博题,但是没什么人$A$,为什么呢?因为是$bzoj$上的交互,真特么麻烦

#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#define nc() getchar()
inline int read(){
	int f=1,x=0;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc());
	if(ch=='-')f=-1,ch=nc();for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x*f;
}
#define MAGIC_BEGIN -435634223
#define MAGIC_END -324556462
#define MIN_K 1
#define MAX_K 1000000
#define MAX_N 15000000
#define MIN_A 1
#define MAX_A 1000000000
#define MIN_TYP 1
#define MAX_TYP 3
#define MIN_PAR 0
#define MAX_PAR 1000000000
#define ERROR 0
#define CORRECT 1
#define unlikely(x) __builtin_expect(!!(x), 0)
static int init = 0;
static int lib_n;
static int con_k;
static int N, K, A, TYP, PAR;
static int bre, len_sub, bou, is_end;
static int rand2_status = 198402041;
static inline int rand2(int a, int b){
  rand2_status = rand2_status * 1103515245 + 12345;
  int x = rand2_status;
  if (x < 0) x = -x;
  x >>= 1;
  x = a + x % (b - a + 1);
  return x;
}
static inline int random_test(){return rand2(1, A);}

static inline int decreasing_test(){
	int tmp;
	if(bre == 0) {
		bre = rand2(0, (N - lib_n + 1 - len_sub));
		tmp = A;
		A -= rand2(0, (A - 1) / len_sub);
		len_sub--;
	}
	else {
		bre--;
		tmp = rand2(1, A);
	}
	return tmp;
}

static inline int increasing_test()
{
	return bou - decreasing_test();
}

static void finish(int res, char *com)
{
	if(res == ERROR)
		printf("%s\n", com);
	exit(0);
}

int inicjuj()
{
	if(init == 1)
		finish(ERROR, "Program zawodnika moze wywolac funkcje inicjuj tylko raz!!!");
	init = 1;
	K=read();
	if (K > 0){
	  TYP = 0;
	  N = MAX_N + 2;
	  return K;
	}
	int magic_begin, magic_end;
	magic_begin=read(),TYP=read();
	if(magic_begin != MAGIC_BEGIN || TYP < MIN_TYP || TYP > MAX_TYP)
		finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!");
	N=read(),K=read(),A=read(),PAR=read();
	if(N < 1 || N > MAX_N || N < K || K > MAX_K || A < MIN_A || A > MAX_A 
		|| PAR < MIN_PAR || PAR > MAX_PAR)
		finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!");
	magic_end=read();
	if(magic_end != MAGIC_END)
		finish(ERROR, "Program zawodnika nie moze korzystac z stdin!!!");
	con_k = 0;
	lib_n = 0;
	is_end = 0;
	if(TYP == 2 || TYP == 3) {
		len_sub = PAR;
		bre = 0;
	}
	if(TYP == 2)
		bou = A--;
	return K;
}
int wczytaj(){
	if(unlikely(init == 0))
		finish(ERROR, "Program zawodnika nie wywolal funkcji inicjuj!!!");
	if(unlikely(lib_n > N || is_end == 1))
		finish(ERROR, "Program zawodnika wywolal funkcje wczytaj po otrzymaniu informacji o koncu ciagu!!!");
	if(unlikely(lib_n == N))
		return 0;
	lib_n++;
	switch (TYP) {
	  case 0:
		A=read();
		if(A == 0)
		  is_end = 1;
		return A;
		break;
	  case 1: return random_test(); break;
	  case 2: return increasing_test(); break;
	  case 3: return decreasing_test(); break;
	  default:
			  finish(ERROR, "Nieznany typ testu");
	}
	return -1;
}

void wypisz(int jakoscProjektu)
{
	if(init == 0)
		finish(ERROR, "Program zawodnika nie wywolal funkcji inicjuj!!!");
	printf("%d\n", jakoscProjektu);
	if(++con_k == K)
		finish(CORRECT, "");
}
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define N 15050000
int i,k,n,x,a[N];
struct queue{
	int h,r,q[N];
	void push(int x){
		while((r-h)>=1&&q[r]<x)--r;
		if((r-h)<k)q[++r]=x;
	}
	inline void pop(){q[++h]=0;}
	inline int front(){return q[h+1];}
}q;
int main(){
	k=inicjuj();
	for(n=0;n<k;++n)a[n]=wczytaj();
	for(--n;x=wczytaj(),x;)a[++n]=x,q.push(a[n-k]);
	for(i=k-1;~i;--i)q.push(a[n-i]),wypisz(q.front()),q.pop();
}

$1525: [POI2006]Zos$

一看到 独立集这种的,首先不就是想到随机吗,命中率很高啊

#include<bits/stdc++.h>
using namespace std;
#define N 1000010
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
int T,n,i,y,m,x,ans,k,q[N],t,lc[N],dl[N],cnt,last[N],s;
struct edge{int to,next;}e[N*6];
inline void add(int u,int v){
	e[++cnt]=(edge){v,last[u]},last[u]=cnt;
	e[++cnt]=(edge){u,last[v]},last[v]=cnt;
}
int main(){
	for(n=read(),k=read(),m=read();m--;)add(read(),read());
	for(T=n>=100000?1:20;T--;){
		for(s=0,t=n,i=1;i<=n;++i)q[i]=lc[i]=i,dl[i]=0;
		while(t){
			y=q[x=rand()%t+1],lc[q[x]=q[t--]]=x,++s;
			for(i=last[y];i;i=e[i].next)if(!dl[e[i].to])dl[e[i].to]=1,x=lc[e[i].to],lc[q[x]=q[t--]]=x;
		}
		ans=max(ans,s);
	}
	if(ans<k)puts("NIE");else printf("%d",ans);
}

$1133: [POI2009]Kon$

题面有歧义?$f_{i,j}$表示最后一次查到$i$与$i+1$,查了$j$次的最多人数,暴力转移即可

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 606
int K,i,j,k,m,n,x,y,f[N][N],p[N][N],ans[N],loc,sm[N][N];
int main(){
	for(n=read(),K=read(),i=1;i<n;++i)for(j=i+1;j<=n;++j)sm[i][j]=read()+sm[i][j-1];
	for(i=1;i<n;++i)for(j=1;j<=n;++j)sm[i][j]+=sm[i-1][j];
	for(memset(f,-1,sizeof f),f[0][0]=0,i=1;i<n;++i)for(j=1;j<=min(i,K);++j)for(k=0;k<i;++k){
		int ret=sm[i][n]-sm[i][i]-sm[k][n]+sm[k][i];
		if(f[i][j]<f[k][j-1]+ret)f[i][j]=f[k][j-1]+ret,p[i][j]=k;
	}
	for(i=1;i<n;++i)if(f[i][K]>f[loc][K])loc=i;
	for(i=K;i;--i)ans[i]=loc,loc=p[loc][i];
	for(i=1;i<K;++i)printf("%d ",ans[i]);printf("%d\n",ans[K]);
}

$1524: [POI2006]Pal$

$hash$+$tire$直接上好了。。然而跑的好慢,应该有其他做法

#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
#define S 100000
char bf[S],*p1=bf,*p2=bf;
#define nc() (p1==p2&&(p2=(p1=bf)+fread(bf,1,S,stdin),p2==p1)?0:*p1++)
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}inline void read(char&c){for(c=nc();c==' '||c=='\n';c=nc());}
#define N 2000020
#define uint unsigned int
#define ll long long
int i,j,k,m,n,x,y,len[N];string s[N];char ch[N];uint h,p[N],hs[N];ll ans;
struct tire{tire*go[26];int ct,id;}C[N],*c=C,*rt=C,*o;
inline void insert(){
	for(o=rt,j=0;j<len[i];++j){
		if(x=ch[j]-'a',!o->go[x])o->go[x]=++c;
		o=o->go[x],h=h*131+x+1;
	}++o->ct,hs[o->id=i]=h;
}
int main(){
	for(p[0]=1,i=1;i<N;++i)p[i]=p[i-1]*131;
	for(n=read(),i=1;i<=n;++i){
		for(len[i]=read(),j=0;j<len[i];++j)read(ch[j]),s[i].push_back(ch[j]);
		h=0,insert();
	}
	for(i=1;i<=n;++i)for(o=rt,j=0;j<len[i];++j){
		if(!o->go[s[i][j]-'a'])break;o=o->go[s[i][j]-'a'];
		if(o->ct&&hs[o->id]*p[len[i]]+hs[i]==hs[i]*p[len[o->id]]+hs[o->id])ans+=o->ct;
	}
	printf("%lld\n",(ans<<1)-n);
}

 

 

$updating...$


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com