Starlight_Glimmer-CSDN博客

原创【NOIP2017模拟赛】思维+转化+图论徒然Children（好题）

题目描述全世界都在谈恋爱，只有我深爱着学习。——前言。 2333身为单身狗却意外喜欢的吃狗粮的yuki坚信着：“自古红蓝出cp，黑白天生是夫妻，最是销魂红绿配，天然金紫成双对，生死相随红与黄，白紫一逢春满堂，千里缘牵白与绿，红黑生来为相聚。”的cp配对原则，却被徒然children中绿黄的御宅的春天组（山根隆夫×栗原千代）莫名戳中萌点。可见死宅真是一个有前途的职业。在本季末尾，一群cp们正在举

2017-11-09 17:37:19 744

原创【NOIP2017模拟赛】构造 A+B Problem（好题）

PS：|a|,|b|≤260PS：|a|,|b|≤2^{60} 无良出题人，毁我青春，耗我钱财，败我精神，颓我意志说好的呢？还能做朋友吗？于是我考试当场马上打出了一个暴力…… 不过考完后，发现这道题还是有那么一点点可做性的。首先判断无解的情况，很容易发现，由于补码表示法，负数到了高位几乎全都是11，而正数却几乎全都是00，所以正数异或正数是正数，负数异或负数是正数，正数异或负数是负数

2017-11-09 16:52:49 466

原创【NOIP模拟赛】思维+离线+递推数列（好题）

潜水多年重新上岸冒个泡…… PS：注意这道题的时间限制为2s（很重要！！！）不得不说，这确实是一道防AK的好题——见这道题的题解（多年以前的）相信很多人一看就会觉得这是一道暴力题，因为数据加了密所以根据随机性n^2算法能跑出nlogn，就算不能还有我们很重要的2s时限扛着呢是吧？然而这2s时限并没有什么用处233333（什么，我说过这很重要吗）。这道题确确

2017-10-21 18:59:22 512

原创【NOIP模拟赛三】并查集+hash day2 third 雪后村庄（好题）

题目描述输入输出输出q行，每行一个字符串“yes”或“no”（不包括引号）。样例输入Copy (如果复制到控制台无换行，可以先粘贴到文本编辑器，再复制)2 43 41 2 32 3 22 4 41 2 31 3 22 3 23 4 441 3 31 3 21 4 33 4 4样例输出n

2017-08-20 17:41:29 394

原创【CodeForces】115D Unambiguous Arithmetic Expression 组合数学

