outer_form-CSDN博客

原创【NOI2017】退役记——这是最坏的时代，也是最好的时代

NOI2017Day 0早上从重庆坐火车去杭州，中途在利川恩施段遇到暴雨铁路封闭，到杭州的时候比预计晚了大概80min，成功错过去绍兴的高铁，只好在杭州住了一晚上。Day1 Check in Day 中午从杭州去绍兴，下了火车才意识到绍兴原来比火炉之首的重庆还要热，嘿嘿。听说重庆队其他从重庆出发的人坐的飞机晚点了，所以他们比我还来得晚一个小时，然而从芜湖出发的dalao早就到了。南开的两

2017-07-29 00:08:09 7810 7

原创【回文树】[APIO2014]Palindromes

题目链接分析用回文树，求出回文串的长度和出现的次数即可。代码#include#include#include#define MAXN 300000#define MAXC 26using namespace std;char s[MAXN+10];int n;long long ans;inline void Read(int &x){ static ch

2017-07-15 17:25:36 488

原创【线段树】[BZOJ2104/WC2009]最短路问题

题目描述分析在一个长条状的东西上维护信息，我们可以想到使用线段树。对于一个对应范围为[L,R][L,R]的节点，我们维护区间内最左边的那一列的点的每一个点和最右边一列的每一个点两两之间只经过[L,R][L,R]的点的最短路。关于合并，可以查看http://blog.csdn.net/iamzky/article/details/42119193 关于最后求答案呢。我们求出1..l +

2017-07-15 17:24:56 778

原创【提交答案题】[WC2009]优化设计

题目描述分析第1、2组数据很小，直接枚举。第3、4组数据都是A|BA|B的形式，其中AA和B=xiB=x_i或~xix_i，而且答案是全都可以满足，标准的2−SAT2-SAT第5、6组数据也是A|BA|B的形式，但是AA和B=xi1&xi2…B=x_{i1}\verb'&'x_{i2}\dots 可以使用一下分配律。第5组可以全部满足，又是

2017-07-15 17:24:02 989

原创【数论+组合数学】[省选十连测第十场]基本题

题目描述【问题描述】所谓的考试，就一定会有一道基本题给大家送分，而不嵌套题目的基本题怎么称得上基本呢？我们可以把基本题具体看成由(),!四种字符组成的一个字符串，一道基本题是由若干个嵌套题中间加上,分隔组成，而所谓的嵌套题指的是一对括号之间放入若干道由 ! 分隔的基本题。例如 (()!(()!())),(()!())就是一道基本

2017-07-15 17:23:34 785

原创杜教筛

莫比乌斯函数前缀和51nod - 1244 令S(n)=∑ni=1μ(i)S(n)=\sum_{i=1}^n\mu(i)，求S(n),1≤n≤1010S(n),1 \le n \le 10^{10}做法[n=1]=∑d|nμ(d)[n=1]=\sum_{d|n}\mu(d) ∑i=1∑d|iμ(d)=∑i=1∑j=1⌊ni⌋μ(j)=∑i=1nS(ni)=1\sum_{i=1}

2017-07-15 17:22:04 1666 1

原创【PKUSC2017】我是一条咸鱼

Day0报到日，我准备先去PKUSC考一天，再决定是继续是留在PKU还是THU，结果重庆省队过了THU初审的同学都是这么想的。。。。由于酒店离PKU有4km，试了试骑ofo去pku，由于有了之前apio、ctsc的骑(qiao)行(ke)经验，去北大只要20分钟，然后徒步和坐公交需要1h左右，感觉很赞。Day1今年先考数学，由于我太弱，所以感觉很难，考完之后有把握的只有两道题，和去年相比难度陡增

2017-05-23 11:58:14 2837 1

原创【数论】[CQOI2017]小 Q 的表格

好气哦！！！题目描述输入输出输出文件 table.out。输出共m行，每次操作之后输出1行，表示答案mod 1,000,000,007之后的结果。分析好气啊！！！好气啊！！这样一个傻逼题为什么当时不A 观察式子(a,a+b)(a,a+b)可以发现，我们可以根据gcdgcd给表格的元素分组。每次修改一个一个数(i,j)(i,j)，和它同组的元素都会修改。对于每一组，比如第gg组，f(i,j)

2017-04-11 10:33:28 866

原创【考试总结】[CQOI2017]考试总结

