10
4
2018
1

[UOJ15] 【NOIP2014】生活大爆炸版石头剪刀布

练一下python

以下代码在python2.7编译通过

这个题直接做,循环就可以了

win=[[1, 0, 2, 2, 0], [2, 1, 0, 2, 0], [0, 2, 1, 0, 2], [0, 0, 2, 1, 2], [2, 2, 0, 0, 1]]
xiaoa=[]; xiaob=[]; wina=0; winb=0
n, na, nb=map(int, raw_input().split())
#print n, na, nb
p=raw_input().split()
for i in range(0, na):
    xiaoa.append(int(p[i]))
p=raw_input().split()
for i in range(0, nb):
    xiaob.append(int(p[i]))
for i in range(0, n):
    px=win[int(xiaoa[i%na])][int(xiaob[i%nb])]
    if px==0:
        winb+=1
    elif px==2:
        wina+=1
print wina, winb
Category: 其他OJ | Tags: uoj
8
19
2016
0

[hihoCoder1225] 向日葵

题解clj大神有了就不放了

链接

一道非常好的题目,只是调试能死人罢了

注意要点:

1.此时的极角排序必须加上象限的判断不然会出错(重要!)

2.注意每次point数组必须清空而不能复用因为编号乱了

3.以后数组开到原来的4倍左右防止因数组开小而出错

4.使用long long类型可以有效避免精度误差

5.以后碰到这种题我就写一个$O(n^3)$的暴力,因为这题数据很良心是可以过的,而且我考场上几乎100%不能调试成功

下面版本复杂度为$O(n^2logn)$

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=4005;
const double eps=1e-17;

int n,cnt,ind[N];
double ans;

struct Point{
long long x,y;
int id;
Point(){}
Point(long long _x,long long _y){x=_x;y=_y;}
friend inline Point operator+(const Point &A,const Point &B){return Point(A.x+B.x,A.y+B.y);}
friend inline Point operator-(const Point &A,const Point &B){return Point(A.x-B.x,A.y-B.y);}
friend inline long long operator*(const Point &A,const Point &B){return A.x*B.y-A.y*B.x;}
friend inline bool operator==(const Point &A,const Point &B){return A.x==B.x && A.y==B.y;}
}ChosenPoint,point[N<<1];

inline int Check(Point A){
if(A.x-ChosenPoint.x>0 && A.y-ChosenPoint.y>=0)return 0;
if(A.x-ChosenPoint.x<=0 && A.y-ChosenPoint.y>0)return 1;
if(A.x-ChosenPoint.x<0 && A.y-ChosenPoint.y<=0)return 2;
return 3;
}

inline int Dist2(const Point &A,const Point &B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}
inline bool cmp(const Point &A,const Point &B){int x=Check(A),y=Check(B);if(x!=y)return x<y;return (A-ChosenPoint)*(B-ChosenPoint)>=0;}
inline bool OnRight(const Point &A,const Point &B,const Point &C){return (B-A)*(C-A)>=0;}

struct Pair_Points{
Point A,B;
}poi[N];