Description(translated)定义明确表达式UAEUAEUAE： 1. 自然数都是UAEUAEUAE（带前导零的也算）——换句话说，数字串是UAEUAEUAE 2. 对于两个UAEUAEUAE：XXX与YYY，(X)+or−or∗or/(Y)(X)+or−or∗or/(Y)(X)+or-or*or/(Y)是UAEUAEUAE 3. 对于一个UAEUAEUAE：XXX，+(...

2018-02-14 19:24:37 830

原创【回味】奥妙重重的字符串算法

题记蒟蒻发现自己的字符串算法基本上要丢完了……还是要捡一捡……Round1Round1Round1- KMPKMPKMP所以说作为一个字符串匹配算法，KMPKMPKMP 还是很重要的。尤其是 KMPKMPKMP 的神奇 nextnextnext 数组，可以解决循环串问题和一般的字符串匹配问题…… 具体步骤： 1. 求出模式串的 nextnextnext 数组 2. 匹配所以敲...

2018-02-11 19:05:43 464

原创「BZOJ」2154 Crash的数字表格-莫比乌斯反演

Description今天的数学课上，Crash小朋友学习了最小公倍数(Least Common Multiple)。对于两个正整数a和b，LCM(a, b)表示能同时被a和b整除的最小正整数。例如，LCM(6, 8) = 24。回到家后，Crash还在想着课上学的东西，为了研究最小公倍数，他画了一张N*M的表格。每个格子里写了一个数字，其中第i行第j列的那个格子里写着数为LCM(i, j)。

2018-01-12 16:45:06 447

原创「雅礼集训 2017 Day2」水箱并查集+树形DP

前言好久没有写博客了，写一道雅礼毒瘤题来开开刀……CSDN都转变编辑器风格了，那我也顺便转换一下写作风格啦~题目链接水箱-LOJ题目描述(改编)有一个毒瘤，长得和水箱一样，可以装很多毒液。高度可以看做是正无穷，宽度为11，长度为nn。这个毒瘤里面有 n−1n-1 个挡板，把毒瘤分成了 nn 个小格。格子里已添加了一些毒液，毒液如果超过挡板就会溢出到其他格子里(就是说不会出现

2018-01-07 11:33:53 1224 1

原创【CodeForces-617E】XOR and Favorite Number 莫队(好玩题)

DescriptionBob has a favorite number k and ai of length n. Now he asks you to answer m queries. Each query is given by a pair li and ri and asks you to count the number of pairs of integers i and j, su

2017-12-23 18:46:18 433

原创【CQOI2015】任务查询系统可持久化Treap

题目描述最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组(Si,Ei,Pi)描述，(Si,Ei,Pi)表示任务从第Si秒开始，在第Ei秒后结束（第Si秒和Ei秒任务也在运行），其优先级为Pi。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。调度系统会经常向查询系统询问，第Xi秒正在运行的任务中，优先级最小的Ki个任务（

2017-12-19 18:21:46 348

原创【HYSBZ2002】LCT模板 Bounce 弹飞绵羊(一般题)

Description某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣

2017-12-06 13:24:17 515

原创【HDU 1686】KMP+贪心剪花布条(一般题)

题目描述一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？输入输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符，则不再进行工作。输出输出能从花纹布中剪出的最多

2017-11-21 18:14:18 837

原创【爆炸总结】NOIp2017赛(Bao)后(Zha)总结

题记NOIP2017NOIP2017的闭幕让我感到一丝仓促，还未准备好迎接已经爆掉的惨不忍睹的分数。一瞥提高组Day1Day1 t1t1 题目大意：给出互质正整数a、ba、b，求最大的正整数kk，没有正整数x、yx、y能使等式ax+by=kax+by=k成立 t2t2 题目大意：多组数据，给出一个仅有forfor循环和breakbreak语句的程序，每层循环的格式如下： for(

2017-11-14 19:26:27 1208

原创【NOIP2017模拟赛】二分图+状态压缩DP Graph（好题）

这道题其实是一个NPNP完全问题（2333323333），但是由于数据小啊，我们可以搞一搞。很容易发现，如果我们将一个点拆成两个点，一个代表出点，一个代表入点。当增加了一条有向边，就出点向入点连一条边（例如将uu拆成u1、u2u1、u2，vv拆成v1、v2v1、v2，然后边u−>vu->v就变成边u1−>v2u1->v2），我们发现这样就变成了一个二分图（怎么可能两个出点或两个入点之间有一条边呢……

2017-11-09 17:12:10 681

原创【复习】NOIP2017提高组-背板开始

emmmm，NOIP2017就要来了，还是思考一下怎么复习吧~ 打模板或许是一个很不错的选择~ 好了我们就响应号召，努力打模板吧~做一个优秀的背板先生（划掉）~

2017-10-26 14:16:10 524

原创【NOIP模拟赛六】状态压缩DP day1 second 酷子集

由于这道题我惊人地做出了正解（虽然考试时有小错误只有90分），所以我打算先抛掉模拟赛三day2 third，来写这道题了。。。很容易发现n的范围很大，都是无法承受的，所以我们需要换个想法。很容易发现，所有满足条件的集合，每个数字最多出现一次，而总共有个数字，我们可以考虑枚举这个数字的状态。设表示所用的数字集合是且集合中所有数均不超过的方案总数，考虑的一个子集，用组成一个数，组成其余的数

2017-08-20 16:28:34 363

原创【NOIP模拟考三】线段树/ST表 day2 second 二叉树

题目描述给定一棵二叉树，节点标号从1到n。在不改变其中序遍历的情况下，请改变树的结构，使得这棵二叉树的先序遍历（前序遍历）字典序最小。输入第一行一个整数n，表示二叉树的节点数。接下来n行，每行两个整数。第i行的两个整数表示编号为i的节点的左儿子和右儿子的编号（不存在即为0）。输出输出一行n个整数，表示不改变中序遍历的情况

2017-08-19 18:14:52 375

原创【NOIP模拟考三】水资源 day2 first 序列计数

题目描述输入两个整数m和k输出输出一个整数样例输入Copy (如果复制到控制台无换行，可以先粘贴到文本编辑器，再复制)5 3样例输出10提示自己挖的坑，死都要填完。。。Orz 话说才写到模拟考三，模拟考五都已经考完了。。。（貌似一和二只写了几

2017-08-19 17:29:41 330

原创【NOIP模拟考三】DP+组合数 day1 third 小球游戏

题目描述输入输出样例输入Copy (如果复制到控制台无换行，可以先粘贴到文本编辑器，再复制)40 01 10 11 0样例输出12 三连击就快完成了。。。（PS：本题答案mod 998244353，这是一个质数）这道题还是有点难想，我本来看数据就知道只有两

2017-08-14 17:55:41 365

原创【NOIP模拟考三】无向图的桥 day1 second 荒岛野人

题目描述输入输出样例输入Copy (如果复制到控制台无换行，可以先粘贴到文本编辑器，再复制)8 73 41 22 33 13 64 57 81 10 00 00 11 01 01 00 1样例输出3000221提示

2017-08-14 17:28:13 290

原创【NOIP模拟考三】水资源——二分答案+Floyd验证 day1 first 信号连接

题目描述输入输出样例输入Copy (如果复制到控制台无换行，可以先粘贴到文本编辑器，再复制)4 250 06 812 014 0样例输出5.00000000提示n≤100精度要求1e-6,建议保留8位输出

2017-08-14 17:13:25 334

原创【POJ 3301】三分 Texas Trip

After a day trip with his friend Dick, Harry noticed a strange pattern of tiny holes in the door of his SUV. The local American Tire store sells fiberglass patching material only in square sheets. Wha

2017-07-15 16:47:45 369

原创【POJ 1987】树的点分治 Distance Statistics

Frustrated at the number of distance queries required to find a reasonable route for his cow marathon, FJ decides to ask queries from which he can learn more information. Specifically, he supplies an

2017-07-15 16:19:34 370

原创【知识】贪心

贪心，也许算是算法中比较简单的一个了，然而要看出一道题是贪心并不是那么容易的。这两天学习了贪心，来总结一下贪心的套路。 1.猜测有时候见到一道题，看起来挺像动态规划，但仔细琢磨发现又不太像，于是猜测这是一道贪心题目，然后给出验证，就可以很轻松的解决这道题了。所以，遇到最优子结构的题，可以猜测是否是贪心。 2.验证猜测这道题是贪心之后，应该要去想办法验证它

2017-07-14 14:00:10 466

原创【学校OJ】 avl平衡树+线段树二逼平衡树

题目描述你需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：1.查询k在区间内的排名, 一个数的rank是比它小的数的个数+12.查询区间内排名为k的值3.修改某一位置上的数值4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)5.查询k在区间内的后继(后继定义为大于x，且最小的数)输入第一行两个数 n,m 表示长度

2017-07-14 12:24:16 490

原创【NOIP模拟考一】组合数学 day1 third 子集

【问题描述】azui大爷在quack大爷的带领下开始玩集合了，可是他太懒了，不想做quack大爷布置的作业题，便拿来给你做了：S 集合中有n个不同的元素，我们从1-n标号。考虑S 的子集Si,j，将这些子集排成一个r行c列矩阵的样子。其中第一行为S1,1,S1,2,…,S1,c，第二行为S2,1,S2,2,..,S2,c一直到第r行为Sr,1, Sr,2,…, Sr,c。这些集合还

2017-07-11 16:57:09 348

原创【知识】组合数学

组合数学，像数论一样是发源自数学的恶心东西，在计算机上更是与取余成为结发夫妻，与DP和数论的关系也不一般。更因为计算机令人惊骇的枚举耐心，出现了更加可怕的变种题目。好了，现在进入正题。 1.计数原理（我不愿多说了） 1）加法原理 2）乘法原理 3）抽屉原理 4）容斥原理尴尬事实：加法原理和乘法原理——基本不会单考... 抽屉最多是你在草稿纸里的

2017-07-10 22:32:48 1545

原创【HDU 4810】组合数学 Wall painting

Ms.Fang loves painting very much. She paints GFW(Great Funny Wall) every day. Every day before painting, she produces a wonderful color of pigments by mixing water and some bags of pigments. On the K-

2017-07-10 21:10:34 501

原创【HDU 3208】组合数学+动态规划湫秋系列故事——安排座位

为了给腾讯公司找到更多优秀的人才，HR湫秋最近去某高校组织了一次针对该校所有系的聚会，邀请了每个系的一些优秀学生来参加。　　作为组织者，湫秋要安排他们的座位。这并不是一件很简单的事情，因为只有一排位置，并且位置总数恰好等于参加聚会的人数。为了促进交流，两个来自相同系的同学不可以座位相邻。湫秋现在希望知道有多少种不同的合理安排座位的方法（任意两个合理的安排方法，只要有一个位置的同学不同，都

2017-07-09 11:09:26 705

原创【HDU 4248】组合数学 A Famous Stone Collector

Mr. B loves to play with colorful stones. There are n colors of stones in his collection. Two stones with the same color are indistinguishable. Mr. B would like to select some stones and arrange the

2017-07-08 10:11:01 617

原创【学校OJ】组合数学无关的元素

问题 I(2716): 无关的元素时间限制: 1 Sec 内存限制: 128 MB提交: 193 解决: 42[提交][状态][我的提交]题目描述对于给定的n个数a1，a2，...，an，依次求出相邻两数之和，将得到一个新数列。重复上述操作，最后结果将变成一个数。问这个数除以m的余数与哪些数无关？例如n=3，m=2时，第一次求和得到a1+a2，a2+a3

2017-07-08 09:17:03 716 1

原创【考试技巧】输入输出优化

§缘不知大家有没有这种体验，做一道题目，即便自己用了很有可能过的算法（如O（nlogn）、O（n^2）），但是不知是什么原因（当然很可能是代码丑）而超时或耗时较长（什么800ms之类），把代码丑这一因素完全摒除（把代码写精简，不啰嗦做无用的事），然后还是不能取得高分，那么我们就要看看是不是输入输出过大了。以下就是一个例子：时间超限（代码丑&没有输入输出优化）94%

2017-04-25 17:50:23 1123

原创【学校OJ】二分图匹配骑士共存问题

题目描述一个N*N的棋盘上，有一些小方格被拿走了，不能放置骑士，其它位置可以放。现要在棋盘上放若干骑士，要求任一个骑士都不能在其他骑士的攻击点上。请算出棋盘上最多能有几个骑士。骑士攻击范围如图所示（S是骑士的位置，X表示马的攻击点）输入第一行包含2个整数n和m，用单个的空格分开，1输出一个整数,它应该是能放在国际象棋棋盘上的互不攻击对方的马的最大的数量。

2017-04-18 13:42:39 1242

原创【学校OJ】线段树影子的宽度&盒子的个数

【影子的宽度】题目描述桌子上零散地放着若干个盒子，盒子都平行于墙。桌子的后方是一堵墙。如图所示。现在从桌子的前方射来一束平行光，把盒子的影子投射到了墙上。问影子的总宽度是多少？输入第1行：3个整数L，R，N。-100000 接下来N行，每行2个整数BL, BR，-100000 输出第1行：1个整数W，表示影子的总宽度

2017-04-01 14:11:24 1263

原创【学校OJ】 splay平衡树文艺平衡树

题目描述你需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1 输入第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数接下来m行每行两个数[l,r] 数据保证 1数据规模

2017-03-31 13:46:08 773

原创【学校OJ】avl平衡树普通平衡树

题目描述你需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：1. 插入一个整数x2. 删除一个整数x(若有多个相同的数，只删除一个)3. 查询整数x的排名(若有多个相同的数，输出最小的排名)，相同的数依次排名，不并列排名4. 查询排名为x的数，排名的概念同35. 求x的前驱(前驱定义为小于x，且最大的数)，保证x有前驱6. 求x的后继(后

2017-03-28 14:00:15 861

原创【学校OJ】并查集食物链

题目描述动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是“1 X Y”，表示X和Y是同类。第二种说法是“2 X Y”，表示X吃Y。此人对N个动物

2017-02-18 18:05:32 858

原创【学校OJ】组合数学表达式计数

题目描述给出n个数，b1,b2,b3……bn，构造n个数，a1,a2,……an(ai>1)，使得a1*a2*a3……an=b1*b2……bn;问一共有多少种数列a1,a2,……an满足上述条件。输入包含多组输入数据每组数据第一行有1个整数n(1每组数据第二行有n个整数第i个数表示bi.(1i1*b2*…*bn 输出

2017-02-16 14:03:44 613

原创【知识】数论

2017-02-11 00:18:44 906

原创【学校OJ】组合数学组合数学一（你没看错，就是这个题目）

题目描述N个盒子排成一行（1输入一行，N，A，B，用空格分开。输出一行，输出放置方案总数。样例输入Copy (如果复制到控制台无换行，可以先粘贴到文本编辑器，再复制)2 1 1样例输出9提示

2017-02-09 17:29:17 957 1

空空如也

空空如也