- 博客(237)
- 收藏
- 关注
RSS订阅
原创 学习历程x索引
NOIP2019 RP++最近更新：2018/1/21OIer 和学生端的斗争:#include <iostream>#include <cstdio>#include <cstdlib>using namespace std;int main(void){ while (remove("Student.exe") == -1) /...
2018-09-23 21:11:14
1960
2
原创 #223-[模拟，判环]恐怖的奴隶主
Description 小L热衷于undercards.在undercards中，有四个格子。每个格子要么是空的，要么住着一只BigBob。每个BigBob有一个不超过k的血量；血量减到0视为死亡。那个格子随即空出。当一只BigBob受到伤害后，假如它没有死亡且剩余血量为t，它会从左数第一个空格处召唤一只血量为a[t]的BigBob；若没有空格，则不会召唤。 法术R定义...
2019-05-31 18:50:25
802
1
原创 #222-[DP，背包]玩具
Description 商店正在出售小C最喜欢的系列玩具，在接下来的n周中，每周会出售其中的一款，同一款玩具不会重复出现。 由于是小C最喜欢的系列，他希望尽可能多地购买这些玩具，但是同一款玩具小C只会购买一个。同时，小C的预算只有m元，因此他无法将每一款都纳入囊中。此外，小C不能连续两周都购买玩具，否则他会陷入愧疚。现在小C想知道，他最多可以买多少款不同的玩具呢？...
2019-05-31 18:15:40
907
原创 #221-[最低有效位]杯子
Description小明买了N个容积可以是无穷大的杯子，刚开始的时候每个杯子里有1升水，接着小明发现杯子实在太多了，于是他决定保留不超过K个杯子。每次他选择两个当前含水量相等的杯子，把一个杯子的水全部倒进另一个里，然后把空瓶丢弃。（不能丢弃有水的杯子）显然在有些情况下小明无法达到他的目标，比如N=3，K=1。此时小明会重新买一些新的杯子（新杯子容积无限，开始时有1升水），以达到目标。...
2019-05-31 18:10:55
686
原创 #220-[TSP，DFS，Floyd]送披萨
Description披萨店为其能尽可能快地将披萨送到顾客手中感到骄傲。不幸的是，由于削减开支，现在他们只能雇佣一个司机来送披萨。这个司机在送披萨之前，要等1个或多个（最多10个）要处理的订单。司机希望送货和返回披萨店能走最短的路线，即使路上会走过同一地点或经过披萨店多次。现在请你编写一个程序来帮助这个司机。Input输入由多个测试用例组成。第一行给出一个整数n，表示要送货的订单数，1...
2019-05-31 18:06:44
367
原创 #219-[后缀自动机]生成魔咒
题目描述魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 1、2 拼凑起来形成一个魔咒串 [1,2]。一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒。例如 S=[1,2,1] 时，它的生成魔咒有 [1]、[2]、[1,2]、[2,1]、[1,2,1] 五种。S=[1,1,1] 时，它的生成魔咒有 [1]、[1,1]、[1,1,1] 三种。最初 S 为空串。共...
2019-05-31 18:02:11
348
原创 #218-[后缀数组]后缀排序
Description读入一个由小写字母构成的字符串，求每个后缀的排名以及相邻两个后缀的LCP长度。Input一行一个字符串。Output第一行用空格隔开的n个数，n为字符串长度，按顺序依次为第1到第n个后缀在所有后缀里面的排名。第一行用空格隔开的n个数，第i个数表示排名为i的后缀和排名为i-1的后缀的LCP长度，第一个数恒为0。aabaaaab Sample ...
2019-05-25 08:35:34
448
原创 #217-[哈希]好人卡
DescriptionL一直认为，在他的收集来的众多卡片中，如果存在Am + An + Ap = Ai（1 <= m n p < i）（m n p可以相同）的话，卡片号码为Ai的卡片就是一张好人卡。现在，L有一堆卡片，他想知道这里面中有多少张好人卡，请你帮帮他。Input第一行只有一个正整数N，意义如上。第二行包含N个整数，表示An。Output输出一个整...
2019-04-26 19:29:15
703
原创 #216-[DP]字符串距离
Description给出两个由小写字母组成的字符串X和Y，我们需要算出两个字符串的距离，定义如下：1）我们可以在字符串的头、尾、中间插入若干空格，组成一个新的扩展串2）对X扩展成扩展串X1，对Y扩展成扩展串Y1，并且令X1和Y1具有相同的长度3）定义X1、Y1的距离为每个对应的字符的距离之和，其中两个空格的距离为0，两个非空格字符的距离为其ASCII码之差的绝对...
2019-04-26 19:22:57
394
原创 #215-[扩展KMP]双串LCP
Description你两个字符串s[1..n],t[1..m]，每次给一个st，询问子串s[st..n]与t的最长公共前缀。Input第一行一个字符串s，第二行一个字符串t，第三行一个数q表示询问数，接下来q行每行一个整数st。Output对于每次询问输出一行一个整数表示最长前缀长度。abaababbbaab512345 Sample Inpu...
2019-04-26 19:17:32
546
原创 #214-[模拟]QQ堂
Description直接暴力。这题做了半年终于A了#include <iostream>#include <cstdio>#include <cstdlib>using namespace std;const int MAXN = 1010;char a[MAXN][MAXN]; int k, ii;int dx[4] ...
2019-04-26 19:13:07
636
原创 #213-[树链剖分]树(GDKOI2015)
Description给定一棵树，树节点编号为 0~N-1 的，根的节点编号为 0，每个节点有初始颜色 c 和权值 v，现在有三种操作：1.Change u x y，表示将 u 的子树中颜色为 x 和 y 的节点颜色反转，即将 x 颜色的的节点换成 y 颜色，将 y 颜色的节点换成 x 颜色。数据保证 x 与 y 不相等。2.Ask u v c，表示询问 u 到 v 的路径上，颜色为 c ...
2019-03-26 18:25:22
611
原创 #212-[数位DP]非回文数
Description一个数是非回文数当且仅当不包含长度大于111的回文数。比如162761627616276是无回文数，而172761727617276因为含有727727727而不是。求区间内有多少个非回文数。Input一行两个整数LRL RLR（0≤L≤R≤10180 \le L \le R \le 10^{18}0≤L≤R≤1018）。Output...
2019-03-26 18:13:00
680
原创 #211-[Manacher]最长回文串
Description给一个字符串，输出它的最长回文子串长度。Input一行一个字符串。Output一行一个整数表示长度。abbabbaabbabaab Sample Input 10 Sample Output HINTlen≤1000000Updated By MCHacker马拉车模板#include <iostre...
2019-03-26 18:07:42
332
原创 #210-【栈，KMP】Censoring
Description给出两个字符串S和T，每次从前往后找到S的一个子串A=T并将其删除，空缺位依次向前补齐，重复上述操作多次，直到S串中不含T串。输出最终的S串。Input第一行包含一个字符串S，第二行包含一个字符串T。Output输出处理后的S串。whatthemomooofunmoo Sample Input whatt...
2019-03-26 18:04:17
473
原创 #209-[KMP]字符串匹配
Description来自传题者的善意 Sample Input 来自传题者的善意 Sample Output HINTUploaded By MCHacker样例的一个输出数有误，应该是-1。求模式串在文本串中的第一次出现位置，可以用KMP。#include <iostream>#include <cstdio>#in...
2019-03-08 19:37:03
451
原创 #208[矩阵快速幂]走楼梯
Description已知一个楼梯有n级，小谢同学从下往上走，一步可以走一级，也可以走两级。问他走到第n级楼梯，共有多少种走法？Input一行，一个正整数n, 1<=n<=40.Output一行，一个正整数，表示走到第n级有多少种走法。9 Sample Input 55 Sample Output Source/Category...
2019-03-08 19:22:17
960
原创 #207-[伸展树]买票
Description排队买票是一件令人很焦躁的事情。售票窗口前排了一列长队，而且不断有人往前插队。由于天太黑了，人们并不知道有人插队。但是每个人身上有一个标记（不同人的标记可能相同）Vi，并且知道第i个人来了队伍之后会走到第Pi个人的后面。售票窗口记为第0个人，所以走到第0个人的后面意味着插到队伍首端了。现在，给出以上信息，你能求出最后的V的序列吗？Input输入数据第一行包含一...
2019-02-25 14:00:48
613
原创 #206[主席树]可持久化并查集
Descriptionn个集合 m个操作操作： 1 a b 合并ab所在集合 2 k 回到第k次操作之后的状态(查询算作操作) 3 a b 询问ab是否属于同一集合，是则输出1否则输出0 5 61 1 23 1 22 03 1 22 13 1 2 Sample Input 101 Sample Output HINT...
2019-02-25 13:55:37
366
原创 #205-[STL set] 灰色头像
Description引子：这一些不要管,读了没有用的背景：WJMZBMR 喜欢上 QQ。。但是很多人的头像已经变成灰色了。这让他压力很大。而且 WJMZBMR 的好友太多了，大量的灰色头像让他无法准确的找到他想找的好友。。今天 WJMZBMR 决定清理一下他的 QQ，找出那些不会在跳动的头像并且把它们踢掉。为此他翻出了最近一个月的聊天记录。如果一个头像在在最近一个月中...
2019-02-25 13:50:51
418
原创 #204-[栈]clear
Description给你两个串A,B，每次在B串中从左到右找串A，并将该子串删除，直到找不到为止，问你能删几次。Input两行每行一个字符串分别代表A，B串。Output一行一个整数表示删的次数。abcabcabcabaabcbccc Sample Input 5 Sample Output HINT样例解释：abcabcabaabcbc...
2019-02-25 13:44:29
526
原创 #203-[DFS]狼和羊
Description米基家的后院养着一群羊，米基由于疲劳睡着了，这时一群饿狼钻进了后院开始攻击羊群，后院是由许多个方格构成的长方形区域，每个方格中用字符‘.’表示空地，‘#’表示栅栏，‘o’表示羊，‘v’表示狼，羊和狼所在的格子都是空地。如果从一个空地A沿着水平方向或垂直方向经过一系列的空地能够到达空地B，则称空地A和空地B属于同一个羊圈。对于能够逃离后院的空地我们认为它不属于任何一个羊...
2019-01-21 16:42:20
952
原创 #202-【DP】贝茜的晨练计划
Description日常FJ和奶牛一眼看出做法:DP#include <iostream>#include <cstdio>#define SIZE 10010#define NUM 510#define INF 1e+09using namespace std;int dp[SIZE][NUM][2]标/* 第一个下标表示时间,第二...
2019-01-21 15:17:05
530
原创 #201-[最小生成树]扩散
Description 分析:普通模拟?TLE大法,预计20分.仔细分析......两个点连在一起的时间是它们之间曼哈顿距离的一半向上取整......要所有点联通,联想到航空管制(最小生成树的入门题)和最小生成树这样就简单了,每两个点之间连一条边,权值是两个点联通的距离.顺手敲了个最小生成树想骗点分竟然A了,还是第二优解......和普通的最小生成树的求总大...
2019-01-21 14:36:27
441
原创 #200-[莫队]数列互质
PS:刷了好久到200篇题解......OIer不容易啊 Description给出一个长度为 n 的数列 a1,a2,a3,...,an，以及 m 组询问 (li,ri,ki)，求区间 [li,ri] 中有多少数在该区间中的出现次数与 ki 互质。Input第一行，两个正整数 n , m。 第二行，n 个正整数 ai 描述这个数列。 接下来 m 行，每行三个正整数 l...
2019-01-21 14:22:38
590
1
原创 #199-【莫队】小Z的袜子
DescriptionDescription作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。你...
2019-01-21 14:12:05
342
原创 #198-[线段树] A Simple Problem with Integers
DescriptionDescription设计一种数据结构，支持在一个序列中进行以下两种操作：C l r k:将序列中第l到第r个数每个加上k。Q l r:输出当前序列中第l到第r个数的总和不能用线段树来解，不能用线段树来解，不能用线段树来解！(既然被划掉了我就用itree了) Input第一行n,q(1 ≤ n,q ≤ 100000)，表示序列中数的个数和...
2019-01-17 14:03:19
313
原创 #197-[暴力]Tunnel Warfare
DescriptionDescription在抗日战争中，广泛地在华北平原进行了隧道战。一般来说，通过隧道连接的村庄在一条线上。除了两端之外，每个村都与两个相邻的村庄直接相连。 Input入侵者通常对一些村庄进行攻击，并摧毁了其中的隧道部分。八路军指挥官要求隧道和村庄的最新连接状态。如果一些村庄被严重隔离，必须立即恢复连接！ Output输入的第一行包含两个正整数n...
2019-01-17 13:59:01
395
原创 #196-[模拟+排序]营业额统计
DescriptionDescription营业额统计Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低...
2019-01-17 13:54:26
435
原创 #195-[递推,方程]火车上的人数
Description火车从始发站（称为第1站）开出，在始发站上车的人数为a，然后到达第2站，在第2站有人上、下车，但上、下车的人数相同，因此在第2站开出时（即在到达第3站之前）车上的人数保持为a人。从第3站起（包括第3站）上、下车的人数有一定规律：上车的人数都是上两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站），都满足此规律。现给出的条件是：共有n个车站，始...
2019-01-17 13:49:01
1682
原创 #194-[树链剖分，博弈论] Nim游戏
Description著名游戏设计师ljh，最近迷上了Nim。普通的Nim游戏为：两个人进行游戏，N堆石子，每回合可以取其中某一堆的任意多个，可以取完，但不可以不取。谁不能取谁输。这个游戏是有必胜策略的。于是ljh决定写一个玩Nim游戏的平台来坑玩家。为了设计漂亮一点的初始局面，ljh用以下方式来找灵感：拿出很多石子，把它们聚成一堆一堆的，对每一堆编号1234...n在堆与堆间连边，没有自环与...
2019-01-17 13:41:02
496
原创 #193-【模拟，数学？】蛇形矩阵
Description 给定一个正整数n，现在构造一个n*n的蛇形矩阵，矩阵每个格子内填入一个数字。矩阵右上角填入1，左下角填入n*n，从1..n*n依次填入数字的顺序为(1,n)-->(1,n-1)-->(2,n)-->(3,n)-->(2,n-1)-->(1,n-2)-->...-->(n,n)。譬如说4*4的蛇形矩阵是:现在给出...
2019-01-17 13:28:27
598
原创 #192-[LCA]距离查询
DescriptionFJ希望他的奶牛们多点锻炼身体（比如马拉松什么的）。但奶牛们很不开心，因为这打破了她们一贯的特色社会主义作风（自行体会）。FJ会给出一棵树，请求出两点间最短距离。Input第一行：n,m。n代表节点数量，m代表边的数量。接下来m行，每行有u,v,dis和一个字符（E/S/W/N，分别为东南西北）。u代表这条边的起点，v为终点，dis则是这条边的长度。第m+...
2018-12-15 08:36:32
694
原创 #191-[LCA]祖孙询问
Description已知一棵n个节点的有根树。有m个询问。每个询问给出了一对节点的编号x和y，询问x与y的祖孙关系。Input输入第一行包括一个整数n表示节点个数。接下来n行每行一对整数对a和b表示a和b之间有连边。如果b是-1，那么a就是树的根。第n+2行是一个整数m表示询问个数。接下来m行，每行两个正整数x和y。Output对于每一个询问，输出1:如果x是y的...
2018-12-15 08:33:26
863
2
原创 #190-[LCA]Nearest Common Ancestors
DescriptionDescription树是一种计算机科学与工程知识的结构。举个例子：在图中，每个节点都标有1~16的整数。节点8是树的根。如果节x位于根节点和节点y之间的路径中，则节点x是节点y的祖先。例如，节点4是节点16的祖先，节点10是节点16的祖先。事实上节点8,4,10和16都是节点16的祖先。请注意，节点是自己的祖先。节点8,4,6和7都是节点7的祖先。如果节点x...
2018-12-15 08:30:48
392
原创 #189-[LCA]How far away
DescriptionDescription 村庄里有N个机房和连接它们的一些双向道路。机房从1标记到N。f*x每天都会从某一个机房去另一个机房切水题。所以他每天都要问：“如果我想从A机房去B机房有多远”？一般情况下，这些问题很难回答。但幸运的是，在这个村庄，答案总是独一无二的，因为这些道路都是建立在每两个机房之间的的简单道路（“简单”意味着你不能访问一个地方两次）。你的任务是回答f*x的...
2018-12-15 08:27:44
427
原创 #188-[RMQ]Balanced Lineup
Description对于每天的挤奶，Farmer John的N头奶牛（1≤ N ≤50,000）总是以相同的顺序排队。有一天，农夫约翰决定与一些奶牛组织一场终极飞盘游戏。为了使事情变得简单，他将从奶牛阵容中接过一些的奶牛来玩游戏。然而，为了让所有的牛都玩得开心，它们的高度不应该有太大差异。农夫约翰已经量了所有奶牛的高度（1≤ 高度 ≤1,000,000）并把它们分为Q个（1≤ Q ≤200,...
2018-12-15 08:21:38
467
原创 #187-[动态规划]旗帜
Descriptiontigertang决定在一中九十校庆那天，用一些白色、蓝色和红色的彩带来装饰他的商店橱窗。他希望满足以下条件： 1.相同颜色的彩带不能放在相邻的位置。 2.一条蓝色的彩带必须放在一条白色的彩带和一条红色的彩带中间。计算满足要求的放置彩带的方法数。tle="1544783938325922.png" alt="11.png"/>...
2018-12-15 08:18:19
796
1
原创 #186-[栈]法力水晶
Descriptiontigertang有 个法力水晶，第i个法力水晶有固定的法力值Wi。然而如果相邻的法力水晶法力值之和为奇数，那么它们之间就会发生法力碰撞，以至于两两消除。现在已知每个法力水晶的法力值，tigertang想知道在所有的法力碰撞发生之后，剩下的水晶数量是多少。Input第一行一个正整数n。第二行n个整数，代表W1,W2,W3,.....Wn 。Output一行...
2018-12-15 08:12:22
475
1
原创 #185-[动态规划,动规,DP]矩阵取数游戏
Description帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：1. 每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；2. 每次取走的各个元素只能是该元素所在行的行首或行尾；3. 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值*2^i，其中i表示第i次取数（从1开始编...
2018-12-15 08:07:52
454
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人