Processing math: 100%
5
30
2016
1

呵呵

没拿到D类名额

NOI2016我去不了了

仔细一算，发现NOIP要是考到500+也许就拿到D类了吧

AFO

 

Category: 随笔 | Tags: 随笔 弱
5
25
2016
1

[51Nod1676] 无向图同构

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

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

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

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

?
51nod 1676
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#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的大小启发式合并就好了

?
51nod 1515
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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
5
24
2016
0

[BZOJ2095] [Poi2010]Bridges

首先最大值最小显然是二分

然后就是混合图的欧拉回路

首先我们对于无向图的欧拉回路可以记录点的度数(度数为偶数)，有向图的欧拉回路则是Abs(入度-出度)为偶数时有欧拉回路

那么混合图怎么办？网络流判定就好了。

为了方便和卡常数我所有的流量都除以了2.

我们把无向边随便定个方向再计算出度和入度，然后再连接一条反向边流量为1表示可以返回(因为可能无向边定的方向是相反的，那么对入度和出度会造成总共2的影响，所以连接流量为1)

然后对于入度>出度的点，我们连接源点到这个点，流量是入度减去出度再除以2.

否则连接这个点到汇点，流量是出度减去入度再除以2.

那么判断这个图是否满流就知道能不能形成欧拉回路了(因为欧拉回路每条边都经过所以一定满流)

?
bzoj 2095
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
 
const int N=2005,INF=2100000000;
 
int n,m,h[N],level[N],S,T,cur[N],in[N],out[N],en;
queue<int> Q;
 
struct E{
int u,v,a,b;
}es[N];
 
struct Edge{
int b,f,back,next;
}e[N<<2];
 
int Abs(int x){return x>0?x:-x;}
 
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}
 
int BFS(){
memset(level,0,sizeof(level));
Q.push(S);
level[S]=1;
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(level[v] || !e[i].f)continue;
        level[v]=level[u]+1;
        Q.push(v);
    }
}
return level[T];
}
 
int DFS(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b,fl;
    if(level[v]==level[u]+1 && e[i].f && (fl=DFS(v,min(f,e[i].f)))){
        f-=fl;
        e[i].f-=fl;
        e[e[i].back].f+=fl;
        if(f==0)return flow;
    }
}
return flow-f;
}
 
int Dinic(){
int ans=0;
while(BFS()){for(int i=1;i<=n+2;i++)cur[i]=h[i];ans+=DFS(S,INF);}
return ans;
}
 
bool Odd(){for(int i=1;i<=n;i++)if(Abs(in[i]-out[i])&1)return 1;return 0;}
 
bool Test(int k){
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
memset(h,0,sizeof(h));
en=0;S=n+1;T=n+2;
for(int i=1;i<=m;i++){
    if(es[i].a<=k && es[i].b<=k)AddEdge(es[i].v,es[i].u,1),out[es[i].u]++,in[es[i].v]++;
    else if(es[i].a<=k)out[es[i].u]++,in[es[i].v]++;
    else if(es[i].b<=k)out[es[i].v]++,in[es[i].u]++;
    else return 0;
}
if(Odd())return 0;
int ank=0;
for(int i=1;i<=n;i++){
    if(in[i]>out[i])AddEdge(S,i,in[i]-out[i]>>1),ank+=in[i]-out[i]>>1;
    if(in[i]<out[i])AddEdge(i,T,out[i]-in[i]>>1);
}
return Dinic()==ank;
}
 
int main(){
freopen("2095.in","r",stdin);
freopen("2095.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d %d %d %d",&es[i].u,&es[i].v,&es[i].a,&es[i].b);
int l=1,r=1000,ans=0;
while(l<=r){
    int mid=l+r>>1;
    if(Test(mid))r=mid-1,ans=mid;
    else l=mid+1;
}
if(!ans)puts("NIE");
else printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
5
24
2016
0

[BZOJ3513] [MUTC2013]idiots

这题一眼FFT，注意ai的范围也是10W左右(题目没写)

怎么做：构建指数型母函数F(x)=a0+a1∗x+...+ak∗xk，其中ai是长度为i的木棍个数，指数就是长度

那么卷积一次后顺着扫描一遍，边扫描边统计当前有多少种组合情况，注意偶数会多算一倍需要减掉

那么不能组成的概率就是当前的组合种数乘以当前长度的木棍数

最后答案只需要用1减一下就好了

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
  
const int N=262144;
const double Pi=acos(-1);
  
int n,Step,Rev[N],tn,test,nn,Su[N];
  
struct Complex{
double a,b;
Complex(){}
Complex(double sa,double sb){a=sa;b=sb;}
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,A.b*B.a+B.b*A.a);}
}A[N];
  
