4
21
2015
0

SDOI2015

你们啊,我感觉你们AHOI还要学习,你们非常熟悉NOIP的这一套难度。

你们毕竟TOO YOUNG,你明白我的意思吗?我告诉你们,我是身经百战了,见得多啊。NOIP的哪一个考试我没有做过?你们要知道强省的OI比你们不知要高到哪里去了,哎,我也被他们虐。

OI啊,还是要提高自己的知识水平,晓得不晓得啊?唉,我也替你们着急啊,真的。你们有一个好,NOIP跑到什么地方,比其他的强省OI跑得还快,但是问来问去的问题啊,都TOO SIMPLE,SOMETIMES NAIVE。懂了没有?懂不懂得?

SDOI比AHOI不知要高到哪里去了。

排序:

顺序无关,爆搜大法吼

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

typedef long long LL;

const int N=1<<12;

int w[N],n;

LL fac[N],Ans;

void Up(int x,int y,int t)
{
	while(t--)
		swap(w[x],w[y]),
		x++,y++;
}

void dfs(int Now,int s)
{
	if(Now==n)
	{
		Ans+=fac[s];
		return;
	}
	int num=0,pos[5]={};
	for(int i=0;i<(1<<n)&&num<=2;i+=1<<Now+1)
		if(w[i+(1<<Now)-1]+1!=w[i+(1<<Now)])
			pos[++num]=i;
	if(num>2)
		return;
	if(num==0)
		dfs(Now+1,s);
	else if(num==1)
	{
		int p=pos[1];
		if(w[p+(1<<Now+1)-1]+1==w[p])
			Up(p,p+(1<<Now),1<<Now),
			dfs(Now+1,s+1),
			Up(p,p+(1<<Now),1<<Now);
	}
	else
	{
		int p1=pos[1],p2=pos[2];
		if(w[p1+(1<<Now)-1]+1==w[p2+(1<<Now)]&&w[p2+(1<<Now)-1]+1==w[p1+(1<<Now)])
			Up(p1,p2,1<<Now),
			dfs(Now+1,s+1),
			Up(p1,p2,1<<Now),
			Up(p1+(1<<Now),p2+(1<<Now),1<<Now),
			dfs(Now+1,s+1),
			Up(p1+(1<<Now),p2+(1<<Now),1<<Now);
		if(w[p2+(1<<Now)-1]+1==w[p1]&&w[p2+(1<<Now+1)-1]+1==w[p1+(1<<Now)])
			Up(p1,p2+(1<<Now),1<<Now),
			dfs(Now+1,s+1),
			Up(p1,p2+(1<<Now),1<<Now);
		if(w[p1+(1<<Now)-1]+1==w[p2]&&w[p1+(1<<Now+1)-1]+1==w[p2+(1<<Now)])
			Up(p2,p1+(1<<Now),1<<Now),
			dfs(Now+1,s+1),
			Up(p2,p1+(1<<Now),1<<Now);
	}
}

int main()
{
	scanf("%d",&n);
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i;
	for(int i=0;i<1<<n;i++)
		scanf("%d",&w[i]);
	dfs(0,0);
	cout<<Ans<<endl;
	return 0;
}

寻宝游戏:

很像虚树啊,显然按dfs序跑是最优的= =set大法吼

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

set<int> T;

typedef set<int>::iterator Lzz;

typedef long long LL;

const int N=300005;

int pos[N],dfn[N],lg[N],Index,e[N],next[N],G[N],Len[N],tot,n,m;

LL Ans,dis[N],Min[N][20];

bool flag[N];

void adde(int u,int v,int l)
{
	e[++tot]=v;next[tot]=G[u];G[u]=tot;Len[tot]=l;
}

void dfs(int u,int p)
{
	pos[u]=++Index;
	dfn[Index]=u;
	Min[Index][0]=dis[u];
	for(int v,i=G[u];i;i=next[i])
		if((v=e[i])!=p)
			dis[v]=dis[u]+Len[i],
			dfs(v,u),
			Min[++Index][0]=dis[u];
}

void Prepare()
{
	for(int i=2;i<=Index;i++)
		lg[i]=lg[i>>1]+1;
	for(int j=1;j<=lg[Index];j++)
		for(int i=1;i+(1<<j)-1<=Index;i++)
			Min[i][j]=min(Min[i][j-1],Min[i+(1<<j-1)][j-1]);
}

LL dist(int u,int v)
{
	int x=pos[u],y=pos[v];
	if(x>y)
		swap(x,y);
	int l=lg[y-x+1];
	return dis[u]+dis[v]-2*min(Min[x][l],Min[y-(1<<l)+1][l]);
}

