- 博客(158)
- 收藏
- 关注
RSS订阅原创 [普通型母函数+容斥+FFT]BZOJ 3771:Triple
看到ZZK大佬的blog写的太好啦，所以就“转”来了。题目概述CHNJZ有nn把价值不一样的斧子，ZigZagK偷走了11把或22把或33把，对于每个可能的总损失，计算有几种可能的方案。解题报告emm……显然是母函数啊？但是有数量限制。由于最多偷走三把，所以我们可以直接三种情况都讨论过去。11把：母函数：A(x)=xa1+xa2+xa3+...+xanA(x)=x^{a_1
2018-01-10 19:24:09
533
原创 [二进制分组维护凸包]BZOJ 4140—— 共点圆加强版
[二进制分组维护凸包]BZOJ 4140—— 共点圆加强版题目描述在平面直角坐标系中，Wayne需要你完成n次操作，操作只有两种：1.0 x y。表示在坐标系中加入一个以(x, y)为圆心且过原点的圆。2.1 x y。表示询问点(x, y)是否在所有已加入的圆的内部（含圆周），且至少在一个圆内部（含圆周）。为了减少你的工作量，题目保证圆心严格在x轴上方（纵坐标为正），且横坐标非零。解题思路如果不强制
2017-12-28 18:10:53
832
1
原创 [巴什博奕]HDU 2147——kiki's game
题目描述给你n*m表格，初始在右上角，每次在上个人移动后的基础上移动一步（向左or向下or向左下）先到左下角则获胜。解题思路先来说说巴什博奕。给出n个数，每次可以取x个(1<=x<=m)。显然可以按m+1分，每次操作看对手上次操作，保持和为m+1，如果n为m+1的倍数后手显然必胜。得到如果n不为m+1的倍数，先手必胜。回到这题，必胜策略为每次保持行数列数为奇数，如果n,m为奇数后手显然必胜，否则先手
2017-12-20 21:09:39
411
原创 [威佐夫博奕]POJ 1067——取石子游戏
题目描述有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。解题思路裸的威佐夫博奕。#include<cmath>#include<cstdio>#inc
2017-12-20 20:45:14
1542
原创 [Dsu on tree]CodeForces 600 E
题目描述给出一个树，树的每个节点有一个颜色。询问每个节点颜色最多的颜色编号和。解题思路树上启发式合并？考虑暴力，对于每个节点暴力遍历，之后删除该子树的贡献。不然发现有些删除没有必要，贪心的思想，对于每棵子树保留重儿子的贡献。所以操作为：遍历所有轻儿子不保留贡献，遍历重儿子保留贡献，遍历轻儿子增加贡献，得到该树答案。时间复杂度：考虑每个节点遍历的次数，显然是到根节点的轻边个数加重链个数+1，所以效率就
2017-12-19 19:32:27
367
原创 [最小割]BZOJ 3175—— [Tjoi2013]攻击装置
题目描述给定一个矩阵，这个矩阵上有一些位置可以放置装置。装置会日字形互相攻击，求最多可放置多少个装置。解题思路因为日字形相互攻击的两个点肯定满足一个坐标和是奇数，另一个是偶数。将矩阵看成零一奇偶矩阵，那么互相攻击的装置可以形成一个二分图。答案显然是总数-最小割。怎么思考？最小割不存在同时选择两个装置且互相攻击（因为不满足最大流）。#include<cstdio>#include<cstring>
2017-12-13 20:51:59
651
1
原创 [点分治]BZOJ 2152——聪聪可可
题目描述给出一棵有边权的树。求边权和%3=0的路径数。解题思路累计以每个点为路径LCA的方案数，所以直接点分就好了。累计方法为分别找出距离某个点路径和为0,1,2的方案数，返回2∗t[1]∗t[2]+t[0]∗t[0]2*t[1]*t[2]+t[0]*t[0]然后减去所以子树方案就是当前方案。#include<cstdio>#include<algorithm>using namespace s
2017-12-12 20:17:40
532
原创 [虚树+树形DP]BZOJ 2286—— [Sdoi2011]消耗战
题目梗概给出一棵有比边权的树。每次给出K个点，询问使这K个点不与1联通所需要砍掉的边权总和最小值。解题思路假如只有一次询问，显然可以用树形DP解决，f[i]f[i]表示使i的子树下所有特殊点与1不连通的最小代价，转移状态显然。但是多次询问会超时，但是∑K\sum K与n同阶，所以就变成虚树的裸题。虚树的基本思想是，每次询问不需要遍历所有点，于是我们只存关于特殊点的图，边权显然是路径上的最小边权。关于
2017-12-12 18:21:40
471
原创 [基环外向树+树形DP]BZOJ 1040—— [ZJOI2008]骑士
题目描述有n个骑士，每个骑士有一个不想一起组队的人。每个骑士还有一个战斗力，求战斗力最大的队伍。解题思路把每个骑士和不想组队的骑士之间连边，会形成一堆基环外向树形成的森林。假设每个联通块是树，边数=n-1，显然不符合。假设每个联通块存在两个及以上的简单环，边数>n，也不符合。所以图必然是基环外向树形成的森林。先随意建树寻找返祖边，确定两个点和一条边。分别以这两个点为树根并砍掉这条边进行树形DP,f[
2017-12-11 19:04:41
606
原创 [二分+DFS序上DP]BZOJ 4753—— [Jsoi2016]最佳团体
题目梗概题目给定一棵树，选K个节点。任意节点满足如果它被选其父亲也必须被选。使得价值与花费之比最大。解题思路这类题目显然是要二分的。最初的想法，在树上进行左儿子右父亲DP合并，这样每次check的效率是O(n^2)。但是怎么卡就是不过（我下面给出的就是树上合并的代码）。我将其归结为常数过大，记住其效率是稳定的。因此引进DFS序上DP，可以想象常数极小。fi,jf_{i,j}表示DFS序的前i个选择j
2017-12-05 20:19:11
761
原创 [树形DP+贪心]BZOJ 1217—— [HNOI2003]消防局的设立 Plus？
题目描述给出一棵树。你可以设置一个特殊节点，距离这个节点小于等于2的节点被覆盖。求覆盖所有节点所需的最小特殊节点数。解题思路这题是51 Nod 夹克老爷的愤怒的弱化版。51Nod上的那题将范围推广至于n同阶的级别。主要就是利用贪心进行树形DP。#include<cstdio>using namespace std;const int maxn=100005,INF=2147483647;int
2017-12-03 21:21:52
381
原创 [数学杂题]BZOJ 2111—— [ZJOI2010]Perm 排列计数
题目梗概求[1,n]有多少个排列满足Pi>Pi/2P_i>P_{i/2}解题思路不难发现排列构成一个小根堆，因此树形可以确定。然后用f[i]f[i]表示以第i个节点为根的方案数。转移方程不难得出。最主要的是这题虽然P很大但是依然要用Lucas，为什么呢？因为处理n的阶乘时到后面%P会变成0，所以要限制阶乘的范围。WA了5发才反应过来。#include<cstdio>#include<algorit
2017-12-03 20:51:34
531
原创 [Lucas定理+中国剩余定理]1951—— [Sdoi2010]古代猪文
题目梗概求G∑d|n(nd)%PG^{\sum _{d|n} (^n_d)}\%P解题思路由欧拉定理可得原式=G∑d|n(nd)%ϕ(P)%P=G^{\sum _{d|n} (^n_d)\%\phi(P)}\%P(nd)(^n_d)由Lucas定理可得，然后ϕ(P)=999911658=2∗3∗4679∗35617\phi(P)=999911658=2 * 3 * 4679 * 35617可以用中国
2017-12-03 19:41:29
503
原创 [模拟退火]POJ 2420——A Star not a Tree
题目描述给定n个点，求关于这个n个点的广义费马点。题目梗概必须折服于先人的智慧。初值随便给个位置，每次随机一个角度走温度的距离。概率函数为eΔ/Te^{Δ/T}。过了之后感觉非常神奇。#include<cstdio>#include<cmath>#include<cstdlib>using namespace std;const int maxn=105;const double coe=
2017-11-28 21:08:20
728
原创 [Splay]BZOJ 1208——[HNOI2004]宠物收养所
题目描述最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物，阿Q根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养所总是会有两种情况发生：被遗弃的宠物过多或者
2017-11-27 20:20:42
524
原创 [主席树]BZOJ 3524——[Poi2014]Couriers
题目描述给一个长度为n的序列a。1≤a[i]≤n。 m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。解题思路直接上主席树。构造权值线段树，询问时不停遍历节点数最多的一边就可以了。但是要注意：最后停下的节点并不是出现次数最多的节点但对于这道题，如果有解这种方法一定正确。#include<cstdio>using
2017-11-26 21:12:57
487
原创 [左偏树]BZOJ 2809——[Apio2012]dispatching
题目描述在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。在这个帮派里，有一名忍者被称之为 Master。除了 Master以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者 支付一定的薪水，同时使得支付的薪水总
2017-11-26 21:06:41
491
原创 [树状数组]51 Nod 1463——找朋友
题目描述给定：两个长度为n的数列A 、B一个有m个元素的集合K询问Q次每次询问[l,r]，输出区间内满足|Bi-Bj|∈K 的最大Ai+Aj解题思路注意这题M的范围是10离线一下，对于每个新加的元素用树状数组暴力维护就可以了。#include<cstdio>#include<algorithm>using namespace std;const int maxn=100005;struct
2017-10-29 18:42:57
615
原创 [单调队列]51 Nod 1952——栈
[单调队列]51 Nod 1952——栈题目梗概要维护一个栈。能够从栈顶和栈底加数，并能从栈顶取数。询问每次操作后栈里的最大元素。解题思路维护一个单调递减的单调队列就可以了。但是要注意统计每个元素前面有几个未删的比当前元素小的元素个数。#include<cstdio>using namespace std;const int maxn=10000005,MOD=1e9+7;int n,A,B,
2017-10-29 18:38:46
618
原创 [容斥原理+组合数学]51 Nod 1829——函数
题目描述想知道f:A->B这个函数（其中|A|=n, |B|=m）的所有映射关系要使B的每个元素都要被A的一个元素覆盖到。数字可能很大你只要输出方案数模1,000,000,007即可。解题思路一看就是要用到容斥原理。有ii个B元素没被覆盖的方案数为Cim∗(m−i)NC^{i}_{m}*{(m-i)}^{N}容斥一下答案就出来了。#include<cstdio>#define LL long lo
2017-10-29 18:31:28
1192
原创 [边双]hihocoder 1184——边的双连通分量
题目梗概裸的边双。解题思路没有桥的极大图就是边双。考虑怎么求桥。Tanjan的时候回不去的就是桥，即low[son[j]]>dfn[x]low[son[j]]>dfn[x]#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=20005,maxm=200005;int t
2017-10-29 07:53:16
548
原创 [堆]51 Nod 1461——稳定桌
题目描述有一张桌子，有n个腿。第i根腿的长度是li。现在要拿掉一些腿，使得桌子稳定，拿掉第i根腿需要di的能量。稳定的条件是，假如拿掉若干条腿之后，桌子还有k个腿，那么长度最长的腿的数目要超过一半。比如桌子有5根腿，那么至少要有三根腿是最长的。另外，只有一根腿的桌子是稳定的，两个腿的桌子想要稳定，必需长度是一样的。你的任务是拿掉若干腿，使得桌子稳定，并且所消耗的能量要最少。解题思路考虑枚举长度，每个
2017-10-25 18:02:59
693
原创 [树状数组]51 Nod 1711——平均数
题目描述LYK有一个长度为n的序列a。你只要告诉他所有区间(n*(n+1)/2个区间)中第k大的平均数就行了。解题思路显然要二分，考虑如何验证。sum[R]−sum[L−1]>=x∗(R−L+1)——>sum[R]−x∗R>=sum[L−1]−x∗(L−1)sum[R]-sum[L-1]>=x*(R-L+1)——>sum[R]-x*R>=sum[L-1]-x*(L-1)那么就是求sum[i]−x∗i
2017-10-25 17:48:02
449
原创 [树状数组]BZOJ 2028——[SHOI2009]会场预约
题目梗概有两种操作：一种是插入一段区间，并删除与这段区间相交的区间，返回删除区间的个数。另一种是返回目前的区间数。解题思路有一个非常重要的特性是在任何时候区间的末端随区间的始端递增而递增。于是考虑树状数组维护始端个数的前缀和，维护这个就可以二分查找小于等于某个点最近的始端。知道始端的位置后，我们可以得到相应的末端，如果形成相交就删去这个区间（其实就是删去始端）。因为始末端的单调性，当查找出的区间不形
2017-10-25 17:01:59
532
原创 [DP]51 Nod——[1048 整数分解为2的幂 V2]
题目描述给定正整数N，求N分解成若干个2的次幂的方案数。N<=1030N<=10^30解题思路之前写过O(n)O(n),看到这个数据范围瞬间就恐惧了。将N表示成一个二进制数，对于每个ai=1ai=1，都有一段区间的和刚好等于2ai2^{ai}我们考虑如何构造区间设g[i][j]g[i][j]表示前i个位置，最大数是2j2^j的方案数很快得到递推式g[i][j]+=g[i−1][k]∗f[ai−k][
2017-10-24 20:29:51
722
原创 [Lucas 原理+逆元]BZOJ 4403——序列统计
题目描述给定三个正整数N、L和R，统计长度在1到N之间，元素大小都在L到R之间的单调不降序列的数量。输出答案对10^6+3取模的结果。解题思路显然L,R的大小对答案没有影响，但是相对大小有影响，设m=R−L+1m=R-L+1用隔板法可推出长度为n的方案数(n+m−1m−1)(^{n+m-1}_{m-1})于是总方案就是∑ni=1(i+m−1m−1)\sum_{i=1}^{n}(^{i+m-1}_{m
2017-10-24 20:03:23
497
原创 [组合数学]51 Nod 1486——大大走格子
题目描述第一行有三个整数h, w, n(1 ≤ h, w ≤ 10^5, 1 ≤ n ≤ 2000)，表示棋盘的行和列，还有不能走的格子的数目。接下来n行描述格子，第i行有两个整数ri, ci (1 ≤ ri ≤ h, 1 ≤ ci ≤ w)，表示格子所在的行和列。输入保证起点和终点不会有不能走的格子。解题思路如果不考虑障碍，那么从起点走到（x,y）的方案数为Cx−1x+y−2C^{x-1}_{
2017-10-23 18:41:56
700
原创 [二分+树状数组]51 Nod 1685——第K大区间2
[二分+树状数组]51 Nod 1685——第K大区间2题目描述定义一个长度为奇数的区间的值为其所包含的的元素的中位数。 现给出n个数，求将所有长度为奇数的区间的值排序后，第K大的值为多少。解题思路二分枚举答案x。考虑如何验证中位数>=x的区间总数是否>=K。构造s[i]s[i]表示前i个数有多少个数>=x>=x。如果一个区间的中位数>=x>=x肯定有(s[R]−s[L−1])∗2>R−L+1(s
2017-10-23 18:37:30
580
原创 [思维题]51 Nod 1671——货物运输
题目描述公元2222年，l国发生了一场战争。 小Y负责领导工人运输物资。 其中有m种物资的运输方案，每种运输方案形如li,ri。表示存在一种货物从li运到ri。 这里有n个城市，第i个城市与第i+1个城市相连（这里1号城市和n号城市并不相连），并且从i号城市走到i+1号或者从i+1号走到i号需要耗费1点时间。 由于高科技的存在，小Y想到了一种节省时间的好方案。在X号城市与Y号城市之间设立传送
2017-10-23 07:34:42
528
原创 [二分+最大流]51 Nod——1757 大灾变
题目描述死亡之翼降临了！艾泽拉斯大陆的子民们必须逃出他的魔爪！ 艾泽拉斯的结构是一棵树，这棵树上的一些节点是地精建造的通往地下避难所的洞口。 除了这些洞口之外，树上的每个节点上都有一个种族，每个种族通过树上的一条边都需要一个单位时间。 因为地精比较矮小，所以洞口很窄，每个单位时间只能让一个种族通过，但是一个单位时间内的一个节点上可以存在多个种族。 地精们需要你求出最少需要多少单位时间才能让所
2017-10-22 20:38:32
729
原创 [乱搞]51 Nod 1421——最大MOD值
题目描述有一个a数组，里面有n个整数。现在要从中找到两个数字(可以是同一个) ai,aj ，使得 ai mod aj 最大并且 ai ≥ aj。解题思路对于每个数字，有n/ain/ai个区间,每个区间是[1+ai∗(k−1),ai∗k][1+ai*(k-1),ai*k]显然对于每个区间只有最接近这个区间末边界的值会更新答案。提前预处理一下就可以了。ps：我预处理有log的，其实不需要log。#inc
2017-10-21 11:25:15
669
原创 [DP] 51 Nod 1274——最长递增路径
题目描述一个无向图，可能有自环，有重边，每条边有一个边权。你可以从任何点出发，任何点结束，可以经过同一个点任意次。但是不能经过同一条边2次，并且你走过的路必须满足所有边的权值严格单调递增，求最长能经过多少条边。 以此图为例，最长的路径是： 3 -> 1 -> 2 -> 3 -> 2 或 3 -> 1 -> 2 -> 3 -> 4 长度为4。解题思路很自然想到将边排序。 然后DP。 但是
2017-10-21 11:21:08
601
原创 [分块]51 Nod——1225 余数之和
题目梗概例如F(6) = 6 % 1 + 6 % 2 + 6 % 3 + 6 % 4 + 6 % 5 + 6 % 6 = 0 + 0 + 0 + 2 + 1 + 0 = 3。给出n，计算F(n), 由于结果很大，输出Mod 1000000007的结果即可。解题思路x%y运算其实可以看成x−x/y∗yx-x/y*y，这里的除是整除。那么对于整除x等于固定值的数我们可以一起统计，这些数显然是一个区间，我
2017-10-20 20:36:35
763
原创 [贪心+单调队列+ST算法]51 nod 1288 ——汽油补给
题目梗概有（N+1）个城市，0是起点N是终点，开车从0 -> 1 - > 2…… -> N，车每走1个单位距离消耗1个单位的汽油，油箱的容量是T。给出每个城市到下一个城市的距离D，以及当地的油价P，求走完整个旅途最少的花费。如果无法从起点到达终点输出-1。解题思路ZZK大佬说这是N年前做过的一道题目，但是我并没有看出来。贪心比较明显，对于一个点，我们可以知道它最远能到哪个点，这样形成一个区间。如果存
2017-10-20 18:25:50
885
原创 [最小割]BZOJ 1497——[NOI2006]最大获利
题目梗概有m个通讯，你可以获得一定的利润。但是通讯必须开通ai,biai,bi两个中转站，开通中转站需要额外的费用。问你能获得最大的利润是多少。解题思路你要换个角度思考这个问题，把边看成一个点。如果要获得这个点的值就必须开通另外两个点。这样显然会形成一张二分图，但是我们会在这张图上进行取舍。显然每种取舍方式都对应一种最小割。以上只是简略的概述了这个思想，详见胡伯涛的《最小割模型在信息学竞赛中的应用》
2017-10-19 16:25:25
720
原创 [树形DP]51 Nod 1500——苹果曼和树
题目梗概有一个n个节点的树，每个节点都有黑色或白色。问有多少种删边方式，使得删完后的每棵树有且仅有一个黑点。解题思路没什么好suo的，直接树形DP。#include<cstdio>#define LL long longusing namespace std;char nc(){ static char buf[100000],*l=buf,*r=buf; if (l==r)
2017-10-18 21:11:43
693
原创 51 Nod 1616——最小集合
题目梗概现在有一个集合，对于任意的x,y，gcd(x,y)也在这个集合中。给出原集合中一部分的数，求原集合的最小大小。解题思路因为ai的范围感人，所以肯定能枚举原集合中元素然后判断是否存在。考虑如何判断。显然只要关于xx的倍数的gcd==xgcd==x那么xx肯定存在。所以暴力维护就可以了。#include<cstdio>#include<cmath>using namespace std;c
2017-10-18 20:06:30
587
原创 [并查集]51 Nod 1525——重组公司
题目梗概普通的并查集问题？多了一种区间合并的操作。解题思路还是很水。维护每个点前面最近的没合并的节点是谁就可以了。#include<cstdio>using namespace std;char nc(){ static char buf[100000],*l=buf,*r=buf; if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
2017-10-18 19:13:57
610
原创 [数学杂题]51 Nod 1765——谷歌的恐龙
题目梗概给出一个数n，每次随机[0,n)[0,n)之间的一个数，如果随机到给出的mm个数之一就停止。求随机出来的数字的期望。解题思路真TM智障，我想了很久……能够继续下一次操作的概率为p=(n−m)/mp=(n-m)/m显然答案就是1∗1n∗S+p∗1n∗S+p2∗1n∗S……1*\frac{1}{n}*S+p*\frac{1}{n}*S+p^2*\frac{1}{n}*S……其中SS表示所有数的和
2017-10-18 15:10:00
632
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人