Algo

学习 http://www.docin.com/p-598829500.html 线段树合并中的一道例题。 详细见那个课件。 复杂度$O(nlgn)$. 需要注意下空间 code: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; int n; int LS[400005],RS[400005]; int cc; int Root; int w[400005]; int siz[400005]; int ls[15000500],rs[15000500],sum[15000500]; int num; int stk[15000500],top; int getnew(){ if(top>0){ ls[stk[top-1]]=rs[stk[top-1]]=sum[stk[top-1]]=0; return stk[--top]; } return ++num; } void add(int &o,int l,int r,int pos){ if(!o) o=getnew(); if(l==r){ sum[o]=1; }else{ int mid=(l+r)>>1; if(pos<=mid) add(ls[o],l,mid,pos);else add(rs[o],mid+1,r,pos); sum[o]=1; } } int read(){ int x; scanf("%d",&x); int now=++cc; if(!x){ LS[now]=read(); RS[now]=read(); siz[now]=siz[LS[now]]+siz[RS[now]]+1; }else{ add(w[now],1,n,x); siz[now]=1; } return now; } LL ans; LL ans0,ans1; int merge(int a,int b,int l,int r){ if(!a) return b; if(!b) return a; int now=getnew(); int mid=(l+r)>>1; int lft=sum[ls[a]]+sum[ls[b]]; int rgt=sum[rs[a]]+sum[rs[b]]; ans0+=sum[rs[a]]*1LL*sum[ls[b]]; ans1+=sum[ls[a]]*1LL*sum[rs[b]]; if(lft<rgt){ rs[now]=merge(rs[a],rs[b],mid+1,r); ls[now]=merge(ls[a],ls[b],l,mid); }else{ ls[now]=merge(ls[a],ls[b],l,mid); rs[now]=merge(rs[a],rs[b],mid+1,r); } stk[top++]=a; stk[top++]=b; sum[now]=sum[ls[now]]+sum[rs[now]]; return now; } void dfs(int x){ if(!LS[x]) return; else{ if(siz[LS[x]]<siz[RS[x]]) dfs(RS[x]),dfs(LS[x]); else dfs(LS[x]),dfs(RS[x]); ans0=ans1=0; w[x]=merge(w[LS[x]],w[RS[x]],1,n); ans+=min(ans0,ans1); } } int main(){ http://www.docin.com/p-598829500.html scanf("%d",&n); Root=read(); dfs(1); printf("%lld\n",ans); return 0; }

题意: 给你n个不相交的凸多边形或圆，每个图形有一个权值。 询问m次，从一个点到另一个点，穿越过的图形的权值异或和。 题解: 扫描线+树链剖分。 这些图形的互相包含关系形成了一些树。 每次相当于求从树上一个点走到另一个点边上的权值异或和。 扫描线算法$O(nlgn)$求出这颗树，然后树链剖分维护下就好了。 ...

贪心一下。 接水的时候肯定是从小到大接。 好像没什么性质。莫队好了。 观察到奇怪的强制在线方法。。。 类似[糖果公园/苹果树]做法。 块大小没仔细算，直接$n^{0.5}$的，卡了70s评测姬 233。 复杂度不明。。 ...

求红黑树红色节点的最大最小值。 参考 百度百科 性质1. 节点是红色或黑色。 性质2. 根节点是黑色。 性质3 每个叶节点（NIL节点，空节点）是黑色的。 性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) 性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 ...

求最长双回文串. 首先Manacher求回文半径p[i]。 然后求每个点最左是可以由哪一个点扩展来的left[i]。 具体就是拿个数组弄一个 i+p[i] 的后缀min。 刚开始想单调队列好像也行。 然后对于一个点以它为右回文串中心的最大双回文串长度就是i-left[i-p[i]+1]. 取个max就行了。 ...

