make_it_for_good-CSDN博客

原创智障错误大全

1. for(int i=1,j;i<=top;i++) { j=i; while(st[j]==st[i]&&j<=top)j++;j--; tmp=(ll)tmp*njc[j-i+1]%p; i=j; }st这个栈多次使用，一开始没写j<=topj<=top 然后就gg了。。。。

2016-09-06 09:21:38 434

原创我根本不懂数学

一.结论： Ax≡B(modC)Ax\equiv{B}(mod C) 有解的充要条件为B|gcd(A,C)B|gcd(A,C) 且解的个数有gcd(A,C)gcd(A,C) 个。证明（扯淡）：方程ax≡b(modc)ax\equiv{b}(mod c)（a,c互质）在[0,c)[0,c) 内有且仅有一个解。那么原式就有gcd(A,C)gcd(A,C) 个解。二.结论：f[i]f[i]表示斐波那契

2016-08-27 20:22:05 852

原创 codeforces 755G 多项式

题意：n个球，分成一些组，一个组里可以有1个球或相邻的两个球。一个球只能在一个组里或不在任何组里。求组数为1，2，…m时的方案数。正常的递推式：f[i][j]f[i][j] 表示i个球分成j组的方案数。 f[i][j]=f[i−1][j]+f[i−1][j−1]+f[i−2][j−1]f[i][j]=f[i-1][j]+f[i-1][j-1]+f[i-2][j-1]那么 f[n]f[n] 的生

2017-04-10 10:19:43 853

原创 bzoj 3519 线段树

题意说的什么jb玩意写完之后我都开始怀疑人生了。。。每行每列开个线段树，维护加点删点找前驱后继（好像可以set）第一问找询问的点两个方向的第一个点，看是不是相同颜色。第二问把一开始能选的放进一个队列，然后每删除一个点只会影响到上下左右第一个点的答案。一坨判断#include <bits/stdc++.h>using namespace std;#define N 110000#

2017-03-11 15:49:13 548

原创 bzoj 4727 [POI2017]Turysta 竞赛图

对于一个竞赛图：一定存在哈密顿路径如果强连通，一定存在哈密顿回路 tarjan缩点后得到的拓扑图是一条有向链，上方的点向下方的点连边。#include <bits/stdc++.h>using namespace std;#define N 2100int n,top,scc,cnt;int mp[N][N],dfn[N],low[N],st[N],ins[N],bel[N];i

2017-03-09 16:22:48 816

原创 bzoj 4562 [NOI2016]循环之美莫比乌斯反演

几年没写题解来更一篇。首先有一个规律就是如果满足条件那么gcd(y,k)=1gcd(y,k)=1 那么答案就是 ∑i=1n∑j=1m[gcd(i,j)=1][gcd(j,k)=1]\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i,j)=1][gcd(j,k)=1] =∑j=1m[gcd(j,k)=1]∑i=1n∑t|i,t|jμ(t)=\su

2017-03-08 19:23:32 693

原创 bzoj 3630 [JLOI2014]镜面通道计算几何网络流

只要上下边界不连通就可以。然后两个图形相交就连边，拆点跑网络流就行了。判相交比较麻烦（抑或是我写得麻烦）#include <bits/stdc++.h>using namespace std;#define N 310#define inf 1e9#define eps 1e-8#define M 1100000int n,X,Y,c1,c2,cnt,S,T,tot,ans;i

2017-01-24 11:37:34 572

原创 3551 [ONTAK2010]Peaks加强版 kruskal重构树可持久化线段树

名字是大爷起的。不过这个东西好像确实很厉害的样子。。一开始在想一个可持久化并查集+线段树合并+可持久化线段树维护根的做法。不过看到128M的内存果断选亡。。。设最初的所有点点权为0. 在kruskal的时候，每加一条边时新加一个点，两个并查集的根并到这个点上，这个点的点权是这条边的边权。然后这个东西构成了一个堆式的结构，父节点的点权大于儿子的点权。并且叶节点是最初的点。两个点间

2017-01-06 19:32:41 539

原创 bzoj 3545 [ONTAK2010]Peaks 平衡树启发式合并

