Algo

双倍经验2716. KD-Tree模板题。 注意一下"nth_element()" 参考： http://blog.csdn.net/jiangshibiao/article/details/34144829 code: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,D,root,x,y; struct N{ int d[2]; int l,r; int min[2]; int max[2]; }a[1000005]; bool cmp(const N&a,const N&b){ if(a.d[D]!=b.d[D]) return a.d[D]<b.d[D]; return a.d[D^1]<b.d[D^1]; } inline void up(int k,int s){ a[k].min[0]=min(a[k].min[0],a[s].min[0]); a[k].min[1]=min(a[k].min[1],a[s].min[1]); a[k].max[0]=max(a[k].max[0],a[s].max[0]); a[k].max[1]=max(a[k].max[1],a[s].max[1]); } int bd(int l,int r,int d){ D=d; int mid=(l+r)>>1; nth_element(a+l,a+mid+1,a+r+1,cmp); a[mid].min[0]=a[mid].max[0]=a[mid].d[0]; a[mid].min[1]=a[mid].max[1]=a[mid].d[1]; if(l!=mid) a[mid].l=bd(l,mid-1,d^1); if(r!=mid) a[mid].r=bd(mid+1,r,d^1); if(a[mid].l) up(mid,a[mid].l); if(a[mid].r) up(mid,a[mid].r); return mid; } const int inf=0x7fffffff; int ans; int getdis(int k){ int ret=0; if(x<a[k].min[0]) ret+=a[k].min[0]-x; if(x>a[k].max[0]) ret+=x-a[k].max[0]; if(y<a[k].min[1]) ret+=a[k].min[1]-y; if(y>a[k].max[1]) ret+=y-a[k].max[1]; return ret; } void ask(int k){ int d0=abs(a[k].d[0]-x)+abs(a[k].d[1]-y); if(d0<ans) ans=d0; int d1=(a[k].l)?getdis(a[k].l):inf; int d2=(a[k].r)?getdis(a[k].r):inf; if(d1<d2){ if(d1<ans) ask(a[k].l); if(d2<ans) ask(a[k].r); }else{ if(d2<ans) ask(a[k].r); if(d1<ans) ask(a[k].l); } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d%d",&a[i].d[0],&a[i].d[1]); } root=bd(1,n,0); for(int i=0,t;i<m;i++){ scanf("%d%d%d",&t,&x,&y); if(t==1){ n++; a[n].min[0]=a[n].max[0]=a[n].d[0]=x; a[n].min[1]=a[n].max[1]=a[n].d[1]=y; int p=root,D=0; while(1){ up(p,n); if(a[n].d[D]<a[p].d[D]){ if(!a[p].l) { a[p].l=n; break; }else{ p=a[p].l; } }else{ if(!a[p].r) { a[p].r=n; break; }else{ p=a[p].r; } } D^=1; } }else{ ans=inf; ask(root); printf("%d\n",ans); } } return 0; }

题目 题里的矩阵是这样的： A11 A12 A13… A1n-1 B1 A21 ………. A2n-1 B2 …… An-11 An-12….An-1n-1 Bn-1 C1 C2 C3… Cn-1 0 需要取整。每个元素大概有两种选择，一种是floor另一种是ceil。 这两种之间差了1。 网络流。 ...