int main(){
freopen("1225.in","r",stdin);
freopen("1225.out","w",stdout);
scanf("%d",&n);
if(n<3){puts("0.000000");return 0;}
for(int i=1;i<=n;i++)scanf("%lld %lld %lld %lld",&poi[i].A.x,&poi[i].A.y,&poi[i].B.x,&poi[i].B.y);
for(int i=1;i<=n;i++){
	ChosenPoint=poi[i].A;
	cnt=0;
	for(int j=1;j<=n;j++){
		if(i==j)continue;
		point[++cnt]=poi[j].A;point[cnt].id=j;point[++cnt]=poi[j].B;point[cnt].id=j;
	}
	sort(point+1,point+cnt+1,cmp);
	memset(ind,0,sizeof(ind));
	int cntx[3]={n-1},pos=1;
	for(int j=cnt+1;j<=2*cnt;j++)point[j]=point[j-cnt];
	for(int j=1;j<=cnt;j++){
		while(pos<j+cnt && OnRight(ChosenPoint,point[j],point[pos])){
			ind[point[pos].id]++;
			cntx[ind[point[pos].id]]++;
			cntx[ind[point[pos].id]-1]--;
            pos++;
		}
		//printf("%d %d %d %d\n", pos, cntx[0], cntx[1], cntx[2]);
		if(cntx[1]+cntx[2]==n-1){
			double afk=0.125;
			if(ind[point[j].id]==1)afk/=pow(2,cntx[1]-1);
			else afk/=pow(2,cntx[1]);
			ans+=afk*(ChosenPoint*point[j]);
		}
		ind[point[j].id]--;
		cntx[ind[point[j].id]]++;
		cntx[ind[point[j].id]+1]--;
	}
}
for(int i=1;i<=n;i++){
	ChosenPoint=poi[i].B;
	cnt=0;
	for(int j=1;j<=n;j++){
		if(i==j)continue;
		point[++cnt]=poi[j].A;point[cnt].id=j;point[++cnt]=poi[j].B;point[cnt].id=j;
	}
	sort(point+1,point+cnt+1,cmp);
	memset(ind,0,sizeof(ind));
	int cntx[3]={n-1},pos=1;
	for(int j=cnt+1;j<=2*cnt;j++)point[j]=point[j-cnt];
	for(int j=1;j<=cnt;j++){
		while(pos<j+cnt && OnRight(ChosenPoint,point[j],point[pos])){
			ind[point[pos].id]++;
			cntx[ind[point[pos].id]]++;
			cntx[ind[point[pos].id]-1]--;
            pos++;
		}
		//printf("%d %d %d %d\n", pos, cntx[0], cntx[1], cntx[2]);
		if(cntx[1]+cntx[2]==n-1){
			double afk=0.125;
			if(ind[point[j].id]==1)afk/=pow(2,cntx[1]-1);
			else afk/=pow(2,cntx[1]);
			ans+=afk*(ChosenPoint*point[j]);
		}
		ind[point[j].id]--;
		cntx[ind[point[j].id]]++;
		cntx[ind[point[j].id]+1]--;
	}
}
printf("%.17lf\n",ans);
return 0;
}
Category: 其他OJ | Tags: OI hihoCoder
8
17
2016
0

[UOJ222] 【NOI2016】区间

two points+线段树

按长度排序之后一个个加就行

我考场上居然没想到

数组开小wa了2次……身败名裂

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=500005,INF=1000000000;

int b[N<<1],n,m,cnt,ans=INF,tot;

struct Inside{
int l,r,len;
friend bool operator<(const Inside &A,const Inside &B){return A.len<B.len;}
}ins[N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

struct SegTree{
int l,r,tag,cnt;
}tree[N<<3];

inline void Pushup(const int &rt){
tree[rt].cnt=tree[rt].tag+max(tree[rt<<1].cnt,tree[rt<<1|1].cnt);
}

void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r)return;
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
}

void Add(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r){tree[rt].cnt++;tree[rt].tag++;return;}
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Add(rt<<1,l,r);
if(r>mid)Add(rt<<1|1,l,r);
Pushup(rt);
}

void Del(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r){tree[rt].cnt--;tree[rt].tag--;return;}
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Del(rt<<1,l,r);
if(r>mid)Del(rt<<1|1,l,r);
Pushup(rt);
}

int main(){
freopen("222.in","r",stdin);
freopen("222.out","w",stdout);
Read(n);Read(m);
for(int i=1;i<=n;i++){
	Read(ins[i].l);Read(ins[i].r);
	ins[i].len=ins[i].r-ins[i].l;
	b[++cnt]=ins[i].l;b[++cnt]=ins[i].r;
}
sort(b+1,b+cnt+1);
cnt=unique(b+1,b+cnt+1)-b-1;
for(int i=1;i<=n;i++)ins[i].l=lower_bound(b+1,b+cnt+1,ins[i].l)-b,ins[i].r=lower_bound(b+1,b+cnt+1,ins[i].r)-b;
sort(ins+1,ins+n+1);
Build(1,1,cnt);
int cur=0;
for(int i=1;i<=n;i++){
    while(cur<n && tree[1].cnt<m){cur++;Add(1,ins[cur].l,ins[cur].r);}
    if(tree[1].cnt<m)break;
    ans=min(ans,ins[cur].len-ins[i].len);
    Del(1,ins[i].l,ins[i].r);
}
printf("%d\n",ans==INF?-1:ans);
return 0;
}
Category: 其他OJ | Tags: OI uoj
8
4
2016
0

[UOJ3] 【NOI2014】魔法森林

sbLCT调了这么长时间……

Splay部分写错了

按照a从小到大排序,用LCT维护最小生成树

没了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=50005,INF=1000000000;

int n,m,ans=INF;