把所有询问离线下来，从小到大枚举边合并，用并查集维护连通块，每块维护一个平衡树，合并时启发式合并。一开始写的是splay找前驱后继然后插入TLE，改成插到叶子上才过。不过在官网还是T的。splay常数果然大。。。这题读入太大，要用读入优化。。。插入时插成叶子：#include <bits/stdc++.h>using namespace std;#define N 110000#def

2017-01-06 19:15:06 270

原创 uoj #86 mx的组合数 FFT 原根

把l,r的条件看成前缀相减，那么就是求Cnx%p(1≤x≤bound)C_x^n\%p(1\le x\le bound) 设n的p进制形式为a1a2a3....acnta_1a_2a_3....a_{cnt} bound的p进制形式为b1b2b3.....bcntb_1b_2b_3.....b_{cnt} 由lucas定理原式为∏Caixi\prod C_{x_i}^{a_i}。设g[i]

2017-01-06 08:22:01 650

原创 bzoj 3533 [Sdoi2014]向量集凸包

和2961求的是一个东西。维护上下两个凸包，然后三分。上次写得是一个正常的线段树，填满一个区间就合并。这次写了一个奇怪的按二进制维护log棵类线段树状物的东西，然后发现跑得比线段树慢。。。#include <bits/stdc++.h>using namespace std;#define ll long long#define N 810000const ll inf=~0ll

2017-01-05 10:56:52 342

原创 bzoj 2961 共点圆 CDQ分治凸包