void Update(int u)
{
	flag[u]^=1;
	if(flag[u]==1)
	{
		if(T.size())
		{
			Lzz it=T.insert(pos[u]).first;
			Lzz A,B;
			if(it==T.begin())
				A=T.end(),A--;
			else
				A=it,A--;
			it++;
			if(it==T.end())
				B=T.begin();
			else
				B=it;
			Ans+=dist(u,dfn[*A])+dist(u,dfn[*B])-dist(dfn[*A],dfn[*B]);
		}
		else
			T.insert(pos[u]);
	}
	else
	{
		if(T.size()>1)
		{
			Lzz it=T.find(pos[u]);
			Lzz A,B;
			if(it==T.begin())
				A=T.end(),A--;
			else
				A=it,A--;
			it++;
			if(it==T.end())
				B=T.begin();
			else
				B=it;
			Ans-=dist(u,dfn[*A])+dist(u,dfn[*B])-dist(dfn[*A],dfn[*B]);
			T.erase(pos[u]);
		}
		else
			T.erase(pos[u]);
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,u,v,l;i<n;i++)
		scanf("%d%d%d",&u,&v,&l),
		adde(u,v,l),
		adde(v,u,l);
	dfs(1,0);
	Prepare();
	while(m--)
	{
		int u;
		scanf("%d",&u);
		Update(u);
		printf("%lld\n",Ans);
	}
	return 0;
}
  

序列统计:

原根= =想到原根之后就好办了= =NTT快速幂(模数太显眼了)

程序见http://wuzuofan.is-programmer.com/posts/88375.html NTT模板

星际战争:

二分+网络流判定。。。

程序见http://wuzuofan.is-programmer.com/posts/88375.html DINIC模板

约数和个数:

莫比乌斯反演。。。

程序见http://wuzuofan.is-programmer.com/posts/88375.html MobiusInversion模板

道路修建:

堵塞的交通即视感= =线段树乱搞。。。

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

const int N=100005;

int Li[N][2],Ro[N],n,m;

struct status
{
	int Max_Li,l,r,Len,lmax,rmax,lpos,rpos,Num;
	
	status(){}
	
	status(int pos)
	{
		l=r=lpos=rpos=pos;
		lmax=rmax=Len=Ro[pos];
		Max_Li=0;
		Num=1;
	}
}T[N<<2];

status operator+(const status& Lc,const status& Rc)
{
	status x;
	int W=max(Li[Lc.r][0],Li[Lc.r][1]),Max=max(W,max(Lc.rmax,Rc.lmax));
	x.Max_Li=max(max(Lc.Max_Li,Rc.Max_Li),W);
	x.l=Lc.l;
	x.r=Rc.r;
	x.Len=Lc.Len+Rc.Len+Li[Lc.r][0]+Li[Lc.r][1]-Max;
	x.Num=Lc.Num+Rc.Num;
	x.lpos=Lc.lpos;
	x.lmax=Lc.lmax;
	x.rpos=Rc.rpos;
	x.rmax=Rc.rmax;
	if(Ro[Lc.rpos]==Max)
	{
		x.Num--;
		if(Lc.Num==1)
			x.lpos=Rc.lpos,
			x.lmax=max(max(Lc.Max_Li,Rc.lmax),W);
	}
	else if(Ro[Rc.lpos]==Max)
	{
		x.Num--;
		if(Rc.Num==1)
			x.rpos=Lc.rpos,
			x.rmax=max(max(Rc.Max_Li,Lc.rmax),W);
	}
	return x; 
}

#define Lc (x<<1)
#define Rc (x<<1|1)
#define Mid (l+r>>1)

void Build(int x,int l,int r)
{
	if(l==r)
		T[x]=status(l);
	else
		Build(Lc,l,Mid),
		Build(Rc,Mid+1,r),
		T[x]=T[Lc]+T[Rc];
}

void Change_Ro(int x,int l,int r,int p)
{
	if(l==r)
		T[x]=status(l);
	else
	{
		if(p<=Mid)
			Change_Ro(Lc,l,Mid,p);
		else
			Change_Ro(Rc,Mid+1,r,p);
		T[x]=T[Lc]+T[Rc];
	}
}

void Change_Li(int x,int l,int r,int p)
{
	if(p<Mid)
		Change_Li(Lc,l,Mid,p);
	else if(p>Mid)
		Change_Li(Rc,Mid+1,r,p);
	T[x]=T[Lc]+T[Rc];
}

status Ask(int x,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)
		return T[x];
	if(R<=Mid)
		return Ask(Lc,l,Mid,L,R);
	else if(L>Mid)
		return Ask(Rc,Mid+1,r,L,R);
	return Ask(Lc,l,Mid,L,R)+Ask(Rc,Mid+1,r,L,R);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
		scanf("%d",&Li[i][0]);
	for(int i=1;i<n;i++)
		scanf("%d",&Li[i][1]);
	for(int i=1;i<=n;i++)
		scanf("%d",&Ro[i]);
	Build(1,1,n);
	while(m--)
	{
		char op[10];
		scanf("%s",op);
		if(op[0]=='C')
		{
			int x1,y1,x2,y2,w;
			scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&w);
			if(y1==y2)
				Ro[y1]=w,
				Change_Ro(1,1,n,y1);
			else
			{
				if(y1>y2)
					swap(y1,y2);
				Li[y1][x1-1]=w,
				Change_Li(1,1,n,y1);
			}
		}
		else
		{
			int x,y;
			scanf("%d%d",&x,&y);
			printf("%d\n",Ask(1,1,n,x,y).Len);  
		}
	}
	return 0;
}
 

 

Category: My Oi,My Life | Tags: SDOI 逗比 | Read Count: 848

登录 *


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