struct Node{
int v,id;
bool rev;
Node *ch[2],*fa,*mxe;
Node();
void Pushdown();
void Pushup();
}*tree[N<<2],*Null;

struct Ed{
int u,v,a,b;
friend bool operator<(const Ed &A,const Ed &B){return A.a<B.a||(A.a==B.a && A.b<B.b);}
}es[N<<1];

Node::Node(){fa=ch[0]=ch[1]=Null;mxe=this;v=-INF;rev=id=0;}

inline void Node::Pushdown(){
if(rev){
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
    swap(ch[0],ch[1]);
    rev=0;
}
}

inline void Node::Pushup(){
mxe=this;
if(ch[0]->mxe->v>mxe->v)mxe=ch[0]->mxe;
if(ch[1]->mxe->v>mxe->v)mxe=ch[1]->mxe;
}

inline bool Notroot(Node *x){return x->fa->ch[0]==x || x->fa->ch[1]==x;}
inline void Prepare(Node *x){if(Notroot(x))Prepare(x->fa);x->Pushdown();}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
    if(!Notroot(y))Rotate(x,y->ch[0]==x);
    else {
        if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
        else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
        else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
        else {Rotate(y,0);Rotate(x,0);}
    }
}
}

void Access(Node *x){for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}}
void Makeroot(Node *x){Access(x);Splay(x);x->rev^=1;}
void Link(Node *x,Node *y){Makeroot(x);x->fa=y;}
void Cut(Node *x,Node *y){Makeroot(x);Access(y);Splay(y);y->ch[0]=x->fa=Null;y->Pushup();}
Node *Find(Node *x){Access(x);Splay(x);while(x->ch[0]!=Null)x=x->ch[0];return x;}
Node *GetNull(){Node *p=new Node();p->ch[0]=p->ch[1]=p->fa=p->mxe=p;return p;}
Node *Query(Node *x,Node *y){Makeroot(x);Access(y);Splay(y);return y->mxe;}

int main(){
freopen("3.in","r",stdin);
freopen("3.out","w",stdout);
scanf("%d %d",&n,&m);
Null=GetNull();
for(int i=1;i<=m;i++)scanf("%d %d %d %d",&es[i].u,&es[i].v,&es[i].a,&es[i].b);
sort(es+1,es+m+1);
for(int i=1;i<=n;i++)tree[i]=new Node();
for(int i=1;i<=m;i++)tree[i+n]=new Node(),tree[i+n]->v=es[i].b,tree[i+n]->id=i;
for(int i=1;i<=m;i++){
    if(es[i].u==es[i].v)continue;
	if(Find(tree[es[i].u])==Find(tree[es[i].v])){
		Node *c=Query(tree[es[i].u],tree[es[i].v]);
		if(c->v>es[i].b){Cut(tree[es[c->id].u],c);Cut(tree[es[c->id].v],c);}
		else {if(Find(tree[1])==Find(tree[n]))ans=min(ans,es[i].a+Query(tree[1],tree[n])->v);continue;}
	}
    Link(tree[es[i].u],tree[i+n]);Link(tree[es[i].v],tree[i+n]);
    if(Find(tree[1])==Find(tree[n])){ans=min(ans,es[i].a+Query(tree[1],tree[n])->v);}
}
printf("%d\n",ans==INF?-1:ans);
return 0;
}
Category: 其他OJ | Tags: OI uoj
8
4
2016
0

[UOJ207] 共价大爷游长沙

虽然已经有官方题解了而且写的和我一样……但是我还来写一次题解凑文章数

首先看了一下题目,发现不会做,就去看题解。

题解中说:"用LCT统计子树异或和",我不会啊!

找到myy代码仔细看了一遍,大概也会统计子树异或和了。

首先我们考虑正常的LCT,你直接把两个child的和异或起来的和其实是你Access的那条链上的和。

那么统计子树就要从这里入手。

我们在Access时加上一些操作:如果原先选中的链不为Null,异或之;如果当前的选中的节点不为Null,异或之;

这样为什么就可以统计子树了呢?

(注意题目的性质,我们的子树异或和一定是Access访问过这个子树的全部节点,所以才能这么做)

考虑一开始啥都没有。

然后我们选中了一条链,那么原先的链啥也没有,我们在Pushup的时候就不考虑异或。

但是现在选中的链是存在的,我们异或一下。

那么我们就统计了这一条链。

之后同理

至于为什么要异或s_c,那是因为你在选中时统计了这个,之后Pushup时s_t又统计了一次