void FFT(Complex *r,int flag){
for(int i=0;i<n;i++)if(i<Rev[i])swap(r[i],r[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 x=r[i+j],y=r[i+j+k]*wkj;
            r[i+j]=x+y;
            r[i+j+k]=x-y;
            wkj=wkj*wk;
        }
    }
}
if(flag==-1)for(int i=0;i<n;i++)r[i].a/=n;
}
  
int main(){
freopen("3513.in","r",stdin);
freopen("3513.out","w",stdout);
scanf("%d",&test);
while(test--){
    scanf("%d",&tn);nn=0;Rev[0]=0;
    memset(Su,0,sizeof(Su));
    for(int i=1;i<=tn;i++){int x;scanf("%d",&x);Su[x]++;nn=max(x,nn);}
    nn++;
    nn<<=1;
    for(n=1,Step=0;n<nn;n<<=1,Step++);
    nn>>=1;
    for(int i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Step-1));
    for(int i=0;i<n;i++)A[i]=Complex(Su[i],0.0);
    FFT(A,1);
    for(int i=0;i<n;i++)A[i]=A[i]*A[i];
    FFT(A,-1);
    long long ans=0,tot=1ll*tn*(tn-1)*(tn-2)/6,can=0;
    for(int i=0;i<=nn;i++){
        can+=(long long)(A[i].a+0.5);
        if(!(i%2))can-=Su[i/2];
        if(!Su[i])continue;
        ans+=Su[i]*can;
    }
    ans>>=1;
    printf("%.7lf\n",1.0-1.0*ans/tot);
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
5
24
2016
0

[BZOJ2143] 飞飞侠

首先你会发现这是一个最短路

然后你会发现边数太多了

然后就不会了

hzwer教导我们：不连边也能跑最短路

具体就是设定一个高度不断下降，像分层图那么搞就可以了

?
bzoj 2143
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
  
const int N=155,INF=1000000000,dx[]={1,-1,0,0,0},dy[]={0,0,-1,1,0};
  
int n,m,A[N][N],B[N][N],X[5],Y[5],D[N][N][N<<1],ans=INF,flag,num,a1,a2,b1,b2,c1,c2;
bool vis[N][N][N<<1];
  
struct Data{
int v,x,y,s;
Data(int vs,int xs,int ys,int ss){v=vs;x=xs;y=ys;s=ss;}
friend bool operator<(Data A,Data B){return A.v>B.v;}
};
  
priority_queue<Data> PQ;
  
void Dijkstra(int Xs,int Ys){
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        for(int k=0;k<=num;k++){
            D[i][j][k]=INF;
            vis[i][j][k]=0;
        }
    }
}
D[Xs][Ys][B[Xs][Ys]]=A[Xs][Ys];
while(!PQ.empty())PQ.pop();
vis[Xs][Ys][0]=1;
PQ.push(Data(A[Xs][Ys],Xs,Ys,B[Xs][Ys]));
while(!PQ.empty() && !(vis[X[1]][Y[1]][0] && vis[X[2]][Y[2]][0] && vis[X[3]][Y[3]][0])){
    Data u=PQ.top();PQ.pop();
    if(vis[u.x][u.y][u.s])continue;
    vis[u.x][u.y][u.s]=1;
    if(u.s){
        for(int i=0;i<5;i++){
            int nx=u.x+dx[i],ny=u.y+dy[i];
            if(nx<1 || nx>n || ny<1 || ny>m || vis[nx][ny][u.s-1])continue;
            if(u.v<D[nx][ny][u.s-1]){
                D[nx][ny][u.s-1]=u.v;
                PQ.push(Data(u.v,nx,ny,u.s-1));
            }
        }
    }
    else {
        if(D[u.x][u.y][B[u.x][u.y]]>u.v+A[u.x][u.y]){
            D[u.x][u.y][B[u.x][u.y]]=u.v+A[u.x][u.y];
            PQ.push(Data(D[u.x][u.y][B[u.x][u.y]],u.x,u.y,B[u.x][u.y]));
        }
    }
}
}
  
