- 博客(160)
- 收藏
- 关注
RSS订阅
原创 Newnode's NOI 模拟赛 第三题（可持久化线段树优化建图+Tarjan）
第三题问题描述 。输出格式 n行每行一个整数，如果第i个宇宙可以成为最大宇宙则第i行为1，否则为0。样例输入 1 3 1 3 ...
2018-03-08 20:00:47
2800
原创 HDU 4946 Area of Mushroom （凸包）
Area of Mushroom问题描述 **中学有一个很大的操场，上面有n名同学(编号1到n)。我们可以看做一个无限大的平面上有n个坐标点。同学们跑步速度有快有慢。对于操场上的任何一点，如果一个学生能比其他学生都先到达(跑直线，没有人比他先到或同时到)，那么这个点就被他占领。 请你计算，哪些同学能占领无穷多个点。输入格式 输入含有多组数据(<=8组)，对于每组数据...
2018-03-08 19:26:38
324
原创 HDU 5794 A Simple Chess （容斥原理+Lucas定理+dp）
A Simple Chess问题描述 有一个n*m棋盘，一枚棋子要从(1,1)格子移动到(n,m)格子。 该棋子能从坐标为(x1,y1)的格子跳到格子(x2,y2),当且仅当: (x2-x1)^2+(y2-y1)^2=5 x2>x1，y2>y1 棋盘上有r个格子有障碍物，棋子不能落到有障碍物的格子上。 请你计算，该棋子从起...
2018-03-08 19:11:47
397
原创 HDU 5781 ATM Mechine（数学期望+dp）
自动取款机问题描述 Alice打算从自动取款机上取出她的所有存款。但是她忘了自己有多少存款了，她只知道存款不超过k块钱。 但是这台取款机很奇怪，它不支持余额查询功能，Alice只能通过多次尝试的方式取钱。每次尝试，Alice输入一个提取金额y，若账户余额>=y,取款机会立即吐出y块钱。若余额 < y，取款机会发出警告。如果取款机发出了w次警告，它会认为Alic...
2018-03-08 16:50:50
298
原创 BZOJ 4169 LＭC的游戏 （博弈+树dp）
4169 LMC的游戏【题目描述】 RHL 有一天看到 lmc 在玩一个游戏。 “愚蠢的人类哟,what are you doing”,RHL 说。 “我在玩一个游戏。现在这里有一个有 n 个结点的有根树,其中有 m 个叶子结点。这 m个叶子从 1 到 m 分别被给予了一个号码,每个叶子的号码都是独一无二的。一开始根节点有一个棋子,两个玩家每次行动将棋子移动到当前节点的一个...
2018-03-08 16:29:18
508
原创 Ｎewnode‘s NOI 模拟赛 第二题 （单调dp）
第二题问题描述 样例输入 1 3 2 *# #* ##样例输出 1 2样例输入 2 4 5 *#### *#### *#### #* * * #样例输出 2 3提示 对于20%的数据n,m<=5； 对于50%的数据满足n,m<=500； ...
2018-03-07 17:33:18
614
原创 BZOJ 4171 RHL的游戏（高斯消元+压位）
4171: Rhl的游戏Description RHL最近迷上一个小游戏：Flip it。游戏的规则很简单，在一个N*M的格子上，有一些格子是黑色，有一些是白色 每选择一个格子按一次，格子以及周围边相邻的格子都会翻转颜色（边相邻指至少与该格子有一条公共边的格子 ），黑变白，白变黑。RHL希望把所有格子都变成白色的。不幸的是，有一些格子坏掉了，无法被按下。这时，它 可以...
2018-03-07 16:44:59
560
原创 JZOJ 5495 MiniumCut （最小割树）
MiniumCutDescription 从前有张图。 图里 n 个顶点两两之间有 n2n2n^2 种最小割。 告诉你这 n2n2n^2 个最小割。 还原出这张图。Input 第一行一个正整数 n, 表示图的顶点数。 接下来 n 行每行 n 个非负整数, 第 i 行第 j 列的数表示第 i 个点与第 j 个点的最小割。 点的编号从 1 开始。...
2018-03-07 16:18:26
326
原创 JZOJ 5497 塔（哈希）
塔问题描述 有一个塔,他的名字叫做粽粑,粽粑的每一层都有一个颜色 . 粽粑非常厉害,它在吸收天地精华之后会长高.粽粑的长高方式有两种: 1.在塔顶长出一层. 2.在塔底长出一层,即原来的第一层变成第二层,第二层变成第三层,以此类推,新长出来的是第一层. 粽粑有可能在某个时刻不是很开心,这个时候它会撤销它的前若干次长高. 你现在想知道粽粑长高的奥秘,于是找到...
2018-03-06 23:27:05
344
原创 Code+三月月赛 Div1 C 博弈论与与概率统计（莫队+组合数+数学期望）
[CODE+]博弈论与概率统计问题描述 样例输入 3 500 1 1 2 3 4 4样例输出 500000004 200000002 728571435提示 首先，容易得到题目中的p是没有用的，因为Alice每一种输赢序列的出现概率是相等的，因此只需要算出每种排列的得分之和再除以Cnn+mCn+mnC_{...
2018-03-06 20:33:42
659
原创 NKOJ 4028（HZOI 2015）疯狂的机器人（NTT+卡特兰数）
P4028[HZOI 2015]疯狂的机器人问题描述 现在在二维平面内原点上有一只机器人 他每次操作可以选择向右走，向左走，向下走，向上走和不走(每次如果走只能走一格） 但是由于本蒟蒻施展的大魔法，机器人不能走到横坐标是负数或者纵坐标是负数的点上 否则他就会big bang 给定操作次数n，求有多少种不同的操作序列使得机器人在操作后会回到原点 ...
2018-03-05 23:22:32
343
原创 JZOJ 5496 Tree（点分治+树形dp）
Tree* Description* 从前有棵树。 找出 k 个点 A 1 , A 2 , · · · , A k 。 ∑ k−1 使得 i=1 dis(A i A i+1 ) 最小。Input 第一行两个正整数 n, k, 表示数的顶点数和需要选出的点个数。 接下来 n − 1 行每行 3 个非负整数 x, y, z, 表示从存在一条从 x 到...
2018-03-05 16:09:36
338
原创 NKOJ 4022（HEOI 2015）最短不公共子串（后缀自动机+序列自动机+dp）
P4022 [HEOI2015]最短不公共子串问题描述 在虐各种最长公共子串、子序列的题虐的不耐烦了之后，你决定反其道而行之。 一个串的“子串”指的是它的连续的一段，例如bcd是abcdef的子串，但bde不是。 一个串的“子序列”指的是它的可以不连续的一段，例如bde是abcdef的子串，但bdd不是。 下面，给两个小写字母串A，B，请你计算： ...
2018-03-04 22:03:45
262
原创 2015 HN Training 7.7 C （线段树）
C问题描述 样例输入 4 0 0 R 0 1 B 1 1 R 1 0 B样例输出 2提示 先考虑如果平行线恰好平行于y轴的情况，那么只需要按照x轴排序后求出最长连续R串即可。 注意到如果有点在直线上，那么是可以通过微小扰动来解决的，因此一定合法。然后考虑一般情况，我们考虑平行线来旋转，等价于坐标系...
2018-03-04 21:40:13
234
原创 2015 HN Training 7.7 B（AC自动机）
B问题描述 样例输入 3 10 AT TT AAAAA 3 10 ATT TT AAAAA样例输出 No Yes提示 构造一个串不含某些给定串，考虑将给定串构造AC自动机，并将其改造成有限状态自动机（每个点不存在的转移改成fail树上第一个该转移），将串结尾的标记沿着f...
2018-03-04 21:20:21
241
原创 NKOJ 3984 （WC 2010）重建计划（二分答案+点分治+单调dp）
P3984[WC2010]重建计划问题描述 输入格式 第一行包含一个正整数N，表示X国的城市个数. 第二行包含两个正整数L和U，表示政策要求的第一期重建方案中修建道路数的上下限 接下来的N-1行描述重建小组的原有方案，每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi 其中城市由1..N进行标号输出格式 输出最大平均估值，保留...
2018-03-04 13:05:12
293
原创 NKOJ 3967 （SCOI 2007）最大土地面积（旋转卡壳）
P3967【SCOI2007】最大土地面积问题描述 在某块平面土地上有N个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成的多边形面积最大。输入格式 在某块平面土地上有N个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成的多边形面积最大。输出格式 最大的多边形面积，答案精确到小数点后3位。样例输入 ...
2018-03-04 12:28:40
267
原创 NKOJ 3966 （ZJOI 2008）瞭望塔（半平面交/模拟退火）
P3966【ZJOI2008】瞭望塔问题描述 致力于建设全国示范和谐小村庄的H村村长dadzhi，决定在村中建立一个瞭望塔，以此加强村中的治安。 我们将H村抽象为一维的轮廓。如下图所示 我们可以用一条山的上方轮廓折线(x1, y1), (x2, y2), …. (xn, yn)来描述H村的形状，这里x1 < x2 < …< xn。瞭望塔可以...
2018-03-04 12:16:44
315
原创 NKOJ 3961 zMy的lcm （Pollard_Rho+欧拉函数+高精度）
P3961zMy的lcm问题描述 首先注意到，题目中的异或是不存在的，因为出题人懒得写高精度异或。 先推导一番 Ans=∑i=1nlcm(n,i)=n∑i=1nigcd(n,i)=n∑d|n∑i=1nid[gcd(n,i)==d]=n∑d|n∑i=1ndi[gcd(nd,i)==1]Ans=∑i=1nlcm(n,i)=n∑i=1nigcd(n,i)=n∑d|n∑i=1ni...
2018-03-04 11:55:33
368
原创 NKOJ 3957 （BZOJ 2820）YY的GCD （莫比乌斯反演+线性筛）
P3957YY的GCD问题描述 神犇YY虐完数论后给傻×kAc出了一题 给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对 kAc这种傻×必然不会了，于是向你来请教…… 输入格式 第一行一个整数T 表述数据组数 接下来T行，每行两个正整数，表示N, M输出格式 T...
2018-03-04 10:32:22
244
原创 NKOJ 3941 （HNOI 2014）世界树（虚树+树形dp+倍增）
P3941[Hnoi2014]世界树问题描述 世界树是一棵无比巨大的树，它伸出的枝干构成了整个世界。在这里，生存着各种各样的种族和生灵，他们共同信奉着绝对公正公平的女神艾莉森，在他们的信条里，公平是使世界树能够生生不息、持续运转的根本基石。 世界树的形态可以用一个数学模型来描述：世界树中有n个种族，种族的编号分别从1到n，分别生活在编号为1到n的聚居地上，种族的编号与其聚居地的编...
2018-03-04 09:50:07
241
原创 NKOJ 3933 贝壳串（CDQ分治+FFT）
P3933贝壳串问题描述 海边市场有长度分别为1到n的贝壳串出售，其中长度为i的贝壳串有a[i]种，每种贝壳串有无限个，问用这些贝壳串链接成长度为n的串有多少种方案? 输入格式 第一行，一整数n， 第二行，n个整数ai表示长度为i的贝壳串的种类数 (n<=10^5,0<=ai<=10^7) 输出格式 输出方案数，结果模313 ...
2018-03-03 18:30:11
258
原创 NKOJ 3932 Meteors （整体二分+树状数组）
P3932Meteors问题描述 Byteotian Interstellar Union有N个成员国。现在它发现了一颗新的星球，这颗星球的轨道被分为M份（第M份和第1份相邻），第i份上有第Ai个国家的太空站。 这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。 BIU的第i个成员国希望能够收集Pi单位的陨石样本。你的任务是判断对于每个国家，它需要在第几次陨石雨...
2018-03-03 18:18:09
235
原创 NKOJ 3579 （NOI 2010）海拔（平面图最小割+对偶图）
P3579【NOI2010】海拔问题描述 YT市是一个规划良好的城市，城市被东西向和南北向的主干道划分为n×n个区域。简单起见，可以将YT市看作一个正方形，每一个区域也可看作一个正方形。从而，YT城市中包括(n+1)×(n+1)个交叉路口和2n×(n+1)条双向道路（简称道路），每条双向道路连接主干道上两个相邻的交叉路口。下图为一张YT市的地图(n = 2)，城市被划分为2×2个区域，...
2018-03-03 17:53:20
347
原创 NKOJ 4128 （JSOI 2016）独特的树叶（树哈希）
P4128[Jsoi2016]独特的树叶问题描述 JYY有两棵树A和B：树A有N个点，编号为1到N；树B有N+1个点，编号为1到N+1。JYY知道树B恰好是由树A加上一个叶 节点，然后将节点的编号打乱后得到的。他想知道，这个多余的叶子到底是树B中的哪一个叶节点呢？输入格式 输入一行包含一个正整数N。 接下来N-1行，描述树A，每行包含两个整数表示树A中...
2018-03-01 22:58:56
514
原创 NKOJ 3652 shallot （线性基+CDQ分治）
P3652 shallot问题描述 小苗去市场上买了一捆小葱苗，她突然一时兴起，于是她在每颗小葱苗上写上一个数字，然后把小葱叫过来玩游戏。 每个时刻她会给小葱一颗小葱苗或者是从小葱手里拿走一颗小葱苗，并且让小葱从自己手中的小葱苗里选出一些小葱苗使得选出的小葱苗上的数字的异或和最大。 这种小问题对于小葱来说当然不在话下，但是他的身边没有电脑，于是他打电话给同为OI选手的你，你...
2018-03-01 22:41:08
218
原创 NKOJ 2640 （SDOI 2013）方程（扩展Lucas+容斥原理）
P2640【SDOI2013 R1 Day2】方程问题描述 输入格式 输入含有多组数据 ，第一行两个 正整数 T，p。T表示这个测试点内的 数据 组数 ，p的含义见题目描述 。 对于每组数据，第一行 四个非负 整数 n，n1 ，n2 ，m。 第二行 n1+ n2 个正整数，表示 整数，表示 A1…An1+n2 。请注意，如果 。请注意，如果 n1+ n2 等于...
2018-02-28 22:52:46
229
原创 NKOJ 3458 （POJ 1635）地铁系统 （树哈希）
P3458地铁系统问题描述 一些大城市的地铁线路呈一棵树状，一条树枝就是一条双向地铁道路，它直接连接两个站点。任意两个站点间，有且仅有一条路径可以到达。 大多数这样的城市都有一个中央地铁站，你是一个地铁迷，假设你现在就在一座这样的城市，你想要探索所有的地铁站。你从中央地铁站出发，随机选了一条地铁线就出发了。每到一个地铁站，你都会选一条没走过的道路继续乘地铁旅行。如果当前你所在的地...
2018-02-28 22:35:50
258
原创 NKOJ 2936 （BZOJ 2001）城市建设（CDQ分治+LCT）
P2936【FJ Training 2014 Day2】城市建设问题描述 PS国是一个拥有诸多城市的大国，国王Louis为城市的交通建设可谓绞尽脑汁。Louis可以在某些城市之间修建道路，在不同的城市之间修建道路需要不同的花费。Louis希望建造最少的道路使得国内所有的城市连通。但是由于某些因素，城市之间修建道路需要的花费会随着时间而改变，Louis会不断得到某道路的修建代价改变的消息...
2018-02-22 22:29:06
377
原创 HDU 5716 带可选字符的多字符串匹配 （shift-and）
带可选字符的多字符串匹配Problem Description 有一个文本串，它的长度为m(1≤m≤2000000)，现在想找出其中所有的符合特定模式的子串位置。 符合特定模式是指，该子串的长度为n(1≤n≤500)，并且第i个字符需要在给定的字符集合Si中。 因此，描述这一特定模式，共需要S1,S2,…,Sn这n个字符集合。每个集合的大小都在1∼62之间，其中的字符只为数...
2018-02-22 20:54:35
233
原创 BZOJ 4939 （Ynoi 2016）掉进兔子洞（莫队+压位）
4939: [Ynoi2016]掉进兔子洞Description 您正在打galgame，然后突然发现您今天太颓了，于是想写个数据结构题练练手： 一个长为 n 的序列 a。 有 m 个询问，每次询问三个区间，把三个区间中同时出现的数一个一个删掉，问最后三个区间剩下的数的个数和，询问独立。 注意这里删掉指的是一个一个删，不是把等于这个值的数直接删完， 比如三个区间...
2018-02-22 16:01:15
458
原创 BZOJ 4810 由乃的玉米田 （莫队+压位）
4810: [Ynoi2017]由乃的玉米田Description 由乃在自己的农田边散步，她突然发现田里的一排玉米非常的不美。这排玉米一共有N株，它们的高度参差不齐。 由乃认为玉米田不美，所以她决定出个数据结构题 这个题是这样的： 给你一个序列a，长度为n，有m次操作，每次询问一个区间是否可以选出两个数它们的差为x，或者询问一个区间是 否可以选出两个数它们...
2018-02-22 14:53:09
247
原创 NKOJ 3446 （HN Training 2015）Shopping （点分治+树形dp）
P3446【HN Training 2015 Round7】问题描述 容易发现最后答案是树上的一个联通块，但直接dp难度较大，考虑用点分治转化成一定包含根的联通块。点分治后，每一层考虑包含根的联通块，那么转化成一个树形依赖背包，只有选了父节点才能选子节点，并且每个物品有个数限制。这里对于这种树形依赖dp，可以采用dfs序来简化，因为在dfs序中，一颗子树必然是连续的一...
2018-02-21 23:04:07
310
原创 Codeforces 666E Forensic Examination （后缀自动机+线段树合并）
E. Forensic Examination The country of Reberland is the archenemy of Berland. Recently the authorities of Berland arrested a Reberlandian spy who tried to bring the leaflets intended for agitation...
2018-02-21 22:40:35
390
原创 NKOJ 2966 （BZOJ 3622）已经没什么好害怕的了 （DP+二项式反演）
P2966【2014湖北省队互测week2】已经没什么好害怕的了问题描述 已经使Modoka有签订契约，和自己一起战斗的想法后，Mami忽然感到自己不再是孤单一人了呢。 于是，之前的谨慎的战斗作风也消失了，在对Charlotte的傀儡使用终曲——Tiro Finale后，Mami面临着即将被Charlotte的本体吃掉的局面。 这时，已经多次...
2018-02-21 22:22:18
446
原创 NKOJ 3441 Lucas的数论（杜教筛）
P3441【HN Training 2015 Round5】lucas的数论问题描述 数据范围 对于100%的数据:n<=1000000000直接推式子，用到一个公式，这个公式也比较显然，就是根据定义直接得到，注意到不互质的数对乘积也一定会被乘积相同的一个互质数对算到。 Ans=∑i=1N∑j=1Nτ(i×j)，已知τ(i×j)=∑x|i∑y|j1[gcd(x,...
2018-02-20 23:38:59
286
原创 NKOJ 2003 （CQOI 2006）凸多边形（半平面交）
P2003【CQOI2006】凸多边形问题描述 逆时针给出n个凸多边形的顶点坐标，求它们交的面积。例如n=2时，两个凸多边形如下图： 则相交部分的面积为5.233。输入格式 第一行有一个整数n，表示凸多边形的个数，以下依次描述各个多边形。第i个多边形的第一行包含一个整数mi，表示多边形的边数，以下mi行每行两个整数，逆时针给出各个顶点的坐标。输出格式...
2018-02-20 22:19:01
214
原创 NKOJ 1522 （NOI 2006）最大获利（最小割）
P1522【NOI2006 Day2 T1】最大获利问题描述 新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。 THU集团旗下的 CS&T通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。 在前期市场调查和站址勘测之后，公司得到了一共 N个可以作为通讯信号中转站的地址，而由于...
2018-02-20 22:14:44
196
原创 PKUWC2018 游记
Day 0刚到长沙，下午签到很水的样子，人没到也能签到。 晚上做了几道模板题，感觉ACM赛还是很稳。Day 1上午开幕式听了一波计算机史，很有意思。 笔试的数学水的不行，然而并没能做完，解答题四道，T1裸的归纳法，T2叉乘随便算一下，T3均值不等式+三角不等式，T4向量变换，直接用模长反证即可，详细情况可以去网上翻翻？ 下午机试，出人意料的是IOI赛制，五个小时三道题。 ...
2018-02-11 14:08:09
736
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人