所以要还原

然后我们这题可以随机赋权值,每次碰到就异或一下,求解时确认这条边是否唯一存在即可。

代码跑得并不快(6097ms)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=500005;

int n,m,ID,ans,h[N],en,fa[N],val[N],cnt;
pair<int,int> path[N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

inline int Abs(const int &x){return x>0?x:-x;}

inline int Rand(){
return (rand()<<16)|rand();
}

struct Edge{
int b,next;
}e[N<<1];

inline void AddEdge(const int &sa,const int &sb){e[++en].b=sb;e[en].next=h[sa];h[sa]=en;}

struct Node{
int v,v_t,s_c,s_t;
bool rev;
Node *ch[2],*fa;
Node();
inline void Pushdown();
inline void Pushup();
}*tree[N],*Null;

Node::Node(){v=v_t=s_c=s_t=rev=0;ch[0]=ch[1]=fa=Null;}

inline void Node::Pushdown(){
if(rev){
    if(ch[0]!=Null)ch[0]->rev^=1;
    if(ch[1]!=Null)ch[1]->rev^=1;
    swap(ch[0]->ch[0],ch[0]->ch[1]);
    swap(ch[1]->ch[0],ch[1]->ch[1]);
	rev=0;
}
}

inline void Node::Pushup(){
s_t=v_t;s_c=v;
if(ch[0]!=Null)s_t^=ch[0]->s_t,s_c^=ch[0]->s_c;
if(ch[1]!=Null)s_t^=ch[1]->s_t,s_c^=ch[1]->s_c;
}

Node *GetNull(){Node *p=new Node();p->fa=p->ch[0]=p->ch[1]=p;return p;}
int Notroot(Node *x){return x->fa->ch[0]==x||x->fa->ch[1]==x;}
void Prepare(Node *x){if(Notroot(x))Prepare(x->fa);x->Pushdown();}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y))Rotate(x,y->ch[0]==x);
    else {
        if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else {Rotate(y,0);Rotate(x,0);}
    }
}
}

void Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){
	Splay(x);
	if(x->ch[1]!=Null)x->v_t^=x->ch[1]->s_t^x->ch[1]->s_c;
	if(y!=Null)x->v_t^=y->s_t^y->s_c;
	x->ch[1]=y;
    x->Pushup();
}
}

inline void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
swap(x->ch[0],x->ch[1]);
}

inline void Link(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
y->v_t^=x->s_t^x->s_c;
x->fa=y;
Access(x);
}

inline void Cut(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
x->fa=Null;
y->ch[0]=Null;
x->Pushup();
}

inline void Change(Node *x,int y){Access(x);Splay(x);x->v^=y;x->Pushup();}
inline bool Query(Node *x,Node *y){Makeroot(x);Access(y);Splay(y);/*printf("DEBUG_Q: %d %d %d %d\n",y->v,y->v_t,y->v^y->v_t,ans);*/return (y->v^y->v_t)==ans;}
inline void dfs(int u){for(int i=h[u];i;i=e[i].next){int v=e[i].b;if(v==fa[u])continue;fa[v]=u;dfs(v);}}

int main(){
freopen("207.in","r",stdin);
freopen("207.out","w",stdout);
Read(ID);Read(n);Read(m);
if(ID==11){puts("OrzOrzOrz\nHello,world!\n233666");return 0;}
Null=GetNull();
for(int i=1;i<n;i++){
	int u,v;
    Read(u);Read(v);
	AddEdge(u,v);AddEdge(v,u);
}
dfs(1);
for(int i=1;i<=n;i++)tree[i]=new Node();
for(int i=2;i<=n;i++)tree[i]->fa=tree[fa[i]];
for(int i=0;i<m;i++){
	int opt,u,v,x,y;
    Read(opt);
    if(opt==1){Read(u);Read(v);Read(x);Read(y);Cut(tree[u],tree[v]);Link(tree[x],tree[y]);}
    if(opt==2){Read(x);Read(y);int tp=Rand();ans^=tp;Change(tree[x],tp);Change(tree[y],tp);path[++cnt]=make_pair(x,y);val[cnt]=tp;}
    if(opt==3){Read(x);Change(tree[path[x].first],val[x]);Change(tree[path[x].second],val[x]);ans^=val[x];}
    if(opt==4){Read(x);Read(y);puts(Query(tree[x],tree[y])?"YES":"NO");}
}
return 0;
}
Category: 其他OJ | Tags: OI uoj
5
25
2016
1

