- 博客(114)
- 资源 (3)
- 收藏
- 关注
RSS订阅
原创 浅谈质数与同余
浅谈质数与同余一、质数定义：除了1和本身两个数都不能被整除的自然数叫做质数，否则为合数。0和1既不是质数也不是合数，最小的合数是4，最小的质数是2，是唯一的偶质数，质数有无穷多个质数分布定理：对正实数x，定义P(x)为不大于x的质数个数，则有P(x)=O(x/lnx)由质数定理可以给出第n个质数p(n)的渐进估计：p(n)≈nlnn二、唯一分解定理（算术基本定理）任意大于1的自然数都能被质数的质数幂的乘积表示运用：试除法（质因数分解或求一个数的约数）、质数判定时间复杂度O(sqrt(
2021-05-22 15:17:57
822
1
原创 【ybtoj】逆序对
逆序对题目描述解题思路将a数组离散化Code#include<iostream>#include<cstdio>#include<algorithm>using namespace std;int n, tot;int a[1000100], p[1001000], c[1000100];void lsh(){ for(int i=1; i<=n; i++) p[i]=a[i]; sort(p+1, p+1+n); tot=uni
2022-02-18 18:47:17
200
原创 【ybtoj】重复子串
【ybtoj】重复子串题目描述样例输入abcdaaaaababab.样例输出143解题思路这道题的数据规模很大，直接暴力会超时，find函数也会超时，只能使用KMP算法代码#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;char s[10000005];int len, p[1000
2021-12-25 08:39:31
335
原创 【ybtoj】单源最短路径
【ybtoj】单源最短路径题目描述样例输入4 6 11 2 22 3 22 4 11 3 53 4 31 4 4样例输出0 2 4 3解题思路dij加上堆优化，在随机数据下可以考虑SPFA，但在构造数据下还是用dij比较稳。代码#include<iostream>#include<cstring>#include<cstdio>#include<queue>#define pa pair<int,int>
2021-12-18 09:02:42
165
原创 exgcd模板（扩展欧几里得）
exgcd模板扩展欧几里得模板#define ll long longll exgcd(ll a,ll b,ll &x,ll &y){ if(b==0) { x=1; y=0; return a; } ll d; d=exgcd(b,a%b,y,x); y=y-a/b*x;//返回的值是最大公约数 return d;}谢谢阅读...
2021-08-22 20:53:08
133
1
原创 【牛客练习赛87】k小数查询
【牛客练习赛87】k小数查询题目描述输入样例5 3 21 2 3 4 5输出样例3解题思路由于需要查找的数x是第k小的数，所以总共有k-1个数比它大。我们从当前忘前查找，有f个数比它大，所以它后面就有k-1-f个数比它大，我们将所有的方案书相加即可Code#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int maxn=2010
2021-08-21 11:18:40
137
1
原创 【牛客练习赛87】中位数
中位数题目描述输入样例15 14 3 5 1 2输出样例2解题思路从小到大排序，从n~n-k+1进行合并，然后输出a[(k+n-1)/2]。Code#include<iostream>#include<algorithm>#include<cstdio>#define ll long longusing namespace std;int main(){ ll a[200010]; ll n,k,t; ci
2021-08-21 11:12:35
105
原创 【NOIP2014】提高组初赛答案加解析
NOIP2014提高组初赛答案加解析本蒟蒻第一次写初赛解析，若有错误欢迎大家纠正一、单项选择题1、B汇编语言是面向机器的低级语言，而FORTRAN、Basic是面向过程。2、D1TB=210GB=220MB=230KB=240B1TB=2^{10}GB=2^{20}MB=2^{30}KB=2^{40}B1TB=210GB=220MB=230KB=240B3、D二进制数的运算规则是逢二进一4、B这个东西就只能背了QWQ…5、CIP地址中每个域的取值范围为0~2556、C每一条边都
2021-08-19 21:42:40
856
4
原创 【SSL】20210817A
【SSL】20210817题目描述给出长度为n的字符串S，以及Q个询问每个询问给出一个字符串T，判断T是否为S的一个子序列所有串仅包含小写字母30%：n<=1e4,q<=1e5100%：输入格式第一行给出正整数n,Q第二行给出S接下来Q行，每行给出一个询问T输出格式对于每个询问输出一行表示答案，符合输出YES，不符输出NO输入样例3 1abcac输出样例YES解题思路输入时用f[i,j]表示位置i以后字符j第一次出现的位置然后预处理所有的f[i,
2021-08-17 19:04:15
66
1
原创 【SSL】20210816C
【SSL】20210816C题目描述对于一个正整数N，若x满足，(N-0.5x)/(N-x)为正整数，则x为N的幸运数。给出一个N，求出[1,N-1]所有N的幸运数，先回答个数，在将幸运数从小到大输出。输入格式第一行一个正整数N输出格式第一个整数为cnt，表示有多少个满足的幸运数，后面cnt个数，表示满足的幸运数输入样例 9输出样例 2 6 8解题思路首先我们打个暴力，发现一个规律：我们发现(N-x)一定是N的约数，我们用时间复杂度是n\sqrt nn然后我们把他的每一
2021-08-16 15:24:00
60
1
原创 【SSL】20210816B
【SSL】20210816B题目描述有10个小球，小球的编号从0~9。初始状态按照从左到右编号为0,1,2,3…9的顺序摆在了桌子上，有一个长度大小为n的操作序列。操作序列的每一行表示一次操作都有两个非负整数a,b，表示本次操作将会交换位置a,b的2个小球(下标从0编号)一共有m次询问，每次询问时，将杯子中的小球重置为初始状态。给出[li,ri]，连续从操作li进行到ri，连续操作完后依次回答位置0到9，对应位置的小球编号。鉴于输出量太大，会出事，采用输入输出优化，void rea
2021-08-16 15:16:27
99
原创 【洛谷CF1110E】Magic Stones
【洛谷CF1110E】Magic Stones题目描述多个询问，每个询问给出长度为n的2个序列a，b每次可以对1<i<n的ai进行操作，操作后：问能否通过若干次操作，使得序列a变成 b输入格式给出询问数T第一行一个正整数n第二行给出序列a第三行给出序列b输出格式是否能转变，输出Yes或者No，每个询问对应一行输入样例样例114 7 2 4 127 15 10 12样例2134 4 41 2 3输出样例样例1Yes样例2No解
2021-08-14 16:46:15
81
1
原创 【SSL】20210812-A
【SSL】20210812-A题目描述若数列A存在位置k，满足①i<k,ai<ai+1②i>=k,ai>ai+1则称该数列为单峰数列给出正整数n，求全排列n中存在多少个单峰数列输入格式给出1个正整数n输出格式单峰数列个数（对10^9+7取模）输入样例3输出样例4解题思路首先用一个队列暴力一遍。但是，我们会发现，这些答案有一个规律：ans=2n+1ans=2^{n+1}ans=2n+1然后使用快速幂Code#include<iost
2021-08-13 11:57:25
58
原创 快速幂模板
快速幂模板#include<iostream>#include<csitdio>#include<algorithm>#define ll long longusing namespace std;ll m=100007;ll quick_pow(ll a,ll b) { ll answer=1; while(b>0) { if(b&1) { answer*=a; answer%=m; } a*=a;
2021-08-10 20:06:00
62
原创 快读模板
快读模板因为输入字符的速度比数字快，所以快读采用的字符方式输入数字，再转换回来。int read(){ int m=0,n=1; char ch; ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') n=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { m=m*10+ch-'0'; c
2021-08-10 19:53:15
85
原创 【SSL】20210809A
【SSL】20210809A题目描述定义操作a(X)b= ((a&b) + (a|b))>>1给出n个数ai每次用操作合并任意相邻ai求进行n-1次操作以后可能得到的最终结果所有结果从小到大输出输入格式第一行一个n第二行给出a1,a2,…,an-1,an输出格式按照题目要求作答输入样例41 4 3 2输出样例1 2解题思路枚举区间的起点和终点，然后枚举中间的分界点，判断左右两个小区间能否合成这个数，如果可以，改为true，否则为false。Co
2021-08-09 16:19:48
66
原创 【SSL】20210808D
【SSL】20210808D题目描述有n个人依次排队打饭，有m种饭菜可以选择，每个人可能选择其中一种，如果相邻排队的人打的菜一样，那么就会影响彼此吃饭的心情，求这个队伍中有人被影响心情的状态数，对100003取余。输入格式一行整数依次给出m,n输出格式相应的状态数输入样例2 3输出样例6样例解释样例解释000 001011 100110 1116种解题思路在草稿纸上列出多种方案，找规律，最终得到ans=m^n-m*(m-1) ^ (n-1)要使用快速幂和龟速乘！
2021-08-09 16:13:22
66
原创 【ybtoj】新的开始
【ybtoj】新的开始题目描述发展采矿业当然首先得有矿井，小 F 花了上次探险获得的千分之一的财富请人在岛上挖了n口矿井，但他似乎忘记考虑矿井的供电问题……为了保证电力的供应，小 F 想到了两种办法：在这一口矿井上建立一个发电站，费用为v（发电站的输出功率可以供给任意多个矿井）。将这口矿井与另外的已经有电力供应的矿井之间建立电网，费用为p。小 F 希望你帮他想出一个保证所有矿井电力供应的最小花费。输入格式输出格式输出仅一个整数，表示让所有矿井获得充足电能的最小花费。样例输入4 5
2021-08-08 19:54:21
151
原创 【ybtoj】繁忙都市
繁忙都市题目描述城市 C 是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市 C 的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接地连接起来。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：1．改造的那些道路能够把所有的交叉路口直接或间接地连通起来。2．在满足要求1
2021-08-08 19:36:58
104
原创 【ybtoj】银河英雄传说
【ybtoj】银河英雄传说题目描述解题思路这是带边权的并查集。用并查集维护战舰是否在同一列，以每一列的第一艘战舰作为集合代表，用一个dis数组记录边权。Code#include <iostream>#include <cstdio>#include <cmath>using namespace std;int n, x, y, xx, yy, fa[50010], num[50010], dis[50010];char c;int find(i
2021-08-08 16:08:27
89
原创 【ybtoj】并查集
【模板】并查集题目描述有n个元素，你需要完成集合的合并和判断两个元素是否在同一集合中这两种操作。输入格式第一行包含两个整数n,m,表示共有n个元素和m次操作。接下来m行，每行包含三个整数zi,xi,yiz_i,x_i,y_izi,xi,yi.当zi=1z_i=1zi=1时，讲xix_ixi与yiy_iyi所在的集合合并。当zi=2z_i=2zi=2时，判断xix_ixi与yiy_iyi是否在同一集合内，是的话输出“Y”，否则输出“N”。输出格式对于每一个zi=2z_i=2zi
2021-08-08 15:01:39
148
原创 【NOIP普及】排座椅
【NOIP普及】排座椅题目描述上课的时候总会有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的 D 对同学上课时会交头接耳。同学们在教室中坐成了 M 行 N 列，坐在第 ii 行第 jj 列的同学的位置是(i,j)，为了方便同学们进出，在教室中设置了KK 条横向的通道，L 条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，
2021-07-21 09:44:52
215
原创 【总结】纪中Day7比赛总结
纪中Day7比赛总结今天发挥的有些差。T3的模拟有许多特殊情况没有考虑到，导致只得了T3只得了30分，第二题其实可以直接暴力的，可惜没看出来。最终得分130分。T1思路这道题就是将环形DP转成线性DP，最后变为区间DP，需要用到三维数组。T2思路因为本蒟蒻太菜了，没有听懂，但是kyx巨爷竟然也没有听懂。根据题目我们可以得出下面的式子：ax+by=c。然后我们要求出x和y，再找出最大值和最小值AC做法好像是扩展欧几里得啥的。T3思路这道题直接暴力模拟就能过。首先我们先
2021-07-19 16:32:01
82
原创 【总结】纪中Day6比赛总结
纪中Day6比赛总结今天果然爆掉了。只有130分，排名掉了20多。T1直接眼睛瞎掉，硬生生地把一个01背包打成了暴力，30分。第三题没找着规律，果然我数论就是菜啊。T4还想拿一点部分分，结果一分没拿到。T101背包，差不多是个模板题吧，只是要多判断一下重要度。Code#include#include#include#include#include#include#include#includeusing namespace std;int te[30010],p[30010]
2021-07-17 15:59:35
88
原创 【总结】纪中Day4比赛总结
纪中Day4比赛总结今天比赛差了点，第三题可以拿点部分分的。T1刚开始看还以为是水题，结果发现如果真的完全按照题目所说的来做的话，会超时。我们将A矩阵的每一行压缩的10进制数，但我们发现太大了会炸掉，所以我们18位18位的压缩。同理，我们将B矩阵的每一行压缩，最后A矩阵和B矩阵做与运算，在异或运算，得出结果后马上和C矩阵对比，只要有一个不相同，马上输出NO，退出。#include<iostream>#include<cstring>#include<cstd
2021-07-16 16:43:39
89
2
原创 【总结】纪中Day5比赛总结
纪中Day5比赛总结今天比赛突然蹦进了前十，连我自己都不敢相信（今天考那么好，明天rp必定爆掉 ）T1看到这道题的第一眼，我以为要用DFS来做，又看到有一个最后必须回到道路，觉得有些难度，先去做了T3。回来后，仔细看了一下题目，发现题中有下面这句话：先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生所以,这道题可以用暴力来做。用一个结构体保存植株的花生个数和它的坐标，然后以花生的个数从大到小排序。排完序后，从最大的开始，枚举从当前点到每一棵植株并且
2021-07-16 15:44:02
92
1
原创 [ybtoj]前缀统计
前缀统计题目描述样例输入3 2abbcabcabcefg样例输出20数据范围解题思路字典数模版Code#include<iostream>#include<cstdio>using namespace std;int n,m,sum,c[1000005],t[1000005][30];string s; void insert(){ int o=0,len=s.size(); for(int i=0;i<len;i++)
2021-07-11 19:28:51
110
原创 【ybtoj】移位包含
移位包含题目描述对于一个字符串来说，定义一次循环移位操作为：将字符串的第一个字符移动到末尾形成新的字符串。给定两个字符串s1和s2，要求判定其中一个字符串是否是另一字符串通过若干次循环移位后的新字符串的子串。例如 CDAA 是由 AABCD 两次移位后产生的新串 BCDAA 的子串，而 ABCD 与 ACBD 则不能通过多次移位使得其中一个字符串是新串的子串。输入格式一行，包含两个字符串，中间由单个空格隔开。字符串只包含字母和数字。输出格式如果一个字符串是另一字符串通过若干次循环移位产生的新
2021-07-08 08:22:50
85
原创 【ybtoj】数字反转
数字反转题目描述给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零。输入格式输入共1行，一个整数N。输出格式输出共1行，一个整数，表示反转后的新数。解题思路我用了两种方法：第一种不用字符串，不需要处理首位是0。第二种是用字符串，需要处理首位是0的情况。注意，两种都需要预处理负数的情况。（太水了吧 ）code第一种方法#include<iostream>#include&l
2021-06-19 08:46:59
78
原创 【ybtoj】荆轲刺秦王
荆轲刺秦王题目描述输入格式第一行五个整数n,m,c1,c2,dn,m,c_1,c_2,dn,m,c1,c2,d，代表地图的大小为n*m隐身的使用限制次数为c1c_1c1，瞬移的使用次数为c2c_2c2，和一次瞬移的距离d。接下来n行,每行m个元素。每个字符为“S”或“T”或“.”或一个正整数ai,ja_i,_jai,j代表一个格点，具体含义详见题目描述。输出格式若荆轲无法到达秦王所在点，则输出一行一个 -1。否则输出一行三个整数t,u1,u2t,u_1,u_2t,u1,u2
2021-06-19 08:17:16
147
原创 【ybtoj】立体推箱子
立体推箱子题目来源解题思路这道题有点恶心，主要是长方体的状态难处理，你要考虑它是站着还是躺着，而且躺着还分竖着躺和横着躺，卡在这里很久。后来豁然开朗，用一个t来表示长方体的状态，t=0表示站立在(x,y)上，t=1表示横着躺,右半部分在(x,y)上，t=2表示竖着躺，下半部分在(x,y)上。接下来就直接BFS就好了Code#include<cstdio>#include<cstring>using namespace std;int n,m,x1,y1,px[2500
2021-06-13 15:31:32
153
原创 【ybtoj】山峰和山谷
山峰和山谷题目描述给定一个n*n的网格状地图，每个方格（i,j）有一个高度wi,jw_i,_jwi,j。如果两个方格有公共顶点，则它们是相邻的。定义山峰山谷如下：均由地图上的一个联通块组成。所有方格高度都相同。周围的方格（即不属于山峰或山谷但与山峰或山谷相邻的格子）高度均大于山谷的高度，或小于山峰的高度。求地图内山峰和山谷的数量。特别的，如果整个地图方格的高度均相同，则整个地图即是一个山谷，也是一个山峰。输入格式第一行一个正整数n，表示地图的大小。接下来n行，每行n个整数表示地图。
2021-06-13 08:40:58
172
原创 【ybtoj】走迷宫
走迷宫题目描述现在有一个N*N的地图，问从起点(sx,sy)(sx,sy)(sx,sy)到(tx,ty)(tx,ty)(tx,ty)最少要走几步。输入格式输出格式仅有一个数，表示答案。样例输入501111001111000111101111001 1 5 5样例输出8解题思路考虑BFS（广度优先搜索）。可以用dx,xy等常数数组预先保存移动一步坐标的变化情况，简化代码Code#include <cstdio>#include <iostre
2021-06-12 19:38:52
147
原创 【ybtoj】虫食算
虫食算题目来源解题思路这道题其实和数独游戏差不多，但是它的合法条件更复杂，要符合加法运算。同样是要剪枝Code#include<cstring>#include<cstdio>using namespace std;int n,tot,c[30],cc[30],ans[30];char a[30],s[5][30];bool check(){ int o=0; for(int i=n;i>=1;i--) { int x=ans[s[1][i]
2021-06-12 19:03:13
125
原创 【ybtoj】数独游戏
数独游戏题目描述数独是一种传统益智游戏，你需要把99的数独补充完整，使得图中每行、每列、每个33的九宫格内数字1~9均恰好出现一次。请编写一个程序填写数独。输入格式输入包含多组测试用例。每个测试用例占一行，包含81个字符，表达数独的81个格内数据（顺序总体由上到下，同行由左到右）。每个字符都是一个数字或一个 .（表示尚未填充）。您可以假设输入中的每一个谜题都只有一个解决方案。文件结尾处包含单词 end 的单行，表示输入结束。输出格式每个测试用例，输出一行数据，表示填充完全后的数独。
2021-06-12 18:57:34
222
原创 【ybtoj】拔河比赛
拔河比赛题目描述学校组织了一场拔河比赛，为了拔河比赛的公平性，老师提出以下要求：（1）拔河比赛两边人数最多相差1（2）每个队员都有体重，我们要使两边比赛的人体重和相差最小。现在有N个队员，老师想让你帮忙分配，并且把分配后两边体重和只差最小值输出。输入格式首先输入T,表示有T组样例。每个样例：首先输入人数N，占一行。后面跟着N个数，表示N个人的体重W1W_1W1 ~ WnW_nWn。输出格式每组数据输出一行，一个整数表示两边体重只差的绝对值。样例输入1355 50 100
2021-06-12 17:02:14
853
原创 【ybtoj】最大均值
最大均值题目描述给定正整数序列A，求一个平均数最大的，长度不小于L的（连续的）子段。输入格式第一行两个整数N和L。接下来N行，每行输入一个正整数AiA_iAi。输出格式输出一个整数，表示平均值的最大值乘以1000再向下取整之后得到的结果。输入样例10 66 4210385941输出样例6500解题思路注意到答案具有单调性，考虑二分答案，判定“是否存在一个长度不小于L的子串，平均值不小于mid”。Code#include <iostream>
2021-06-12 16:43:41
212
原创 【ybtoj】防具布置
防具布置题目描述输入格式第一行是一个整数T，表示有T组互相独立的测试数据。每组数据的第一行是一个整数N。之后N行，每行三个整数Si,Ei,DiS_i,E_i,D_iSi,Ei,Di，代表第i组防具的三个参数，数据用空格隔开。输出格式对于每组测试数据，如果防线没有破绽，输出一行 There’s no weakness.。否则在一行内输出两个空格分隔的整数P和C，表示在位置P有C个防具。当然C应该是奇数。输入样例321 10 12 10 121 10 1 1 10 1
2021-06-12 15:22:21
102
1
原创 【ybtoj】数列分段
数列分段题目描述对于给定的一个长度为N的正整数数列A，现在将其分成M段，并要求每段连续，且每段和的最大值最小。输入格式第1行包含两个正整数N,M。第2行包含N个空格隔开的非负整数AiA_iAi。输出格式仅包含一个正整数，即每段和最大值最小为多少。输入样例5 34 2 4 5 1输出样例6解题思路题目描述中有类似“最大值最小”的含义，我们马上就知道这答案具有单调性。设最优解为S，因为S的最优性，如果要求每段和都<S，则肯定不能分成连续的M段，需要分成更多连续段。如果每
2021-06-12 08:44:55
390
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人