int main(){
freopen("2143.in","r",stdin);
freopen("2143.out","w",stdout);
scanf("%d %d",&n,&m);num=n+m-2;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++)scanf("%d",&B[i][j]),B[i][j]=min(B[i][j],max(num-i-j,i+j-2));
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++)scanf("%d",&A[i][j]);
}
for(int i=1;i<=3;i++)scanf("%d %d",&X[i],&Y[i]);
Dijkstra(X[1],Y[1]);a1=D[X[2]][Y[2]][0];a2=D[X[3]][Y[3]][0];
Dijkstra(X[2],Y[2]);b1=D[X[1]][Y[1]][0];b2=D[X[3]][Y[3]][0];
Dijkstra(X[3],Y[3]);c1=D[X[1]][Y[1]][0];c2=D[X[2]][Y[2]][0];
if(ans>b1+c1)ans=b1+c1,flag=0;
if(ans>a1+c2)ans=a1+c2,flag=1;
if(ans>a2+b2)ans=a2+b2,flag=2;
if(ans==INF)puts("NO");
else {printf("%c\n%d\n",'X'+flag,ans);}
return 0;
}
Category: BZOJ | Tags: OI bzoj
5
24
2016
0

[BZOJ4602] [Sdoi2016]齿轮

dfs判定一下就没了

?
bzoj 4602
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
  
const int N=20005;
const long double eps=1e-8;
  
int t,n,m,h[N],vis[N],en,flag;
long double dep[N];
bool d[N];
  
struct Edge{
int b,next;
long double l1,l2;
bool l;
}e[N];
  
void AddEdge(int sa,int sb,int sc,int sd,bool se){
e[++en].b=sb;
e[en].l1=sc;
e[en].l2=sd;
e[en].l=se;
e[en].next=h[sa];
h[sa]=en;
}
  
void DFS(int u,int fa){
vis[u]=1;
for(int i=h[u];i && !flag;i=e[i].next){
    int v=e[i].b;
    if(v==fa)continue;
    if(!vis[v]){
        d[v]=(d[u]^e[i].l);
        dep[v]=dep[u]+log(e[i].l2)-log(e[i].l1);
        DFS(v,u);
    }
    else {
        if(d[v]!=(d[u]^e[i].l) || fabs(dep[u]-dep[v]+log(e[i].l2)-log(e[i].l1))>eps){flag=1;return;}
    }
}
}
  