[51Nod1676] 无向图同构

首先树同构我是写过的……就是BJOI那题

然后图同构我是不会的……

然后就花了点头盾看了题解。

原来和树Hash差不多,只要进行迭代就好了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int M=4005,N=205;
const long long P1=808080808080803ll,P2=888888888888887ll;

int n,m,hA[N],hB[N],enA,enB,test;
long long valA_1[N],valB_1[N],valA_2[N],valB_2[N],tmp1[N],tmp2[N],Vt1[N],Vt2[N];

struct Edge{
int b,next;
}eA[M<<1],eB[M<<1];

void AddEdgeA(int sa,int sb){
eA[++enA].b=sb;
eA[enA].next=hA[sa];
hA[sa]=enA;
}

void AddEdgeB(int sa,int sb){
eB[++enB].b=sb;
eB[enB].next=hB[sa];
hB[sa]=enB;
}

void Solve_A(){
for(int i=1;i<=n;i++){
	int cnt=0;
	for(int j=hA[i];j;j=eA[j].next){
		int v=eA[j].b;cnt++;
		tmp1[cnt]=valA_1[v];
		tmp2[cnt]=valA_2[v];
	}
	sort(tmp1+1,tmp1+cnt+1);
	sort(tmp2+1,tmp2+cnt+1);
	long long Ha1=0,Ha2=0;
    for(int j=1;j<=cnt;j++){Ha1=(Ha1*233ll+tmp1[j])%P1;Ha2=(Ha2*666ll+tmp2[j])%P2;}
    Vt1[i]=Ha1;Vt2[i]=Ha2;
}
for(int i=1;i<=n;i++){valA_1[i]=Vt1[i];valA_2[i]=Vt2[i];}
}

void Solve_B(){
for(int i=1;i<=n;i++){
	int cnt=0;
	for(int j=hB[i];j;j=eB[j].next){
		int v=eB[j].b;cnt++;
		tmp1[cnt]=valB_1[v];
		tmp2[cnt]=valB_2[v];
	}
	sort(tmp1+1,tmp1+cnt+1);
	sort(tmp2+1,tmp2+cnt+1);
	long long Ha1=0,Ha2=0;
    for(int j=1;j<=cnt;j++){Ha1=(Ha1*233ll+tmp1[j])%P1;Ha2=(Ha2*666ll+tmp2[j])%P2;}
    Vt1[i]=Ha1;Vt2[i]=Ha2;
}
for(int i=1;i<=n;i++){valB_1[i]=Vt1[i];valB_2[i]=Vt2[i];}
}

void Solve(){
scanf("%d %d",&n,&m);
memset(hA,0,sizeof(hA));
memset(hB,0,sizeof(hB));
enA=0;enB=0;
for(int i=1;i<=m;i++){
	int u,v;
	scanf("%d %d",&u,&v);
	AddEdgeA(u,v);AddEdgeA(v,u);
}
for(int i=1;i<=m;i++){
	int u,v;
	scanf("%d %d",&u,&v);
	AddEdgeB(u,v);AddEdgeB(v,u);
}
for(int i=1;i<=n;i++)valA_1[i]=valA_2[i]=valB_1[i]=valB_2[i]=1;
for(int i=1;i<=n;i++)Solve_A();
for(int i=1;i<=n;i++)Solve_B();
sort(valA_1+1,valA_1+n+1);
sort(valA_2+1,valA_2+n+1);
sort(valB_1+1,valB_1+n+1);
sort(valB_2+1,valB_2+n+1);
int flag=1;
for(int i=1;i<=n;i++)if(valA_1[i]!=valB_1[i] || valA_2[i]!=valB_2[i]){puts("NO");flag=0;break;}
if(flag)puts("YES");
}

int main(){
freopen("1676.in","r",stdin);
freopen("1676.out","w",stdout);
scanf("%d",&test);
while(test--)Solve();
return 0;
}
Category: 其他OJ | Tags: OI 51nod
5
24
2016
0

[51Nod1515] 明辨是非

维护相等的关系要用并查集

而对于不等关系,因为没有传递性我们用一个set来维护

合并时根据set的大小启发式合并就好了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;

const int N=200005;

int n,f[N],b[N],cnt,id[N];
set<int> S[N];

struct Save{
int a,b,p;
}sav[N];

