page重要性质圆上的矩形对角线一定等于直径直角即该两点间弧长

Author:

BZOJy，ans=(nuessf[i][j][k]表示i行，有j列有1个子，有k列有2个子。(c[i][j]ijj0,1,2）i行不放子：f[i+1][j][k]+=if[i+1][j+1][k]f[i][j][k]*c[m-j-k][1]1个子的那一列f[i+1][j-1][k+1f[i][j][k]*c[j][1]i2个子，三种情况。n行的每一种情况都累加。?ryona题意：一棵树，每个点都有权值。q个询问，询问x中的第k大值。nlogn^2+qlogn或(n+q)logn同时对每个答案的值二分。每次扫描时用线段树，进出x时各询问一遍mid[x]。复杂度qlogW^2。dfsk大。划分树/函数式平衡树。复杂度(n+qlognodnlognl?ersf[i,x1,x2,y1,y2]i1x1,x22最后送入的两1<=i<=100000,ff[i,*,*,*,*]的影响，所以我们就可以使用滚动数组优化空间。rs45度.....(x,y)(x-这样有什么好处呢我们需要查询,(xi,yi)|xi-x|+|yi-y|<=d这些点,在图上表现出来是一个斜着的正方形(现实中肯定倒然后我们这样转换(xi-yi,xi+yi),(x-3维就是立体转为平面.....此时因为坐标不大..就没必要用树状数组统计一个面了...map[z][x][y]z个面(x,y)-(0,0)这查询:zO(1)得到范围。坐标范围一定要注意,要不+d,-个d就溢出了......维复杂度nlogn维复杂度nlogn维复杂度W^3+n*W4hypercube3nlogm^3。小结：n1-norm2^(n-1)infinity-norm。ining???转移:f[i][j][v]=min(f[lch[i]][p][v]+f[rch[i]][q][v]+dis(i,v)//ip+q=j,f[lch[i]][p][i]+f[rch[i]][q][v]//ip+q+1=j)n^2*k^2?rmula连通性状态压缩DP。括号表示法/最小表示法。可以用化+hash使转移的复杂度降为O(1)。复3^(n+1)*n*n*m/3^(n+1)*n*m。lor?nlogn鼠double。(std精度有误离散，扫描线，树状数组部分和。复杂度nlognueryhash，增量。复杂度m*Σlen树状数组。复杂度(n+m)*len+mlogn。pressf[i][j][k]iijkoupkruskaln^2logn入。若全部加入后达到要求，则对这一部分快排做kruskal。通过调整平衡系数DDn^2+n^2/D*lognD=lognn^2(logn+α(n))ozenNova2-sat。tarjan。看看有没有两个的量在一个强连通分量里。复杂度O(n)?y->xv[x]-v[y]。2a->b,b->c1,b->c2，2次调整bb变为b+c2-c1c1=c2，否则+inf推论：第一个分叉点下方所有边权都相等且分叉点的儿子全为叶节点或分叉点上下所有边权都相等。现在一次操作即为交换(a,b):k1和所有(b,ci):k2ans变化量：k1*size[b]+k2*(size[b]-1)->k2*size[b]+k1*(size[b]-1) nlognf[i]ii位置还在里面，就可以更早的减少交换缓存的次数。用堆ar]gatherar]balloc如何证明这个贪心策略呢下面是我的证明…1、Lj>Ri||Lk>Rii牛，jk2、Lj<=Li||Lk<=Li那么，j和ki3、Li<=Lj<=Ri&&Li<=Lk<=Rip=max(Lj,Lk)i牛，j牛和k牛能同时取，那必然能共存，那么造成了，所以不可能。ar]starcar]starc?1789:Ahoi2008]NecklaceY1786:Ahoi2008]Pair会1787:Ahoi2008]Meetunttwork0的边。se选?ay9]cavli倒序预处理出加点的顺序。平衡树动态凸包。复杂度nlogn?树链剖分+堆+nlogn^2qsqrt(n)lognAMID单调队列矩形内最值。复杂度n*mn同 使用线段相交，离散切大条(n^2条)n^3lognistory2692:表达式计数()简化版?单调队列矩形内最值。复杂度n*mributing二分答案，n^2DP，剪枝。见<<周动态规划的非常规优化>>。f[i][j]ij的最大矩形数。p,qpqi。每次选择p和q中较大者尽量往回走（pre函数，然后用走的次O(n)O(n^2log但实际运行速度相当不错，即使是数据也能在0.3s内出解先求出幸运数字，删掉倍数，然后容斥戏（看起来不靠谱，可是过了票 就行了。比如说买：d[i][j]=max{d[i-w-1][k]-(j-k)*AP[i-w-1]}=max{d[i-w-1][k]+k*AP[i-型三1]}1]}j*AP[iw1]把未来可能用的决策放进一个单调队列里，保证随kd[iw1][kjk)*AP[--]递减。还要注意一点：第nn+W+天。复杂度n*c?n+10，m-11（注意，01nm的关系调换了）的数列数，我们考虑01有i个，0i+12i+11i+(m-(i+1))=m-1，0的个数为n+1，于是一个n+10，m-11的数列。n+10，m-11n>=m2i+1使得2i+101多，把后面的数取反即可。logn^2log0ms(nlognwlhjong1.f[i1][i][j][k]i1个数,3位是(i,j,k)dfs(DP)+hash2.1-n1,2,53a+4b的形式表示出来。f[i1][i][j][k]表示:i2位是(i,j)，koknlognmeZ游戏字符串用hash映射成数字，使用sy。复杂度nlognouble的LostickettoBZOJ1402：TickettoRiden^2DP??n^2WinterCamp]?WinterCamp]?otaWinterCamp]。子f[i,j]f[i,j]ijf[i,j]=sigma(f[i-1,k]){jk的终点，jk非同一条边的两个方向矩阵乘法+n^3logt跑最小费用最大流，spfa+堆优化，zkw线段树/nlogn。树套树/nlogn^2llaxiadijkstra(n^2)求出4个点分别到其他点的最短路径。用dijkstra DP的转移。f[i]i这个点最长的链的长度