cjk_cjk-CSDN博客

原创 [NOI2014]随机数生成器（模拟+贪心）

【题解】先一步步按题目的操得出序列然后在方阵中找出最小的数(对于初始方阵是1)的位置(x,y)再在矩阵(1,1)-(x,y),(x,y)-(n,m)中分别找出最小数的位置递归是没必要的，也不容易找出每个子矩阵内最小的数可以反过来考虑：1,2,3……能不能依次使用？1肯定可以，2的话，必须在1划分出的子矩阵(1,1)-(x,y)或(x,y)-(n,m)中才行

2015-07-14 11:42:39 1588

原创 [NOI2014]动物园（kmp+递推）

【题解】这里首先定义失配指针f[i]满足：第i个位置的字符与第f[i]位相同，字符数组从1开始如：aba f[1]=0,f[2]=0,f[3]=1 要求出num[i]，只需延f指针上溯，找到所有长度不超过i/2的位置，它的数目即为num[i]可以考虑fail树的思想，用cnt[i]记录从i延失配指针上溯，能遇到的结点数目找出最大的长度不超过i/2的位置j，则num[i]=c

2015-07-13 22:59:02 1589

原创 [NOI2014]魔法森林（动态加边+SPFA）

【题解】求两个变量构成的最优值，可以考虑限制一个变量，最优化另一个观察此题，可以得到这样一个思路：假设已知答案中的Ai的最大值不超过x，只需最小化1到n路径上的Bi的最大值不难想到二分这个Ai的上限x更新方式为SPFA，即，设d[i]为：只考虑Ai然而这样的话，对于每个x，d数组都要重新求不如我们按Ai从小到大加边，随着加边来更新 BiMax 的最小值，这样d[i

2015-07-13 00:45:55 2732 3

原创 [NOI2014]起床困难综合症（二进制拆分+贪心）

【题解】还是老思路：二进制位运算的题，我们单独考虑每一位，最后合并答案这道题中：在0~m中选一个数"丢"到那一堆运算里，相当于判断从每一位"丢"下去0或1后，得出结果的高位尽量是1的方案为了方便，我们直接丢两个数：0000000……000与1111111……111，就可以O(2*n)求出每一位"丢"0或是"丢"1能得到的方案了，并不需要每一位"丢"两次然后从高位到低位贪心地判

2015-07-13 00:20:27 891

原创 [NOI2004]郁闷的出纳员（Treap）

【题解】Treap水过注意：对于null结点，不能进行 o->s = o->ch[0]->s + 1 + o->ch[1]->s 操作，一定要考虑此问题【代码】#include#includeint ans=0;struct Node{ Node* ch[2]; int v,r,s; int cmp_v(int x) const { if(x==v) r

2015-07-10 19:55:59 710

原创 [NOI2009]植物大战僵尸（最大流）

我冒着明天困屎= = 的危险写了这道题和题解【题解】最大权闭合子图模型，注意同一排里面的植物可以保护外面的若A能保护B，就连边 A->B，容量无穷大，将s与所有正权点相连，所有负权点与t相连，容量都为点权的绝对值还要注意若A,B互相保护，即图上有环，或环能保护一个点，则它们都不可能取！预处理时把它们都删掉。这个预处理只需记录入度，拓扑排序即可。再注意，千万别把s和t也考虑进

2015-07-05 08:08:16 742

原创 BZOJ2763 [JLOI2011]飞行路线（分层图最短路）

【题解】设 d[i][j]为到达结点i，免费票用掉j张时，花费的最小值则 d[i][j]可以更新 d[k][j] (i与k有边相连)，若j注意总共会产生n*k=10^5种状态，SPFA算法，队列要开大一些，10^7可过，或者循环队列还有SPFA会跑的很慢，"Spfa不适和分层图" ──贴吧【代码】#include#include#define INF

2015-06-29 23:09:20 1301

原创 [NOI2002]银河英雄传说（并查集）

【题解】建立并查集，并维护每个结点到root的距离、每个连通块中结点的个数sum "M i j"即：将father(i)到root的距离改为 sum[father(y)]，将sum[father(y)]增加 sum[father(x)]【代码】#include#include#includeint fa[30005],dis[30005]={0},sum[3000

2015-06-29 17:14:41 1064

原创 BZOJ1202 [HNOI2005]狡猾的商人（并查集）

【题解】给出[l,r]的区间和，相当于s[r]-s[l](前缀和思想)一旦已经知道了 s[a]-s[b],s[b]-s[c]，再给出一条[a,c]就可以判断"账本的真假"了将每条这样的信息(l,r,w)，l,r放入一个集合中，用并查集来维护，并维护cha[l]=s[root]-s[l],cha[r]=s[root]-s[r]若 l,r已经在同一个集合中，就直接查询cha[l]

2015-06-29 13:45:47 2255

原创 BZOJ1854 [Scoi2010]游戏（并查集/二分图匹配）

【题解】将一个装备抽象成一条边，它连接着编号为其属性值的两个结点这样，取装备等价于取边; 每个装备只能用一次，等价于在每条边上仅能取一个端点因此，连好所有的边，构成一个个连通块，它们产生了这样一条性质：对于某一连通块，若其为一棵树，则它的所有结点(属性值)中，只有一个不能取。(因为树的边比点少一，每条边上只能取一个点)

2015-06-28 23:30:49 688

原创 BZOJ1044 [HAOI2008]木棍分割（二分答案/单调性优化dp+递推优化）

【题解】f[i][j]:前i个数分j段的最小值设 f[i][x]:前i个数分j段的最小值f[i][x]=min{ max(f[j][x-1],s[i]-s[j]) }二分答案即可然而我的方法类似于斜率优化：假设j比k优，讨论j,k的大小关系，可得(只写最后结论)：1) j<k(前优) f[j][x-1]<f[k][x-1] 且 s[j]+f[k][x-1]>...

