- 博客(50)
- 收藏
- 关注
RSS订阅原创 写不了博客了吗？
你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Markdown的基本语法知识。我们对Markdown编辑器进行了一些功能拓展与语法支持，除了标准的Markdown编辑器功能，我们增加了如下几点新功能，帮助你用它写博客：撤销：Ctrl/Command + Z重做：Ctrl/Command + Y加粗：Ctrl/Command + B斜体：Ctrl/Command + I标题：Ctrl/Command + S
2023-04-18 21:13:44
538
原创 bzoj4817[Sdoi2017]树点涂色
4817: [Sdoi2017]树点涂色Time Limit: 10 Sec Memory Limit: 128 MB Submit: 557 Solved: 326 [Submit][Status][Discuss] DescriptionBob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路 径的权值是：这条路径上的点（包括起点和
2017-12-27 20:54:34
293
原创 bzoj3585mex
3585: mexDescription 有一个长度为n的数组{a1,a2,…,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。Input 第一行n,m。 第二行为n个数。 从第三行开始，每行一个询问l,r。Output 一行一个数，表示每个询问的答案。Sample Input5 52 1 0 2 13 32 32 41 23 5Sample Output12303HI
2017-12-12 08:22:23
437
原创 51nod 1175 区间中第K大的数
1175 区间中第K大的数 一个长度为N的整数序列，编号0 - N - 1。进行Q次查询，查询编号i至j的所有数中，第K大的数是多少。 例如: 1 7 6 3 1。i = 1, j = 3，k = 2，对应的数为7 6 3，第2大的数为6。 Input 第1行：1个数N，表示序列的长度。(2 <= N <= 50000) 第2 - N + 1行：每行1个数，对应序列中的元素。(0 <= S
2017-10-26 20:28:40
372
原创 1411矩阵取数问题V3
1411矩阵取数问题V3 给定一个m行n列的矩阵，你可以从任意位置开始取数，到达任意位置都可以结束，每次可以走到的数是当前这个数上下左右的邻居之一，唯一的限制是每个位置只能经过一次，也就是说你的路径不自交。所经过的数的总作为你的得分，求最大的得分。 Input 第一行两个整数m, n (0 < m, n < 10)，表示矩阵的行数和列数。 后面m行，每行n个整数表示矩阵里的数，整数范围[-1
2017-10-25 18:48:59
423
转载 最长公共上升子序列
最长公共上升子序列 转载 2014年08月13日 16:04:00 标签：最长公共上升子序列 1222 最长公共上升子序列 问题: 给定两个字符串x, y, 求它们公共子序列s, 满足si < sj ( 0 <= i < j < |s|).要求S的长度是所有条件序列中长度最长的. 比较直观的做法(O(n^4))可以仿照最长上升子序列用dp[i][j], 表示以xi, yj结束的公共字串
2017-10-21 13:56:27
354
原创 51nod 1681公共祖先
1681 公共祖先 有一个庞大的家族，共n人。已知这n个人的祖辈关系正好形成树形结构(即父亲向儿子连边)。 在另一个未知的平行宇宙，这n人的祖辈关系仍然是树形结构，但他们相互之间的关系却完全不同了，原来的祖先可能变成了后代，后代变成的同辈…… 两个人的亲密度定义为在这两个平行宇宙有多少人一直是他们的公共祖先。 整个家族的亲密度定义为任意两个人亲密度的总和。 Input 第一行一个数n(1
2017-10-20 19:25:07
325
原创 3714: [PA2014]Kuglarz
**3714: [PA2014]Kuglarz Description 魔术师的桌子上有n个杯子排成一行，编号为1,2,…,n，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。花费c_ij元，魔术师就会告诉你杯子i,i+1,…,j底下藏有球的总数的奇偶性。 采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？ Input 第一行一个整数n(
2017-10-20 19:13:14
454
原创 最强阵容加强版
题目描述 拿着新换来的英雄卡，小李满心欢喜的准备和同学们PK一下。 他们的游戏规则非常简单，双方把自己的牌绕成一圈，然后指定一个起点，从该张牌开始顺时针方向往后取，谁取出的字符串字典序更小（从左到右开始比较，碰到第一个不一样的字符进行比较，比较规则为a < b <…< z）谁将获得胜利。具体规则可参考样例。虽然现在小李的牌已经很好了，但是你能不能帮他快速算出起始位置，使得他能够派出最强阵容。输入
2017-09-30 13:51:34
1526
原创 序列统计
4403: 序列统计 Description 给定三个正整数N、L和R，统计长度在1到N之间，元素大小都在L到R之间的单调不降序列的数量。输出答案对10^6+3取模的结果。 Input 输入第一行包含一个整数T，表示数据组数。 第2到第T+1行每行包含三个整数N、L和R，N、L和R的意义如题所述。 1≤N,L,R≤10^9，1≤T≤100，输入数据保证L≤R。 Output 输出包含
2017-09-22 17:03:21
995
原创 鏖战字符串
鏖战字符串 题目描述 Abwad在nbc即将完成她的程序的时候，急中生智拔掉了她电脑的电源线，争取到了宝贵的时间。作为著名论文《论Ctrl-C与Ctrl-V在信息学竞赛中的应用》的作者，他巧妙地使用了这种上古秘术，顺利扳回一城。 在决胜局中，Abwad决定和nbc鏖战字符串，比的是谁能更快地将一个“量子态的字符串”删除。“量子态的字符串”的每个字符都有一个删除难度dif[i]。“量子态的字符串
2017-09-20 14:46:05
578
原创 数
数 题目描述 给定正整数n,m，问有多少个正整数满足： (1)不含前导0； (2)是m的倍数； (3)可以通过重排列各个数位得到n。 输入 一行两个整数n，m。 输出 一行一个整数表示答案对998244353取模的结果。 样例输入 1 1 样例输出 1 提示 【数据范围】对于20%的数据，n<10^10。对于50%的数据，n<10^16，m<=20。对于100%的数据，
2017-09-20 09:55:54
834
原创 宝藏
宝藏 【问题描述】 一棵 个点的树，到达一个点会获得这个点上的宝藏，每个宝藏都有一定的 价值。经过每条边需要支付一定的过路费。每个点只有一个宝藏，但过路费每次 都要交。求从每个点出发能得到的最大收益。 【输入文件】 输入文件为treasure.in。 第一行为一个正整数n。 接下来n-1行，每行三个整数x,y,z ，描述一条边的两个端点 x,y和过路费 。 最后一行n个
2017-09-19 20:11:38
745
原创 1120 机器人走方格 V3
卡特兰数列+Lucas定理卡特兰数列+Lucas定理 假如机器人在线的上方走，无论在什么时刻，机器人向下走的次数一定小于等于向右走的次数假如机器人在线的上方走，无论在什么时刻，机器人向下走的次数一定小于等于向右走的次数 在线的下方走同理在线的下方走同理 所以总方案数为2∗Cn−12∗n−2所以总方案数为2*C_{2*n-2}^{n-1} 但要对10007取模但要对10007取模 Lucas
2017-08-16 18:10:34
397
原创 旅行
旅行 题目描述 小 C 上周末和他可爱的同学小 A 一起去 X 湖玩。X 湖景区一共有 n 个景点，这些景点由 n-1 条观光道连接着，从每个景点开始都可以通过观光道直接或间接地走到其他所有的景点。小 C 带着小 A 从 1 号景点开始游玩。游览完第一个景点后，先由小 C 决定下一个游览的景点，他们一起走去那个景点玩。接下来，他们轮流决定他们下一步去哪个景点玩。他们不会选择已经走过的景点，因为重
2017-07-27 16:24:09
1655
3
原创 孤独一生
孤独一生 题目描述 下课了，Polo来到球场，但他到了之后才发现…..被放了飞机……无事可做的他决心找点乐子，比方说……跳台阶……球场边有N个台阶拍成一行，第i个台阶的高度是Hi(0< mHi<=10^9)，第0个台阶，也就是地面的高度为0。Polo打算把这N个台阶分成两个集合Sa,Sb（可以为空），对于一个台阶集合S={P1,P2,…P|S|}，其中P1< P2< …< P|S|，他需要花费
2017-07-24 20:17:05
517
原创 乐曲创作
乐曲创作 题目描述 小可可是音乐学院的一名学生，他需要经常创作乐曲完成老师布置的作业。 可是，小可可是一个懒惰的学生。所以，每次完成作业时，他不会重新创作一首新的乐曲，而是去修改上一次创作过的乐曲作为作业交给老师。小可可的乐曲由N个音调不同的音符组成，分别记为音符1…N。因此，他创作的乐曲是由1…N的一个排列构成，例如N=5时，他创作的乐曲可能为：2,1,3,5,4。但是，小可可每一次会按照一
2017-07-17 18:42:15
450
原创 分组
分组 题目描述 Bsny所在的精灵社区有n个居民，每个居民有一定的地位和年龄，ri表示第i个人的地位，ai表示第i个人的年龄。最近社区里要举行活动，要求几个人分成一个小组，小组中必须要有一个队长，要成为队长有这样的条件：1、队长在小组中的地位应该是最高的(可以并列第一)；2、小组中其他成员的年龄和队长的年龄差距不能超过K。有些人想和自己亲密的人组在同一个小组，同时希望所在的小组人越多越好。比如x
2017-07-11 14:51:23
366
原创 帮助Bsny
帮助Bsny 题目描述 Bsny的书架乱成一团了，帮他一下吧！他的书架上一共有n本书，我们定义混乱值是连续相同高度书本的段数。例如，如果书的高度是30，30，31，31，32，那么混乱值为3；30，32，32，31的混乱值也为3。但是31，32，31，32，31的混乱值为5，这实在是太乱了。Bsny想尽可能减少混乱值，但他有点累了，所以他决定最多取出k本书，再随意将它们放回到书架上。你能帮助他吗
2017-07-10 19:00:08
433
原创 单词接龙1
单词接龙1 题目描述 Bsny从字典挑出N个单词，并设计了接龙游戏，只要一个单词的最后两个字母和另一个单词的前两个字母相同，那么这两个单词就可以有序的连接起来。Bsny想要知道在所给的所有单词中能否按照上述方式接龙组成一个单词环（可能是多个），若能，求所有环的环中单词平均长度最大值。输入 第一行一个整数N，表示单词数量。接下来N行，每行一个字符串，仅包含小写字母。输出 若能组成单词环，输出环
2017-07-10 18:33:41
812
原创 离线求LCA（深搜）
离线求出任意点对u−v的最近公共祖先离线求出任意点对u-v的最近公共祖先 不妨令v的深度优先搜索序小于u不妨令v的深度优先搜索序小于u 深搜到u时，v已经被扫过，答案为v到root路径上没有处理完的第一个灰色点深搜到u时，v已经被扫过，答案为v到root路径上没有处理完的第一个灰色点 可用并查集优化，若一个点全部扫完则加入集合中，代表元素为集合最先被搜到的点可用并查集优化，若一个点全部扫完则加
2017-06-23 20:45:22
325
原创 poj 2152 Fire
Fire DescriptionCountry Z has N cities, which are numbered from 1 to N. Cities are connected by highways, and there is exact one path between two different cities. Recently country Z often caught fire
2017-06-23 14:34:49
302
原创 灰色的果实
灰色的果实问题描述 树为灰色果实之树，不定时会长出灰色果实。贸然接近果实只会使得自己受其迷惑最后神经错乱而 浑浑噩噩不得终日，与死人无异。你的目标是成功到达树的顶端，砍下灰色果实的灵脉。 为了能够免除灰色果实的影响，你需要在灰色果实力量微弱时在树的各个点 设置若干个保护点，保护点内燃烧着镇定人心的香，以此来抵御灰色果实的精神 袭击。一个点必须在 lim[i]距离以内有保护点才能收到保护。而
2017-06-20 16:54:24
826
原创 卡片游戏
卡片游戏 题目描述 小D举办了元旦联欢活动，其中有一个卡片游戏。游戏的规则是这样的：有n张卡片，每张卡片上正面写着一个小于等于100的正整数ai，反面都是一样的花色。这n张卡片正面朝下叠成一堆，玩这个游戏的人从中可以抽出连续的k（1≤k≤n）张卡片。如果对于这k张卡片上的数字的平均值a，满足l<=a<=r，那他就可以获得小礼物一件。小W来玩这个游戏了，她事先通过某些途径知道了这n张卡片上写的数字
2017-06-16 17:47:27
1047
原创 I Hate It(splay)
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。 这让很多学生很反感。 不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。 Input 本题目包含多组测试，请处理到文件结束。 在每个测试的第一行，有两个正整数 N 和 M ( 0< N<=200000,0< M<5000 )，分别代表
2017-06-13 21:12:01
482
原创 最优贸易简化版
最优贸易简化版题目描述 C国有n座城市，编号是1到n，编号为i的城市有路到编号为i+1的城市（编号为n的城市没有路到其他的城市）。 C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。 商人阿龙再次来到C国旅游。他还是想贩卖水晶赚取旅费，在某个城市买入，再另一个城市卖出。 他将从编号为a的城市到编
2017-06-13 20:23:41
918
原创 pinball
pinball题目描述 A喜欢玩一个叫pinball的游戏。游戏规则如下： Pinball的游戏界面由m+2行、n列组成。第一行在顶端。一个球会从第一行出发，开始垂直下落，A会得到一个积分当他击中一个球的时候。 小天才lyk觉得这太困难了，于是在界面中放入了一些漏斗，一共有m个漏斗分别放在第2~m+1行，第i个漏斗的作用是把经过第i+1行且列数在Ai~Bi之间的球将其移到第Ci列。 但是使用
2017-06-13 20:11:28
560
原创 三条最短路
tower题目描述 A去推塔。但是推第n座塔必须先推了第1~n-1座塔。 为了加快速度A召唤出了B和C。求A和他的召唤兽们为了推完所有塔所经过的最短距离。输入 第一行一个数N，代表一共要去多少个城市。 下面N-1 行，对于第 i 行，有 n-i 个数，表示第 i 个城市分别和第i+1, i+2, i+3, ……, N 的距离（距离<=10000）输出 一个数，表示最短距离样例输入 5
2017-06-13 19:49:06
254
原创 奶牛异或
奶牛异或 时间限制: 2 Sec 内存限制: 64 MB 提交: 265 解决: 41 [提交][状态][讨论版] 题目描述 农民约翰在喂奶牛的时候被另一个问题卡住了。他的所有N(1 <= N <= 100,000)个奶牛在他面前排成一行(按序号1..N的顺序)，按照它们的社会等级排序。奶牛#1由最高的社会等级，奶牛#N最低。每个奶牛同时被赋予了一个唯一的数在0..2^21 - 1的范
2017-06-13 19:34:55
488
原创 零件加工
零件加工题目描述 工匠小K最近有n个零件需要加工。每个零件都需要ti天的时间来完成，每个零件每延迟一天加工都要缴纳一定的罚金si。延迟的天数为从今天算起到该工作开始的那天，第一个零件加工没有罚金。现在小K想知道怎样安排加工顺序可以使他要交的罚金最少，最少是多少。这个数可能会很大，请输出这个数对m取模后的结果。输入 输入文件名为process.in。输入第一行为一个整数n，表示需要加工的零件总数。
2017-06-13 18:24:55
764
转载 算法导论-第22章-基本的图算法-22.5 强连通分量
转自#include <iostream>using namespace std;//8个点#define N 8 #define WHITE 0#define GRAY 1#define BLACK 2//边结点结构struct Edge{ int start;//有向图的起点 int end;//有向图的终点 Edge *next;//指向同一个起点的下一
2017-06-03 21:16:55
753
原创 宿命的PSS
宿命的PSS 题目描述 最小生成树P.S.S在宿命的指引下找到了巫师Kismi。P.S.S希望Kismi能帮自己变成一个完全图。Kismi由于某些不可告人的原因，把这件事交给了你。 PS: 可以保证，这个最小生成树对于最后求出的完全图是唯一的。输入 输入的第一行是一个整数n，表示生成树的节点数。 接下来有n-1行，每行有三个正整数，依次表示每条边的端点编号和边权。 （顶点的边号在1-n之间
2017-06-03 21:12:25
907
原创 Flowerpot
Flowerpot题目 此题，他说用线段树，但我发现只要二分答案+two pointers， 二分出答案后，维护区间最大值最小值，来验证答案是否合法。 维护区间最小，就是维护最长不下降子序列。(因为，有比当前小的，直接替代了） 维护区间最大，就是维护最长不上升子序列。(有比当前大的，也直接替代了）
2017-06-03 20:59:55
508
原创 poj 3624 Balanced Lineup
For the daily milking, Farmer John’s N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things s
2017-06-02 14:17:00
301
原创 括号序列
括号序列 题目描述 定义如下规则序列（字符串）： 1.空序列是规则序列； 2.如果S是规则序列，那(S)和[S]也是规则序列； 3.如果A和B都是规则序列，那么AB也是规则序列。 例如，下面的字符串都是规则序列： (), [], (()), ([]), ()[], ()[()] 这几个不是规则序列： (, [, ], )(, ([() 现在，给出一些有’(’ ,
2017-06-01 21:16:41
613
原创 乘积最大
乘积最大今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目: 设有一个长度N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。 同时，为了帮助选手能
2017-06-01 20:37:14
326
原创 低价购买
低价购买题目描述“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(216范围内的正整数)，你可以选择在哪些天购
2017-06-01 19:50:11
380
原创 bzoj 3156 防御准备
防御准备DescriptionInput第一行为一个整数N表示战线的总长度。第二行N个整数，第i个整数表示在位置i放置守卫塔的花费Ai。Output共一个整数，表示最小的战线花费值。Sample Input102 3 1 5 4 5 6 3 1 2Sample Output18HINT
2017-05-25 20:13:40
419
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人