375.QTREE 给你一棵n个点$n-1$条边的树，支持修改一条边的边权、查询两点之间路径上的最大边权。 树链剖分+线段树基础题 code: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n; int H[10005],X[20005],P[20005],tot, w[20005],E[20005],num[20005]; inline void add(int x,int y,int z,int no){ P[++tot]=y;X[tot]=H[x];H[x]=tot;E[tot]=z;num[tot]=no; } int mx[10005<<2]; int to[10005],tt,siz[10005],son[10005],top[10005],dep[10005],f[10005],tim; void dfs1(int x,int fa){ siz[x]=1;son[x]=0;top[x]=0; int mx=0; for(int i=H[x];i;i=X[i]){ if(P[i]==fa) continue; f[P[i]]=x; dep[P[i]]=dep[x]+1; w[P[i]]=E[i]; to[num[i]]=P[i]; dfs1(P[i],x); siz[x]+=siz[P[i]]; if(siz[P[i]]>mx){ mx=siz[P[i]]; son[x]=P[i]; } } } void dfs2(int x,int fa){ if(!top[x]) top[x]=x; num[x]=++tim; E[tim]=w[x]; if(son[x])top[son[x]]=top[x],dfs2(son[x],x); for(int i=H[x];i;i=X[i]){ if(P[i]!=son[x]&&P[i]!=fa){ dfs2(P[i],x); } } } int _c,_l,_r; void ask(int o,int l,int r){ if(_l<=l&&r<=_r){ _c=max(mx[o],_c); return ; }else{ int mid=(l+r)>>1; if(_l<=mid) ask(o<<1,l,mid); if(_r>mid) ask(o<<1|1,mid+1,r); } } int ask(int l,int r){ _c=0; _l=l,_r=r; ask(1,1,n); return _c; } int Ask(int a,int b){ int ret=0; while(top[a]!=top[b]){ int x=top[a],y=top[b]; if(dep[x]<dep[y]) swap(x,y),swap(a,b); ret=max(ask(num[x],num[a]),ret); a=f[x]; } if(a!=b){ if(dep[a]>dep[b]) swap(a,b); ret=max(ret,ask(num[a]+1,num[b])); } return ret; } char s[50]; void change(int o,int l,int r,int p,int k){ if(l==r){ mx[o]=k; }else{ int mid=(l+r)>>1; if(p<=mid) change(o<<1,l,mid,p,k); else change(o<<1|1,mid+1,r,p,k); mx[o]=max(mx[o<<1],mx[o<<1|1]); } } void bd(int o,int l,int r){ if(l==r){ mx[o]=E[l]; }else{ int mid=(l+r)>>1; bd(o<<1,l,mid); bd(o<<1|1,mid+1,r); mx[o]=max(mx[o<<1],mx[o<<1|1]); } } int main(){ scanf("%d",&tt); while(tt--){ tim=tot=0; memset(H,0,sizeof H); scanf("%d",&n); for(int i=1,a,b,c;i<n;i++){ scanf("%d%d%d",&a,&b,&c); add(a,b,c,i); add(b,a,c,i); } dep[1]=1; dfs1(1,-1); dfs2(1,-1); bd(1,1,n); int a,b; while(scanf("%s",s),s[0]!='D'){ if(s[0]=='Q'){ scanf("%d%d",&a,&b); printf("%d\n",Ask(a,b)); }else{ scanf("%d%d",&a,&b); change(1,1,n,num[to[a]],b); } } } return 0; } 913.QTREE2 一棵树，两个操作。 1.询问a到b的最短路。 2.询问a到b的最短路上第k个点是啥。 倍增或者树链剖分。 ...

SPOJ GSS系列是一系列序列维护的问题。 大部分用线段树，Splay等可以解决。 1043. GSS1 题意：给定长度为N的数串，M个询问查询[a,b]的的最大连续子段和。 线段树每个节点维护左端最大连续和，右端最大连续和，中间最大连续和。 就可以快速合并了。 ...

