【BZOJ4765】普通计算姬
我没救了 将\([1,n]\)分块，每次询问的就是若干整块和若干散点的\(sum\)和 对于整块，可以先预处理 … 阅读更多【BZOJ4765】普通计算姬
分块
【BZOJ1086】【SCOI2005】王室联邦
教你树上如何分块
|
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 |
// <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; } |
【BZOJ2120】数颜色
麻麻我会分块辣 令pre[i]表示上一个和它颜色相同的地方 那么就是求[l,r]中pre[i]<l的个数 … 阅读更多【BZOJ2120】数颜色
【BZOJ2002】【HNOI2010】弹飞绵羊
嗯好我只是来学Link-cut tree的 好像说是动态树是一类问题 LCT是解决动态树的数据结构 随便怎么叫 … 阅读更多【BZOJ2002】【HNOI2010】弹飞绵羊