- 博客(164)
- 收藏
- 关注
RSS订阅原创 2020 计蒜之道 线上决赛（C，D，E，F，G）
D. 两个多项式的卷积数据范围样例输入复制21 2 33 2 131 1 42 0 -11 1 4样例输出复制3330标准题解：自己就照这个思路写的，不多说，上板子/**/#include <cstdio>#include <cstring>#include <cmath>#include <cctype>#include <iostream>#include <a.
2020-10-24 23:00:18
486
原创 2020牛客暑期多校训练营（第二场）
E.Exclusive OR 题意：给你一个长度为n的数组a，求选择一个的最大异或和，两个的最大异或和，三个的最大异或和，....，n个的最大异或和，每一个数可以选择多次（1 <= n <= 200000, 0 <= a[i] < 2^18） 题解：首先我们知道极限情况下选择2^0, 2^1, 2^2, 2^3, 2^4, 2^5, ...... , 2^17共18个数，所以选择18个数必能到达最大值，同时在这个极限情况下，选择19个数应该在18个数的基础上...
2020-07-16 13:06:05
539
原创 斐波那契(gcd+矩阵快速幂)
时间限制:1Sec内存限制:128 MB题目描述定义斐波那契数列F[0]=0, F[1]=1, F[n]=F[n-1]+F[n-2](n>=2)小猪很喜欢这个数列，她听说你可以求F[n] mod 998244353，觉着很厉害，于是她会进行多次询问，每次询问给出五个整数n,a,b,c,d，她希望你求出gcd(a*F[n]+b*F[n+1],c*F[n]+d*F[n+1]) mod 998244353.输入第一个一个正整数q，表示询问数输出q行，每行一个[0,9982...
2020-07-12 21:56:51
485
原创 快速傅里叶变换（容斥+dp）
时间限制:1Sec内存限制:128 MB题目描述chen_03在切快速傅里叶变换(FFT)。一共有n种FFT的题，他做出一道第i种题后能获得ci点的巨佬值。他一共要打m场模拟赛，由于Rainy7的魔法，每次赛前，他的巨佬值会清零。chen_03不希望他的巨佬值为0。为了获得一些巨佬值，每场模拟赛前，他都要去切FFT的题。然而他太巨了，Rainy7为了限制他的实力，又施了一个魔法，使得第i种题只有di道，且每道题在切完后会消失。对于每场模拟赛，chen_03都有一个幸运数字，他想要知...
2020-07-04 14:45:40
261
原创 树统计 (dfs序+线段树)
时间限制:1Sec内存限制:128 MB题目描述然而，这一切宛如一度揉过的复写纸，无不同原来有着少许然而却是无可挽回的差异。—— 村上春树关于树的算法有一大堆，样样都是毒瘤。比如说 2019 CSP-S 的树论题，如果擅长树形数据结构马上想到正解，但是 3edc2wsx1qaz 并不擅长，就只好骗分了。3edc2wsx1qaz 当时数组开小了，惨遭 RE，3edc2wsx1qaz 一想起这事，不禁夙夜忧叹，辗转反侧。现在他又遇到一道毒瘤的树上问题了，他下定决心：这次一定要写出正解！...
2020-07-04 13:57:02
431
6
原创 树统计（虚树）
时间限制:1Sec内存限制:128 MB题目描述骗分过样例，暴力出奇迹。关于树的算法有一大堆，样样都是毒瘤。比如说 NOIP2018 提高组的 D2T3，如果会动态 DP 的做法那么就马上想到正解，但是 Tweetuzki 不会动态 DP，就只好骗分了。可惜树题的码量也是超级大的。听说好多学长都会动态 DP，但是考场上调不出来，只好暴力分收场了。疯狂暗示Tweetuzki 当时暴力写挂了，有 4 个点写成了死循环……于是分数白白少了 16 分。Tweetuzki 一想起这事，不禁夙...
2020-07-03 16:10:17
209
原创 神灯 (lamp)（BIT+优先队列）
时间限制:2Sec内存限制:128 MB题目描述巨神 Ctt 被阿拉丁与神灯的故事吸引。于是，他马上去了神灯所在的山洞。Ctt 在山洞中苦苦寻找，终于找到神灯的藏身之处，他马上将神灯从玛瑙高台上取下。在那瞬间，神灯起了反应，周围的灯火全亮了。Ctt 仔细打量，发现这里是一个很大洞穴，洞穴周围有n座木门 Ctt 按照阿拉丁的步骤，轻轻擦拭神灯，洞穴周围的木门悄然打开，门后的洞穴中都是挤满洞穴的钻石。Ctt 正准备把钻石从门后的洞穴全部抱出，却听见神灯中似乎在说话：“贪婪的人没有好下场！” 后...
2020-06-30 13:49:59
300
原创 斐波那契求和(矩阵快速幂+多项式拆分)
https://ac.nowcoder.com/acm/contest/5477/JFib(i)表示斐波那契函数，Fib(n)=Fib(n-1)+Fib(n-2)，如Fib(1)=1，Fib(2)=1，Fib(3)=2，Fib(4)=3，Fib(5)=5，Fib(6)=8。给定正整数n和k，求：由于结果太大，你需要把求和的结果对998244353取余介绍两种矩阵构造方法:方法一:设，那么 ...
2020-05-11 16:11:25
501
原创 商店(分块+二分)
题目描述从前有一个奇怪的商店，一共售卖k种物品，第i种物品的初始价格为i。但是这商店有个很奇怪的规矩，就是你每次购买一样物品之后，这种物品的价格都会在当前基础上翻一倍。现在我们想要用最少的钱从里面买n样物品，不限购买的物品种数和每种物品购买的次数，请求出若这样做，所买到的最贵的物品的价格，由于这个数字可能过大，你只需要输出其模1000000007=10^9+7的结果即可。输入每个测...
2020-04-29 12:25:08
270
原创 表格（拉格朗日插值法）
众所周知，Logx精通Excel。他觉得表格只有单调的白色非常无聊，他决定将一些单元格涂黑。在一个n行m列的表格里，刚开始所有单元格都是白的。Logx打算在这个表格选出三个不同的单元格A(x1,y1),B(x2,y2),C(x3,y3)，并将选中的三个单元格涂黑。为了使表格看起来美观，Logx会使每一行和每一列均至多有一个格子被涂黑。他称一种选择方案是好的，当且仅当L≤|x1-x2|+|...
2020-03-23 13:44:10
2695
原创 Preliminaries for Benelux Algorithm Programming Contest 2019
A.Architecturepurpose：给你第一行的值表示m列的最大值，给你第m行的值表示n行的最大值，问是否会行列冲突。Solve:求出行列最大值，如果一样即possible，否则impossible。Std:https://pasteme.cn/26956B.Bracket Sequencepurpose：给你一串字符串，最外面数字之间全用+，一层括号用*...
2020-03-14 17:32:13
553
原创 2019icpc徐州 E题 Multiply(pollard_rho)
样例输入复制23 10 102 3 42 2 101 1样例输出复制28O(1)快速乘你能秒我？？/**/#include <cstdio>#include <cstring>#include <cmath>#include <cctype>#include <iostream>...
2019-12-09 21:45:06
543
原创 费马大定理（原根+扩欧）
考虑方程x^k+y^k=z^k，其中x,y,z,k≠0 ，且均为正整数。众所周知，由费马大定理，当k> 2时，方程无解。现在考虑在模意义下的问题。给定一个质数P，以及一个正整数L，现在想知道有多少个整数k，满足1<=k<=L，存在x,y,z，0<x,y,z<P，使得x^k+y^k≡z^k(mod P)输入输入两个整数P,L。输出输出一个整数代表合法...
2019-11-06 17:47:25
667
1
原创 2019 ccpc网络赛 hdu6704 K-th occurrence
题意：给你一个字符串，再给你q个询问，每一个询问有l，r，k， 求字符串中下标l到下标r这个子串第k次出现在字符串中的位置，不存在则输出-1.后缀数组:将所有后缀排序，height数组是比较第i个后缀和第i-1个后缀的最长公共前缀的长度rmq：求区间的最小/最大数主席树：求区间第k大的数首先求出后缀数组(包括height函数)，对于每一个询问，我们知道它的开始下标是i，通过后缀数组...
2019-08-23 22:40:37
193
原创 2019ccpc女生赛
hdu 6544~65541.Ticket签到题/**/#include <cstdio>#include <cstring>#include <cmath>#include <cctype>#include <iostream>#include <algorithm>#include <ma...
2019-07-15 15:21:40
1698
1
原创 JSCPC Chika and Friendly Pairs(莫队+树状数组+离散化)
Chika and Friendly PairsTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 0Accepted Submission(s): 0Problem DescriptionChika gives ...
2019-05-19 13:40:56
240
原创 JackRabbit Slim（二分 + rmq）
问题 E: JackRabbit Slim时间限制:1 Sec内存限制:128 MB提交:23解决:1题目描述We all love rabbits, right? Unfortunately, they don’t even like us, rather, they love carrots instead!They love carrots so much t...
2019-04-10 17:04:22
264
原创 Determine the Price（ZJU 2002）
Determine the Price时间限制:1 Sec内存限制:128 MB题目描述For the manager of a theatre, setting the price of a ticket is a rather delicate matter. Suppose that a theatre has n (<= 1000000) seats, and t...
2019-02-27 23:02:22
198
原创 问题 D: 统计序列
时间限制: 1 Sec 内存限制: 128 MB题目描述有一天， 小Q想起了一个统计公式， 定义一个长度为m的序列，我们可以得到V,V的计算如下：其中：现在给你n个整数，需要从中选出m个数，使得他们构成的序列的V值最小。为了方便，你只需要输出最小的V值乘以m2的值，可以证明这是一个整数。 输入输入第一行两个正整数n和m。接下来n行，每行一个正整数，表示给你的n个数。...
2019-01-25 20:32:26
730
原创 成（思维）
成时间限制: 1 Sec 内存限制: 128 MB题目描述乌龟家的屋顶是凹凸不平的，所以每次雨后都会积水。为了知道屋顶是否会在暴雨后塌掉，他把屋顶的形 状给了你，希望你帮他计算暴雨后屋顶的积水总量。乌龟的屋顶由顺次排在同一水平线上的 n 个宽度为 1、高度为整数 (分别给出) 的瓦片组成。例如给定n = 5，瓦片的高度分别为 4, 2, 3, 5, 1，屋顶可以画在下图所示的网格中...
2019-01-02 16:30:43
900
1
原创 有（晒素数+枚举）
有时间限制: 1 Sec 内存限制: 128 MB题目描述乌龟给自己的贵重物品上了密码锁。密码锁上有5个数字拨盘。每个数字拨盘每次向上拨使数字增加1(9向上拨得到0)，向下拨使数字减少1(0向下拨得到9)。拨盘上的数字组成一个5位数。只要拨盘上的数字变为素数，密码锁就会被解开。素数(又称质数)是只能被1和它自身整除的大于1的自然数。因为乌龟动作实在太慢，他希望你帮他计算如何开锁，使...
2019-01-02 16:29:28
2322
3
原创 穿（string类的运用）
穿时间限制: 1 Sec 内存限制: 128 MB题目描述乌龟得到了他的基因组，一个只包含“ATCG”四种字母的字符串。乌龟想起科学家说，基因组中很多片段都多次重复出现，而且这种重复是很有意义的，于是他想计算一下自己基因组里片段的重复情况。给定一个基因组，其中一个长度为k的子串称为一个“k-片段”。乌龟希望你计算出基因组中不同的k-片段数量。例如，基因组“TACAC”的2-片段有“...
2019-01-02 16:27:00
1060
原创 幻想道路(最短路径)
幻想道路时间限制: 1 Sec 内存限制: 128 MB题目描述幻想世界最近发生了几件大事，先是有快乐星球代表，再是有黑暗星球代表来到了幻想世界，他们在幻想世界建造了一个自己的王国，并带领了一大批自己星球上的人入驻。对于这两个新的伙伴，原来的幻想王国里的人们还不知道应该以怎样的态度去应对。但阿卡表示，不管快乐星球与黑暗星球多么的势不两立，这都不关他们的事，他们还是要与两个星球之间都...
2019-01-02 16:21:36
468
原创 阿卡分糖果（滑动窗口）
阿卡分糖果时间限制: 10 Sec 内存限制: 128 MB题目描述阿卡的冬眠营马上要结束啦，他正在为这次活动筹办一场闭幕式。闭幕式上他策划了许多精彩的小游戏，并且打算用糖果作为这些小游戏的奖品。但是分糖果成为了一个难题。阿卡一共让大家玩了M轮小游戏，每一轮都有一个胜出者，阿卡要给他们其中的每个人分一些糖果。给每个人分相同数量的糖果虽然公平，但这太不符合阿卡的作风了，于是阿卡写...
2019-01-02 10:59:48
235
原创 组装玩具（优先队列）
组装玩具时间限制: 1 Sec 内存限制: 128 MB题目描述小华打算用 n 种（编号为 1 到 n）材料组装玩具。其中第 i 种材料的数量为 Xi 个。组装一个玩具需要第 i 种材料 Yi 个。小华另外有 m 个万能材料，每个万能材料可以作为 n 种材料中的任意一个材料使用。 请编程计算小华最多可以组装多少个玩具？ 输入输入共3行。第1行两个整数n和m，分...
2018-12-27 18:23:47
1185
原创 小X与神牛（dfs）
小X与神牛时间限制: 1 Sec 内存限制: 128 MB题目描述小X在野外遇到了一种神奇的牛，并将其命名为“神牛”。神牛都长着B只角，B只角从左到右在头顶上排成一排。每只角上都标着数字，不是0就是1。小X将每头神牛的B只角上的数字从左到右依次取出，组成一个只含0或1的B位二进制数。小X将这个二进制数转化为十进制，用这个十进制数来代表一头神牛，这个十进制就是这头神牛的编号。神牛们...
2018-12-24 19:34:35
1749
原创 小X与队列
小X与队列时间限制: 1 Sec 内存限制: 128 MB题目描述小X正和同学们做列队的练习。有n名同学排成一路纵队，编号为i的同学排在从前往后数第i个位置上，即：初始时的队列为1, 2, 3, ..., n。接下来小X会发出若干条指令，每条指令形如“请编号为x的同学排到最前面来”。（例如：若当前时刻的队列为5, 4, 3, 2, 1，发出一条x=2的指令后，队列变成了2, 5,...
2018-12-24 19:26:39
970
原创 小X与游戏（策略）
小X与游戏时间限制: 1 Sec 内存限制: 128 MB题目描述小X和小Y正在玩一个游戏，这个游戏是这样的：桌上放着n叠卡片，每叠恰好有两张。每张卡片有一个分数。小X为先手，双方轮流操作。轮到一方操作时，他可以选择取走某一叠卡片顶端的那一张（即：若这一叠还剩2张则取走上面的一张，否则取走下面的一张），并获得它的分数。他也可以选择不取。若卡片取完了、或者双方都选择不取卡片，那么游戏结...
2018-12-24 19:23:21
2212
原创 春游
春游时间限制: 1 Sec 内存限制: 128 MB 题目描述小Ｘ就读的CZ 中学今年又取得了小高考的空前佳绩，全校师生都很开心，于是大家希望找个地方去春游，在广泛征集了全校师生的意见后，最终决定前往嬉戏谷游玩一天。出行方案为租用大巴，可供租用的大巴有两种，一种是49 座的，一种是33 座的，49 座的大巴每辆租金为3300 元，33 座的大巴每辆租金为1900 元，全校师生共有n...
2018-12-22 22:16:58
1826
原创 人工智能
人工智能时间限制: 1 Sec 内存限制: 128 MB题目描述人胖了就容易打瞌睡，打瞌睡又会导致长胖，这对小Ｘ的减重计划很不利，于是小Ｘ决定做点动脑子的事来抵御瞌睡虫的进袭，小Ｘ决定响应国务院的号召投身到人工智能的研究开发大潮中去，具体研究什么好呢？小Ｘ再三思考后决定开发国际象棋的人工智能软件，虽然国际象棋的软件已经能够战胜人类世界冠军了，但那是基于搜索的 AI(AI 是人工智能的...
2018-12-22 22:09:29
814
1
原创 基因锁
基因锁时间限制: 1 Sec 内存限制: 128 MB题目描述小Ｘ终于意识到需要花大力气减重了，他询问了若干个减重专家后决定采用最适合年轻人的运动减重方案，考虑再三，小Ｘ最终选择了打羽毛球的方式，一个原因是小Ｘ的小伙伴大都喜欢打羽毛球，其次是打羽毛球要抬头，对活动颈椎有好处，刚好可以缓冲编程久了对颈椎的压迫。经过一个月的努力，小Ｘ的国际象棋 AI 在机器学习的环境中进步神速，已经能...
2018-12-22 22:04:11
3264
原创 常州买衣服（优先队列）
常州买衣服时间限制: 1 Sec 内存限制: 128 MB题目描述不知道是拔河训练的作用还是那个梦的缘故，反正小Ｘ是一天天瘦下来了，虽然还没有中天学长那么帅，但比起 Q 老师已经瘦了很多，小Ｘ原先买的衣服都嫌大了，于是他想去买些新衣服，小Ｘ的衣服原先一直是在非主流服装店买的，他的衣服一般店里是买不到的，而去非主流服装店肯定能买到，如膝盖上挖了两个洞的牛仔裤，正常人穿了像雨衣的冲锋衣等...
2018-12-22 21:56:59
619
原创 Block（暂时只想到暴力算法）
Block时间限制: 1 Sec 内存限制: 128 MB题目描述Alice得到了一张由n×m个黑白像素点组成的图片，她想要压缩这张图片。压缩图片的过程如下：1.首先，选择一个正整数k(k>1)，将图片划分成若干个k×k的小块。如果n,m不能被k整除，用白色像素点在图片的右边或下面补全，使补全成n,m都能被k整除。2.由于压缩时每个k×k的小块必须颜色一致(即全黑或者全白)...
2018-12-22 21:52:39
626
原创 Ring
Ring时间限制: 1 Sec 内存限制: 128 MB题目描述一个n×n的矩阵，可以分成一些环(如图a中，n=5，可以划分成3个环)，每个环上的数字都可以沿着环顺时针或者逆时针转动，每次转动只能将任意一个环顺时针或者逆时针转动一格。初始状态如图a，将矩阵从左到右、从上到下依次用1到n×n填满。现在给你一个局面，请问至少通过多少次环的转动能使矩阵恢复到初始状态？例如，图b的局面可以...
2018-12-22 21:48:17
370
原创 StringII（求两个人操作后得到一个串）
StringII时间限制: 1 Sec 内存限制: 128 MB题目描述老师给Alice和Bob出了个题，要他们把一个字符串S变成字符串T。为了增加难度，老师要求Alice只能交换字符串中任意字符的位置，Bob只能删除字符串中任意字符。你能告诉Alice和Bob，他们要怎样合作才能解决老师的问题吗？ 输入输入的第一行为一个正整数n(n≤10)，表示老师的提问次数。...
2018-12-22 21:43:19
442
原创 区域划分问题（数学题）
区域划分问题时间限制: 1 Sec 内存限制: 64 MB题目描述已知黑暗军团的魔法炮发射轨迹成直线，现有n座魔法炮产生n(n≤500)条直线将地面（可视为平面，因为魔法炮具有降维属性，即可将三维空间降为二维空间）分割成了许多区域，并且已有p（p≥2）条直线相交于同一点，问n条直线最多能将平面分割成多少个不同的区域？ 输入输入一个数n和p。 输出输出分割的区域...
2018-12-19 20:06:36
1225
原创 兔子与兔子（BKDRhash）
兔子与兔子时间限制: 1 Sec 内存限制: 128 MB题目描述很久很久以前，森林里住着一群兔子。有一天，兔子们想要研究自己的 DNA 序列。我们首先选取一个好长好长的 DNA 序列（小兔子是外星生物，DNA 序列可能包含 26 个小写英文字母），然后我们每次选择两个区间，询问如果用两个区间里的 DNA 序列分别生产出来两只兔子，这两个兔子是否一模一样。注意两个兔子一模一样只可能是...
2018-12-19 18:55:18
1274
原创 The XOR Largest Pair（tire树）
The XOR Largest Pair时间限制: 1 Sec 内存限制: 128 MB题目描述在给定的N个整数A1，A2……AN中选出两个进行xor运算，得到的结果最大是多少？ 输入第一行一个整数N，第二行N个整数A1～AN。 输出一个整数表示答案。 样例输入复制样例数据31 2 3样例输出3 提示对于100%的...
2018-12-19 18:49:25
240
原创 偶数３的个数（递推式）
偶数３的个数时间限制: 1 Sec 内存限制: 64 MB题目描述“报告，我军已探出地雷阵中所有的地雷位置，并且还发现了一份使用说明书。”一个黑暗军团的小兵匆忙跑来，交给修罗王一张纸。只见这张纸上面写道：“我是一颗萌萌的地雷，拆除我很容易，看到我身上标着的整数Ｎ了吗？你只要输入这个Ｎ位数中有多少个数中有偶数个数字3就可以把我拆除哦，加油！你行的。” 输入一个整数Ｎ。...
2018-12-19 18:42:54
2209
原创 分割绳子（二分）
分割绳子时间限制: 1 Sec 内存限制: 128 MB题目描述现有N条绳子，它们的长度分别为L1，L2，„„，Ln，如果从它们中切割出K条长度相同的绳子，这K条绳子每条最长能有多长？ 输入共有两行，第一行包含两个正整数N和K，用一个空格分隔；第二行包含N个数，依次表示N条绳子的长度，两数间用一个空格分隔。每条绳子长度的小数不超过两位。（1<=N<=1000，...
2018-12-17 20:20:29
2767
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人