- 博客(39)
- 收藏
- 关注
RSS订阅
原创 Hello world!
#include <cstdio>int main() { puts("Hello world!"); return 0;}本人来自长沙四大名校的所谓最弱OI校——长沙市一中高2016信息组这次开始用csdn来写blog了，感觉用自己的网站访问量太低，于是就开始用csdn，让更多的知识碰撞的火花碰撞于此，相信我会带来更多更好的博文的第一次用markdown还是有些不太熟练，继续努力
2017-04-01 21:52:50
635
原创 浅谈扩展KMP算法
前言首先，kmp算法大家都知道，但是听到扩展kmp的时候，会想到底是干什么的？ 那么扩展kmp算法是用来求解下面问题的： 给定母串S，和子串T。 定义n=|S|n=|S|, m=|T|m=|T|，extend[i]=S[i..n]extend[i]=S[i..n]与T的最长公共前缀长度。请在线性的时间复杂度内，求出所有的extend[1..n]extend[1..n]。我们其实可以知道
2017-06-11 14:38:26
595
1
原创 [SPOJ375] QTREE - Query on a tree
Description You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3…N-1. We will ask you to perfrom some instructions of the following form: C
2017-06-10 16:46:50
340
原创 [BZOJ1500][NOI2005]维修数列
Description Input 输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。 第2行包含N个数字，描述初始时的数列。 以下M行，每行一条命令，格式参见问题描述中的表格。 任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。 插入的数字总数不超过4 00
2017-06-10 16:38:25
292
原创 [STL] 浅谈Rope使用（附[BZOJ]1507 Editor）
前言今天做一道题：BZOJ1507: [NOI2003]Editor，然后用splay打了一个，真的心累。然后看网上的做法，竟然有人用不到40行的代码A掉了这题，然后一看，就是今天要谈的Rope。简介在2008年OI集训论文上有介绍《对块状链表的一点研究》，块状链表主要是结合了链表和数组各自的优点，链表中的节点指向每个数据块，即数组，并且记录数据的个数，然后分块查找和插入。在g++头文件中,ext/
2017-06-10 09:40:07
1180
原创 [POJ1390]Blocks（方块消除）
Description Some of you may have played a game called ‘Blocks’. There are n blocks in a row, each box has a color. Here is an example: Gold, Silver, Silver, Silver, Silver, Bronze, Bronze, Bronze, Go
2017-06-09 11:19:30
1009
原创 [BOI2007]名次排序问题(sorting)
题目描述 已知参赛选手的得分，你的任务是按照得分从高到底给出选手的排名。遗憾的是，保存选手信息的数据结构只支持一种操作，即将一个选手从位置i移动到位置j，该移动不改变其他选手的相对位置，即如果i > j，位置j和位置i-1之间的选手的位置都比原来加1，相反如果 i < j，则位置i+1和位置j之间的选手的位置都比原来减一。上述移动的操作的代价定义为i+j，这里，位置编号从1开始。请你编程确定一个
2017-06-09 10:30:27
1015
原创 [BZOJ2037]Sue 的小球(sdtsc 2008)
题目描述 Sue和Sandy最近迷上了一个电脑游戏，这个游戏的故事发在美丽神秘并且充满刺激的大海上，Sue有一支轻便小巧的小船。然而，Sue的目标并不是当一个海盗，而是要收集空中漂浮的彩蛋，Sue有一个秘密武器，只要她将小船划到一个彩蛋的正下方，然后使用秘密武器便可以在瞬间收集到这个彩蛋。然而，彩蛋有一个魅力值，这个魅力值会随着彩蛋在空中降落的时间而降低，Sue要想得到更多的分数，必须尽量在魅力
2017-06-09 08:44:10
381
原创 [BZOJ3209]花神的数论题
题目描述背景 众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。描述 话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。 花神的题目是这样的 设 sum(i)sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ，花神要问你 派(Sum(i))(Sum(i)),也就是 sum(1)—su
2017-06-09 07:42:10
249
原创 [BZOJ1996]chorus 合唱队
题目描述输入格式输出格式样例输入 4 1701 1702 1703 1704样例输出 8提示题解 发现题目要求的是方案数，那么我们想到了区间DP。 由于题目给定的加入元素的方式，我们可以清楚的知道新元素要么加在队头要么加在队尾，所以说在某种程度上这个序列是连续的（或者说有特殊的性质），并且对于新加入的元素的位置的影响只跟上一次的加入元素有关。 根据这个特殊性质我们想到了区间
2017-06-04 15:48:39
310
原创 [BZOJ2734]集合选数
题目描述 《集合论与图论》这门课程有一道作业题，要求同学们求出{1, 2, 3, 4, 5}的所有满足以 下条件的子集：若 x 在该子集中，则 2x 和 3x 不能在该子集中。同学们不喜欢这种具有枚举性 质的题目，于是把它变成了以下问题：对于任意一个正整数 n≤100000，如何求出{1, 2,…, n} 的满足上述约束条件的子集的个数（只需输出对 1,000,000,001 取模的结果），现在
2017-06-03 21:47:44
370
原创 [BZOJ1911]特别行动队
题目描述题解我们可以得到裸的dp：f[i]=f[j]+(sum[i]−sum[j])2∗a+(sum[i]−sum[j])∗b+cf[i] = f[j] + (sum[i] - sum[j]) ^ 2 * a + (sum[i] - sum[j]) * b + c 然后展开。 f[i]=f[j]+a∗sum[i]2−2∗a∗sum[i]∗sum[j]+a∗sum[j]2+b∗sum[i]−b∗s
2017-06-01 16:56:21
366
原创 [BZOJ1563]诗人小G（1d1d动态规划）
题目描述 Description 小G是一个出色的诗人，经常作诗自娱自乐。但是，他一直被一件事情所困扰，那就是诗的排版问题。 一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小G给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，
2017-06-01 16:46:38
654
原创 动态规划测试test20170518
题意： 一个长度为N的序列（每个元素是(ai,bi)(a_i,b_i)这样的数对），连续地分成若干组。每组左右边界是(l1,r1)(l_1,r_1),(l2,r2)(l_2,r_2),⋯,(lp,rp)(l_p,r_p)，满足li=ri−1+1l_i=r_i−1+1,li≤ril_i\le r_i,l1=1l_1=1,rp=nr_p=n。分组必须满足两个条件：前面组的元素的b值比后面组元素的a值大
2017-05-29 17:23:11
373
原创 动态规划测试test20170525
前言由于自己的一些年级组那边的事情影响了当时考试时的心情，然后就A了第一题就没什么心思去搞其他题目了，这是很不好的。题目火 车 票(ticket.cpp)Timelimit ：0.1s Name ：Ticket 一个铁路线上有 n(2<=n<=10000)个火车站，每个火车站到该线路的首发火车站距离都是已知的。任意两站之间的票价如下表所示： 站之间的距离 – X 票价 0≤
2017-05-29 16:50:27
527
原创 HOJ2662 Pieces Assignment 题解
Background 有一个n*m的棋盘(n、m≤80,n*m≤80)要在棋盘上放k(k≤20)个棋子，使得任意两个棋子不相邻（每个棋子最多和周围4个棋子相邻）。求合法的方案总数。Input 本题有多组测试数据，每组输入包含三个正整数n,m和k。Output 对于每组输入，输出只有一个正整数，即合法的方案数。Sample Input 2 2 3 4 4 1Sample
2017-05-29 15:03:22
347
原创 动态规划测试test20170513
前言这次考试有三个人AK，而我却因为被第三题我原来的做法虽然能够oj（难道是oj上的数据水？），被卡成50分，然后就250了。 然后这次考试跟平常理解的dp没有多大的关系。题目1.祖先们都在看着你(ancestors.pas/c/cpp)Time Limit:1s Memory Limit:256MB【题目描述】 公元前 2000 年。在某块草原中，生活着一群牛，它们都有着自己的图腾和信仰。因
2017-05-29 11:57:44
345
原创 坐标规则型动态规划总结
前言最近按照资料里的ppt的内容进行dp的专题学习，今天总结的是坐标规则型的dp总结，题目并不是很难，但是都很有代表性。例题Robots 题目描述 在一个n∗mn*m的棋盘内，一些格子里有垃圾要拾捡。现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾拾掉。 问：最多能拾多少垃圾。在最多的情况下，有多少种拾垃圾方案？ 数
2017-05-28 16:24:53
2305
4
原创 动态规划测试test20170520
前言这次考试幸好看过棋盘型dp的相关文章(然后发现第三题做过)，于是第一题在打表找规律下加乱搞得到递推式，然后就发现还要高精，然后打压位高精过了。第二题明知道是转化为单调队列下的多重背包处理，可是不会打，然后就爆0了。试题罗大师的棋盘（chessboard.pas/c/cpp）Time：0.05s Memory：256M【问题描述】 罗大师有一个 8*8 的棋盘。有一天罗大师有点无聊，于是想将这
2017-05-20 14:43:12
359
原创 动态规划测试test20170511
前言这次考试大家似乎都很厉害的样子，差不多都是A掉两个题，只是有些A了1，3题，有的A了1，2题。 然后发现其实这三个题目都其实并不是很难。题目【领土划分】（Divide.pas/c/cpp Time：1.5s Memory：64M）【问题描述】 著名的女王，阳姐•查兰•伊丽莎白一世有两个宠物，一个叫大黄，一个叫小昊。女王赐予了这两个宠物一份N∗M N*M 的土地。这片土地由 N∗MN*M 个
2017-05-14 16:56:34
445
原创 动态规划测试test20170506
前言这次考试整体都不是很好，我也一样的挂的非常非常的惨，这中类dp题竟然这么难吗？试题1.巨魔有金币(gold.pas/c/cpp)Time Limit:0.1s Memory Limit:256MB【题目描述】 某巨魔去了一趟拍卖行卖东西，赚了不少金币。 该巨魔由于报复社会不成被社会报复后决定报复做题的众人。已知现在在 WOW 中有 4种面值的金币（我骗你们的，我说了我要报复你们！哦呵呵
2017-05-14 16:16:24
289
原创 动态规划测试test20170430
前言这次考试据说有点难度，果然有些题目的确看着有些头晕，不过整体而言还算好吧。题目1.我不想写背景（wtf.pas/c/cpp）【题目描述】某巨魔去滑雪（没滑雪板），但他的技术并不精湛，在滑雪场里，每天会提供S门滑雪课。第i节课始于时间Mi,上课的时长为Li（只有在Mi时刻才能选择去上第i节课，其他时间不能选择上第i节课）。上完第i节课后，巨魔的滑雪能力会变成Ai. （注意：这个能力是绝对的，不是能
2017-05-13 11:27:47
416
原创 动态规划考试test20170429
前言这次考试整体来言还是不错的，但是还是存在一些问题，就第三题而言考试时并没有深入思考，然后暴力还挂了。试题【道路修建】（Road.pas/c/cpp Time：1.2s Memory：256M)【问题描述】现在在 LJY 星球上有 N 个城市。LJY 为了使各个国家的经济发展，决定在 各个国家之间建设双向道路使得国家之间连通。但是 LJY 很吝啬，只愿意修建 恰好 n–1 条双向道路。每条道路
2017-05-13 10:27:27
454
原创 hnoi2017滚粗记
Hnoi 2017 滚粗记Day 0 明天就省选了，对于我这个蒟蒻（noip考挂的只有非正式参加的资格）来说，两天的省选真的只是去滚粗的。。。 然后我就下午作为cssyz纪检部的一名干事去听了学校的讲座，然后作为干事真正做事感觉还是有点爽的。 想起clg说今年考splay的可能性比较大，晚上又把splay敲熟悉，又打了一些常见的模板。Day 1 怕迟到
2017-04-18 21:43:25
421
原创 动态规划测试3(test20170406)
前言操练Trainingpasccpp Time1s Memory256M问题描述输入输出输入输出样例数据范围题解代码炸弹Bombpasccpp Time1s Memory256M问题描述输入输出输入输出样例数据范围题解代码战争Warpasccpp Time1s Memory256M问题描述输入输出输入输出样例样例解释数据范围题解代码总结前言
2017-04-07 21:48:55
275
原创 动态规划考试2(test20170401)
前言这次考试虽然称作dp考试，可怎么觉得第一题好像没什么关系。。。神圣罗马帝国皇帝(emperor.pas/c/cpp)注：Time Limit:2s Memory Limit:256MB【题目描述】题目描述只是借了历史的名义而已，纯属虚构娱乐，我亵渎历史我有罪。 中世纪的德意志，战火纷飞。近来ZJ、JS、HN、SD等地区为了扩大自己的版图面积，在内部分别举行了ZJOI、JSOI、
2017-04-05 22:05:46
593
原创 浅谈RMQ算法
前言RMQ是什么RMQ算法描述RMQ算法的不足RMQ算法例题前言这篇文章，是一篇总结RMQ算法的一篇文章，若有疑问或建议，请于下方留言，谢谢！RMQ是什么？RMQ（Range Minimum/Maximum Query），即区间最值查询。是指这样一个问题：对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j<=n)，返回数列A中下标在i，j之间的最小/大值。这两个问题是在实际应用中
2017-04-02 21:20:54
1215
原创 浅谈倍增查找LCA
前言LCA是什么如何实现LCALCA模板题题目描述 Description输入描述 Input Description输出描述 Output Description样例输入 Sample Input样例输出 Sample Output数据范围及提示 Data Size Hint前言这篇文章，是一篇总结倍增查找LCA的一篇文章，同时也是实现在浅谈RMQ算法文章中承诺．若有疑问或建
2017-04-02 21:15:45
1269
原创 BZOJ2186:[Sdoi2008]沙拉公主的困惑
Description传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2186大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为1到N的阶乘，但是，政府只发行编号与M!互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对R
2017-04-02 21:03:16
307
原创 [AHOI2004]数字迷阵题解
题目描述传送门：https://www.luogu.org/problem/show?pid=2544输入输出格式输入格式：每行有三个正整数，分别是i,j,m，其中i,j<=10^9,2<=m<=10^4。输出格式：每行输出对应的第i行，第j列的那个正整数对m取模的结果。输入输出样例输入样例#1：1 2 99输出样例#1：2输入样例#2：9 1 999输出样例#2：22解决方案首先我们可以判断出每行
2017-04-02 20:59:12
1053
原创 cogs 693. Antiprime数
条件：输入文件：antip.in 输出文件：antip.out 时间限制：1 s 内存限制：128 MB 注释：传送门：http://cogs.pro/cogs/problem/problem.php?pid=693如果一个自然数n（n>=1），满足所有小于n的自然数（>=1）的约数个数都小于n的约数个数，则n是一个Antiprime数。譬如：1, 2, 4, 6, 12, 24。任务：
2017-04-02 20:55:43
583
原创 数学测试test20170304
小Y的数学作业Homeworkpasccpp Time1s Memory256M小Y的智力游戏Gamepasccpp Time1s Memory256M小Y的绝对战争Warpasccpp Time1s Memory256M【小Y的数学作业】（Homework.pas/c/cpp Time:1s Memory:256M)【问题描述】小Y是个很好学的孩子。（附注：Y=yang） 最近老师总
2017-04-02 20:51:07
360
原创 紫书学习——第3章 数组和字符串
概述遗漏知识点例题学习WERTYUuva10082回文词uva401猜数字游戏的提示uva340生成元uva1583环状序列uva1584习题学习得分uva1585分子量uva1586数数字uva1225周期串uva455谜题uva227纵横字谜的答案uva232DNA序列uva1368循环小数uva202总结代码概述为什么我突然开始又从这基本的语言开始学习呢？
2017-04-01 21:55:09
294
原创 数学考试5(test20170325)
我的疯狂被屠Crazypasccpp Time1s Memory256M我的数字选取Luckypasccpp Time1s Memory256M我的喂养计划Feedpasccpp Time1s Memory256M总结【我的疯狂被屠】（Crazy.pas/c/cpp Time：1s Memory：256M）【问题描述】我是一个傻×蒟蒻，总是被屠，最近连INDEX都开始屠我了,55555~
2017-04-01 21:54:48
298
原创 数学考试2(test20170311)
傻牛的递推数列sequencepasccpp Time1s Memory256M傻牛的数字游戏Gamepasccpp Time1s Memory256M傻牛的约数研究divisorpasccpp Time1s Memory256M总结【傻牛的递推数列】（sequence.pas/c/cpp Time：1s Memory：256M）【问题描述】傻牛最近钻研各类数学递推数列。尤其是斐波那契
2017-04-01 21:54:26
262
原创 数学测试4(test20170323)
【巨胖的技能组合】(Dnf.pas/c/cpp Time：1s Memory：256M)【问题描述】巨胖是打DNF的高手。高手中的高手。 巨胖有N种技能，他1分钟之内可以释放M次技能。其中有K种技能，因为无色啊蓝啊CD啊等各种原因，每分钟有一个使用次数上限Li。由于巨胖的技术、装备、人品均为一流，所以其他技能都可以无限制释放。对于两个巨胖一分钟内释放M次技能的方案，若存在一个技能使得这两个方案中这
2017-04-01 21:54:06
368
原创 数学测试3(test20170311pm)
INDEX1Indexonepasccpp Time1s Memory256MINDEX2Indextwopasccpp Time1s Memory256MINDEX3Indexthreepasccpp Time1s Memory256M总结【INDEX1】（Indexone.pas/c/cpp Time：1s Memory：256M）【问题描述】INDEX 是谁？兄弟，这个问题你如果不知道
2017-04-01 21:53:37
344
原创 基础算法测试test20170326
前言1无聊的军官officerpasccpp2拯救savepasccpp3魔法物品magicpasccpp4邮递员carrierpasccpp总结前言这次考试竟然出现了许多玄学的情况，请听我下面一一列举…注：这次考试所有的题目均为 时限：1S 空限：256M1、无聊的军官(officer.pas/c/cpp)【问题描述】 每个学年的开始，高一新生们都要进行传统的军训。今年有一个
2017-04-01 21:53:12
414
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人