一个叫做整体二分的东西。 单个国家可以二分。 为了节约时间，可以把情况相同的一同二分。 可以用树状数组做必要的统计。 时间复杂度不明。 code: #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; int n,m; vector<int> has[300005]; int p[300005]; typedef long long LL; LL c[300005]; int k,T; int l[300005],r[300005], a[300005]; int ans[300005]; int id[300005]; bool mark[300005]; int tmp[300005]; #define lowbit(x) ((x)&-(x)) void add(int x,int k){ while(x<=m){ c[x]+=k; x+=lowbit(x); } } LL ask(int x){ LL ret=0; while(x>0){ ret+=c[x]; x-=lowbit(x); } return ret; } void Add(int x,int f){ if(l[x]<=r[x]){ add(l[x],f*a[x]); add(r[x]+1,-f*a[x]); }else{ add(l[x],f*a[x]); add(1,f*a[x]); add(r[x]+1,-f*a[x]); } } void solve(int l,int r,int L,int R){ if(L>R) return; if(l==r){ for(int i=L;i<=R;i++){ ans[id[i]]=l; } }else{ int mid=(l+r)>>1; while(T<mid) T++,Add(T,1); while(T>mid) Add(T,-1),T--; for(int i=L;i<=R;i++){ LL tmp=0; for(int j=0;j<has[id[i]].size();j++){ tmp+=ask(has[id[i]][j]); if(tmp>=p[id[i]]) { mark[id[i]]=1;break; } } } int cc=0,tot=0; for(int i=L;i<=R;i++){ if(mark[id[i]]){ id[L+cc]=id[i]; cc++; }else{ tmp[tot++]=id[i]; } } for(int i=L;i<L+cc;i++) mark[id[i]]=0; for(int i=0;i<tot;i++) id[L+cc+i]=tmp[i]; solve(l,mid,L,L+cc-1),solve(mid+1,r,L+cc,R); } } int main(){ scanf("%d%d",&n,&m); for(int i=1,x;i<=m;i++) scanf("%d",&x),has[x].push_back(i); for(int i=1;i<=n;i++) scanf("%d",&p[i]); scanf("%d",&k); for(int i=1;i<=k;i++){ scanf("%d%d%d",&l[i],&r[i],&a[i]); } k++; l[k]=1,r[k]=m,a[k]=0x3fffffff; for(int i=1;i<=n;i++) id[i]=i; solve(1,k,1,n); for(int i=1;i<=n;i++){ if(ans[i]==k) puts("NIE"); else printf("%d\n",ans[i]); } return 0; }

题解： 简单的说就是给定平面上n个点，求这n个点组成三角形的最小面积。 如果分别枚举三个点的话是$O(n^3)$的，时间无法承受。 如果枚举了两个点a,b。设它们间的距离是L。如果以点a,b所在直线为y轴的话，与其他点所组成的三角形的面积$S=L*|x|/2$，x是其他点在这个坐标系中的横坐标。可以看出面积最小的就是离这个坐标系y轴最近的一个点。如果我们能够快速的得知最近的点的话，就可以将复杂度降低到$O(n^2)$。 ...

题解： 参考小胖的奇偶那道题。 那道题用的并查集维护。 如果知道 i..j 之间奇偶性的话，实际上知道的是 sum[j]-sum[i-1]的奇偶性（sum为前缀和）。 ...

题解: 鉴于F[44]> 1e9。于是可以把两两乘积算出来，枚举即可。 code: #include<cstdio> #include<cstring> #include<algorithm> #include<set> //by zrt //problem: using namespace std; int f[46]; set<int> s; int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif f[0]=0;f[1]=1; for(int i=2;i<=45;i++){ f[i]=f[i-1]+f[i-2]; } int MAX=1e9; for(int i=0;i<=45;i++) s.insert(f[i]); for(int i=3;i<=45;i++){ for(int j=i;j<=45;j++){ if(f[i]*1LL*f[j]<=MAX){ s.insert(f[i]*f[j]); } } } int t,x; scanf("%d",&t); while(t--){ scanf("%d",&x); if(s.count(x)){ puts("TAK"); }else{ puts("NIE"); } } return 0; }

题解： 若d[x]<a[x]，杀这个怪是有收益的，可以按d值从小到大杀。 若d[x]>a[x]，考虑反过来的过程，如果都杀完后血量是S，那么从后向前就是 S-a[i]+d[i]，相当于第一种情况，需要按a值从大到小杀。 ...

题解： 定义F[i]为前 i-1 只奶牛工作效率的最大值。 sum[i]是Ei的前缀和。 有F[i]=max{F[j]+sum[i-1]-sum[j]} (i-j<k) 可以用单调队列维护 F[j]-sum[j] 。 ...