再奋斗一年，争取AK NOIP2016 CQOI2017、这是去年我立的flag。Day0看考场，电脑挺快，而且配置和评测机一样，可以放心的在自己的电脑上卡常测试啦，好评。码了一道fft的题，没网只好拷着回家交，键盘蜜汁小，enter占据了两行，旁边还有关机按钮。。。。座位安排奥妙重重，和巴蜀dyf大神坐在一起。晚上在背模板中度过。Day1巴蜀同学和往常一样，考前大喊AK，一脸懵逼。当

2017-04-10 00:00:48 1290 8

原创【NOI2016】网格

题目描述输入输出样例输入 4 4 2 1 1 4 4 2 3 1 1 2 2 2 2 1 1 2 2 1 1 0样例输出 2 1 0 -1分析我们很容易看出答案只有可能是2,1,0,-1。关于一些表述的解释我们将蝈蝈所在格子称为障碍，其余格子称为空地。根据题意，我们可以看做最外围也是一圈障碍，但是我们不去管它，一下所提到的障碍都不包括外围的一圈

2017-02-18 23:01:44 1635

原创 WC2017&THUWC2017 游记

我可能去了假的WC QAQ 人世几回伤往事，山形依旧枕寒流。day1报到日，然而我们学校从重庆坐火车去绍兴，完美错过开幕式day2上午鏼鏼鏼讲字符串，勉强听懂前半截。下午rzz的猜数游戏，尛焱轟讲IOI2016试题，勉强跟上节奏。从晚上的营员交流开始，冬眠营正式拉开序幕。 myy的Berlekamp Massey算法，从头开始懵逼敦敦敦的30KB神题彻底将我催眠，接下来的仙人掌计数在

2017-02-16 01:12:56 2846 2

原创【矩阵相关】[Codeforces - 736D]Permutations

题目大意n个的排列，给你m条规则，规则是一个数对(ai,bi)(a_i,b_i)，代表数字bib_i可以放在第aia_i个位置。对于每一条规则，如果我们删掉它，符合剩下的规则的排列数如果是奇数，就输出YES，否则输出NO。分析首先，我们可以把这些规则表示成邻接矩阵。那本来的排列数就是邻接矩阵的积和式，但是我们无法快速计算积和式，但是我们只需要知道奇偶性。考虑一下求积和式

2016-12-27 14:41:20 1007

原创【暴力/网络流】[Codeforces - 739E]Gosha is hunting

题目大意有n个口袋妖怪，a个精灵球，b个超级球，抓住第i个口袋妖怪的几率分别为pip_i和uiu_i，对于每个口袋妖怪，每种球最多只能使用1个，你必须在一开始就决定丢球的方案，使得抓住的口袋妖怪的数量最大。分析费用流对于每个口袋妖怪，如果只扔一个球，那么收益就是pi p_i或者qiq_i，如果两球都扔，收益就是分别扔两球的和减去pi×qip_i \times q_i，

2016-12-27 14:40:36 4110

原创【网络流】[Codeforces - 739D]Recover a functional graph

题目大意有一个n个点的有向图，每个点的出度为1。对于每个点，有两个信息，一个是这个点到环的距离x，一个是这个点能够到达的环的长度y。有一些点的的某些信息未知，求能否构造出这样一个图。分析对于两个信息都已经知道的点，我们就可以根据这些点来算出我们还需要哪些点。那些有部分信息未知的点就可以向需求连边，跑网络流。如果所有需求都能被满足，则有解。特别地，对于y未知的点，如果

2016-12-02 19:16:52 665

原创【DP+二分】[CodeForces - 713D] Animals and Puzzle

题目大意给你一个01矩阵，询问一个矩形区域内最大的全1正方形。分析令f[i][j]f[i][j]表示以(i,j)(i,j)为右下角的最大全1正方形。显然f[i][j]=min(f[i−1][j],f[i][j−1],f[i−1][j−1])+1f[i][j]=\min(f[i-1][j],f[i][j-1],f[i-1][j-1])+1 然后用二维st表维护f数组的区间最大值然后对于每个询

2016-09-19 13:44:54 662

原创【DP】[CodeForces - 713C]Sonya and Problem Wihtout a Legend

题目大意给你一个序列，每次操作你可以使一个数+1或-1，问最少需要多少次操作能够使这个序列严格递增。分析严格递增就是要ai+1>=ai+1a_{i+1}>=a_i+1，我们两边同时减去i−1i-1，就是ai+1−(i+1)>=ai−ia_{i+1}-(i+1)>=a_i-i 我们令bi=ai−ib_i=a_i-i，原问题就等价于使bb序列不降，这是一个经典问题。可以参考poj3666或者cf1