int Find(int x){return f[x]==x?x:f[x]=Find(f[x]);}

void Union(int x,int y){
if(x==y)return;
if(S[x].size()>S[y].size())swap(x,y);
for(set<int>::iterator i=S[x].begin();i!=S[x].end();i++)S[y].insert(Find(*i));
f[x]=y;
}

int main(){
freopen("1515.in","r",stdin);
freopen("1515.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%d %d %d",&sav[i].a,&sav[i].b,&sav[i].p);
    b[++cnt]=sav[i].a;f[cnt]=cnt;
    b[++cnt]=sav[i].b;f[cnt]=cnt;
}
sort(b+1,b+cnt+1);
cnt=unique(b+1,b+cnt+1)-b-1;
for(int i=1;i<=n;i++){
	sav[i].a=Find(lower_bound(b+1,b+cnt+1,sav[i].a)-b);
	sav[i].b=Find(lower_bound(b+1,b+cnt+1,sav[i].b)-b);
	if(sav[i].p){
		if(S[sav[i].b].find(sav[i].a)!=S[sav[i].b].end() || S[sav[i].a].find(sav[i].b)!=S[sav[i].a].end())puts("NO");
		else puts("YES"),Union(sav[i].a,sav[i].b);
	}
	else {
		if(sav[i].a==sav[i].b)puts("NO");
		else puts("YES"),S[sav[i].a].insert(sav[i].b),S[sav[i].b].insert(sav[i].a);
	}
}
return 0;
}
Category: 其他OJ | Tags: OI 51nod
4
6
2016
0

[UOJ164] 【清华集训2015】V

最近集训出了很多SGTB(SeGmentTree Beats!)的题目,所以被迫来学习这个冬令营上的黑科技。。

这题照着其他人写的程序理解了几个小时,然后自己写了一发居然是最快的。。。

记录一下自己对于这题的理解吧

输入的操作分别对应:

1.区间加

2.区间max(0,v)

3.区间赋值

4.询问单点值

5.询问单点历史最值

然后我一开始试图维护十来个标记然后暴力搞。。然后就不会了

然后膜了一下其他人的程序和lzz的冬令营课件,总算有了一点理解了

这题关键在于单点询问,所以我们仅仅把区间当成一整个标记,每次下传后就清零

然后问题在于两个操作:询问历史最值和区间max

我们先不管询问历史最值

其实我们进行一番转化后可以发现,其实123操作都可以对应到一个(x,y)(加上x对y取max)上(这是对于一个区间的标记)

1:区间加v -> (v,INF)

2:区间max(0,v) -> (v,0)

3.区间赋值为v -> (-INF,v);

这很显然吧。。

然后我们考虑两个标记的合并,这里我还是想了一下的

设旧标记为A,新标记为B

那么我们进行合并就变成了(A.x+B.x,max(A.y+B.x,B.y))

为什么是这样呢?

首先我们考虑如果A.x+B.x,那么就直接相当于普通线段树的Add操作,明显可行

而max(A.y+B.x,B.y)则表示如果旧标记产生的最大值为A.y,那么我们最终要取的值要么就是旧标记的A.y加上新标记要加上的值(因为旧标记可能取A.y),要么就是新标记要取的B.y(感觉我这句话比较意识流啊),当然是在这两个数里面选一个最大值了

于是我们就处理完了没有历史最值询问的操作

但是这题是有历史最值询问的。。好坑啊

那么我们考虑再加上两个标记mx,addmx表示当前区间的历史最值和要加上去的值的历史最值

那么我们继续考虑合并标记

同样,我们设(X,Y)表示mx和addmx两个值(偷懒),那么我们继续设以前的旧标记为A,用来更新旧标记的新标记为B

那么历史最值可以怎么构成?可以由旧标记的历史最值、新标记的历史最值,或者是旧标记的当前值加上新标记的的历史最大加值。

前两个很好理解,但是最后一个是什么意思呢?

首先,新标记的历史最大加值可以用这样一段话来叙述:“这一段区间曾经加过这么大的值”

那么我们每次拿旧标记当前的值加上新标记的历史最大加值,就意味着这个合并后的标记曾经在某个时刻达到了这个可能的最大值

因为每次更新标记时都是自顶向下,那么没有被更新的旧标记的值一定是当前值,如果被更改了那么之前一定在这里下传过标记,所以这样是对的

而我们再考虑addmx可以怎么构成

显然这个值可能的取值为:旧标记的addmx,新标记的addmx加上旧标记的add