写个高精度。 然后扫过去就行了。 抽题器竟然抽了这么水的题233. code: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int k; struct N{ int a[100]; friend N operator + (const N&a,const N&b){ N c; for(int i=0;i<100;i++) c.a[i]=a.a[i]+b.a[i]; for(int i=0;i<99;i++) c.a[i+1]+=c.a[i]/10,c.a[i]%=10; return c; } N mul2(){ N b; for(int i=0;i<100;i++) b.a[i]=a[i]*2; for(int i=0;i<99;i++) b.a[i+1]+=b.a[i]/10,b.a[i]%=10; return b; } void out(){ int top=99; while(top>0&&a[top]==0){ top--; } while(top>=0) printf("%d",a[top--]); puts(""); } }po2[105],ans; char s[205]; int p; void solve(int k){ if(s[p]=='0') ans=ans+po2[2*k],p++; else if(s[p]=='1'){ p++; }else{ p++; solve(k-1); solve(k-1); solve(k-1); solve(k-1); } } int main(){ po2[0].a[0]=1; for(int i=1;i<=100;i++){ po2[i]=po2[i-1].mul2(); } scanf("%d",&k); scanf("%s",s+1); p=1; solve(k); ans.out(); return 0; }

首先看正着的三角形。 每个点向右上方可以扩展的距离叫 mxl[],左上方叫mxr[]。 枚举三角形右下端点。 设右下为j.坐下为i。 需要满足 底边i..j 联通，并且$j-i<=mxr[j]$且$j-i<=mxl[i]$。 把i挪到一边，把j挪到一边就是 $j-mxr[j]<=i$且$j<=mxl[i]+i$ ...

题目是求三角形面积并。$n<= 100$ 就像hwd冬令营上讲的。 先$n^2$求交点。 然后在每两个交点之间求梯形中位线总长，然后求和。 ps.听说simpson也可以。。 …被卡精度了… ...

题意是仙人掌图直径。 大概做法就是树的直径dp求法加上基环树的技巧特技。 改了好长好长时间啊。 参考题解: http://z55250825.blog.163.com/blog/static/150230809201412793151890/ 很细致。。 code: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m; int H[50005],X[20000005],P[20000005],tot=1; int dp[50005]; inline void add(int x,int y){ P[++tot]=y;X[tot]=H[x];H[x]=tot; } int stk[50005],top; int dfn[50005]; int low[50005],tim; int ans; int list[100005],t; struct N{ int pos,w; N(int a=0,int b=0){ pos=a;w=b; } }; struct dddl{ N q[100005]; int h,t; void clear(){ h=t=0; } void pop(int x){ if(q[h].pos==x) h++; } int ask(){ return q[h].w; } void push(N a){ while(h<t&&q[t-1].w<=a.w) t--; q[t++]=a; } }q; bool debug; int fa[50005]; void dfs(int x){ dfn[x]=low[x]=++tim; for(int i=H[x];i;i=X[i]){ if(P[i]==fa[x])continue; if(fa[P[i]]&&dfn[P[i]]>dfn[x]){ //find circle int k=P[i]; t=0; while(k!=x) list[t++]=k,k=fa[k]; list[t++]=x; int mx=0x80808080; for(int j=0;j<t;j++){ list[j+t]=list[j]; mx=max(mx,dp[list[j]]+min(j+1,t-j-1)); } q.clear(); q.push(N(0,dp[list[0]])); int adds=0; for(int j=1;j<2*t;j++){ q.pop(j-t/2-1); adds++; ans=max(ans,dp[list[j]]+adds+q.ask()); q.push(N(j,dp[list[j]]-adds)); } dp[x]=max(dp[x],mx); }else if(!low[P[i]]){ fa[P[i]]=x; dfs(P[i]); low[x]=min(low[x],low[P[i]]); if(low[P[i]]>dfn[x])ans=max(ans,dp[x]+dp[P[i]]+1),dp[x]=max(dp[x],dp[P[i]]+1); }else low[x]=min(low[x],dfn[P[i]]); } ans=max(ans,dp[x]); } int main(){ scanf("%d%d",&n,&m); for(int i=0,k;i<m;i++){ scanf("%d",&k); int last; scanf("%d",&last); for(int i=1,t;i<k;i++){ scanf("%d",&t); add(last,t);add(t,last); last=t; } } dfs(1); printf("%d\n",ans); return 0; }

给你一个字符集合,你从其中找出一些字符串出来. 希望你找出来的这些字符串的最长公共前缀*字符串的总个数最大化. 这个问题很简单吧..用trie随便搞一搞。 但是Input是这么写的: 第一行给出数字N.N在[2,1000000] 下面N行描述这些字符串,长度不超过20000 。总字符不超过20000。 ...