- 博客(69)
- 收藏
- 关注
RSS订阅原创 【题解】[SDOI2010]古代猪文
【题目描述】猪王国的文明源远流长，博大精深。iPigiPigiPig 在大肥猪学校图书馆中查阅资料，得知远古时期猪文文字总个数为 nnn。当然，一种语言如果字数很多，字典也相应会很大。当时的猪王国国王考虑到如果修一本字典，规模有可能远远超过康熙字典，花费的猪力、物力将难以估量。故考虑再三没有进行这一项劳猪伤财之举。当然，猪王国的文字后来随着历史变迁逐渐进行了简化，去掉了一些不常用的字。iPigiPigiPig 打算研究古时某个朝代的猪文文字。根据相关文献记载，那个朝代流传的猪文文字恰好为远古时期的
2020-10-07 19:13:36
505
1
原创 【题解】Rainbow的信号（位运算+概率期望）
Rainbow的信号1s,128 MB1s,128\ MB1s,128 MB【题目描述】FredaFredaFreda 发明了传呼机之后，rainbowrainbowrainbow 进一步改进了传呼机发送信息所使用的信号。由于现在是数字、信息时代，rainbowrainbowrainbow 发明的信号用 NNN 个自然数表示。为了避免两个人的对话被 大坏蛋 VariantFVariantFVariantF 偷听，rainbowrainbowrainbow 把对话分成 A、B、CA
2020-07-27 16:57:10
852
原创 【题解】绿豆蛙的归宿
绿豆蛙的归宿【题目描述】给出一个有向无环的连通图，起点为 111 终点为 NNN ，每条边都有一个长度。绿豆蛙从起点出发，走向终点。数据保证从起点出发能够达到图中所有点，图中所有点都能够到底终点。到达每一个顶点时，如果有 KKK 条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1K\frac 1 KK1 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？【输入】第一行: 两个整数 N,MN, MN,M ，代表图中有 NNN 个点、MMM 条边。
2020-07-26 17:57:46
874
原创 【题解】「JSOI 2011」分特产
「JSOI 2011」分特产【题目描述】JYYJYYJYY 带队参加了若干场 ACM/ICPC\text{ACM/ICPC}ACM/ICPC 比赛，带回了许多土特产，要分给实验室的同学们。JYYJYYJYY 想知道，把这些特产分给 nnn 个同学，一共有多少种不同的分法？当然，JYYJYYJYY 不希望任何一个同学因为没有拿到特产而感到失落，所以每个同学都必须至少分得一个特产。例如，JYYJYYJYY 带来了 222 袋麻花和 111 袋包子，分给 AAA 和 BBB 两位同学，那么共有 444 种
2020-07-25 20:30:52
314
原创 【题解】day2
A：蓝蓝的棋盘时间限制：1s1s1s 空间限制：128MB128 MB128MB【题目描述】AAA淘淘和蓝蓝在下棋.这个棋盘是 1×n1\times n1×n 的,棋盘的第 iii 个格子上有一个数 a[i]a[i]a[i] ,因此我们可以把棋盘看做一个序列.一开始棋子在位置 000 ,双方得分都是 000 .双方轮流操作棋子,如果当前棋子的位置是 ppp ,可以选择把棋子移动到[p+1,min(n,p+m)][p+1,min(n,p+m)][p+1,min(n,
2020-07-21 11:35:46
684
原创 【题解】day1
A：doughnut来源：CF407B Long PathCF407B\ Long\ PathCF407B Long Path时间限制：2s2s2s 空间限制：256MB256 MB256MB【题目描述】AAA 有很多甜甜圈。有一天，她在地上画了 n+1n+1n+1 个格子，她想从第 111 个格子跳到第 n+1n+1n+1 个格子。规则是，AAA 每到一个格子，都会放一个甜甜圈在里面。在第 iii 个格子时，如果当前甜
2020-07-21 10:58:04
557
原创 【题解】「BZOJ2982」combination（Lucas定理求组合数）
【题目描述】LMZ有n个不同的基友，他每天晚上要选m个进行[河蟹]，而且要求每天晚上的选择都不一样。那么LMZ能够持续多少个这样的夜晚呢？当然，LMZ的一年有100071000710007 天，所以他想知道答案mod 10007mod \ 10007mod 10007的值。(1<=m<=n<=200,000,000)(1<=m<=n<=200,000,000)(1<=m<=n<=200,000,000)【输入】第一行一个整数 t
2020-07-16 21:43:51
563
1
原创 【详解】欧拉函数
互质与欧拉函数互质任意自然数 a,ba,ba,b，若 gcd(a,b)=1gcd(a,b)=1gcd(a,b)=1，则称 a,ba,ba,b 互质。对于三个数或更多个数，将 gcd(a,b,c)=1gcd(a,b,c)=1gcd(a,b,c)=1 的情况称为 a,b,ca,b,ca,b,c 互质。把 gcd(a,b)=gcd(b,c)=gcd(a,c)=1gcd(a,b)=gcd(b,c)=gcd(a,c)=1gcd(a,b)=gcd(b,c)=gcd(a,c)=1 称为两两互质，两者有明显的区别，显
2020-07-14 09:54:15
438
原创 【详解】同余问题
同余问题1. 同余定义给定整数 mmm ，若两个整数 a，ba，ba，b 除以 mmm 所得余数相同，称 aaa 和 bbb 对模 mmm 同余，表示为：a≡b( mod m)a ≡ b(\ mod \ m)a≡b( mod m)。若一个整数集合中所有数模 mmm 的余数相同，这个集合中的数都称为模 mmm 的同余类。每个同余类中的任意两个整数对模 mmm 同余。定理 111 ： a≡b( mod m)a ≡ b(\ mod \ m)a≡b
2020-07-13 17:49:11
2698
2
原创 【详解】二叉查找树BST与平衡树Treap
二叉查找树BST与平衡树Treap一、二叉查找树1.概念二叉查找树（简称BST），是满足以下条件的二叉树：树上每一个节点都有一个权值；树上任意一个节点x，若左子树不为空，则左子树上所有节点权值均小于x的权值；树上任意一个节点x，若右子树不为空，则左子树上所有节点权值均大于x的权值；2.二叉查找树的操作二叉查找树的建立struct BST{ int l,r; int val;}s[SIZE];二叉查找树的查找二叉查找树的插入二叉查找树找最值二叉查找树的
2020-05-26 15:36:07
784
原创 【题目】[USACO2015FEB」Censoring (Gold金组)（AC自动机）
题面FJ把杂志上所有的文章摘抄了下来并把它变成了一个长度不超过10^5的字符串S。他有一个包含n个单词的列表，列表里的n个单词记为t_1…t_N。他希望从S中删除这些单词。FJ每次在S中找到最早出现的列表中的单词(最早出现指该单词的开始位置最小)，然后从S中删除这个单词。他重复这个操作直到S中没有列表里的单词为止。注意删除一个单词后可能会导致S中出现另一个列表中的单词FJ注意到列表中的单词不会出现一个单词是另一个单词子串的情况，这意味着每个列表中的单词在S中出现的开始位置是互不相同的请帮助FJ完成这
2020-05-23 12:17:23
552
原创 【题解】「USACO2015FEB」Censoring (Silver银组)（KMP）
题面【题目描述】FarmerJohnFarmer JohnFarmerJohn为他的奶牛们订阅了GoodHooveskeepingGood HooveskeepingGoodHooveskeeping杂志，因此他们在谷仓等待挤奶期间，可以有足够的文章可供阅读。不幸的是，最新一期的文章包含一篇关于如何烹制完美牛排的不恰当的文章，FJFJFJ不愿让他的奶牛们看到这些内容。FJFJFJ已经根据杂志的所有文字，创建了一个字符串 $S $( SSS 的长度保证不超过 10610^6106 )，他想删除其中的子串
2020-05-23 08:31:07
571
原创 【题解】「JSOI2012」玄武密码（AC自动机）
题面【题目描述】在美丽的玄武湖畔，鸡鸣寺边，鸡笼山前，有一块富饶而秀美的土地，人们唤作进香河。相传一日，一缕紫气从天而至，只一瞬间便消失在了进香河中。老人们说，这是玄武神灵将天书藏匿在此。很多年后，人们终于在进香河地区发现了带有玄武密码的文字。更加神奇的是，这份带有玄武密码的文字，与玄武湖南岸台城的结构有微妙的关联。于是，漫长的破译工作开始了。经过分析，我们可以用东南西北四个方向来描述台城城砖的摆放，不妨用一个长度为 NNN 的序列来描述，序列中的元素分别是 E，S，W，NE，S，W，NE，S，W，
2020-05-20 19:10:25
637
原创 【题解】Keywords Search（AC自动机）
题面【题目描述】给定n个长度不超过50的小写字母组成的单词，以及一篇长为m的文章，问有多少个单词在文章出现。输入第一行一个整数T，表示测试数据组数。对于每组测试数据，每一行一个整数n，接下去n行n个单词，最后一行输入一个字符串，表示文章。【输出】对于每组测试数据，输出一个数，表示有多少个单词在文章中出现。【样例输入】15shehesayshrheryasherhs【样例输出】3提示n<=104,m<=106n<=10^4,m<=10^6n&
2020-05-16 13:56:13
657
原创 【题解】前缀（字典树）
题面时间限制：3s，空间限制：512MB【题目描述】给你一个字符串集合，请从中找出一些字符串，使得找出来的这些字符串的最长公共前缀与这些字符串数的总个数的乘积最大化，并输出这个最大值【输入】输入文件第一行给出字符串个数n(1≤n≤1000000）n(1≤n≤1000000）n(1≤n≤1000000），下面n行描述这n个字符串，每个字符串长度不超过200002000020000；输入文件在10MB10MB10MB以内。【输出】输出文件一行一个数，代表最大化的结果【样例输入】7Jora d
2020-05-13 19:22:43
324
原创 【题解】The XOR Largest Pair（Trie字典树）
题面【题目描述】在给定的NNN个整数A1，A2……AnA_1，A_2……A_nA1，A2……An中选出两个进行XORXORXOR运算，得到的结果最大是多少？【输入】第一行一个整数NNN，第二行NNN个整数A1～ANA_1～A_NA1～AN。【输出】一个整数表示答案。【样例输入】31 2 3【样例输出】3【数据范围】对于100%100\%100%的数据:N<=105,0<=Ai<231N<=10^5, 0<=A_i<2^{31}N&l
2020-05-10 15:43:17
876
1
原创 【题解】「NOI2014」动物园（KMP）
题面【题目描述】近日，园长发现动物园中好吃难做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。某天，园长给动物们讲解KMPKMPKMP算法。园长：“对于一个字符串SSS，它的长度为LLL。我们可以在O(L)O(L)O(L)的时间内，求出一个名为nextnextnext的数组。有谁预习了n...
2020-05-05 14:32:53
545
原创 【题解】「POI2010」Beads（哈希）
题面【题目描述】ZxlZxlZxl有一次决定制造一条项链，她以非常便宜的价格买了一长条鲜艳的珊瑚珠子，她现在也有一个机器，能把这条珠子切成很多块（子串），每块有k（k>0）k（k>0）k（k>0）个珠子，如果这条珠子的长度不是k的倍数，最后一块小于k的就不要拉（nc真浪费），保证珠子的长度为正整数。ZxlZxlZxl喜欢多样的项链，为她应该怎样选择数字k来尽可能得到更多的不同...
2020-04-17 18:07:26
516
原创 【题解】「POJ2002」Squares（哈希表）
题面【题目描述】给出平面上一些点的坐标，统计由这些点可以组成多少个正方形。注意：正方形的边不一定平行于坐标轴。【输入】输入包括多组测试数据。每组的第一行是一个整数n (1 <= n <= 1000)，表示平面上点的数目，接下来n行，每行包括两个整数，分别给出一个点在平面上的x坐标和y坐标。输入保证：平面上点的位置是两两不同的，而且坐标的绝对值都不大于50000。最后一组输入数据...
2020-04-17 15:27:14
644
原创 【题解】求后序遍历（二叉树遍历，递归）
题面【题目描述】给出二叉树的先序遍历和中序遍历，求后序遍历。【输入】输入共两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。树的结点一律用小写字母表示。字符串长度小于100100100。【输出】输出仅一行，表示树的后序遍历序列。【样例输入】abdecdbeac【样例输出】debca算法分析二叉树有三种遍历方法：先序遍历：（1）访问根节点；...
2020-04-15 17:39:45
2892
1
原创 【题解】USACO 2020 OPEN Sliver(银组)
Social Distancing题面题目描述由于高传染性的牛传染病 COWVID-19 的爆发，Farmer John 非常担忧他的奶牛们的健康。为了限制疾病的传播，Farmer John 的 N 头奶牛（2≤N≤105）（2≤N≤10^5）（2≤N≤105）决定践行“社交距离”，分散到农场的各处。农场的形状如一维数轴，上有 M 个互不相交的区间（1≤M≤105）（1≤M≤10^5）（1...
2020-04-12 13:36:28
2493
1
原创 【题解】【bzoj 3555】[Ctsc2014]企鹅QQ（字符串Hash）
题面【题目描述】PenguinQQ是中国最大、最具影响力的SNS（Social Networking Services）网站，以实名制为基础，为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验，满足用户对社交、资讯、娱乐、交易等多方面的需求。小Q是PenguinQQ网站的管理员，他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析，小Q发现同一个人注册的账...
2020-04-06 14:19:54
335
原创 【题解】图书管理（哈希表）
题面【题目描述】图书管理是一件十分繁杂的工作，图书馆每天都会有许多新书缴入，为了更方便管理图书（以便于帮助想要结束的客人快速查找是否有他们所需要的书），我们需要设计一个图书朝着系统，该系统需要支持两种操作：1）add(s)，表示新加入一本书名为s的图书；2）find（s)，表示查询是否存在一本书名为s的图书；【输入】第一行包括一个正整数n（n≤30000），表示操作数。以下n行，每行...
2020-04-06 14:03:51
1295
原创 【题解】「BZOJ3916」friends（字符串Hash）
题面【题目描述】有三个好朋友喜欢在一起玩游戏,A君写下一个字符串S,B君将其复制一遍得到T,C君在T的任意位置(包括首尾)插入一个字符得到U.现在你得到了U,请你找出S.【输入】第一行一个数N,表示U的长度.第二行一个字符串U,保证U由大写字母组成【输出】输出一行,若S不存在,输出"NOT POSSIBLE".若S不唯一,输出"NOT UNIQUE".否则输出S.【样例输入】7...
2020-04-06 13:10:59
2211
原创 【题解】「POJ3461」Oulipo（字符串Hash）
题面【题目描述】给定两个串S1，S2，只有大写字母，求S1在S2中出现了几次。【输入】输入T组数据，每组数据两个串S1，S2.strlen(S1)<=10^4strlen(S2)<=10^6，【输出】对于每组数据，输出答案。【样例输入】3BAPCBAPCAZAAZAZAZAVERDIAVERDXIVYERDIAN【样例输出】130算法分析...
2020-04-03 17:23:29
444
原创 树状数组模板程序
#include<iostream>#include<cstring>#include<cstdio> #include<vector>#define N 500100using namespace std;int n,m,c[N];int lowbit(int x){ return x&(-x);}void up...
2020-03-27 17:38:22
139
原创 【题解】「USACO 2007 Jan」Balanced Lineup（ST表）
题面【题目描述】农夫 JohnJohnJohn 的N(1<=N<=50,000)N(1 <= N <= 50,000)N(1<=N<=50,000)头牛总是按同一序列排队. 有一天,$ John$ 决定让一些牛们玩一场飞盘比赛. 他准备找一群在队列中位置连续的牛来进行比赛. 但是为了避免水平悬殊,牛的身高不应该相差太大. $John 准备了准备了准备了Q (...
2020-03-27 14:56:58
353
原创 【题解】「USACO2004NOV」Apple Catching（DP）
题面【题目描述】很少有人知道奶牛爱吃苹果．农夫约翰的农场上有两棵苹果树（编号为111和222），每一棵树上都长满了苹果．奶牛贝茜无法摘下树上的苹果，所以她只能等待苹果从树上落下．但是，由于苹果掉到地上会摔烂，贝茜必须在半空中接住苹果（没有人爱吃摔烂的苹果）．贝茜吃东西很快，所以她接到苹果后仅用几秒钟就能吃完．每一分钟，两棵苹果树其中的一棵会掉落一个苹果．贝茜已经过了足够的训练，只要站在树下就一...
2020-03-23 19:25:06
390
原创 【题解】「USACO2008MAR」River Crossing（DP）
题面【题目描述】FarmerFarmerFarmer JohnJohnJohn以及他的N(1<=N<=2,500)N(1 <= N <= 2,500)N(1<=N<=2,500)头奶牛打算过一条河，但他们所有的渡河工具，仅仅是一个木筏。由于奶牛不会划船，在整个渡河过程中，FJFJFJ必须始终在木筏上。在这个基础上，木筏上的奶牛数目每增加111，FJFJFJ...
2020-03-23 19:06:37
287
原创 【题解】「NOIP2010」乌龟棋（DP）
题面【题目描述】小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。乌龟棋的棋盘是一行NNN个格子，每个格子上一个分数（非负整数）。棋盘第111格是唯一 的起点，第NNN格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。乌龟棋中M张爬行卡片，分成444种不同的类型（M张卡片中不一定包含所有4种类型 的卡片，见样例），每种类型的卡片上分别标有1、2、3、41、2、3、41、2、3、4四个...
2020-03-23 18:54:43
636
原创 【题解】「NOIP1999 普及组」导弹拦截（DP，最长不下降子序列+贪心）
题面【题目描述】某国为了预防敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够达到任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于300003000030000的正整数，导弹数不超过1000...
2020-03-23 18:16:31
740
原创 【题解】「NOIP2004」合唱队形（DP，最长不下降子序列）
题面【题目描述】NNN位同学站成一排，音乐老师要请其中的(N−K)(N-K)(N−K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K1，2…，K1，2…，K，他们的身高分别为T1，T2，…，TKT_1，T_2，…，T_KT1，T2，…，TK， 则他们的身高满足T1<...<Ti>Ti+1>…...
2020-03-23 18:02:59
1022
原创 【题解】「NOI2015」软件包管理器（述链剖分）
题面【题目描述】【输入】【输出】输出文件包括 qqq行。 输出文件的第iii行输出 111 个整数，为第i 步操作中改变安装状态的软件包数。【样例输入】7 0 0 0 1 1 5 5 install 5 install 6 uninstall 1 install 4 uninstall 0 【样例输出】31323算法分析述链剖分模板题目。题目...
2020-03-23 11:35:13
250
原创 【题解】「HAOI2015」树上操作（述链剖分）
题面【题目描述】有一棵点数为NNN 的树，以点 111为根，且树点有边权。然后有MMM个操作，分为三种：操作 111 ：把某个节点 xxx 的点权增加 aaa 。操作 222 ：把某个节点 xxx 为根的子树中所有点的点权都增加 aaa 。操作 333 ：询问某个节点 xxx 到根的路径中所有点的点权和。【输入】第一行包含两个整数 N,MN, MN,M 。表示点数和操作数。接下来一行...
2020-03-23 09:10:54
242
原创 【题解】「ZJOI2008」树的统计（树链剖分）
题面【题目描述】一棵树上有nnn个节点，编号分别为111到nnn，每个节点都有一个权值www。我们将以下面的形式来要求你对这棵树完成一些操作：I.I.I. CHANGECHANGECHANGE uuu ttt : 把结点uuu的权值改为tttII.II.II. QMAXQMAXQMAX uuu vvv: 询问从点uuu到点vvv的路径上的节点的最大权值III.III.III. QSUMQ...
2020-03-20 15:53:41
379
原创 【题解】「USACO 2008 FEB」Hotel（线段树）
题面【题目描述】奶牛们最近的旅游计划，是到苏必利尔湖畔，享受那里的湖光山色，以及明媚的阳光。作为整个旅游的策划者和负责人，贝茜选择在湖边的一家著名的旅馆住宿。这个巨大的旅馆一共有N(1<=N<=50,000)N (1 <= N <= 50,000)N(1<=N<=50,000)间客房，它们在同一层楼中顺次一字排开，在任何一个房间里，只需要拉开窗帘，就能见到波...
2020-03-06 18:34:31
418
原创 【详解】线段树扫描线
题目「VOJ1056」图形面积桌面上放了NNN个平行于坐标轴的矩形，这NNN个矩形可能有互相覆盖的部分，求它们组成的图形的面积。【输入】有多组测试数据。每组测试数据输入第一行为一个数NNN，表示矩形的数量。下面NNN行，每行四个整数，分别表示每个矩形的左下角和右上角的坐标，坐标范围为–108–10^8–108到10810^8108之间的整数。当N==0N==0N==0时，测试文件结束...
2020-03-06 18:16:46
592
原创 【题解】「AHOI2009」维护序列（线段树）
题面【题目描述】老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为NNN的数列，不妨设为a1,a2,…,aNa_1,a_2,…,a_Na1,a2,…,aN。有如下三种操作形式：(1)(1)(1)把数列中的一段数全部乘一个值;(2)(2)(2)把数列中的一段数全部加一个值;(3)(3)(3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模PPP的值。...
2020-03-03 12:47:30
909
2
原创 【题解】[TJOI 2018] 数学计算（线段树）
题面【题目描述】小豆现在有一个数x，初始值为1. 小豆有Q次操作，操作有两种类型:1 m: x = x * m ，输出 x%mod;2 pos: x = x / 第pos次操作所乘的数（保证第pos次操作一定为类型1，对于每一个类型1 的操作至多会被除一次），输出x%mod【输入】一共有t组输入（t ≤ 5）对于每一组输入，第一行是两个数字Q, mod(Q ≤ 100000, ...
2020-03-02 12:52:46
221
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人