2015-06-27 02:28:46 525

原创 [APIO2014]序列分割（斜率优化dp）

【题解】一个重要的结论：对于同一组分割方式，总得分与分割的先后顺序无关不妨考虑最先分成的3部分，设区间和分别为Sa,Sb,Sc可以证明，先分割a,b还是b,c，最终得分都是ab+bc+ca，即最先分成的3部分无需考虑顺序，子问题也是一样于是，从前往后切割即可设f[x][i]为前i个数分x份的最大得分，显然1dp方程：f[x][i]=max{ f[x-1][j]

2015-06-26 03:22:50 550

原创 BZOJ1875 [SDOI2009]HH去散步（矩阵乘法）

【题解】小规模图的连通性问题，可以用邻接矩阵+快速幂求解本题唯一特殊的一点就是：不能沿着刚刚走来的路走回，注意：不是不能走重边，而是不能反向走刚刚走过的边处理方法是将无向边拆成两条有向边，互换点与边的地位，即：将两条有向边按是否首尾相接建立邻接矩阵所有边Ei:u->v与Ej:v->w(w!=u)，都有 Y[i][j]=1此时Y[i][j]=1的意义是：从边i的末端

2015-06-26 03:06:05 766

原创 BZOJ3233 [Ahoi2013]找硬币（线性筛+dp）

【题解】本蒻一直在想二维dp，看了题解才发现竟然一维就可以设f[i]为最大面值为i时，买下所有兔纸花费的最小硬币数 f[i] = min{ f[j] - sigma(a[k]/i*(i/j-1)) } , j|i，其中，j为次大面值，这个方程考虑的是选了i能减小多少j的使用注意，如果硬币种类很多，是不影响最优答案的(不用就行了) -----------> 重要的性质所

2015-06-26 03:04:29 1733 1

原创 BZOJ2038 [2009国家集训队]小Z的袜子（分块法）

【题解】本题中，每个区间的答案不能由子问题合并得到，所以不能使用分治一类的数据结构如线段树等而 ans = sigma( cnt[color[i]]*(cnt[color[i]]-1)/2 )，构成答案的颜色不止一种，所以要将不同颜色分开算答案但 n我这个蒟蒻只能写分块法。分块的对象：由于区间的答案不能由子问题合并得到，所以对序列分块无效，考虑对询问分块考虑将

2015-06-25 01:50:53 523

原创 BZOJ1030 [JSOI2007]文本生成器（AC自动机+dp）

【题解】与poj2778有类似之处，只不过本题模板串太长，无法用到矩阵，而文本较短，适于dpans = 26^m - 不含任意单词的文本数不含任意单词的文本数的求法：转化成从有向图的一点出发，走n步到达另一结点的方案数本题为从字典树的root出发，走m步到达任一结点，且不构成单词的方案数，需使建立的所有有向边合法(无法走出单词)将单词建成AC自动机，每

2015-06-24 18:09:24 1064

原创 poj2778 DNA Sequence（AC自动机+矩阵快速幂）

大神附图的题解：http://blog.csdn.net/morgan_xww/article/details/7834801【题解】将所有病毒串建立成字典树，并标记词尾结点，以下称"非法结点"那么，我们希望改造一下这棵树，即删掉一些结点，构造一些有向边，使得一个n位字符串相当于从改造图的根走n步，且中途不会形成非法串对于树上的某个结点u，先允许它走到非法结点，将所有有向边都

2015-06-24 12:44:53 474

原创 BZOJ3172 [Tjoi2013]单词（AC自动机+打标记）

刚开始把题意理解错了囧题意：给定n个字符串，求每个字符串在其他字符串中出现的次数之和【题解】首先肯定要建立AC自动机暴力算法：以每个词为文本串做匹配，每匹配上一个位置，就从该节点延fail或last数组上溯，给经过的的词尾结点加上1次出现次数优化：由上述算法可知，每个文本串(即每个单词)在AC自动机上的每个结点，都可以使其延fail数组能走到的单

2015-06-23 22:29:45 676

原创 BZOJ1014 [JSOI2008]火星人prefix（Splay+字符串Hash）

【题解】动态的LCP问题用 Splay 处理动态区间：插入操作"I x d"的实现：首先将x旋转至树根，则d应插在x的右字树中找到 x的右子树的最左端结点(即原来的s[x+1]在树中的对应结点)，将d添加为它的左孩子用字符串Hash 判断字符串是否相等：o->H表示由o及其左右子树所对应字母构成的字符串的Hash值，则 o->H = o->ch

2015-06-22 21:03:57 923 1

原创 BZOJ3506 [Cqoi2014]排序机械臂（离散化+Splay）

【题解】题目大意：给定一个n元素数列，n次操作，第i次要求输出第i小的数的当前位置t，再将区间[i,t]翻转模板题，记录伸展树中以每个结点为根的子树的最小值，通过它在logN时间内找到最小值的位置，然后提取出序列并打上翻转标记，每次操作结束，将最左边的元素分裂出去，这样每次操作都是找最小值本题有重复元素，有些麻烦，但题目只让给出位置，可以先离散化去重再处理

2015-06-22 16:37:31 926

原创 BZOJ3173 [Tjoi2013]最长上升子序列（离线处理+Treap+LIS）

【题解】离线处理：第n个数的插入不会改变前n-1个数的相对位置，因此可以直接求得最终序列，第i次操作的答案就是仅含1~i的LIS 最终序列可以用Treap求得;由于仅含1~i的LIS = max( 仅含1~i-1的LIS , 以i为结尾的LIS )，可以用O(N*logN)的动态规划求出以每个数为结尾的LIS，再递推求出每步答案【代码】#include#in

2015-06-22 11:25:26 541

原创 poj3622 Gourmet Grazers（贪心+Treap）

【题解】将牛和草分别按鲜嫩度从大到小排序然后将牛扫一遍：对于第i头牛，将鲜嫩度>=b[i]的草的价格加入平衡树，找出价格>=a[i]的最小的草，计入答案并删除之正确性分析：若i【代码】#include#include#define INF 2000000000typedef long long LL;int a[100005],b[100005]

2015-06-21 18:41:59 487

原创 BZOJ2957 楼房重建（线段树）

【题解】题目描述有误，一栋楼房可见，应满足其最高点到(0,0)的连线不与其他楼房相交这个条件可以等价为：它的斜率比之前的任何一个都大(相等也不行)因此，只需O(logN)修改、O(logN)求出区间[1,n]内比之前的任何一个数都大的数有多少个能使用线段树的条件是：两个子问题可以合并本题中，记cntv[o]为：仅考虑o所代表的区间，有多少满足条件的数那么首先

2015-06-21 15:17:21 1848

原创 BOZJ2733 [HNOI2012]永无乡（Treap+启发式合并）

【题解】Treap 启发式合并：初始时给每个点建一个treap，连边时启发式合并，将小的treap的每个结点插入大的treap中，并delete掉多余结点【代码】#include#includeint fa[100005],num[100005];struct Node{ Node* ch[2]; int v,r,s; int cmp_v(int x)

2015-06-21 02:56:01 735

原创 [NOI2007]项链工厂（线段树）

【题解】仔细探索题目性质：1. "段数"具有类似结合律的性质，可以用线段树维护，断环为链，但线段树不易进行旋转、翻转操作 2. 考虑用函数记录从初始到当前操作的变换方式，将对数列的变换转化为对询问的处理发现：若函数 f(x)=k*x+b表示询问的位置x对应的初始位置，则旋转a之后，函数为：f(x)=k*(x-a)+b; 翻转之后为：f(x)=k*(n+2-x)+b 3.

2015-06-20 16:38:17 537

原创 BZOJ1145 [CTSC2008]图腾totem（数学计数+树状数组）

【题解】拜读了不少网上题解，现在自己来复述一遍设 f(abcd)为：当选出的四个数相对大小关系为abcd时，有多少种选择方式则 ans = f(1324) - f(1243) -f(1432)用拆分法简此问题 f(1324) = f(1x2x) - f(1423)f(1243) = f(12xx) - f(1234)f(1432) = f(14xx) -

2015-06-20 16:10:06 932

原创 BZOJ3192 [JLOI2013]删除物品（树状数组）

【题解】将两堆物品拼接到一起，物品的移动次数等价于中间的"断点"的移动距离之和通过排序预处理出每次删除后的下一个该删除的位置每个物品代表一条长度为1的线段，该物品删除后，线段长度改为0 然后两点之间的距离就转化为了区间和，用树状数组维护即可【代码】#include#includetypedef long long LL;int a[100005],b

2015-06-20 16:05:56 575

原创 BZOJ3211 花神游历各国（树状数组+并查集）

【题解】查询很容易做到O(logN)修改时注意：第i位上的数a[i] -> sqrt(a[i])，最多执行30次，当a[i]==1后，可以不修改，直接跳过跳到之后第一个大于1的位置上去，这个位置可以用并查集维护由于每个点最被修改30次，修改的总复杂度为O(300*N)注意分析题目中修改操作的性质注意两个小优化：1. fa[n+1]=n+1

2015-06-18 02:35:02 532

原创 BZOJ2819 Nim（dfs序+树状数组）

【题解】题目大意：给定一棵树，有两种操作：1. 修改一个节点的权值 2. 查询两点之间路径上所有点的权值异或值运用前缀的思想首先xor运算有一个性质：Xor[l,r]=Xor[1,l]^Xor[1,r]所以，设 Xor[x]为从结点x到根经过的所有结点的权值异或，则 x到y路径上的点权异或值为：Xor[x] ^ Xor[y] ^ Val[LCA(x,y)]

2015-06-17 23:10:30 589

原创 BZOJ1185 [HNOI2007]最小矩形覆盖（旋转卡壳）

【题解】先求出这些点的凸包可以证明，最小的矩形一定与凸包的边有重叠因此，像旋转卡壳一样，逆时针将凸包各边扫一遍，这个过程中维护最上点,最左点,最右点，即可注意这样的写法：Cross(ch[q+1]-ch[i+1],ch[i]-ch[i+1]) - Cross(ch[q]-ch[i+1],ch[i]-ch[i+1]) >-eps （不过写成 >0 也能AC。。。）

2015-06-16 13:27:16 535

原创 BZOJ3190 [JLOI2013]赛车（单调栈+半平面交）

【题解】数形结合思考：画出v-t图像，若一条直线在一、四象限有不被覆盖的部分，它代表的车就可以领跑将直线按他们的斜率从小到大排序后，要维护一个下凸壳，由于一条新加入的直线，能覆盖的左边的直线是从右向左单调的，所以用单调栈来维护需要注意的细节：1. 要在y轴右边做半平面交，我加入了一条过原点，斜率负无穷大的直线，覆盖掉了所有直线的左边一半 2. 平行线无法算交点，重叠

2015-06-15 21:44:04 891

原创 poj2187 Beauty Contest（旋转卡壳）

模板题注意：避免凸包上三点共线代码#include#include#define eps 1e-10struct Point{ double x,y; Point() { x=y=0; }};typedef Point Vector;Point P[50005],ch[50005];double max(double a,double b)

2015-06-15 15:16:50 412

原创 poj2284 That Nice Euler Circuit（欧拉定理+枚举）

欧拉定理：V+F-E=2V的求法：将原有的拐点、线段不在端点处的的交点同一排序、去重，留下的点数就是VE的求法：原有线段数+新被分割出的，枚举点和线段，若点在线段上，新被分割出的就多一条注意：eps设为1e-13挂了，设为1e-10就AC虽然A了但其实是有问题的比如(3.333333333333333,6.0000000) 与 (3.33333333333333

2015-06-14 16:00:37 512

原创 [APIO2015]巴厘岛的雕塑（数位dp）

【题解】引用ZYF神犇一句话："显然位运算的极值问题都应该从高位向低位考虑。优先让这一位为0，如果行的话这一位就是0，否则就设为1。" 设答案为ans，从高位到低位枚举是否有使ans的这一位为0的方案，注意到每一位是互相独立的假设枚举到了倒数第x位，即ans的最高位到倒数第x+1位的最优01分布已确定，现在正在判断第x位是否有可能填0：对于每个x，考虑递推法：设

2015-06-12 16:53:29 1132

原创 BZOJ1040 [ZJOI2008]骑士（基环树+树形dp）

【题解】出现了基环森林，还是考虑断环为链，然后dp对每个连通块，随意找到环上一边并断开，记该边的端点为x,y限制x,y的情况：1. x不取，y取上 2. y不取，x取上树形dp：记 f[i][0]表示不取i时的最大战斗力; f[i][1]表示取i时的最大战斗力，以上两种情况去最优值即可注意：1. 处理破环为链的问题，使用邻接表比较合适 2. 对x,y

2015-06-11 18:15:25 797

原创 [POI2009]石子游戏Kam（阶梯Nim）

【题解】开始时，除第一堆外，每堆能取的石子都有限制，相当于第i堆只能取s[i]-s[i-1]个石子在第i堆取走x个石子后，第i堆能取的石子少了x个，第i+1堆能取的石子多了x个这相当于把x个石子第i堆移到了第i+1堆因此，每次操作，相当于将石子从一堆往后移一堆，这是阶梯Nim的模型本题只需考虑倒数第1,3,5,7,…堆因为仅考虑倒数奇数堆的石子，若为后手必胜

2015-06-07 23:41:46 572

原创 BZOJ1188 [HNOI2007]分裂游戏（SG定理）

注意：1. 位运算的优先级低于"=="2. vis[]的大小不一定等于n，具体多大需实验得知 3. 初始化的问题 4. Nim游戏中SG函数的意义：对于，某状态先手的胜负情况，必败状态的SG==0，必胜状态SG!=0，组合游戏的SG为所有子游戏SG的xor和，独立游戏的SG为：排除所有后继状态的SG 的最小非负整数本题中，将某个未知的数减少1，其后的某两个位置(

2015-06-07 23:22:45 776

原创 BZOJ246 [中山市选2009]谁能赢呢？（讨论奇偶性）

题意：给定一个n*n的棋盘，一个石头被放在棋盘的左上角。两人轮流移动石头。每一回合，选手只能把石头向上，下，左，右四个方向移动一格，并且要求移动到的格子之前不能被访问过。谁不能移动石头了就算输。问最后谁能赢？考虑n的奇偶性：偶数个格子的情况：棋盘可以被1*2的骨牌完全覆盖，Alice先移动一次覆盖一个骨牌，此后无论Bob移动到哪里，Alice必能移动到棋子所在骨牌的另一格，先

2015-06-07 23:19:48 639

原创 BZOJ2428 [HAOI2006]均分数据（模拟退火算法）

【题解】随机10000次左右，每次随机生成初始分组情况，判断将某个元素移入另一组是否会更优，记录全局最优答案注意：1. 自己用平方取中法弄的伪随机数，效果远不如系统函数rand()2. t*=0.9变为t*=0.99 耗时远远超过 solve()从10000次变为50000次 3. 随机打乱原数组【代码】拼RP终于AC了。。。#include#

2015-06-06 00:29:19 672

原创 BZOJ3680 吊打XXX（模拟退火算法）

其实我并不确定这是什么算法。#include#include#include#define eps 1e-6double x[10005],y[10005],w[10005];double dis(double x1,double y1,double x2,double y2){ double d=sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y

2015-06-06 00:26:41 897

空空如也

使用Docker创建镜像时，requests.get超时的问题

函数传递时，若为f(x=1,x=2,x=3)形式，得到的形参均为一，为什么会这样？