Oi

求最长双回文串. 首先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。 ...

双倍经验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]的的最大连续子段和。 线段树每个节点维护左端最大连续和，右端最大连续和，中间最大连续和。 就可以快速合并了。 ...