- 博客(33)
- 收藏
- 关注
RSS订阅原创 【普及+/提高】洛谷P2613 【模板】有理数取余——快读+快速幂
对于所有数据，保证 0≤a≤1010001，1≤b≤1010001，且 a,b 不同时是 19260817 的倍数。给出一个有理数 c=ba，求 cmod19260817 的值。这个值被定义为 bx≡a(mod19260817) 的解。一个整数，代表求余后的结果。由于此题数据超大，所以需要写一个快读函数。第一行，一个整数 a。第二行，一个整数 b。
2025-05-23 18:51:14
63
原创 洛谷P1928 外星密码——字符串/字符
解开密码的第一道工序就是解压缩密码，外星人对于连续的若干个相同的子串 X 会压缩为 [DX] 的形式（D 是一个整数且 1≤D≤99），比如说字符串 CBCBCBCB 就压缩为 [4CB] 或者[2[2CB]]，类似于后面这种压缩之后再压缩的称为二重压缩。如果是 [2[2[2CB]]] 则是三重的。对于 100% 的数据：解压后的字符串长度在 20000 以内，最多只有十重压缩。对于 50% 的数据：解压后的字符串长度在 1000 以内，最多只有三重压缩。输入一行，一个字符串，表示外星人发送的密码。
2025-05-23 17:51:08
412
原创 洛谷P1226 【模板】快速幂
对于 100% 的数据，保证 0≤a,b<231，a+b>0，2≤p<231。，其中 a,b,p 分别为题目给定的值， s 为运算结果。给你三个整数 a,b,p，求 abmodp。输入只有一行三个整数，分别代表 a,b,p。一道模版题，注意开longlong。
2025-05-21 18:55:50
435
原创 洛谷B3840 [GESP202306 二级] 找素数
一个大于 1 的正整数，除了 1 和它自身两个因数，没有其他因数，这样的数叫做素数（也叫质数）所以我们在函数里写一个for循环看它有没有其他因数。
2025-05-21 18:50:38
370
原创 洛谷P1093 [NOIP 2007 普及组] 奖学金
先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。赛场上一般都不手打排序的（C++），一般使用sort，但是sort对结构体的排序就比较麻烦了，需要自己编写一个函数cmp作为sort的第三个参数，之后就可以用sort直接排序。任务：先根据输入的 3 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。NOIP2007 普及组 T1。一道很好的结构体训练题。
2025-05-20 13:40:17
361
原创 AcWing 223. 阿九大战朱最学——扩展欧几里得算法
自从朱最学搞定了 QQ 农场以后，就开始捉摸去 QQ 牧场干些事业，不仅在自己的牧场养牛，还到阿九的牧场放牛！阿九很生气，有一次朱最学想知道阿九牧场奶牛的数量，于是阿九想狠狠耍朱最学一把。举个例子，假如有 1616 头奶牛，如果建了 33 个牛棚，剩下 11 头牛就没有地方安家了。如果建造了 55 个牛棚，但是仍然有 11 头牛没有地方去，然后如果建造了 77 个牛棚，还有 22 头没有地方去。你作为阿九的私人秘书理所当然要将准确的奶牛数报给阿九，你该怎么办？
2025-05-19 21:02:37
382
原创 洛谷P1516 青蛙的约会——扩展欧几里得算法
为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。我们把这两只青蛙分别叫做青蛙 A 和青蛙 B，并且规定纬度线上东经 0 度处为原点，由东往西为正方向，单位长度 1 米，这样我们就得到了一条首尾相接的数轴。设青蛙 A 的出发点坐标是 x，青蛙 B 的出发点坐标是 y。青蛙 A 一次能跳 m 米，青蛙 B 一次能跳 n 米，两只青蛙跳一次所花费的时间相同。对于 100% 的数据，1≤x=y≤2×109，1≤m,n≤2×109，1≤L≤2.1×109。
2025-05-17 10:22:00
400
1
原创 洛谷P1082 [NOIP 2012 提高组] 同余方程——线性同余方程
此题其实就是求ax=1+by,可以转换成ax+by=1的最小正整数解，而我们要求x的最小正整数解，就要套一个公式，Xmin=(x0 mod T+T) mod T,其中T=b/gcd(a,b)。设a,b为整，m为正整数，则把a和b模m同余记为a≡b(mod m),这个算式相当于a=b+my,其中y∈Z。求关于 x 的同余方程 ax≡1(modb) 的最小正整数解。一个整数 x0，即最小正整数解。输入数据保证一定有解。一行，包含两个整数 a,b，用一个空格隔开。
2025-05-17 09:22:26
533
原创 洛谷P1007 独木桥
你希望找些刺激，于是命令你的士兵们到前方的一座独木桥上欣赏风景，而你留在桥下欣赏士兵们。独木桥的长度为 L，士兵们只能呆在坐标为整数的地方。所有士兵的速度都为 1，但一个士兵某一时刻来到了坐标为 0 或 L+1 的位置，他就离开了独木桥。另外，总部也在安排阻拦敌人的进攻，因此你还需要知道你的部队最多需要多少时间才能全部撤离独木桥。但是，如果两个士兵面对面相遇，他们无法彼此通过对方，于是就分别转身，继续行走。对于 100% 的数据，满足初始时，没有两个士兵同在一个坐标，1≤L≤5×10的3次方。
2025-05-12 14:05:50
439
原创 ACWing 01背包问题——动态规划
有 N� 件物品和一个容量是 V� 的背包。每件物品只能使用一次。第 i� 件物品的体积是 vi��，价值是 wi��。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
2025-05-10 11:25:22
189
原创 洛谷P1048 [NOIP 2005 普及组] 采药——0-1背包问题——动态规划
医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。第一行有 2 个整数 T（1≤T≤1000）和 M（1≤M≤100），用一个空格隔开，T 代表总共能够用来采药的时间，M 代表山洞里的草药的数目。接下来的 M 行每行包括两个在 1 到 100 之间（包括 1 和 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。输出在规定的时间内可以采到的草药的最大总价值。
2025-05-10 11:21:50
353
原创 洛谷P8611 [蓝桥杯 2014 省 AB] 蚂蚁感冒
接着的一行是 n 个用空格分开的整数 Xi(−100<Xi<100)，Xi 的绝对值，表示蚂蚁离开杆子左边端点的距离。正值表示头朝右，负值表示头朝左，数据中不会出现 0 值，也不会出现两只蚂蚁占用同一位置。两只蚂蚁碰面掉头，可以看作是一只蚂蚁穿过了另一只蚂蚁。因为，碰面之后两只蚂蚁都感冒了，掉不掉头其实无所谓，毕竟都感冒了。这些蚂蚁中，有 1 只蚂蚁感冒了。并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。它们的头有的朝左，有的朝右。请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。
2025-05-10 10:55:29
284
原创 AcWing 848：有向图的拓扑序列——链式前向星/邻接表+拓扑排序
若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。第一行包含两个整数 n 和 m。链式前向星+拓扑排序。
2025-05-09 17:58:59
362
原创 洛谷B2105 矩阵乘法
计算两个矩阵的乘法。n×m 阶的矩阵 A 乘以 m×k 阶的矩阵 B 得到的矩阵 C 是 n×k 阶的，且 C[i][j]=A[i][0]×B[0][j]+A[i][1]×B[1][j]+ ……+A[i][m−1]×B[m−1][j](C[i][j] 表示 C 矩阵中第 i 行第 j 列元素）矩阵乘法中第一个矩阵的列要等于第二个矩阵的行,一个 n×m 的 A 矩阵，和一个 m×k 的 B 矩阵相乘，将得到一个 n×k 的矩阵 C。输出矩阵 C，一共 n 行，每行 k 个整数，整数之间以一个空格分开。
2025-05-09 13:01:12
282
原创 AcWing 3704:排队——拓扑排序+优先队列+邻接表
在安排每个人的顺序时，有 M 个要求，每个要求包含两个整数 a,b，表示小朋友 a 要排在小朋友 b 的前面。（4）若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在环，否则输出的顶点序列就是一个拓扑序列。● 当符合条件的排队顺序不唯一时，编号更小的小朋友尽量更靠前 → 优先队列。（1）从有向图中选择一个无前驱（即入度为0）的顶点并且输出它。当符合条件的排队顺序不唯一时，编号更小的小朋友尽量更靠前。按排好队列从前到后的顺序在一行内输出每个小朋友的编号。（3）重复上述两步，直至不存在无前驱的顶点。
2025-05-08 13:20:49
679
原创 洛谷P1119 灾后重建（普及+/提高）——Floyd算法
如果无法找到从 x 村庄到 y 村庄的路径，经过若干个已重建完成的村庄，或者村庄 x 或村庄 y 在第 t 天仍未重建完成，则需要输出 −1。如果在第 t 天无法找到从 x 村庄到 y 村庄的路径，经过若干个已重建完成的村庄，或者村庄 x 或村庄 y 在第 t 天仍未修复完成，则输出 −1。接下来 M 行，每行 3 个非负整数 i,j,w，w 不超过 10000，表示了有一条连接村庄 i 与村庄 j 的道路，长度为 w，保证 i=j，且对于任意一对村庄只会存在一条道路。
2025-04-28 20:10:13
1138
原创 洛谷P2437 蜜蜂路线——高精度加法+斐波那契数列
一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你：蜜蜂从蜂房 m 开始爬到蜂房 n，m<n，有多少种爬行路线？（备注：题面有误，右上角应为 n−1）要求到n的方式就是求到n-1的方式和到n-2的方式，跟斐波那契数列的原理一模一样，对于100%的数据，1≤M,N≤1000。
2025-04-28 19:52:55
271
原创 洛谷B2064 斐波那契数列
第 1 行是测试数据的组数 n，后面跟着 n 行输入。每组测试数据占 1 行，包括一个正整数 a（1≤a≤30）。斐波那契数列是指这样的数列：数列的第一个和第二个数都为 1，接下来每个数都等于前面 2 个数之和。输出有 n 行，每行输出对应一个输入。输出应是一个正整数，为斐波那契数列中第 a 个数的大小。这是一道经典题，利用斐波那契数列的原理f[i]=f[i-1]+f[i-2]就可以写出此题。给出一个正整数 a，要求斐波那契数列中第 a 个数是多少。
2025-04-26 09:30:10
308
原创 洛谷B3923 [GESP202312 二级] 小杨做题——斐波那契数列
在本题中，我们需要先定义一个数组f，f[1]与f[2]代表a,b,此后需要写一个for循环，int i=3,然后for循环里就是f[i]=f[i-1]+f[i-2]了，最后加一个if(f[i]>=m) break就行了。小杨前 5 天分别做了 1,1,2,3,5 题，由于第 5 天小杨做了 5 题，而 m=5，于是小杨从此以后不再做题。因此小杨总共做了 1+1+2+3+5=12 题。小杨第一天做 1 题，第二天做 2 题，第三天做 1+2=3 题，第四天做 2+3=5 题，第五天做 3+5=8 题。
2025-04-25 13:47:03
267
原创 洛谷U81206 【模板】链式前向星
若flag=1则m行，flag=0则m*2行，每行三个数，即该点的编号、所指向点的编号，边的长度，先按第一个数升序排列，再以链式前向星中的顺序输出即可。（其实就是i从1到n，再按顺序查找边输出即可） 特殊的，若该点无出边，单独一个空行。链式前向星模板题，读入n个点，m条边，以及flag，若flag==1则图有向，否则无向。第一行三个数n,m,flag，题意如上所示 第2~1+m行，每行三个数，x,y,z，代表从x到y有一条长为z的边。对于100%的数据，m<=4000000;是一道模版题，非常的水；
2025-04-23 18:19:09
445
原创 洛谷B4238 [海淀区小学组 2025] 分数方程
如果能够找到一组符合题目要求的三个数，则输出一行，包含三个整数 x,y,z，两两之间用空格分隔，否则输出 −1。本题可能有多组解，输出任意一组均被视作正确（请注意：洛谷的在线 IDE 模式无法判断多组可能解，可能会误判答案错误）。给定一个正整数 n，请找出一组互不相等的正整数 x,y,z，使得 1/x+1/y+1/z=2/n成立。2025 年海淀区中小学生信息学竞赛小学组复赛题目，数据为洛谷自造。其实这道题很水(虽然me想了快1个半小时）这道题仅仅考察我们的数学能力。当n=1时，此题无解。
2025-04-22 19:46:23
338
原创 洛谷P1044 [NOIP 2003 普及组] 栈——栈
宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。宁宁考虑的是这样一个问题：一个操作数序列，1,2,…,n（图示为 1 到 3 的情况），栈 A 的深度大于 n。你的程序将对给定的 n，计算并输出由操作数序列 1,2,…栈有两种最重要的操作，即 pop（从栈顶弹出一个元素）和 push（将一个元素进栈）。栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由。
2025-04-19 09:33:24
293
原创 洛谷P1090 [NOIP 2004 提高组] 合并果子
例如有 3 种果子，数目依次为 1 ， 2 ， 9。可以先将 1 、 2 堆合并，新堆数目为 3 ，耗费体力为 3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12 ，耗费体力为 12。假定每个果子重量都为 1 ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。
2025-04-16 20:15:35
327
原创 AcWing 836——并查集
对于每个询问指令 Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则输出 Yes，否则输出 No。1. M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。2. Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。一道经典的题，直接上代码，不过代码有亿点点长。
2025-04-11 18:09:36
101
原创 周测（1）——排队接水——AcWing913
推而广之，可得：当第 i（i≥1） 个人接水时，后面一共有 n - i 人等待，可得第 i 人接水时其他人的等待时间为第 i 人的接水时间乘以 n - i。据前文证明，可知若将 n 个人的打水时间从小到大排序，可使总的等待时间最短。有 n 个人排队到 1 个水龙头处打水，第 i 个人装满水桶所需的时间是 ti，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？设 a 和 b 是任意选取的两个人的打水时间，且 a<b。（1）a 先于 b 打水，那么有总的等待时间：t1=x。第一行包含整数 n。
2025-04-10 20:16:31
279
原创 洛谷B3635 硬币问题——动态规划
此题如果使用贪心，则不会通过全部样例，因为此题不是典型面值，所以此题可以用动态规划。今有面值为 1、5、11 元的硬币各无限枚。想要凑出 n 元，问需要的最少硬币数量。仅一行，一个正整数，表示需要的硬币个数。仅一行，一个正整数 n。
2025-04-10 19:35:23
328
原创 洛谷B2143 进制转换———栈
用递归算法将一个十进制整数 X（1≤X≤109）转换成任意进制数 M（2≤M≤16，M 为整数）。一行两个数，第一个十进制整数 X，第二个为进制 M。这道题可以利用进制转换的原理 ，用栈来解，代码见下。
2025-04-02 17:04:59
226
原创 洛谷B2124 判断字符串是否为回文———栈
输入一个字符串，输出该字符串是否回文。回文是指顺读和倒读都一样的字符串。这道题可以通过建一个栈，通过栈来解决。输入一行字符串，长度小于 100。如果字符串是回文，输出。
2025-04-02 16:53:20
267
原创 洛谷P1177 【模板】排序——sort函数
第二行包含 N 个空格隔开的正整数 ai，为你需要进行排序的数。将给定的 N 个数从小到大输出，数之间空格隔开，行末换行且无空格。此题仅用sort函数就可以通过，代码见下。将读入的 N 个数从小到大排序后输出。第一行为一个正整数 N。
2025-03-30 15:06:27
153
原创 洛谷P1176 路径计数2——动态规划
表示坐标 (x,y) 上有障碍不能通过，且有 1≤x,y≤n，且 x,y 至少有一个大于 1，并请注意障碍坐标有可能相同。一个 N×N 的网格，你一开始在 (1,1)，即左上角。每次只能移动到下方相邻的格子或者右方相邻的格子，问到达 (N,N)，即右下角有多少种方法。但是这个问题太简单了，所以现在有 M 个格子上有障碍，即不能走到这 M 个格子上。输入文件第 1 行包含两个非负整数 N,M，表示了网格的边长与障碍数。本人的一篇博客到此结束。
2025-03-30 14:57:55
175
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人