2016-09-19 13:31:57 4148

原创【线段树】[CodeForces - 717F]Heroes of Making Magic III

题目大意一个长度为n的序列，每一个位置都有一些小怪。英雄可以在序列上左右移动，并且可以击杀一个他所到达的位置上的小怪，每次移动必须击杀小怪。有两种操作：1 a b k 区间[a,b]中的每一个位置都增加k个小怪2 a b 英雄能否在一个端点开始，在另一个端点结束，并且杀光[a,b]内所有小怪，英雄不能移动出区间。分析设第ii个位置有aia_i个小怪假设区间为[l,r][l,r]，我们让

2016-09-19 13:14:46 552

原创【费用流】[CodeForces - 717G]Underfail

题目大意题目大概说给一个主串和几个有价值的模式串，某个模式串与主串匹配就能累加对应的价值，一个模式串可以在多个位置和主串匹配但同一个位置只能一次，此外主串各个字符最多可以用x次，问如何匹配使获得的价值最大。分析暴力匹配模式串在主串中的位置，然后在匹配区间的左端点和右端点+1的地方连一条边，容量为1，费用为匹配这个模式串的收益。然后在相邻的两个位置之间连边，容量为1，费用为0。跑一次最大费用流即可

2016-09-19 11:48:51 558

原创【Fibonacci 序列+第一类Stirling数+二项式定理】[CodeForces - 717A]Festival Organization

题目大意问有多少种方案选择k个不同的长度相同01串。这些01串中要求不能出现连续的两个0。长度在[l,r][l,r]区间内。分析很容易发现，长度为ii合法01串个数为Fi+2F_{i+2}(FiF_i表示斐波那契数列的第i项)，方案数就为(Fi+2k)F_{i+2}\choose k，令Sn=∑n+2i=3(Fik)S_n=\sum _{i=3}^{n+2} {F_{i}\choose k}，则

2016-09-19 11:30:24 1257

原创【DP or 生成函数】[CodeForces - 712D]Memory and Scores

题目大意Memory 和 Lexa分别取数，取t轮，每一轮取的数字的范围为[−k,k][-k,k]，并且将取的数字加他们的得分，问有多少种方案Memory的得分严格大于Lexa。分析算法1 :DP很容易想到计算一个人在游戏开始后得分的动态规划。令f[i][j]f[i][j]表示取了ii轮得jj分的情况，显然f[i][j]=∑l=−kkf[i−1][j−l]f[i][j]=\sum_{l=-k}^

2016-09-12 11:07:13 885

原创【多项式求逆】[BZOJ3456]城市规划

题目描述刚刚解决完电力网络的问题, 阿狸又被领导的任务给难住了. 刚才说过, 阿狸的国家有n个城市, 现在国家需要在某些城市对之间建立一些贸易路线, 使得整个国家的任意两个城市都直接或间接的连通. 为了省钱, 每两个城市之间最多只能有一条直接的贸易路径. 对于两个建立路线的方案, 如果存在一个城市对, 在两个方案中是否建立路线不一样, 那么这两个方案就是不同的, 否则就是相同的. 现在你需要求出

2016-09-07 15:49:41 545

原创【Bluestein's Algorithm】[POJ2821]TN's Kingdom III - Assassination

题目大意TN要暗杀Dzx，为了保密，他想到了这样一种方式：首先，把信息编码为N个实数，组成序列α，之后再随便搞一个长度为N的实数序列β。然后按照下面的步骤计算序列γ： 0、做一个空序列γ。 1、把β倒过来。 2、把β向右平移一个元素。最右侧的元素补到左边。 3、计算此时α和β对应元素的积的和。将其加到γ的末尾。 4、如果γ还不足N个元素，重复步骤2和3。虽然这种加密方法是很弱的，

2016-09-07 15:18:36 2200

原创【线段树分治】[BZOJ4311]向量

题目描述Description你要维护一个向量集合，支持以下操作：1.插入一个向量(x,y)2.删除插入的第i个向量3.查询当前集合与(x,y)点积的最大值是多少。如果当前是空集输出0Input第一行输入一个整数n，表示操作个数接下来n行，每行先是一个整数t表示类型，如果t=1，输入向量(x,y)；如果t=2，输入id表示删除第id个向量；否则输入(x,y)，查询与向量(x,y)点积最大

2016-08-22 15:08:04 1740

原创【树状数组】[BZOJ1878]HH的项链

题目大意DescriptionHH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。Input第一行：一个整

