分块 – 徐亦轲的博客

【BZOJ4765】普通计算姬

2017年3月7日2017年3月7日 by 徐亦轲

我没救了将\([1,n]\)分块，每次询问的就是若干整块和若干散点的\(sum\)和对于整块，可以先预处理 … Read more【BZOJ4765】普通计算姬

【BZOJ1086】【SCOI2005】王室联邦

2017年1月29日 by 徐亦轲

教你树上如何分块

// <1086.cpp> - 01/29/17 19:24:30
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=1010;
const int MAXM=2010;
const int INF=1e9;
int bt,b[MAXN],next[MAXM],to[MAXM];
inline void add(int x,int y){
    next[++bt]=b[x];b[x]=bt;to[bt]=y;
    next[++bt]=b[y];b[y]=bt;to[bt]=x;
}
bool vis[MAXN];
int B,t,s[MAXN],cnt,h[MAXN],in[MAXN];
int dfs(int x){
    vis[x]=1;
    int size=0;
    for(int i=b[x];i;i=next[i]){
        if(vis[to[i]])continue;
        if((size+=dfs(to[i]))>=B)
            for(h[++cnt]=x;size;size--)in[s[t--]]=cnt;
    }
    s[++t]=x;
    return size+1;
}
int main(){
    int n=gi();B=gi();
    for(int i=1;i<n;i++)add(gi(),gi());
    dfs(1);
    while(t)in[s[t--]]=cnt;
    printf("%d\n",cnt);
    for(int i=1;i<=n;i++)printf("%d ",in[i]);putchar('\n');
    for(int i=1;i<=cnt;i++)printf("%d ",h[i]);
    return 0;
}

// <1086.cpp> - 01/29/17 19:24:30

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=1010;

const int MAXM=2010;

const int INF=1e9;

int bt,b[MAXN],next[MAXM],to[MAXM];

inline void add(int x,int y){

next[++bt]=b[x];b[x]=bt;to[bt]=y;

next[++bt]=b[y];b[y]=bt;to[bt]=x;

}

bool vis[MAXN];

int B,t,s[MAXN],cnt,h[MAXN],in[MAXN];

int dfs(int x){

vis[x]=1;

int size=0;

for(int i=b[x];i;i=next[i]){

if(vis[to[i]])continue;

if((size+=dfs(to[i]))>=B)

for(h[++cnt]=x;size;size--)in[s[t--]]=cnt;

}

s[++t]=x;

return size+1;

}

int main(){

int n=gi();B=gi();

for(int i=1;i<n;i++)add(gi(),gi());

dfs(1);

while(t)in[s[t--]]=cnt;

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

for(int i=1;i<=n;i++)printf("%d ",in[i]);putchar('\n');

for(int i=1;i<=cnt;i++)printf("%d ",h[i]);

return 0;

}

【BZOJ2120】数颜色

2016年7月20日 by 徐亦轲

麻麻我会分块辣令pre[i]表示上一个和它颜色相同的地方那么就是求[l,r]中pre[i]<l的个数 … Read more【BZOJ2120】数颜色