为什么又是这么取值呢?

第一种情况显然。第二种情况因为新标记的历史最大加值此时没有经过任何更新,也就是和旧标记一点关联也没有

而因为add的定义和题目的描述(就是上面的小写标记),add标记一定不会小于0

那么我们当然需要加上这个add值(新标记此前不可能加过add标记),这样能让解更优

那么你可能会问:为什么不能让旧标记的历史最值加上新标记的add呢?

因为新标记是用来更新旧标记的,所以这样可能重复的加所以不行

这仅仅是个人的理解,我觉得真是漏洞百出,具体的证明lzz冬令营课件里面有,反正我没有看太懂。。。

我真是太弱了

这真是一篇意识流的题解

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int n,m;
long long a[500005];
const long long INF=1000000000000000ll;

template<typename T>void Read(T &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

struct SegTree{
int l,r;
long long v,mx,add,addmx;
SegTree(){}
SegTree(long long V,long long MX,long long ADD,long long ADDMX){v=V;mx=MX;add=ADD;addmx=ADDMX;}
SegTree(int L,int R,long long V,long long MX,long long ADD,long long ADDMX){l=L;r=R;v=V;mx=MX;add=ADD;addmx=ADDMX;}
}tree[2000005],tmp;

SegTree Update(SegTree A,SegTree B){
return SegTree(A.l,A.r,max(A.v+B.add,B.v),max(max(A.mx,B.mx),A.v+B.addmx),max(A.add+B.add,-INF),max(A.addmx,A.add+B.addmx));
}

void Pushdown(int rt){
tree[rt*2]=Update(tree[rt*2],tree[rt]);
tree[rt*2+1]=Update(tree[rt*2+1],tree[rt]);
tree[rt]=SegTree(tree[rt].l,tree[rt].r,0,0,0,0);
}

void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r){
	tree[rt].addmx=tree[rt].add=tree[rt].v=tree[rt].mx=a[l];
	return;
}
int mid=l+r>>1;
Build(rt*2,l,mid);
Build(rt*2+1,mid+1,r);
}

void Change(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r){tree[rt]=Update(tree[rt],tmp);return;}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Change(rt*2,l,r);
if(r>mid)Change(rt*2+1,l,r);
}

long long Query(int rt,int pos,int id){
if(tree[rt].l==tree[rt].r){return id?tree[rt].mx:tree[rt].v;}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)return Query(rt*2,pos,id);
if(pos>mid)return Query(rt*2+1,pos,id);
}

int main(){
freopen("164.in","r",stdin);
freopen("164.out","w",stdout);
Read(n);Read(m);
for(int i=1;i<=n;i++)Read(a[i]);
Build(1,1,n);
for(int i=1;i<=m;i++){
    int opt,l,r,v;
    Read(opt);
    if(opt==1){Read(l);Read(r);Read(v);tmp=SegTree(0,0,v,v);Change(1,l,r);}
    if(opt==2){Read(l);Read(r);Read(v);tmp=SegTree(0,0,-v,-v);Change(1,l,r);}
    if(opt==3){Read(l);Read(r);Read(v);tmp=SegTree(v,v,-INF,-INF);Change(1,l,r);}
    if(opt==4){Read(v);printf("%lld\n",Query(1,v,0));}
    if(opt==5){Read(v);printf("%lld\n",Query(1,v,1));}
}
return 0;
}
Category: 其他OJ | Tags: OI uoj
3
31
2016
0

[UOJ34] 多项式乘法

第一道FFT

话说后缀数组我只会敲模版……这几天的比赛验证了我连暴力都能写挂

但是最近好像碰到好多FFT题目,于是就学习了一下

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;

const double Pi=2*asin(1);
const int NUM_SIZE=100005;

int An,Bn,Cn,Rev[NUM_SIZE*3],Step,n;

struct Complex{
double a,b;
Complex(double as=0.0,double bs=0.0){a=as;b=bs;}
friend Complex operator+(Complex a,Complex b){return Complex(a.a+b.a,a.b+b.b);}
friend Complex operator-(Complex a,Complex b){return Complex(a.a-b.a,a.b-b.b);}
friend Complex operator*(Complex a,Complex b){return Complex(a.a*b.a-a.b*b.b,b.a*a.b+a.a*b.b);}
friend Complex operator/(Complex a,Complex b){return Complex((a.a*b.a+a.b*b.b)/(b.a*b.a+b.b*b.b),(b.a*a.b-a.a*b.b)/(b.a*b.a+b.b*b.b));}
double Mod(){return sqrt(a*a+b*b);}
}A[NUM_SIZE*3],B[NUM_SIZE*3],C[NUM_SIZE*3];

