Bzoj

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

一个叫做整体二分的东西。 单个国家可以二分。 为了节约时间，可以把情况相同的一同二分。 可以用树状数组做必要的统计。 时间复杂度不明。 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)$。 ...