凸包一向写得蛋疼，何况这题有两个凸包。。。条件(x1−x)2+(y1−y)2>x2+y2(x1-x)^2+(y1-y)^2>x^2+y^2 化一下可以变成 x12+y12−2xx1−2yy1>0x1^2+y1^2-2xx1-2yy1>0 最大化x12+y12−2xx1−2yy1x1^2+y1^2-2xx1-2yy1 就是最小化b=2xx1+2yy1b=2xx1+2yy1 y=by1+(−x

2017-01-04 21:40:49 627

原创 bzoj 2827 千山鸟飞绝平衡树

splay和我的常数加到一起简直是灾难。。。坐标没有用，把它离散掉。然后splay维护一个最大值和次大值和最大size的标记。插入的时候查询一下，打个标记。#include <bits/stdc++.h>using namespace std;#define N 410000#define M 810000#define ll long long#define ls(x) ch

2017-01-04 08:10:06 790

原创 poj 2676 Sudoku DLX

数独，用舞蹈链解决。建4∗9∗94*9*9 列，分别表示第i行数j的位置，第i列数j的位置，第i格数j的位置，位置为(i,j)的数是否被使用。最后一个9∗99*9 是限制每个格只有一个数。建9∗9∗99*9*9 行，表示格(i,j)填数k的情况。注意要加一个A*优化#include <stdio.h>#include <string.h>#include <algorithm>

2017-01-02 11:19:51 463

原创 bzoj 2879 [Noi2012]美食节费用流

建图和修车是一样的，不过这题需要动态加边。注意这题费用流必须跑一条路加一条路，不能跑多条路后加边因为如果跑多条路后加边可能导致跑了不是最优的解，然后加了一条边权较小的边出现负环。不过如果每次跑一条路加一条路可以保证每次取的都是最优解。#include <bits/stdc++.h>using namespace std;#define inf 1e9#define N 11000#def

2016-12-29 21:11:46 389

原创 bzoj 2402 陶陶的难题II 01分数规划树链剖分线段树维护凸包

先01分数规划一下，然后这个东西就是求(qj−kpj)+(yi−kxi)(q_j-kp_j)+(y_i-kx_i) 的最大值。把qi−kpiq_i-kp_i 和yi−kxiy_i-kx_i分开考虑，这是一个斜率的式子，只会取上凸包的点。因此树剖把这个东西放到线段树上，线段树每个节点维护一个凸包。然后求的时候三分就行了。虽然这个东西看起来是log4log^4 的，不过01分数规划如果用迭代

2016-12-29 18:07:13 967

原创 hdu 5279 YJC plays Minecraft 分治 NTT

答案中每个岛上一定是一坨森林。岛之间的边可以有可以没有。不过要减去所有岛都1和a[i]连通并且所有岛之间的边都存在的情况。设f[x]表示对于一个城镇数为x的岛，连成森林的方案数。那么f[x]=∑i=0x−1f[i]∗v[x−i]∗Cx−i−1x−1f[x]=\sum\limits_{i=0}^{x-1}f[i]*v[x-i]*C_{x-1}^{x-i-1} =(x−1)!∑i=0x−1

2016-12-29 14:26:25 638

原创 bzoj 2329 [HNOI2011]括号修复 splay

区间赋值，区间翻转，区间反转，也就splay能干这些事吧。。。维护一个区间最小值low，区间最大值up，区间和sum，然后一段区间的答案是 (−low[x]+1)/2+(sum[x]+(−low[x]+1)/2∗2)/2(-low[x]+1)/2+(sum[x]+(-low[x]+1)/2*2)/2再打一坨标记就行了，注意标记重叠#include <bits/stdc++.h>using n

2016-12-29 09:15:26 376

原创 bzoj4405 [WC2016] 挑战NPC 带花树

Orz vfk 前一段写过一次带花树，现在已经不会敲板子了。。把每个筐拆成一个三角形，每个球向匹配的筐的三个点连边，然后跑带花树。答案是匹配数-n，因为每个半空的筐都会自己得到一个匹配，而且一定存在一种最大匹配使所有球匹配。感觉这种题即使考场上想出来了板子能不能敲对还是个问题（汗）。。。#include <bits/stdc++.h>using namespace std;#define

2016-12-28 19:58:37 496

原创 bzoj 2300 [HAOI2011]防线修建 splay维护凸包

正常的splay维护凸包不支持删点，把操作倒过来变成加点。 HAOI真心良心呀，边界都给好了。。。#include <bits/stdc++.h>using namespace std;#define N 110000#define M 210000#define which(x) (ch[fa[x]][1]==x)int d,n,Q,root;int X[N],Y[N],vis[N]

2016-12-28 15:00:35 377

原创 hdu 5322 Hope 分治 NTT

设f[i]f[i] 表示长度为i时的答案，那么 f[i]=∑i=1nCj−1i−1∗f[i−j]∗(j−1)!∗j2f[i]=\sum\limits_{i=1}^{n}C_{i-1}^{j-1}*f[i-j]*(j-1)!*j^2 然后这个东西直接分治fft就行了。推错式子害死人。。。#include <bits/stdc++.h>using namespace std;#define

2016-12-28 11:21:05 454

原创 bzoj 2730 [HNOI2012]矿场搭建点双连通分量

如果只有一个点双，答案为2，随便选两个点。否则求每个点双里有几个割点，如果割点个数大于等于2，那么这个点双中不用选点，如果个数为1，那么点双中需要选一个不是割点的点。#include <bits/stdc++.h>using namespace std;#define N 510#define ll long longint m,tot,cnt,cr,top,ans,Case,scc;

2016-12-28 08:43:52 391

原创 hdu 3749 点双连通分量

留个模板(求所有点双) 求所有点双时开个栈维护。注意求点双时记录一下每个子树开始的位置，如果这个点是对于这个子树的割点，那么点双是这个子树在栈中剩下的点+这个点本身。#include <bits/stdc++.h>using namespace std;#define N 5100#define M 21000int n,m,Q,tot,cnt,tim,Case,top,scc;int

2016-12-27 21:12:40 341

原创 bzoj 2006 [NOI2010]超级钢琴二分答案可持久化线段树

大家好，这里是一个log^2的智障。看到第K大直接想到二分答案+主席树，主席树维护区间的个数和区间的和。良心BZ测总时限竟然16s过了。。。原来正解就是主席树套个堆。。。#include <bits/stdc++.h>using namespace std;#define N 1010000#define M 20000000#define ll long long#define

2016-12-27 18:18:56 322

原创 bzoj 1758 [Wc2010]重建计划 01分数规划点分治单调队列

直接01分数规划，然后把树分治查找所有链，然后合并时就是查一个定长区间的最大值，宽搜离线下来然后单调队列搞就行了。不过我想说这题卡常数。。。卡常数。。。常数。。数。。不过好像三个月之前做就没有这事了。。。树分治可以预处理快了两倍，01分数规划从二分改成迭代快了四倍+，然而bz上还是跑了20+s。。。#include <bits/stdc++.h>using namespace std;#de

2016-12-26 19:27:18 353

原创 bzoj 2759 一个动态树好题 LCT 数学

果然是一道动态树好题。《论LCT的正确使用方法》以及《出题人真会玩》系列把每个点向p连一条边，那么这是一个基环树森林。先从环上拆下来一条边并记录这条边指向的点，然后这玩意就变成了一坨有根树。设根为x1，根指向的点为x2，那么所有点都可以用关于x2的一次函数表示。然后用x2本身的一次函数可以解出x2。然后用LCT维护这坨有根树。 splay上每个点维护用这个点子树中最小（最靠左，原树

2016-12-26 11:27:25 503

原创 bzoj 1453 双面棋盘 LCT 并查集

把每个格子看成点，同色格子之间连边。 LCT维护关于删除时间的最大生成树。设有x1个原来与当前格子同色的连通块与当前格子断开，x2个原来与当前格子不同色的连通块与当前格子连通，那么会增加x1-1个当前格子原来颜色的连通块，减少x2-1个当前格子现在颜色的连通块。写得比较挫，初始状态用的并查集。。。#include <bits/stdc++.h>using namespace std;#

2016-12-24 15:05:54 329

原创 4574 [Zjoi2016]线段树 dp

这题的前缀和开始没有想到。如果不用前缀和状态是五维的。。。由于数据随机所以不会有两个相等的数。最终答案是求每个数在所有方案下的取值的和。对于每个数dp一下，设当前数为val，区间[L,R]为以当前数为最大值的最大区间。设f[i][l][r]f[i][l][r] 表示前i个询问，区间[L,R]剩余的小于等于当前数的区间为[l,r]的方案数。然后转移时处理一个前缀和可以O(1)转移。

2016-12-23 07:55:47 303

原创 bzoj 4321 queue2 dp

设f[i][j][0/1]f[i][j][0/1] 表示前i个数有j个非法的，i是否与i-1相邻的方案数，转移看代码吧。。#include <bits/stdc++.h>using namespace std;#define N 1100#define mod 7777777#define ll long longint f[N][N][2],n;void upd(int &x,int

2016-12-22 17:58:13 324

原创 bzoj 4318 OSU! 概率dp

这道题只是想告诉我们只有两个期望无关时才可乘，因此平方的期望不等于期望的平方。。。需要维护f1[i]表示到i连续的个数的期望，f2[i]表示到i连续的个数平方的期望，f3[i]表示到i连续的个数立方的期望#include <bits/stdc++.h>using namespace std;#define N 110000int n;double f1[N],f2[N],f3[N],pr

2016-12-22 15:02:12 261

原创 bzoj 4197 [Noi2015]寿司晚宴 dp 容斥

注意到小于n√\sqrt{n} 的质数最多有8个。而大于n√\sqrt{n} 的质因子每个数至多有1个。因此状压<n√<\sqrt{n} 的质数。设f[i][j]f[i][j] 表示A选的<n√<\sqrt{n} 的质数集合为i的子集，B选的<n√<\sqrt{n} 的质数集合为j的子集的方案数。预处理num[i][j]num[i][j] 表示<n√<\sqrt{n} 的质因子集合为i，>n

2016-12-22 13:52:12 287

原创 bzoj 4145 [AMPPZ2014]The Prices dp

设f[i][j]f[i][j]表示前i个商店买了j集合的物品的最小花费。 g[i][j]g[i][j] 表示第i个商店的买了j集合的物品的最小花费（含路费）。注意到如果g[i][x]≤g[j][x]g[i][x]\le g[j][x] 那么去i买x的物品一定不比去j买x的物品差。因此对于一种物品集合只需要有一个商店转移时转移这个集合就行。复杂度O(n2m+3m)O(n2^m+3^m)

2016-12-22 09:52:38 319

原创 bzoj 4008 [HNOI2015]亚瑟王期望dp

先考虑这么一个式子： Pr第2次选2=Pr第2次不选1∗Pr第1次不选2∗Pr选2Pr_{\text{第2次选2}}=Pr_{第2次不选1}*Pr_{第1次不选2}*Pr_{选2} 其中Pr表示概率。这个式子是错的，因为第1次不选2和第2次不选1的概率不是独立的。所以直接算的方法gg了。设f[i][j]f[i][j] 表示前i个点有j个被选过的概率。 g[i]g[i] 表示点i被选

2016-12-20 21:27:36 444

原创 bzoj 4000 [TJOI2015]棋盘 dp 矩乘

逗比题面，毁我青春行列编号从零开始。。。然后我以为那个点在最上面那排。。。妈蛋那样要记两排状态！！！点在中间那排的话记一排状态矩乘转移就行了。#include <bits/stdc++.h>using namespace std;#define ui unsigned intint n,m,p,K;int a[4][7],able[71];ui ans;struct Matr

2016-12-20 18:42:04 522

原创 bzoj 3879 SvT 后缀数组 rmq 并查集

先求出后缀数组。对于每组询问，按rank排序，求相邻两个的lcp，按lcp从大到小合并相邻两个，用并查集维护。#include <bits/stdc++.h>using namespace std;#define N 510000#define M 3100000#define ll long long#define mod 23333333333333333llint n,m,Q;

2016-12-20 15:41:01 434

原创 bzoj 3851 2048 dp

一开始sb看错题，没看见两个相等的数拼在一起。如果只有两个相等的数能拼在一起，那只有2的整数次幂有用。设f[i][j]f[i][j] 表示选了202^0 到 2i2^i 的数和为j的方案数。注意到只要和大于等于2048就有解，因此第二维只需要到2048（表示大于等于2048）。然后对组合数求一个后缀和，当第二维大于2048时直接用后缀和转移。#include <bits/stdc++

2016-12-20 12:40:55 471

原创 bzoj 3611 [Heoi2014]大工程虚树 dp

直接上虚树dp一下就好了。。。#include <bits/stdc++.h>using namespace std;#define N 1100000#define ll long longint n,Q,cnt,top,tot,m,tim;int head[N],nex[N<<1],to[N<<1],st[N];int a[N],pos[N],fa[N][21],deep[N],bj

2016-12-20 09:37:46 302

原创 bzoj 3598 [Scoi2014]方伯伯的商场之旅数位dp

当位置向后移动时，可以发现答案加上前面一段所有数字之和减去后面一段所有数字之和。然后前面一段所有数字之和单调不减，后面一段所有数字之和单调不增。为了避免重复找最前面的满足的点。设答案的位置为a1，a1的下一个位置为a2。应该选取的位置满足s1<a1+a2+s2 s1+a1≥a2+s2s1<a1+a2+s2\ \ \ \ \ s1+a1\ge a2+s2 然后对左边右边分别数

2016-12-20 08:39:33 691

原创 bzoj 3572 [Hnoi2014]世界树虚树 dp

先建出虚树（似乎虚树可以不写重新标号） dfs两次维护f[x]f[x] 在x的子树中距x最近的选中的点,g[x]g[x] 整棵树中距x最近的选中的点。考虑虚树中的每一条边，这条边上的所有不在虚树上的点以及他的子树只能选这条边两端的虚树上的点的g[x]g[x]。求出分界位置。对于求一条链上点的子树的大小之和，可以倍增维护一个点到祖先的size之和，假设求链fa[x]到fa[y]上点的子树

2016-12-19 18:41:19 228

原创 bzoj 3566 [SHOI2014]概率充电器概率dp

题里那个直接充电和间接充电是一样的。。。除0挂了半天还以为是卡精。。。设f[i]f[i] 表示i和i的子树使点i充电的概率。设g[i]g[i] 表示除掉i的子树的剩余的部分把i的父亲充电的概率。转移看代码吧。。。。#include <bits/stdc++.h>using namespace std;#define N 510000#define eps 1e-15int n,t

2016-12-19 13:33:17 340

空空如也

空空如也