2016-08-14 11:17:43 401

原创【线段树】[NOI2016]区间

题目描述在数轴上有 nn 个闭区间 [l1,r1],[l2,r2],...,[ln,rn][l_1,r_1],[l_2,r_2],...,[l_n,r_n]。现在要从中选出 mm 个区间，使得这 mm 个区间共同包含至少一个位置。换句话说，就是使得存在一个 xx，使得对于每一个被选中的区间 [li,ri][l_i,r_i]，都有 li≤x≤ril_i \le x \le

2016-07-31 17:10:35 1166

题目描述如果一个字符串可以被拆分为 AABBAABB 的形式，其中 AA 和 BB 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。例如，对于字符串 aabaabaa，如果令 A=aabA = \mathrm{aab}，B=aB = \mathrm{a}，我们就找到了这个字符串拆分成 AABBAABB 的一种方式。一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。比如我们令 A=aA

2016-07-31 17:06:20 2782

原创 [跳蚤国的NOI2016]爆炸记

7 月22日坐了一上午的火车去绵阳，路上碰见了cdqz高一神犇小白（%%%，SCTSC rk5）到了之后感觉环境还不错，和我们学校另一个D类选手&巴蜀pku60分爷住在一起，放下行李之后去食堂吃午饭，南山的食堂自助很良心啊，比cqbz良心多了。下午完成了签到活动，晚上复习了一下笔试题就睡觉了。 ps:睡到一半发现断电的时候把空调的电也断了,mdzz，结果第二天就发现我感冒了7月23日（笔试）上午拍

2016-07-30 18:08:30 1177