template<typename T>void Read(T &x){
int flag=1;
char ch;
while((ch=getchar())<'0' || ch>'9')if(ch=='-')flag=-1;
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
x*=flag;
}

void FFT(Complex *x,int flag){
for(int i=0;i<n;i++)if(i<Rev[i])swap(x[i],x[Rev[i]]);
for(int k=1;k<n;k<<=1){
    Complex wk=Complex(cos(Pi/k),flag*sin(Pi/k));
    for(int i=0;i<n;i+=k<<1){
		Complex wkj=Complex(1.0,0.0);
		for(int j=0;j<k;j++){
			Complex a=x[i+j],b=x[i+j+k]*wkj;
			x[i+j]=a+b;
			x[i+j+k]=a-b;
			wkj=wkj*wk;
		}
    }
}
if(flag==-1){for(int i=0;i<n;i++)x[i].a/=n;}
}

int main(){
freopen("34.in","r",stdin);
freopen("34.out","w",stdout);
Read(An);Read(Bn);
An++;Bn++;
Cn=An+Bn-1;
for(int i=0;i<An;i++)Read(A[i].a);
for(int i=0;i<Bn;i++)Read(B[i].a);
for(n=1,Step=0;n<Cn;Step++,n<<=1);
for(int i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Step-1));
FFT(A,1);
FFT(B,1);
for(int i=0;i<n;i++)C[i]=A[i]*B[i];
FFT(C,-1);
for(int i=0;i<Cn;i++)printf("%d ",(int)(C[i].a+0.5));
putchar('\n');
return 0;
}
Category: 其他OJ | Tags: OI uoj
3
28
2016
1

[POJ1741] Tree

点分治第一题

这题我们考虑点分治

首先我们需要找到树的重心

然后做一遍

然后分成左右两块继续做,每一块重复上面的操作

具体的,我们每次计算每个点到重心的距离

然后放到一个数组里,再将距离和小于k的算进去

但是有可能重复统计了子树里面的数值

所以点分治的时候再减一下就好了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

int n,k,h[10005],en,mx[10005],siz[10005],ans,root,val,vis[10005],temp[10005],cnt;

struct Edge{
int b,v,next;
}e[20005];

void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}

void DfsSiz(int u,int fa){
siz[u]=1;
mx[u]=0;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v!=fa && !vis[v]){
		DfsSiz(v,u);
		siz[u]+=siz[v];
		mx[u]=max(mx[u],siz[v]);
	}
}
}

void DfsRoot(int point,int u,int fa){
mx[u]=max(mx[u],siz[point]-siz[u]);
if(val>mx[u]){val=mx[u];root=u;}
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v!=fa && !vis[v])DfsRoot(point,v,u);
}
}

void GetDist(int u,int fa,int val){
temp[++cnt]=val;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v!=fa && !vis[v])GetDist(v,u,val+e[i].v);
}
}

int Cal(int u,int val){
cnt=0;
int now=0;
GetDist(u,u,val);
sort(temp+1,temp+cnt+1);
int i=1,j=cnt;
while(i<j){
	while(temp[i]+temp[j]>k && i<j)j--;
    now+=j-i;
    i++;
}
return now;
}

void Dfs(int u){
val=2100000000;
DfsSiz(u,u);
DfsRoot(u,u,0);
ans+=Cal(root,0);
vis[root]=1;
for(int i=h[root];i;i=e[i].next){
	int v=e[i].b;
	if(!vis[v]){
		ans-=Cal(v,e[i].v);
		Dfs(v);
	}
}
}

int main(){
freopen("1741.in","r",stdin);
freopen("1741.out","w",stdout);
while(scanf("%d %d",&n,&k),n|k){
	memset(h,0,sizeof(h));
	memset(vis,0,sizeof(vis));
	ans=en=0;
	for(int i=1;i<n;i++){
		int sa,sb,sc;
		scanf("%d %d %d",&sa,&sb,&sc);
		AddEdge(sa,sb,sc);
		AddEdge(sb,sa,sc);
	}
	Dfs(1);
    printf("%d\n",ans);
}
return 0;
}
Category: 其他OJ | Tags: OI poj

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