- 博客(75)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 【杂题】bzoj2144跳跳棋
AC链接 神题一道，反正蒟蒻乱搞拿了25分…举一个栗子： -10 -9 7 分析一下这个栗子： 从（−10，−9，7）（-10，-9，7）棋子向两边跳可以到（−11，−10，7）（-11，-10，7），（−25，−10，−9）（-25，-10，-9） 令dis=−9−(−10)=1,dis2=7−(−9)=16dis=-9-(-10)=1, dis2=7-(-9)=16，由于dis<dis
2016-05-19 23:00:57
598
1
原创 【杂题】[POJ3222]Edge Pairing
AC链接题目大意：给定一个nn个节点，mm条边的图。如果某两条边有公共顶点，则这两条边可以匹配。问是否存在一个匹配方案，使得所有的边都恰好被匹配一次。 数据范围：3≤n≤20000,2≤m≤100000,3≤n≤20000,2≤m≤100000,其中mm为偶数，且图联通。跪膜大神fanhqme 膜拜链接然而感觉就是xjbdfs… 在dfs搜索树上分治？（如果一定要强行加上什么算法的话…在dfs
2016-05-18 15:07:51
723
原创 APIO滚粗记
Day-1 早上就知道了机房断网的好消息（这能玩？！），然后又不知道去何处蹭网…在笔记本上玩辣鸡小游戏默默滴等待隔壁网管… 一开始来了一个网管…然后他走辣（心中无数只草泥马在欢腾…… 在临近午饭时间终于来网辣… 然后下午就敲了敲板子，愉快的回家收东西（lang）辣 Day0 5点钟起床赶飞机… 然后竟然和一中的神犇一个飞机，感觉好尴尬… 上飞机继续睡觉，默默滴感受一中神犇第一次坐飞机
2016-05-08 21:24:17
981
1
原创 【kd-tree】BZOJ4520 CQOI2016K远点对
传送门平生第一次在bzoj上排到了rank1，载图留恋 之所以写这篇博客是因为CQOI2016的SB出题人居然让什么三分和卡壳这样A了（其实三分感觉不是很好卡…） 以下是Claris老司机对卡壳错误的证明…（图片来至UOJ用户群…） 其实这是一个模板题… 第k远点对肯定在某一个点的前k远距离中… 然后就用kd-tree把某一个点的前k远距离都找出来… 然后再加一些弱弱滴剪枝就可以
2016-04-13 13:11:11
2093
原创 CQOI2016滚粗记
day0 上去试机发现鼠标是坏的，旁边是巴蜀的大牛和教师机… 随手敲了一个树剖和Pollard_rho，顺路用批处理对拍了一下，然后想去交一发意外的发现竟然木有网….晚上复习了一下板子…然后写得有点兴奋了就睡不着辣…day1 上歌乐山的时候还在下雨… 然后我7点就悠悠的到了门口…然后就在外面晃荡了40多分钟… 8点过就进了考场，发现解压密码一点都不好玩…看到T1的时候心里一阵窃喜，嘿嘿我做
2016-04-11 21:05:30
2122
13
原创 莫比乌斯反演之入门
前言很久以前就学了莫比乌斯反演，然而一直都木有来写一个总结，省选完后今日来补坑…姿势其实莫比乌斯反演就是一个公式… F(n)=∑d|nf(d)⇒f(d)=∑d|nμ(d)∗F(nd)F(n)=\sum_{d|n}f(d) ⇒ f(d)=\sum_{d|n}\mu(d)*F(\frac n d)证明如下： ∑d|nμ(d)∗F(nd)=∑d|nμ(d)∗∑a|ndf(a)\sum_{d|n}\m
2016-04-11 20:20:58
883
1
原创 【线段树】BZOJ4373算术天才与等差数列
传送门 Description 给定一个长度为 n 的序列，其中第 i 个数为 ai。 有 m 次操作，每次要么修改其中的某一项，要么给出询问l; r; k，问区间 [l; r] 内的数从小到大排序后能否形成公差为 k 的等差数列。 Input 第一行包含两个正整数n,m(1<=n,m<=300000)n,m(1<=n,m<=300000)，分别表示序列的长度和操作的次数。 第二行包含n
2016-03-01 23:59:49
1092
2
原创 【树DP】UVA12929Aerial Tramway
传送门 题目大意：给定 n 个点 (xi,yi)(x_i, y_i)，形成一条折线，满足xi,yi>0x_i, y_i>0，xixi+1x_i，yi≠yi+1yi \neq yi+1对于两个点，如果它们高度相等，且中间所有点都严格低于这两个点，那么你可以在两点间连一条边。你需要连恰好mm条边，满足每个点严格低于不超过kk条边，请最大化所有边的长度和。
2016-03-01 00:05:13
383
原创 【cdq分治&NTT】BNUOJ51279组队活动
传送门在这之前先去看看BNUOJ51280是这道题的弱化版。先附上出题人题解 题解令ans[i]ans[i]表示当n=in=i时的答案。 考虑第ii个人所在队伍的人数为jj。 那么有ans[i]=∑j=0min(i,m−1)ans[i−j−1]∗Cji−1ans[i]=\sum_{j=0}^{min(i,m-1)}ans[i-j-1]*C^{j}_{i-1} 于是乎弱化版问题这样愉快滴解决辣。
2016-02-28 18:29:29
595
原创 【树DP】BZOJ3836[Poi2014]Tourism
Description 给定一个nn个点，mm条边的无向图，其中你在第ii个点建立旅游站点的费用为CiC_i。在这张图中，任意两点间不存在节点数超过1010的简单路径。请找到一种费用最小的建立旅游站点的方案，使得每个点要么建立了旅游站点，要么与它有边直接相连的点里至少有一个点建立了旅游站点。 Input 第一行包含两个正整数n,m(1<=n<=20000,0<=m<=25000)n,m(1<=
2016-02-28 15:51:43
1343
1
原创 【数位DP】CF55D BZOJ3329 HDU4352 SGU390 HDU5519
前言有一些题之前已经写了题解了，就只留一个链接吧…一般的数位DP都是计算一段区间满足某条件的数有多少个。 顾名思义数位DP就是按照数一位一位滴进行DP。通常至少有二维，其中一位表示当前在第ii位上，另一维表示与nn的大小关系。 具体实现方法通常有递推版和记忆化搜索版。SPOJ10606SPOJ10606BZOJ3629BZOJ3629CodeForces55DCodeForces-55D 题目
2016-02-27 01:12:48
1523
原创 【数位DP】BZOJ3780数字统计
Time Limit: 10 Sec Memory Limit: 128 MB Description 小A正在研究一些数字统计问题。有一天他突然看到了一个这样的问题： 将[L..R][L..R]中的所有整数用MM位二进制数表示（允许出现前导00）。现在将这些数中的每一个作如下变换： 从这个数的最低两位开始，如果这两位都是00，那么X=1X=1，否则X=0X=0。现在将这两位删去，然后将X
2016-02-26 12:20:17
1310
原创 【数位DP】BZOJ3629数字之积
传送门数位DP大法好… 乘积太大保存不下来肿么办？ 这乘积都是11到99的数字乘起来滴，于是乎用质因数表示就好了，特别注意对每一种质数的最大个数最好卡着开数组，要不然很容易MLE滴…原谅蒟蒻太弱，代码为了放错就写的很丑= =#include <iostream>#include <cstdio>#include <cstring>#define LL long long intusing
2016-02-24 00:14:07
692
原创 【数位DP】SPOJ10606Balanced Numbers
传送门 题目大意：一个数被称为是平衡的数当且仅当对于所有出现过的数位，偶数出现奇数次，奇数出现偶数次。 给定AA，BB，请统计出[A,B][A, B]内所有平衡的数的个数。注意，这里的偶数是指出现过的数，并且不能计算前导零。蒟蒻一开始理解成所有的偶数和奇数，被坑成狗QAQ对于每一个数有三种状态： 00：这个数还木有出现过。 11：这个数出现过奇数次。 22：这个数出现过偶数次。 于是乎用
2016-02-23 23:49:22
677
原创 【数位DP】ZOJ2599Graduated Lexicographical Ordering
传送门 Time Limit:10S Memory Limit:32768KB Description 我们定义一种独特的给数排序的方法： 对于两个数，数码和较小的排在前面。因此120120排在44前面，44排在42294229前面。对于两个数码和一样的数，字典序小的排在前面。因此555555排在7878前面，2020排在200200前面。 现在给你NN个数1 N1~N，希望你对
2016-02-23 23:23:53
494
原创 【杂题】bzoj3735[Pa2013]Konduktorzy
权限题，无法传送%>_<%Time Limit: 10 Sec Memory Limit: 128 MB Description 一辆无限长的列车,有kk个检票员，每个检票员一次检验aia_i个车厢，初始时所有检票员在00号车厢，列车长每次命令最靠左的编号最小的且能够继续检票的检票员向右走aia_i步，一共发出nn个命令，输出每个售票员走的最后一步是列车长的第几次命令。 Input 第一行
2016-02-23 09:49:26
777
原创 【DP】BZOJ4347[POI2016]Nim z utrudnieniem
一道权限题/(ㄒoㄒ)/~~无法传送Time Limit: 3030 Sec Memory Limit: 6464 MB Description A和B两个人玩游戏，一共有mm颗石子，A把它们分成了nn堆，每堆石子数分别为a[1],a[2],...,a[n]a[1],a[2],...,a[n]，每轮可以选择一堆石子，取掉任意颗石子，但不能不取。谁先不能操作，谁就输了。在游戏开始前，B可以扔掉若
2016-02-20 23:48:38
715
原创 【HDU5452】Minimum Cut
转送门 题目大意：已知一个nn节点mm条边的无向图以及它所对应的一棵生成树，要求只能删除一条树边和若干条非树边，求最少要删除多少条边。 注意：必须删除一条树边且只能删除一条树边（蒟蒻一开始理解成了至少删除一条树边QAQ）既然必须删除一条树边，那么就枚举这一条树边吧o(>﹏<)o 删去这条树边之后，生成树就被分成了两个部分，我们只需要将连接这两个部分的边全部删除即可。那么问题来了，怎样快速滴算出
2016-02-20 22:59:18
676
原创 【点分治】poj1741
众所周知，树分治有两种：点分治和边分治。顾名思义，点分治是按点进行分治，为了让子问题的规模尽量小，我们通常选择重心做为分治的点；而边分治通常选择使得所分离出来的两棵子树的结点个数尽量平均的边。求重心和这样的边均可以用树DP的方法解决。通常点分治和边分治的递归层数为O(logn)O(log_n)，在实际运用中，边分治的层数经常达到O(n)O(n)效率低下…… 以上均属于扯淡……关于树的分治有一篇IO
2016-02-15 23:55:35
485
原创 WC2016酱油记
25日报到日 中午到绵阳，火车站有志愿者接客，还是很不错的。下午在azui大神的带领下，吾等蒟蒻学习了毒瘤算法cdq分冶（逃…… 然而一道题都木有写→_→ 晚上的开幕式，度娘被子德主席黑成谋材害命也是迷醉Q_Q 26日 南山中学的早餐丰盛，早餐罕见的吃撑了→_→ 出于对于神牛的膜拜，蒟蒻一直坚持在第一课堂（虽然每天冬眠一小时QAQ）。第一节课是业界毒瘤picks讲多项式导论（就是他把冬令营
2016-02-02 09:58:10
926
原创 【网络流之最小割模型】poj3469 BZOJ3144 UVA1212
1.poj3469 题目大意：有nn个任务，每个任务均可以在2个核上完成。其中，有mm对任务之间需要信息交换，即若这两个任务在不同核上完成需要另花ww。求最小费用。建立nn个节点表示任务，源点代表第一个核，汇点表示第二个核。第ii个点向源点连边，容量为aia_i；向汇点连边，容量为bib_i。若i,ji,j之间有信息交换，那么i,ji,j之间连一条容量为ww的无向边。答案为最小割。 如何理解？
2016-01-20 23:34:39
412
原创 【搜索】BZOJ3139 HNOI2013比赛
BZOJ3139 搜素题一道。 n<=8n<=8乱搞都可以过。（BZOJ1306和这道题一模一样，只是n<=8n<=8）优化一： 以剩下的队的分数按28进制数来描述。一定要把个数也加进去。之后用map进行离散化。虽然状态很多，map还是可以接受。 注：当一个队的分数已经被用完了的时候才将它放入map中。否则还需要按当前是哪一个队伍以及分配到第几场比赛上，再进行离散化。这不仅耗时，状态太多了…
2016-01-15 01:09:37
456
原创 【上下界网络流】sgu194 zoj3229 sgu176 zoj1994 zoj3496
终于意识到了一个好的网络流模板是有多么重要。%>_<% 而且上下界的代码细节特别多，再加上蒟蒻木有写一段就检查的好习惯，直接导致调了很久……sgu194 这是一道无源点汇点的求上下界网络流的可行流。 首先把它转化为一个有源点汇点的网络流。令du[u]du[u]表示出边的下界之和减去入边的下界之和。把所有边的流量改为up−downup-down（上界-下界）。 建立一个超级源点ss和超级汇点t
2016-01-07 21:14:04
451
原创 【费用流】hdu1533 poj2516 bzoj1070 bzoj1061
费用流是在网络流的基础上求流最大的前提下使得费用最小（或者最大）。算法一：SPFA寻找增广路 在isap算法中，是当dis[v]+1==dis[u]dis[v]+1==dis[u]时才访问vv。即边(u,v)(u,v)的边权为11。在这里令边权为流过该边的费用即可。bool spfa(){ queue<int>q; for(int i=b;i<=e;++i)dis[i]=inf,
2016-01-03 14:47:42
351
原创 【后缀自动机】SPOJLCS SPOJNSUBSTR SPOJLCS2 HDU4416
据说后缀自动机可以替代后缀数组和后缀树…… 后缀自动机，用线性的节点数来保存所有的后缀。构建自动机struct node{ int ch[26], len, link; void init() { len=link=0; memset(ch,0,sizeof ch); }}tree[MAXN<<1];int pos;char w
2015-12-29 23:21:15
358
原创 【AC自动机】hdu2222 hdu2896 hdu3065 zoj3430 poj2778 hdu2243
AC自动机用于多个模式串与多个母串的匹配。 第一步：根据模式串建立字典树int len=strlen(w), r=root; for(int i=0;i<len;++i) { if(tree[r].ch[w[i]])r=tree[r].ch[w[i]]; else r=tree[r].ch[w[i]]=++cnt; } ++tree[r].c
2015-12-24 20:31:17
534
原创 【manacher算法】HDU3294 URAL1297
manacher算法用于计算最长回文子串。 上模板 //s是原子符串，而w是在s的前面、后面、字符之间插入一个未出现的字符‘#’ scanf("%s",s); w[0]='*';//防止越界，在最前面加上一个‘*’ w[++len]='#'; for(int tmp=strlen(s), i=0;i<tmp;++i) { w[++len
2015-12-19 12:08:16
364
原创 【Floyd判圈算法】UVa11549Calculator Conundrum
题目链接 该题在《训练指南》中有，这一道不错的题。 题目描述：对一个数kk，取k∗kk*k的前nn个数。无限操作下去。求其中出现的最大值。 数据范围：1<=n<=91<=n<=9，0<=k<10n0<=k<10^n首先肯定会出现循环，只有10n10^n个数。 如何判环决定了耗时的多少。算法一：用STL中的set set版，耗时823823ms#include <cstdio>#inclu
2015-11-15 21:37:12
372
原创 【总结】20151031重庆市NOIP模拟赛
世上最最悲催的事莫过于手残打错字母… 考完之后还是一句话我是SB… 今日的题其实都想到了正解，然而就木有AC一道题… 第一题当时想了很久，不知道为什么会对这个模型如此生疏（可能是好久都木有做组合数学的题了），还是在写第三题的时候才想出来。一阵狂喜就手残打错字母了……
2015-10-31 16:20:04
1382
原创 【总结】20151024重庆市NOIP模拟赛
考完之后看了题解重写了代码之后的第一感觉就是我是SB= = 第二题想多了做不出来，第三题把映射关系搞反了（明明可以骗个20左右，然后滚粗只骗了个5分，可伶蒟蒻写了1个多小时）。又开始犯SB错误了%>_<% 好吧至少第一题AC了。现在看来第一题还是蛮重要滴……第二题做不出来是一个很严肃的问题，说明思维还有待提升…… 当时看完第二题就蒙了，完全木有思路，然后就开始乱搞了。也想到过一个一个往里面加
2015-10-24 17:57:13
1429
原创 【总结】20151017重庆市NOIP模拟赛
这场比赛有点难，考完了之后感觉要爆零了/(ㄒoㄒ)/~~这次比赛还算不错，发挥出了正常水平（木有犯SB错误）。主要是因为第一题乱yy写了一个不知道比标程慢了无数倍的代码，然后A掉了。 藐似第一题比较关键，之后的比赛不能在第一题上掉以轻心。（默认第一题最简单O__O “…）这次在比赛的前几分钟看了一下题目，在做的过程中先跳过了第二题，所以才尽可能的得到了最多的分。（虽然现在看来第三题要比第二题难得多
2015-10-19 23:18:49
1243
原创 20151006重庆市NOIP模拟赛总结
今天感觉一般般，至少没有出现sb错误。 只不过看了题解感觉自己都应该做得起（= =），在考试的时候也有往正确的方向去想过甚至一样……然而对这个思路报以怀疑的态度，就没有这样写。 比如说今天的第二题在考试的时候就一直纠结，是否会在第一类情况中存在一个数，他并不是在第一类情况中的最优解，并且在向下一个状态转移时应该从第一类情况变为第二类情况，然后是第二类情况的最优解，然后与第一类情况的最优解相比更优
2015-10-06 15:55:29
1150
原创 考试总结
题目及数据下载 这次考得并不好= = 各种sb错误再次重演……第一题连题都木有读完就开始做了，弱弱地过了样例（好吧样例并没有什么卵用……）就开始往下看了……
2015-10-06 15:30:43
473
原创 【STL】STL之lower_bound与upper_bound
这两个函数都用于二分查找。当然，必须要先进行升序排序。一.lower_bound lower_bound用于查找某个元素第一个不小于它的元素地址。 lower_bound(begin,end,a)在[begin,end)中查找第一个不小于a的元素地址。例如： 1 1 2 2 3 5 6 （下标从1开始） lower_bound(1)返回位置为1 lower_bound(4)返回位置为6
2015-09-15 21:37:39
391
原创 【STL】STL之pair
一.构造 1.make_pair()pair<string,int>t1=make_pair("January",1);pair<int,int>t2=make_pair(2,1);2.分别赋值 对第一个元素赋值：p.first= 对第二个元素赋值：p.second=pair<string,int>t1;t1.first="January" ,t1.second=1 ;二.访问 正如上面
2015-09-15 21:08:01
267
原创 【STL】STL之set
集合（set）实现了快速查找元素、插入元素以及删除元素。具体实现则采用了红黑树的二叉平衡搜素。特点： 1.元素不重复。 2.采用中序遍历算法，使得效率比vector，map，list高。 3.自动按照key的大小排序。一.创建set集合对象 在创建set对象时，与其他STL的容器一样，需要指定类型。#include <iostream>#include <set>
2015-09-14 17:51:02
311
原创 【STL】STL之map
mapmap作为STLSTL中一个类似于HASHHASH的容器，内部以红黑树实现。常见操作： 一.构造 例如：mapint,int>hash;第一个类型为原类型，而第二个类型为hash之后的类型。二.插入mapstring,int>hash;hash["hello"]=1;hash.insert(pairstring,int>("hi",2));hash.insert
2015-09-13 11:27:10
324
原创 【扩展欧几里得+解不等式】sgu106The equation
题目链接 题目大意：对于一个不定方程ax+by+c=0ax+by+c=0，其中x∈[x1,x2]x∈[x1,x2]和y∈[y1,y2]y∈[y1,y2]。求有多少组解。 数据范围：每一个数的绝对值不超过10810^8。一道裸的扩展欧几里得。 首先将方程变式为ax+by=−cax+by=−c，即c=−cc=−c。 假设a,b,ca,b,c都是正数。 若求得一组解x,yx,y，那么x=
2015-09-10 16:50:32
1366
原创 COCICONTEST# 29.11.2014# 题解+总结
NOIP临近，刷刷题。 这场比赛下来明显觉得自己代码能力不够，比如第五题stogovi很明显的LCA，也想到是用LCA，然而并木有写出来，对模板的应用不够熟练。在思维方面不够严谨，比如第四题coci，没有意识到题目给的选手分数范围的意义，也可能是因为读题不够仔细吧。在时间分配上还存在严重问题，前面的水题不能保证正确性，想错或者在某个地方手抽打错，在调试上花了很多时间以至于想后面的题时有一点慌。这也
2015-09-04 21:46:14
697
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人