原创 [UOJ NOI Round #1 Day1]总结

感觉考得不是很好。第一题不是很难，想了一会儿，然后一个半小时左右就写完了。读了第二题，感觉懵逼，我觉得这道题根本没法算哪，再看样例解释，完全不懂，然后手推了一下三十分，写了一个比较近似的算法，跑样例发现过了，就交了，没管了，不过最后爆零了，才发现是答案忘了清零，不过似乎清零了也没什么用。第三题我被卡题意了，一开始没有理解题目所说的下落，结果发现自己构造的答案怎么也过不了，后来等发现了就已

2016-07-17 15:15:04 480

原创【矩阵快速幂】[NOI2012]随机数生成器

题目描述栋栋最近迷上了随机算法，而随机数生成是随机算法的基础。栋栋准备使用线性同余法（Linear Congruential Method）来生成一个随机数列，这种方法需要设置四个非负整数参数 m,a,c,X0，按照下面的公式生成出一系列随机数<Xn>： Xn+1=(aXn+c) MOD m; 其中 MOD m 表示前面的数除以 m 的余数。从这个式子可以看出，这个序列的下一个数总是由上一个数

2016-07-13 10:44:00 463

原创【费用流+动态加边】[NOI2012]美食节

题目描述DescriptionCZ市为了欢迎全国各地的同学，特地举办了一场盛大的美食节。作为一个喜欢尝鲜的美食客，小M自然不愿意错过这场盛宴。他很快就尝遍了美食节所有的美食。然而，尝鲜的欲望是难以满足的。尽管所有的菜品都很可口，厨师做菜的速度也很快，小M仍然觉得自己桌上没有已经摆在别人餐桌上的美食是一件无法忍受的事情。于是小M开始研究起了做菜顺序的问题，即安排一个做菜的顺序使得同学们的等待时间最短。

2016-07-13 10:29:40 635

原创【基环树DP】[NOI2012]迷失游乐园

题目描述Description放假了，小Z觉得呆在家里特别无聊，于是决定一个人去游乐园玩。进入游乐园后，小Z看了看游乐园的地图，发现可以将游乐园抽象成有n个景点、m条道路的无向连通图，且该图中至多有一个环（即m只可能等于n或者n-1）。小Z现在所在的大门也正好是一个景点。小Z不知道什么好玩，于是他决定，从当前位置出发，每次随机去一个和当前景点有道路相连的景点，并且同一个景点不去两次（包括起始景点）。

2016-07-13 10:17:11 577

原创【树的遍历】[NOI2011]道路修建

题目描述Description在 W 星球上有 n 个国家。为了各自国家的经济发展，他们决定在各个国家之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿意修建恰好 n – 1条双向道路。每条道路的修建都要付出一定的费用，这个费用等于道路长度乘以道路两端的国家个数之差的绝对值。例如，在下图中，虚线所示道路两端分别有 2 个、4个国家，如果该道路长度为 1，则费用为1×|2 –

2016-07-13 09:38:06 546

原创【矩阵快速幂】[NOI2011]兔农

题目描述Description 农夫栋栋近年收入不景气，正在他发愁如何能多赚点钱时，他听到隔壁的小朋友在讨论兔子繁殖的问题。问题是这样的：第一个月初有一对刚出生的小兔子，经过两个月长大后，这对兔子从第三个月开始，每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第n个月有多少只兔子？聪明的你可能已经发现，第n个月的兔子数正好是第n个Fibonacci(斐波那契)数。栋栋不懂

2016-07-13 09:26:48 490

原创【DP】[NOI2011]智能车比赛

题目描述Description 新一届智能车大赛在JL大学开始啦！比赛赛道可以看作是由n个矩形区域拼接而成（如下图所示），每个矩形的边都平行于坐标轴，第i个矩形区域的左下角和右上角坐标分别为(xi,1,yi,1)和(xi,2,yi,2)。题目保证：xi,1<xi,2=xi+1,1，且yi,1< yi,2，相邻两个矩形一定有重叠在一起的边（如图中虚线所示），智能车可以通过这部分穿梭于矩形区域之间。选手

2016-07-13 01:18:22 470

原创【AC自动机】[NOI2011]阿狸的打字机

题目描述Description 阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和’B’、’P’两个字母。经阿狸研究发现，这个打字机是这样工作的：l 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。l 按一下印有’B’的按键，打字机凹槽中最后一个字母会消失。l 按一下印有’P’的按键，打字机会在纸上打印出凹槽中现

2016-07-13 01:07:06 337

原创【DP】[NOI2011]NOI 嘉年华

题目描述DescriptionNOI2011 在吉林大学开始啦！为了迎接来自全国各地最优秀的信息学选手，吉林大学决定举办两场盛大的 NOI 嘉年华活动，分在两个不同的地点举办。每个嘉年华可能包含很多个活动，而每个活动只能在一个嘉年华中举办。现在嘉年华活动的组织者小安一共收到了 n个活动的举办申请，其中第 i 个活动的起始时间为 Si，活动的持续时间为Ti。这些活动都可以安排到任意一个嘉年

2016-07-13 00:46:26 660

原创【博弈+二分图匹配】[NOI2011]兔兔与蛋蛋游戏

题目描述DescriptionInput输入的第一行包含两个正整数 n、m。接下来 n行描述初始棋盘。其中第i 行包含 m个字符，每个字符都是大写英文字母"X"、大写英文字母"O"或点号"."之一，分别表示对应的棋盘格中有黑色棋子、有白色棋子和没有棋子。其中点号"."恰好出现一次。接下来一行包含一个整数 k（1≤k≤1000），表示兔兔和蛋蛋各进行了k次操作。接下来 2k行描述一局游戏

2016-07-12 22:12:08 2051

原创【拉格朗日乘数法】[NOI2012]骑行川藏

题目描述分析首先，我们来考虑一下部分分。N=1N=1直接算即可，v1=Ek1×s1−−−−−√+v′1T=s1v1v_1=\sqrt{\frac{E}{k_1\times s_1}}+v_1'\\T=\frac{s_1}{v_1} N=2N=2v1=E1k1×s1−−−−−√+v′1v2=E−E1k2×s2−−−−−√+v′2T=s1v1+s2v2v_1=\sqrt{\frac{E_1}{k_1

2016-07-10 09:26:41 1010

原创【二维线段树（二维区间GCD）】[NOI2012]魔幻棋盘

题目描述分析这是经典的区间gcdgcd（最大公约数）问题。差分GCDgcd(a,b)gcd(a,b,c)=gcd(a,b−ka)=gcd(gcd(a,b),c)=gcd(gcd(a,b−a),c)=gcd(gcd(a,b−a),c−k(gcd(a,b−a)))=gcd(gcd(a,b−a),c−b)\begin{align}gcd(a,b)&=gcd(a,b-ka) \\ gcd(a,b,c)

2016-07-09 13:35:32 978

原创【树DP+基环树】[NOI2013]快餐店

题目描述小 T 打算在城市 C 开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的，小 T 希望快餐店的地址选在离最远的顾客距离最近的地方。快餐店的顾客分布在城市 C 的 NN 个建筑中，这 NN 个建筑通过恰好 NN 条双向道路连接起来，不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。小 T 的快餐店可以开设在任一建筑

2016-07-07 23:39:16 785

空空如也

空空如也