int main(){
freopen("4602.in","r",stdin);
freopen("4602.out","w",stdout);
scanf("%d",&t);
for(int i=1;i<=t;i++){
    scanf("%d %d",&n,&m);
    memset(vis,0,sizeof(vis));
    memset(h,0,sizeof(h));
    en=flag=0;
    for(int j=1;j<=m;j++){
        int u,v,x,y;
        scanf("%d %d %d %d",&u,&v,&x,&y);
        if(y<0){AddEdge(u,v,x,-y,1);AddEdge(v,u,-y,x,1);}
        else {AddEdge(u,v,x,y,0);AddEdge(v,u,y,x,0);}
    }
    for(int j=1;j<=n && !flag;j++)if(!vis[j]){dep[j]=0;DFS(j,j);}
    printf("Case #%d: %s\n",i,flag?"No":"Yes");
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
5
24
2016
0

[BZOJ4591] [Shoi2015]超能粒子炮·改

Lucas定理的运用

C(n,k)=C(n/Mod,k/Mod)∗C(n%Mod,k%Mod)

那么我们发现因为是求C(n,0)+C(n,1)+...+C(n,k)，对于其中的C(n%Mod,i),0<=i<=k%Mod似乎会用很多次

然后推一下式子就发现这个可以处理成一个前缀和

然后就没了

?
bzoj 4591
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
  
const int Mod=2333;
  
int t,C[Mod][Mod],Sum[Mod][Mod];
long long n,k;
  
void Pre(){
C[0][0]=1;
for(int i=1;i<Mod;i++){
    C[i][0]=C[i][i]=1;
    for(int j=1;j<i;j++){C[i][j]=C[i-1][j]+C[i-1][j-1];if(C[i][j]>=Mod)C[i][j]-=Mod;}
}
for(int i=0;i<Mod;i++)Sum[0][i]=1;
for(int i=1;i<Mod;i++){
    Sum[i][0]=1;
    for(int j=1;j<Mod;j++){Sum[i][j]=Sum[i][j-1]+C[i][j];if(Sum[i][j]>=Mod)Sum[i][j]-=Mod;}
}
}
  
int Lucas(long long n,long long k){return k==0?1:C[n%Mod][k%Mod]*Lucas(n/Mod,k/Mod)%Mod;}
  
int Cal(long long n,long long k){
if(k<0)return 0;
if(n<Mod)return Sum[n][k];
return (Lucas(n/Mod,k/Mod)*Sum[n%Mod][k%Mod]+Cal(n/Mod,k/Mod-1)*Sum[n%Mod][Mod-1])%Mod;
}
  
int main(){
freopen("4591.in","r",stdin);
freopen("4591.out","w",stdout);
scanf("%d",&t);
Pre();
while(t--){
    scanf("%lld %lld",&n,&k);
    printf("%d\n",Cal(n,k));
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
5
24
2016
0

[BZOJ4592] [Shoi2015]脑洞治疗仪

首先这题显然是线段树

0操作 区间直接赋值为0 很简单

2操作 统计最长连续0的个数 记录lx,rx,mx三个量，随便合并一下就行了，很简单

1操作……

首先需要记录一个sum表示当前区间有多少脑组织

然后二分填满的位置，我偷懒写了线段树外面的二分，然后时间复杂度就多了一个log

?
bzoj 4592
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
  
const int N=200005;
  
int n,m;
  
struct SegTree{
int lx,rx,mx,tag,sum,l,r;
}tree[N<<2];
  
void Pushdown(int rt){
if(tree[rt].tag==1){
    tree[rt<<1].tag=1;
    tree[rt<<1|1].tag=1;
    tree[rt<<1].lx=tree[rt<<1].rx=tree[rt<<1].mx=0;
    tree[rt<<1].sum=tree[rt<<1].r-tree[rt<<1].l+1;
    tree[rt<<1|1].lx=tree[rt<<1|1].rx=tree[rt<<1|1].mx=0;
    tree[rt<<1|1].sum=tree[rt<<1|1].r-tree[rt<<1|1].l+1;
    tree[rt].tag=0;
}
if(tree[rt].tag==-1){
    tree[rt<<1].tag=-1;
    tree[rt<<1|1].tag=-1;
    tree[rt<<1].lx=tree[rt<<1].rx=tree[rt<<1].mx=tree[rt<<1].r-tree[rt<<1].l+1;
    tree[rt<<1].sum=0;
    tree[rt<<1|1].lx=tree[rt<<1|1].rx=tree[rt<<1|1].mx=tree[rt<<1|1].rx=tree[rt<<1|1].mx=tree[rt<<1|1].r-tree[rt<<1|1].l+1;
    tree[rt<<1|1].sum=0;
    tree[rt].tag=0;
}
}
  
void Pushup(int rt){
tree[rt].mx=max(max(tree[rt<<1].mx,tree[rt<<1|1].mx),tree[rt<<1].rx+tree[rt<<1|1].lx);
tree[rt].lx=tree[rt<<1].lx;tree[rt].rx=tree[rt<<1|1].rx;
if(tree[rt<<1].lx==tree[rt<<1].r-tree[rt<<1].l+1)tree[rt].lx=tree[rt<<1].lx+tree[rt<<1|1].lx;
if(tree[rt<<1|1].rx==tree[rt<<1|1].r-tree[rt<<1|1].l+1)tree[rt].rx=tree[rt<<1|1].rx+tree[rt<<1].rx;
tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
  
void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r){tree[rt].mx=tree[rt].lx=tree[rt].rx=0;tree[rt].sum=1;return;}
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
Pushup(rt);
}
  
void Update(int rt,int l,int r,int val){
if(l<=tree[rt].l && tree[rt].r<=r){
    tree[rt].tag=val;
    if(val==-1){tree[rt].lx=tree[rt].rx=tree[rt].mx=tree[rt].r-tree[rt].l+1;tree[rt].sum=0;}
    if(val==1){tree[rt].lx=tree[rt].rx=tree[rt].mx=0;tree[rt].sum=tree[rt].r-tree[rt].l+1;}
    return;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Update(rt<<1,l,r,val);
if(r>mid)Update(rt<<1|1,l,r,val);
Pushup(rt);
}
  
int GetSum(int rt,int l,int r){
if(l<=tree[rt].l & tree[rt].r<=r)return tree[rt].sum;
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l>mid)return GetSum(rt<<1|1,l,r);
else if(r<=mid)return GetSum(rt<<1,l,r);
else return GetSum(rt<<1,l,r)+GetSum(rt<<1|1,l,r);
Pushup(rt);
}
  
void Solve(int l0,int r0,int l1,int r1){
int ResL=GetSum(1,l0,r0);
Update(1,l0,r0,-1);
int ResR=GetSum(1,l1,r1);
//printf("Res:%d %d\n",ResL,ResR);
if(ResL+ResR>=r1-l1+1){Update(1,l1,r1,1);/*puts("666!");*/}
else {
    int l=l1,r=r1;
    while(l<=r){
        int mid=l+r>>1,t=GetSum(1,l1,mid);
        if(mid-l1+1-t==ResL){Update(1,l1,mid,1);return;}
        else if(mid-l1+1<ResL+t)l=mid+1;
        else if(mid-l1+1>ResL+t)r=mid-1;
    }
}
}
  
SegTree Merge(SegTree L,SegTree R){
SegTree M;
M.mx=max(max(L.mx,R.mx),L.rx+R.lx);
M.lx=L.lx;M.rx=R.rx;
if(L.sum==0)M.lx=L.lx+R.lx;
if(R.sum==0)M.rx=L.rx+R.rx;
M.sum=max(L.sum,R.sum);
return M;
}
  
SegTree GetMax(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r)return tree[rt];
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l>mid)return GetMax(rt<<1|1,l,r);
else if(r<=mid)return GetMax(rt<<1,l,r);
else {return Merge(GetMax(rt<<1,l,r),GetMax(rt<<1|1,l,r));}
Pushup(rt);
}
  
void Print(){
//puts("233:");
for(int i=1;i<=n;i++)printf("%d ",GetSum(1,i,i));
putchar('\n');
}
  
int main(){
freopen("4592.in","r",stdin);
freopen("4592.out","w",stdout);
scanf("%d %d",&n,&m);
Build(1,1,n);
//Print();
for(int i=1;i<=m;i++){
    int opt,l0,r0,l1,r1;
    scanf("%d %d %d",&opt,&l0,&r0);
    if(opt==1)scanf("%d %d",&l1,&r1);
    if(opt==0)Update(1,l0,r0,-1);
    if(opt==1)Solve(l0,r0,l1,r1);
    if(opt==2)printf("%d\n",GetMax(1,l0,r0).mx);
    //Print();
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
5
24
2016
0

[BZOJ1316] 树上的询问

考虑点分治

一棵一棵子树处理

用set判断一下有没有与len相等的值就可以了

?
bzoj 1316
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
  
const int N=10005,INF=2100000000;
  
int n,p,len[N],h[N],en,siz[N],vis[N],mx[N],val,root,ans[N],cnt;
long long dis[N*105];
set<long long> St;
  
struct Edge{
int b,next;
long long v;
}e[2*N];
  
void AddEdge(int sa,int sb,long long 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(fa!=v && !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]-mx[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 Cal(int u,int fa,long long val){
for(int i=1;i<=p;i++)if(St.find(len[i]-val)!=St.end())ans[i]=1;
dis[++cnt]=val;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa & !vis[v])Cal(v,u,val+e[i].v);
}
}
  
void DFS(int u){
val=INF;
DfsSiz(u,u);
DfsRoot(u,u,0);
St.clear();
St.insert(0);
//printf("Root:%d\n",root);
vis[root]=1;
for(int i=h[root];i;i=e[i].next){
    int v=e[i].b;
    if(!vis[v]){
        cnt=0;
        //printf("%d %d\n",cnt,v);
        Cal(v,v,e[i].v);
        for(int j=1;j<=cnt;j++){St.insert(dis[j]);/*printf("%d\n",dis[j]);*/}
    }
}
for(int i=h[root];i;i=e[i].next){
    int v=e[i].b;
    if(!vis[v])DFS(v);
}
}
 
int main(){
freopen("1316.in","r",stdin);
freopen("1316.out","w",stdout);
scanf("%d %d",&n,&p);
for(int i=1;i<n;i++){
    int u,v,w;
    scanf("%d %d %d",&u,&v,&w);
    AddEdge(u,v,w);
    AddEdge(v,u,w);
}
for(int i=1;i<=p;i++)scanf("%d",&len[i]);
DFS(1);
for(int i=1;i<=p;i++)puts(ans[i]||!len[i]?"Yes":"No");
return 0;
}
Category: BZOJ | Tags: OI bzoj

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