- 博客(180)
- 收藏
- 关注
RSS订阅
原创 未完成的题
Spfa： 洛谷 2296 寻找道路洛谷 1073 最优贸易堆： SSL 1411 最小函数值 SSL 1220 促销 PKU 2442 Sequence PKU 1442 Black Box HASH表全部 并查集全部 离散全部 网络流全部
2017-03-22 16:44:07
327
原创 【JZOJ 4742】【NOIP2016提高A组模拟9.2】单峰 (数学,快速幂)
问题描述 输入 输出 样例输入 2 样例输出 2 数据范围 算法讨论 #include <cstdio>#define LL long long#define mo 1000000007using namespace std;LL n;LL power(LL a,LL b){ LL ans=1,base=a; wh...
2018-08-25 08:53:42
285
原创 【JZOJ 4725】【NOIP2016提高A组模拟8.22】质数序列 (数学,筛素数)
问题描述 由于去NOI的火车“堵”了数不清时间，小Z和小D打完ETG，闲着无聊开始看今年的JSOI省选题，并尝试着修改题目： 对于一个长度为L ≥ 2的序列，X：x1,x2,…,xL ，如果满足对于任意的1 ≤ i < j ≤ L，均有 xi+xj为质数，则他们把X称为一个“质数序列”。 现在有一个长度为N的序列，A：a1,a2,…,aN ，他希望从中选取一个包含元素最多的子序列，使得...
2018-08-25 08:48:22
333
原创 【JZOJ 2499】【NOIP2011模拟7.28】东风谷早苗 (模拟)
问题描述 在幻想乡，东风谷早苗是以高达控闻名的高中生宅巫女。某一天，早苗终于入手了最新款的钢达姆模型。作为最新的钢达姆，当然有了与以往不同的功能了，那就是它能够自动行走，厉害吧（好吧，我自重）。早苗的新模型可以按照输入的命令进行移动，命令包含’E’、’S’、’W’、’N’四种，分别对应四个不同的方向，依次为东、南、西、北。执行某个命令时，它会向着对应方向移动一个单位。作为新型机器人，自然不会只...
2018-08-25 08:44:59
466
原创 【JZOJ 5838】【广州市选2011一试】旅游路线 (前缀和)
问题描述 GZOI队员们到X镇游玩。X镇是一个很特别的城镇，它有m+1条东西方向和n+1条南北方向的道路，划分成m*n个区域，这些区域标从北到南、从西到东的坐标标识为从坐标 (1,1) 到坐标(m,n)。 GZOI队员们预先对这m*n个区域打分V(i，j)(分数可正可负)。分数越高表示他们越想到那个地方，越低表示他们越不想去。为了方便游玩，队员们需要选定一个连续的区域集合作为活动范围。例如，如果...
2018-08-25 08:40:36
204
原创 【JZOJ 4421】【GDOI2016模拟4.2】aplusb (数学,gcd)
问题描述 SillyHook要给小朋友出题了，他想，对于初学者，第一题肯定是a+b 啊，但当他出完数据后神奇地发现.in不见了，只留下了一些.out，他想还原.in，但情况实在太多了，于是他想要使得[a,b] ([a,b] 表示a,b 的最小公倍数)尽可能大。 输入 输入文件的第一行一个整数T 表示数据组数。 接下来T行每行一个整数n ，表示.out中的数值，即a+b=n 。 输出 共...
2018-08-25 08:34:54
231
原创 【JZOJ 3928】【NOIP2014模拟11.6】射击 (堆)
问题描述 有问题，找副连，无聊的时候当然也可以找他啦。小W找到了他的叔叔——东厂厂长——宇宙超级无敌老WS yy。他们叔侄两个商量之后决定用弹弓打破社区里的一些窗户，但是弹弓每秒只能彻底打破一扇窗户。而且如果某户窗户的主人回来了的话，他们就不能进行破坏了（不然会死得很惨的）。因为有的人装的玻璃好，有的人装的玻璃差，有的人装的玻璃高，有的人装的玻璃矮，所以你不能要求他们叔侄两个打破不同的窗户获得的...
2018-08-24 21:49:08
214
原创 【JZOJ 3927】【NOIP2014模拟11.6】可见点数 (欧拉函数)
问题描述 ZPS经过长期的努力争取，终于成为了0901班的领操员，他要带领0901班参加广播操比赛。现在0901班的队伍可以看作是一个n*n的点阵，每个人都站在格点上。现在作为领操员的ZPS站(0,0)点，他想知道如果0901班的队伍站齐了，他能看到多少个人的脸（假设每个人的身高相同，体积相同）。 输入 一个正整数n。 输出 ZPS能看到多少个人的脸（当然他是看不到自己的脸的）。 样例...
2018-08-24 20:07:26
191
原创 【JZOJ 100029】【NOIP2017提高A组模拟7.8】陪审团 (贪心+排序)
问题描述 陪审团制度历来是司法研究中的一个热议话题，由于陪审团的成员组成会对案件最终的结果产生巨大的影响，诉讼双方往往围绕陪审团由哪些人组成这一议题激烈争夺。 小 W 提出了一个甲乙双方互相制衡的陪审团成员挑选方法：假设共有 n 名候选陪审团成员，则由甲先提名 s 位候选人，再由乙在甲提名的 s 位候选人中选出 t 名，作为最终的陪审团成员。显然这里应当有n ≥ s ≥ t。假设候选人 k 对甲...
2018-08-24 20:01:21
565
原创 【JZOJ 5197】【NOIP2017提高组模拟7.3】C (数学)
问题描述 输入 输出 数据范围 样例输入 3 样例输出 1 算法讨论 #include <cstdio>using namespace std;int n,s,Max;int gcd(int a,int b){ return b?gcd(b,a % b):a;}int main(){ scanf("%d",&a...
2018-08-23 21:47:31
193
原创 【JZOJ 4732】【NOIP2016提高A组模拟8.23】函数 (欧拉函数)
问题描述 输入 输出 样例输入 3 1 2 6 样例输出 4 样例解释： f(1)=1 f(2)=1 f(6)=2 算法讨论 这个函数是欧拉函数，考虑用线性筛法求。 phi(p)=p-1 因为质数p除了1以外的因数只有p，故1至p的整数只有p与p不互质 如果i mod p = 0, 那么phi(i * p)=p * phi(i) 若i mod p ...
2018-08-23 21:31:03
239
原创 【JZOJ 5185】【NOIP2017提高组模拟6.30】tty's sequence (数学)
问题描述 输入 输出 样例输入 input 1： 6 3 1 1 1 0 0 0 input 2： 6 3 1 1 0 1 0 0 input 3: 6 3 11 8 2 1 3 9 样例输出 output 1 1 1 output 2 1 0 output 3 11 1 算法讨论 或就是全部或起来，与就是恰好k个，按位处理每一位的答案就好。...
2018-08-20 16:08:14
213
原创 【JZOJ 5809】【NOIP2008模拟】数羊 (数学 逆元)
问题描述 牧羊人A和牧羊人B总是很无聊，所以他们要玩一个游戏。A有a只羊，B有b只羊。他们想要知道a^b的因子和是多少。这就很为难两个牧羊人了，由于答案太大，你能不能告诉我答案取模9901的数。 输入 仅一行，为两个正整数a和b 输出 a^b的因子和对9901的余数。 样例输入 2 3 样例输出 15 算法讨论 对于100%的数据，我们将a进行质因数分解，将每个质因子的指数乘...
2018-08-20 16:03:22
400
原创 【JZOJ 5182】NOIP2017提高组模拟6.29】码灵鼠 (数学)
问题描述 码零鼠是一只很喜欢mx数学的神犇，上面那个不是ta本人的样子。这天，ta在研究一个神奇的数列，这个数列是这样的： a0 = 1 an = ai + aj (n>=1, i,j均在[0,n-1]内均匀随机) Ta想知道对于给定的n，an的期望值是多少，你能告诉ta吗？ 出于ta对整数的热爱，你只需要输出答案向下取整后的值 输入 一个整数T，表示数据组数 每组数据一...
2018-08-20 15:49:04
221
原创 【JZOJ 5458】【NOIP2017提高A组冲刺11.7】质数 (线筛)
问题描述 小X 是一位热爱数学的男孩子，在茫茫的数字中，他对质数更有一种独特的情感。小X 认为，质数是一切自然数起源的地方。 在小X 的认知里，质数是除了本身和1 以外，没有其他因数的数字。 但由于小X 对质数的热爱超乎寻常，所以小X 同样喜欢那些虽然不是质数，但却是由两个质数相乘得来的数。 于是，我们定义，一个数是小X 喜欢的数，当且仅当其是一个质数，或是两个质数的乘积。 而现在，小X...
2018-08-20 15:43:55
209
原创 【JZOJ 5456】【NOIP2017提高A组冲刺11.6】奇怪的队列 (线段树)
问题描述 nodgd的粉丝太多了，每天都会有很多人排队要签名。 今天有��个人排队，每个人的身高都是一个整数，且互不相同。很不巧，nodgd今天去忙别的事情去了，就只好让这些粉丝们明天再来。同时nodgd提出了一个要求，每个人都要记住自己前面与多少个比自己高的人，以便于明天恢复到今天的顺序。 但是，粉丝们或多或少都是有些失望的，失望使她们晕头转向、神魂颠倒，已经分不清楚哪一边是“前面”了，于...
2018-08-20 15:40:39
314
原创 【JZOJ 5776】【NOIP2008模拟】小x游世界树 (树)
问题描述 小x得到了一个(不可靠的)小道消息，传说中的神岛阿瓦隆在格陵兰海的某处,据说那里埋藏着亚瑟王的宝藏，这引起了小x的好奇，但当他想前往阿瓦隆时发现那里只有圣诞节时才能到达，然而现在已经春天了，不甘心的他将自己的目的地改成了世界树，他耗费了大量的时间，终于将自己传送到了世界树下。世界树是一棵非常巨大的树，它有着许许多多的枝条以及节点，每个节点上都有一个平台。好不容易来到传说中的世界树下，...
2018-08-20 15:34:43
335
原创 【JZOJ 5775】【NOIP2008模拟】农夫约的假期 (二维前缀和)
问题描述 在某国有一个叫农夫约的人，他养了很多羊，其中有两头名叫mm和hh，他们的歌声十分好听，被当地人称为“魔音”······ 农夫约也有自己的假期呀！他要去海边度假，然而mm和hh不能离开他。没办法，他只好把他们两个带上。 到了海边，农夫约把他的羊放在一个(n*n)的矩阵（有n*n个方格）里。mm和hh十分好动，他们要走到m(m<=n*n)个地方，第i个地方的坐标为(x[i...
2018-08-20 15:26:57
243
原创 【JZOJ 5771】【NOIP2008模拟】遨游 (最短路+二分)
问题描述 MWH寒假外出旅游，来到了S国。S国划分为N个省，第i个省有Ti座城市，编号分别为Ci1，Ci2，……CiTi（各省城市编号不会重复）。所有城市间有M条双向的道路连接，从任意一个城市出发，可到达一切城市，每条道路均须收费。 此时恰逢春运期间，S国交通运输局采取了优惠措施。当一条路的路费在[L..R]区间时，可免去。同时，每个省也有优惠措施，第i个省内的每条道路路费收其Xi%...
2018-08-20 15:21:20
269
原创 【JZOJ 5459】【NOIP2017提高A组冲刺11.7】密室 (状压+广搜)
问题描述 小X 正困在一个密室里，他希望尽快逃出密室。 密室中有N 个房间，初始时，小X 在1 号房间，而出口在N 号房间。 密室的每一个房间中可能有着一些钥匙和一些传送门，一个传送门会单向地创造一条从房间X 到房间Y 的通道。另外，想要通过某个传送门，就必须具备一些种类的钥匙（每种钥匙都要有才能通过）。幸运的是，钥匙在打开传送门的封印后，并不会消失。 然而，通过密室的传送门需要耗费大量的...
2018-08-20 15:12:38
198
原创 【JZOJ 3493】【NOIP2013模拟联考13】三角形(triangle) (数学)
问题描述 平面上有n个点，求出用这些点可以构成的三角形数。 输入 第一行一个整数n。接下来n行，每行两个整数，表示点的坐标。 输出 输出仅一个整数，表示所求答案。 样例输入 50 01 11 -1-1 -1-1 1 样例输出 8 算法讨论 枚举第一个点，对于剩下的点按照和这个点连线的斜率排序一下，把相同斜率的线段放在一起，可以算出选到两条相同斜率的线段...
2018-08-06 21:48:18
822
原创 【JZOJ 3487】【NOIP2013模拟联考11】剑与魔法(dragons) (贪心+优先队列)
问题描述 万老师听说某大国很流行穿越，于是他就想写一个关于穿越的剧本。闲话休提。话说老师穿越到了某一个剑与魔法的大陆。因为如此这般，所以老师从维娜艾那里得到了预言。老师一共被告知了若干件按顺序结算的事件。这些事件分为两类：战役事件（CASE）、穿越回去事件（END）。战役事件可以选择是否参加，参加了之后会获得一定的金钱。每个END事件发生需要至少参加一定数量的战役事件。特别的是，END事件如...
2018-08-06 21:45:57
257
原创 【JZOJ 3470】【NOIP2013模拟联考8】最短路(path) (spfa)
问题描述 给定一个n个点m条边的有向图，有k个标记点，要求从规定的起点按任意顺序经过所有标记点到达规定的终点，问最短的距离是多少。 输入 第一行5个整数n、m、k、s、t，表示点个数、边条数、标记点个数、起点编号、终点编号。接下来m行每行3个整数x、y、z，表示有一条从x到y的长为z的有向边。接下来k行每行一个整数表示标记点编号。 输出 输出一个整数，表示最短距离，若没有方案可行...
2018-08-06 21:42:55
508
原创 【洛谷 3367】【模板】并查集
问题描述 如题，现在有一个并查集，你需要完成合并和查询操作。 输入 第一行包含两个整数N、M，表示共有N个元素和M个操作。接下来M行，每行包含三个整数Zi、Xi、Yi当Zi=1时，将Xi与Yi所在的集合合并当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N 输出 如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N 样例输入 ...
2018-07-14 19:05:14
409
原创 【JZOJ 4273】【NOIP2015模拟10.28B组】圣章-精灵使的魔法语（线段树）
问题描述 【背景介绍】 “魔法？？？算了吧，这种东西我肯定学不了的啦！”明明是个剑士，却被眼前这位洋洋自得的精灵使——弗洛莉拖出去学魔法，真是个没事找茬的家伙…… “没事啦。作为一名冒险者会发生很多情况，中毒啦，受伤啦，被咒语束缚之类的，没有魔法就很难办的呀！”她到是好像一副什么都懂的样子，真是令人火大。 “都说我是个人类了，魔法这种东西学起来很困难的吧！”我只好找个看似靠谱的借口。 然...
2018-07-14 16:27:32
276
1
原创 【JZOJ 3385】【NOIP2013模拟】黑魔法师之门（并查集）
问题描述 经过了16个工作日的紧张忙碌，未来的人类终于收集到了足够的能源。然而在与Violet星球的战争中，由于Z副官的愚蠢，地球的领袖applepi被邪恶的黑魔法师Vani囚禁在了Violet星球。为了重启Nescafé这一宏伟的科技工程，人类派出了一支由XLk、Poet_shy和lydrainbowcat三人组成的精英队伍，穿越时空隧道，去往Violet星球拯救领袖applepi。app...
2018-07-14 11:45:28
202
原创 【JZOJ 3383】【NOIP2013模拟】太鼓达人（欧拉图？）
问题描述 七夕祭上，Vani牵着cl的手，在明亮的灯光和欢乐的气氛中愉快地穿行。这时，在前面忽然出现了一台太鼓达人机台，而在机台前坐着的是刚刚被精英队伍成员XLk、Poet_shy和lydrainbowcat拯救出来的的applepi。看到两人对太鼓达人产生了兴趣，applepi果断闪人，于是cl拿起鼓棒准备挑战。然而即使是在普通难度下，cl的路人本性也充分地暴露了出来。一曲终了，不但没有过关，...
2018-07-14 11:40:29
224
原创 【JZOJ 3382】【NOIP2013模拟】七夕祭（均分纸牌）（数学）
问题描述 七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是TYVJ今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕，于是他们决定去TYVJ七夕祭游玩。TYVJ七夕祭和11区的夏祭的形式很像。矩形的祭典会场由N排M列共计N×M个摊点组成。虽然摊点种类繁多，不过cl只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。Vani预先联系了七夕祭...
2018-07-14 11:19:01
356
原创 【JZOJ 1414】平台
问题描述 Alice要搭建平台，平台不能漂在空气中，必须要有两根柱子支撑，具体地说，每个平台的两端必须由一根柱子支撑，柱子的另一端在地板或另一个平台上。 给你平台的放置位置（如下左图所示），每个平台的位置由它的高度（离地面的垂直距离）和水平方向两个端点的坐标决定，每根柱子必须安放在离端点0.5个单位的位置，如下右图所示。 编程计算所需柱子总长是多少。 输入 第一行包含整数N,...
2018-05-23 17:05:52
396
原创 【洛谷 3383】【模板】线性筛素数
问题描述 如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内） 输入 第一行包含两个正整数N、M，分别表示查询的范围和查询的个数。接下来M行每行包含一个不小于1且不大于N的整数，即询问该数是否为质数。 输出 输出包含M行，每行为Yes或No，即依次为每一个询问的结果。 样例输入 100 5 2 3 4 91 97 样例输出 Yes ...
2018-05-11 21:09:33
244
原创 【JZOJ 3966】Sabotage(二分)
问题描述 FJ 的死对头，FP，现在决定了去破坏FJ 的挤奶设备！ 这个挤奶设备由一行N（3 <= N<= 100, 000）个挤奶机器，其中第i 个机器生产Mi 单位的牛奶（1<= Mi <= 10, 000）。FP 计划将机器连续的一块断开——从第i 个机器到第j 个机器（2<= i<= j<= N-1）；注意第一个和最后一个机器FJ 并不想要断开...
2018-03-10 16:24:28
207
原创 【JZOJ 1792】教主的花园（二分）
问题描述 【问题背景】 LHX教主最近总困扰于前来膜拜他的人太多了，所以他给他的花园加上了一道屏障。 【问题描述】 可以把教主的花园附近区域抽像成一个正方形网格组成的网络，每个网格都对应了一个坐标（均为整数，有可能为负），若两个网格(x1, y1)，(x2, y2)有|x1 – x2| + |y1 – y2| = 1，则说这两个网格是相邻的，否则不是相邻的。 教主在y =
2018-02-07 21:22:27
388
原创 【JZOJ 3769】【NOI2015模拟8.14】A+B
问题描述 对于每个数字x，我们总可以把它表示成一些斐波拉切数字之和，比如8 = 5 + 3， 而22 = 21 + 1，因此我们可以写成 x = a1 * Fib1 + a2 * Fib2 + a3 * Fib3 + … + an * Fibn, 其中，Fib1 = 1, Fib2 = 2…. Fib[i] = Fib[i – 1] + Fib[I - 2], 且a[n] > 0.那么我们
2018-02-07 21:19:02
202
原创 【JZOJ 3756】【NOI2014】动物园（kmp）
问题描述 近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。某天，园长给动物们讲解 KMP 算法。园长：“对于一个字符串 S，它的长度为 L。我们可以在 O(L)的时间内，求出一个名为 next 的数组。有谁预习了 next 数组的含义吗？”熊猫：“对于
2018-02-07 21:06:07
323
原创 【JZOJ 4314】【NOIP2015模拟11.4】老司机
问题描述 输入 输出 样例输入 4 1 3 6 6 样例输出 3 1 2 3 算法讨论 注意到1,2,4,8,16,32总是一个可行解，所以答案不会超过6。爆枚答案是什么即可。 事实上字典序最小的通解是1,2,3,6,13,25。#include using namespace std;#define maxn 5656#define maxlong
2018-01-30 21:11:21
443
原创 【JZOJ 4312】【NOIP2015模拟11.4】格点统计
问题描述 输入 输出 样例输入 输入1： 3 输入2： 4 样例输出 输出1： 5 输出2： 8 算法讨论 数学方法。我们将每种组合列一下： 1,1 2,1 3,1 4,1 5,1 6,1 7,1 8,1 9，1 2,1 2,2 3,2 4,2 3,1 2,3 3,3 4,1 2,4 5,
2018-01-30 21:06:03
292
原创 【JZOJ 4310】【NOIP2015模拟11.4】最优交换（贪心）
问题描述 输入 输出 样例输入 2 1432 2 4321 2 样例输出 4312 4321 算法讨论 用贪心就能过了，在当前位置以后，长度为k的子串中找到最大的交换即可。#include using namespace std;long long a[56],t,k,maxx,p;bool f;int main(){ freope
2018-01-30 20:49:11
268
原创 【JZOJ 4309】【NOIP2015模拟11.4】刷题计划 刷题计划
问题描述 输入 输出 样例输入 10000 12 2 1 3 2 9999 3 1 1 3 2 1 3 2 10000 3 2 9999 3 样例输出 1 9999 1 9999 9999 10000 9999 9999 10000 算法讨论 暴力嗯……#include using namespace std;#define
2018-01-30 20:41:00
278
原创 【JZOJ 1367】俄罗斯方块（模拟）
问题描述 相信大家都玩过“俄罗斯方块”游戏吧，“俄罗斯方块”是一个有趣的电脑小游戏，现有一个有C列、行不受限定游戏平台，每一次下落的方块是下列的7个图形的一种： 在下落的过程中，游戏者可以作90、 180或270 度旋转，还可以左右移动，对于每一次方块落地，我们要求方块的每一部分都必须与地面（最底面或己落下的方块上表面）接触，例如，有一个宽度为6列的平台，每一列的初始高度（已经占用的方格
2018-01-28 21:51:16
268
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人