- 博客(220)
- 收藏
- 关注
RSS订阅
原创 初赛复习知识点
初赛复习知识点逻辑运算&(并且) 有false则false|(或者) 有true则true!(非) 非false则true，非true则false^(异或) 相同为false，不同为true&&(短路与) 有false则false,若&&左边表达式或者值为false则右边不进行计算||(短路或) 有true则true,若||左边表达式或者值为true则右边不进行计算计算机基本结构ROM（只读存储器）只能读
2020-10-08 11:24:00
2606
7
原创 【YbtOJ 线段树 - 2】公园遛狗
公园遛狗题目输入输出小白每出去玩一次，都对应输出一行，只包含一个整数，表示小白可以选出的公园得分和的最大值输入样例5 31 2 -3 4 51 2 32 2 -11 2 3输出样例2-1解题思路这题是一题经典线段树的做法，我们是通过找一个分界点的前缀和后缀进行合并，有可能就是这个区域最大然后我们就用线段树来维护这个区间最大程序如下#include<algorithm>#include<iostream>#include<c
2021-08-02 17:07:10
239
原创 【YbtOJ 线段树 - 2】区间查改
区间查改题目输入输出输入样例5 102 6 6 1 12 1 41 2 5 102 1 32 2 31 2 2 81 2 3 71 4 4 102 1 21 4 5 62 3 4输出样例1534323350解题思路就是线段树直接上即可程序如下#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>
2021-07-21 22:08:07
203
原创 【YbtOJ 线段树 - 1】求区间和
求区间和题目给定一数列，规定有两种操作，一是修改某个元素，二是求区间的连续和输入输出对于每个询问输出对应的答案输入样例10 200 1 101 1 40 6 61 4 101 8 91 4 90 10 21 1 80 2 101 3 90 7 80 3 100 1 11 3 81 6 90 5 51 1 80 4 21 2 80 1 1输出样例1060616624145041解题思路我们这题用的是线段树，没啥好说的
2021-07-12 17:01:07
207
原创 【YbtOJ RMQ - 3】数列区间
数列区间题目输入输出输出共 MMM 行，每行输出一个数输入样例10 23 2 4 5 6 8 1 2 9 71 43 8输出样例58解题思路这题我们先看一下数据，达到了10610^6106，显然不能用线段数那么我们就要用ststst表来解决转移方程为：fi,0f_{i,0}fi,0 === aia_iaifi,jf_{i,j}fi,j === maxmaxmax(fi,j−1 , fi+2j−1,j−1)(f_{i , j - 1
2021-07-09 16:40:48
135
原创 【YbtOJ 树状数组 - 3】严格上升子序列数
严格上升子序列数题目输入输出输入样例23 21 2 33 23 2 1输出样例Case #1: 3Case #2: 0解题思路我们设dp(i,j)dp(i, j)dp(i,j)为第iii个数结尾，长度为jjj的严格上升子序列个数考虑到式子有类似于逆序对的操作，我们要先将数组离散化，再建mmm个树状数组来维护方案数，来优化DPDPDP程序如下#include<algorithm>#include<iostream>#includ
2021-07-08 16:49:11
195
原创 【YbtOJ 树状数组 - 2】逆序对
逆序对题目输入第一行为整数 nnn ，表示序列长度第二行 nnn 个整数，表示给定的序列输出输出逆序对总数输入样例43 2 3 2输出样例3解题思路我们这题先从左到右枚举，来计算aia_iai的逆序对，但是这样时间复杂度为O(N2)O(N^2)O(N2)显然不太优，那么我们就可以考虑用树状数组来进行优化，我们依旧先从左到右枚举每次在树状数组中下标aia_iai的位置加一，查询树状数组中下标大于aia_iai的区间的元素个数，然后进行累计答案即可程序如下
2021-07-08 15:54:24
101
原创 【YbtOJ 树状数组 - 1】单点修改区间查询
单点修改区间查询题目输入输出对于每个 222 lll rrr 操作输出一行，每行有一个整数，表示所求的结果输入样例3 21 2 31 2 02 1 3输出样例6解题思路这题用的是树状数组，树状数组支持单点加操作，还支持查询前缀和，这题我们就直接可以用到程序如下#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>us
2021-07-08 15:26:38
135
原创 【YbtOJ 二叉堆 - 2】序列合并
序列合并题目输入输出输入样例32 6 61 4 8输出样例3 6 7解题思路这题用的是二叉堆，我们先固定一边从小到大，然后先选小的再选大的然后就让每一个数与另一边的第一个进行对应，然后丢进堆里程序如下#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<queue>using names
2021-07-08 15:08:10
97
原创 【YbtOJ 二叉堆 - 1】合并果子
合并果子题目输入输出输入样例3 1 2 9 输出样例15解题思路我们这题用的是二叉堆，我们每次合并最小的两堆，先把所有树插入小根堆，每次取出当前最小的两个数然后把它们的和放回堆程序如下#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<queue>using namespace std;
2021-07-08 11:49:57
145
原创 【YbtOJ AC自动机 - 3】前缀匹配
前缀匹配题目输入输出输出有 MMM 行每一行输出一个数，表示查询串的前缀与母串的最大匹配串长度、输入样例7 3SNNSSNSNNSSNNNWSEE输出样例420解题思路我们先将询问构成ACACAC自动机，然后让母串在上面跑，遍历到的点到rootrootroot形成的字符串一定是母串的子串nxtnxtnxt到rootrootroot形成的字符串也是母串的子串那么我们对遍历到的点跳失配指针，并标记rootrootroot所形成的字符串就是母串的子串最后再拿
2021-07-08 11:43:00
165
原创 【YbtOJ AC自动机 - 2】单词频率
单词频率题目某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次输入第一行一个整数NNN，表示有多少个单词，接下来NNN 行每行一个单词输出输出 NNN 个整数，第 iii 行的数字表示第 iii个单词在文章中出现了多少次输入样例3aaaaaa输出样例631解题思路我们这题要先跑一遍ACACAC自动机，然后求出ACACAC自动机上的每一个节点到根形成的字符串是多少个单词的前缀然后我们要按BFS
2021-07-08 11:27:46
174
原创 【YbtOJ AC自动机 - 1】单词查询
给定 n个长度不超过 50 的由小写英文字母组成的单词用于查询，以及一篇长为m 的文章，问：文中出现了多少个待查询的单词
2021-07-08 11:12:53
145
原创 【YbtOJ 强连通分量 - 2】受欢迎的牛
受欢迎的牛题目每头奶牛都梦想成为牛棚里的明星，被所有奶牛喜欢的奶牛就是一头明星奶牛。每头奶牛总是喜欢自己的，奶牛之间的“““喜欢”””是可以传递的——如果 AAA 喜欢 BBB，BBB 喜欢 CCC，那么 AAA 也喜欢 CCC牛栏里共有 NNN头奶牛，给定一些奶牛之间的喜欢关系，请你算出有多少头奶牛可以当明星输入输出一行单独一个整数，表示明星奶牛的数量输入样例3 31 22 12 3输出样例1解题思路我们先根据题目建立一张有向图，然后会发现任意一个强连通对代表的
2021-07-07 20:43:28
208
2
原创 【YbtOJ 强连通分量 - 1】有向图缩点
有向图缩点题目给定一个nnn 个点 mmm 条边的有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和允许多次经过一条边或者一个点，但是重复经过的点，权值只计算一次输入输出共一行，最大的点权之和输入样例2 21 11 22 1输出样例2解题思路这题是一题模板题，我们要进行缩点，既是把一个强连通子图缩成一个图，然后维护其性质然后我们可以发现，所有的强连通的点都可以进行捆绑，进行缩点后再进行DPDPDP程序如下#inclu
2021-07-07 20:07:21
138
原创 【YbtOJ 最短路 - 2】判断负环
判断负环题目给定一个 nnn个点的有向图，请求出图中是否存在从顶点 111 出发能到达的负环负环的定义是：一条边权之和为负数的回路输入输出对于每组数据，输出一行一个字符串，若所求负环存在，则输出 YE5YE5YE5，否则输出 N0N0N0输入样例23 41 2 21 3 42 3 13 1 -33 31 2 32 3 43 1 -8输出样例N0YE5解题思路我们这题要判断负环，那我们只能用spfaspfaspfa来判断负环，dijkstradijks
2021-07-07 15:42:53
181
1
原创 【YbtOJ 最短路 - 1】单源最短路径
单源最短路径题目输入输出输入样例4 6 11 2 22 3 22 4 11 3 53 4 31 4 4输出样例0 2 4 3解题思路我们这题要用堆优化堆优化堆优化 +++ dijkstradijkstradijkstra程序如下#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<queue
2021-07-07 15:11:59
158
原创 【YbtOJ 最小生成树 - 2】新的开始
新的开始题目发展采矿业当然首先得有矿井，小FFF 花了上次探险获得的千分之一的财富请人在岛上挖了nnn口矿井，但他似乎忘记考虑矿井的供电问题……为了保证电力的供应，小 FFF 想到了两种办法：在这一口矿井上建立一个发电站，费用为 vvv（发电站的输出功率可以供给任意多个矿井）将这口矿井与另外的已经有电力供应的矿井之间建立电网，费用为ppp小 FFF 希望你帮他想出一个保证所有矿井电力供应的最小花费输入输出输出仅一个整数，表示让所有矿井获得充足电能的最小花费输入样例4 5
2021-07-07 14:40:25
149
原创 【YbtOJ 最小生成树 - 1】繁忙都市
繁忙都市题目城市 CCC 是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市 CCC 的道路是这样分布的：城市中有nnn个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接地连接起来。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：1．改造的那些道路能够把所有的交叉路口直接或间接地连通起来2．在满足
2021-07-07 11:13:48
176
2
原创 【YbtOJ 并查集 - 2】银河英雄传说
银河英雄传说题目输入输出输入样例4M 2 3C 1 2M 2 4C 4 2输出样例-11解题思路我们这题要用有边权的并查集，大体和普通并查集类似，但需要在合并集合和路径压缩时及时更新父子节点间的边权程序如下#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>using namespace std;int t,
2021-07-07 08:01:54
151
原创 【YbtOJ 并查集 - 1】并查集
并查集题目有nnn个元素，你需要完成集合的合并和判断两个元素是否在同一集合中这两种操作输入输出对于每一个ziz_izi === 222 的操作，都有一行输出，每行包含一个大写字母，为 YYY 或者 NNN输入样例4 72 1 21 1 22 1 21 3 42 1 41 2 32 1 4输出样例NYNY解题思路并查集模板题程序如下#include<algorithm>#include<iostream>#include&
2021-07-07 08:01:47
127
原创 【YbtOJ Trie - 2】最大异或对
最大异或对题目输入输出输出一个整数表示答案输入样例3 1 2 3输出样例3解题思路我们先把nnn个二进制看做字符串存入TrieTrieTrie树中，那我们可以????考虑????选择一个数aaa，然后在其中找一个数 bbb使两者的异或值最大然后再考虑从高位向低位判断即可程序如下#include<algorithm>#include<iostream>#include<cstring>#include<cstdio&
2021-07-07 08:00:20
91
原创 【YbtOJ Trie - 1】前缀统计
前缀统计题目输入输出对于每个询问，输出一个整数表示答案每个答案占一行输入样例3 2abbcabcabcefg输出样例20解题思路我们把nnn个字符都存入TrieTrieTrie，然后记录一个特殊值来表示字符串的结尾是TrieTrieTrie上的节点xxx的字符串个数程序如下#include<algorithm>#include<iostream>#include<cstring>#include<cstd
2021-07-07 07:59:35
76
原创 【YbtOJ KMP - 2】重复子串
重复子串题目给定若干个的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的如：ababababababababab 最多由 333 个 ababab 连接而成输入输入若干行，每行有一个字符串，字符串仅含英文字母。特别的，字符串可能为 . 即一个半角句号，此时输入结束输出输出每个字符串最多是由多少个相同的子字符串重复连接而成输入样例abcdaaaaababab.输出样例143解题思路程序如下#include<algorithm>#i
2021-07-06 11:56:12
242
原创 【YbtOJ KMP - 1】子串查找
子串查找题目输入输出输入样例zyzyzyzzyz输出样例3解题思路KMPKMPKMP的模板题程序如下#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>using namespace std;int n, m, p[10000001];char s[10000001], t[10000001];int mai
2021-07-06 11:03:26
121
1
原创 【YbtOJ 字符串 - 3】单词替换
单词替换题目输入一个字符串，以回车结束该字符串由若干个单词组成，单词之间用一个空格隔开，所有单词区分大小写现需要将其中的某个单词替换成另一个单词，并输出替换之后的字符串输入输出输入样例You want someone to help youYouI输出样例I want someone to help you解题思路我们就不断的查询，找到就替换即可程序如下#include<algorithm>#include<iostream>#i
2021-07-06 10:39:55
137
原创 【YbtOJ 字符串 - 2】移位包含
移位包含题目对于一个字符串来说，定义一次循环移位操作为：将字符串的第一个字符移动到末尾形成新的字符串给定两个字符串 S1S_1S1 和S2S_2S2 ，要求判定其中一个字符串是否是另一字符串通过若干次循环移位后的新字符串的子串。例如 CDAACDAACDAA 是由AABCDAABCDAABCD 两次移位后产生的新串 BCDAABCDAABCDAA 的子串，而 ABCDABCDABCD 与 ACBDACBDACBD 则不能通过多次移位使得其中一个字符串是新串的子串输入一行，包含两个字符串，中
2021-07-06 10:35:36
175
原创 【YbtOJ 字符串 - 1】数字反转
数字反转题目给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零输入输入共 111行，一个整数 NNN输出输出共 111 行，一个整数，表示反转后的新数NNN输入样例-380输出样例-83解题思路用sprintf(s, %d, n) 将整数NNN转化为字符串SSSsscanf(c, “%d”, &n) 将字符串SSS转化为整数NANANA程序如下#include&l
2021-07-06 10:06:05
77
原创 【YbtOJ BFS - 2】山峰和山谷
山峰和山谷题目输入输出输出一行两个整数，分别表示山峰和山谷的数量输入样例58 8 8 7 77 7 8 8 77 7 7 7 7 7 8 8 7 87 8 8 8 8输出样例2 1解题思路就从一个点开始搜，如果没有访问过就加入队列里，然后比较区域即可程序如下#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#inc
2021-07-06 09:51:36
97
原创 【YbtOJ BFS - 1】走迷宫
走迷宫题目输入输出仅有一个数，表示答案输入样例501111001111000111101111001 1 5 5输出样例8解题思路BFS模板，直接上代码程序如下#include<cstdio>#include<cstring>#include<queue>#include<algorithm>#include<iostream> using namespace std;const i
2021-07-06 09:38:20
104
原创 【YbtOJ DFS - 1】拔河比赛
拔河比赛题目输入输出对于每个样例输出一行，一个整数表示两边体重之差的绝对值输入样例1355 50 100输出样例5解题思路我们考虑一下条件一：我们要构造一个大小为N/2N/2N/2的组条件二：构造出来的成员组的体重和尽量接近S/2S/2S/2我们可以遍历每一个人，要么选，要么不选，保证总人数为N/2N/2N/2，在其中找出最小的差值，就是答案程序如下#include<iostream>#include<cstdio>#includ
2021-07-06 09:16:18
133
原创 【YbtOJ 二分 - 2】数列分段
数列分段题目对于给定的一个长度为 NNN 的正整数数列 AAA，现在将其分成 MMM段，并要求每段连续，且每段和的最大值最小输入第111 行包含两个正整数 N,MN,MN,M第 222 行包含 NNN 个空格隔开的非负整数 AiA_iAi输出仅包含一个正整数，即每段和最大值最小为多少输入样例5 34 2 4 5 1输出样例6解题思路我们设最优解为SSS,那么每段和如果<<<SSS,那么就不能分成MMM如果每段和>S>S>S，
2021-07-06 08:50:09
99
原创 【YbtOJ 贪心 - 2】雷达装置
雷达装置题目有 nnn 个建筑物，第 iii 个建筑物在笛卡尔坐标系上的坐标为(xi,yi)(x_i,y_i)(xi,yi) ，你需要在 xxx 轴上安装一些雷达，每个雷达的侦察半径均为 ddd，要求每个建筑物都至少被一个雷达侦测到，求最少要安装几个雷达输入第一行两个正整数 n,dn,dn,d接下来 nnn行，第 iii 行两个整数 xi,yix_i,y_ixi,yi输出输出一行表示答案，若没有解决方案，则答案为 −1-1−1输入样例3 21 2-3 12 1输出样
2021-07-06 08:11:08
133
原创 【YbtOJ 贪心 - 1】奶牛晒衣服
奶牛晒衣服题目有 nnn件衣服，第 iii 件衣服的湿度为hih_ihi在自然条件下，每件衣服每分钟都可以自然晒干 AAA点湿度在烘干机作用下，可以选择一件衣服，用一分钟的时间晒干 BBB点湿度求出晒干所有衣服的最少时间（湿度为 000 为干）输入第一行三个正整数 N,A,BN,A, BN,A,B接下来 NNN行，第 iii 行一个正整数，表示第 iii 件衣服的湿度 hih_ihi输出输出一个数，表示晒干所有衣服的最少时间输入样例3 2 1123输出样例1
2021-07-05 21:57:40
142
原创 【YbtOJ 递推 - 5】平铺方案
平铺方案题目您可以通过几种方式用 2∗12 * 12∗1 或 2∗22 * 22∗2 瓦片平铺 2∗n2 * n2∗n 矩形？这是一个2∗172 * 172∗17 矩形的样本拼贴： 无图输入每行一个整数 nnn输出每行一个整数，表示方案数输入样例2812100200输出样例31712731845100400152152934331135470251107129202950599351702797472822744173501480199585519522353
2021-07-05 21:29:07
294
原创 【YbtOJ 递推 - 4】传球游戏
传球游戏题目输入一行，有两个用空格隔开的整数 nnn,mmm输出111个整数，表示符合题意的方法数输入样例3 3输出样例2解题思路我们设f[i,j]f[i,j]f[i,j]表示传球经过j个人后在第i个同学手上的方法数程序如下#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int
2021-07-05 20:45:01
103
1
原创 【线性筛】线性筛素数
线性筛素数题目描述如题，给定一个范围 n，有 q 个询问，每次输出第 k 小的素数输入格式第一行包含两个正整数 n,q，分别表示查询的范围和查询的个数接下来 q 行每行一个正整数 k，表示查询第 k小的素数输出格式输出 q 行，每行一个正整数表示答案输入样例100 512345输出样例235711说明/提示【数据范围】对于 100% 的数据，n = 10^8 ， 1 ≤ q ≤ 10^6，保证查询的素数不大于 n解题思路先判断它是否为素数，标记，然
2021-05-14 22:23:04
395
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人