- 博客(202)
- 收藏
- 关注
RSS订阅
原创 LG·飞行路线【分层图最短路】
luogu P4568 [JLOI2011] 飞行路线Description--Input--Output--Sample Input--Sample Output--说明--解题思路--代码--Description–一共有 nnn 个城市，分别标记为 000 到 n−1n-1n−1，一共有 mmm 种航线，每种航线连接两个城市，并且航线有一定的价格，可以免费在最多 kkk 种航线上搭乘飞机。花费多少？Input–第一行三个整数 n,m,kn,m,kn,m,k，分别表示城市数，航线数，免费乘坐
2021-11-18 21:53:44
398
原创 LG·Lyrith【模拟】
luogu T207968 Lyrith -迷宮リリス-Description--Input--Output--Sample Input--Sample Output--说明--解题思路--代码--Description–有一个数字 xxx问是否存在一种方案，将数字 xxx 重排后，是 888 的倍数。重排指的是将 xxx 十进制下每一位拿出来，然后重新排列他们的顺序，最后再次组成一个十进制数 x′x'x′。注意这个新的十进制数 x′x'x′ 可以有前导零。Input–输入一个正整数 xxx
2021-11-09 20:07:12
113
原创 LG·网格游走【矩阵乘法】【DFS】
luogu T202676 网格游走Description--Input--Output--Sample Input--Sample Output--说明--解题思路--代码--Description–有一个 3×33\times 33×3 的网格。最开始每一个格子上都有一个机器人。在每一秒内，每一个机器人可能往上下左右四个方向走一步，或者停留在原地不动。也就是如果这一秒一个机器人在 (x,y)(x,y)(x,y)，那么下一秒这个机器人可能会在 (x+1,y),(x−1,y),(x,y+1),(x,y
2021-11-06 07:42:49
123
原创 LG·可重集【线段树】
luogu T202677 可重集Description--Input--Output--Sample Input--Sample Output--说明--解题思路--代码--Description–有一个可重集，初始为空集。有 nnn 个操作，每个操作均属于以下两种类型之一：1x1 x1x：往可重集里加入一个正整数 xxx。2x2 x2x：在可重集中删除数字 xxx。如果数字 xxx 出现了多次只删除一次。如果可重集内没有数字 xxx，那就忽略这次操作。有 mmm 次询问。每次询问给出两个
2021-11-03 21:23:33
147
原创 LG·多项式滚出OI【模拟】
Luogu T202675 多项式滚出OIDescription--Input--Output--Sample Input--Sample Output--说明--解题思路--代码--Description–有一个 nnn 项的多项式 f(x)f(x)f(x) 如下：f(x)=∑i=0n−1ai×xif(x)=\sum^{n-1}_{i=0}a_i\times x^if(x)=∑i=0n−1ai×xi已知 x=mx=mx=m 时这个多项式 f(m)f(m)f(m) 的值。请还原这个多项式。对
2021-11-02 20:29:46
109
原创 ybtoj·约束条件【并查集】
约束条件Description --解题思路 --代码 --Description –高效进阶「图论」第1章 并查集课堂过关 例题2解题思路 –i，ji，ji，j 的范围是 10910^9109 ，所以要做离散化处理然后先处理相同的 i，ji，ji，j 将他们并在一起再处理不同的，如果本应不同的 i，ji，ji，j 在一个集中则不成立代码 –#include <algorithm>#include <iostream>#include <cstdio&g
2021-08-08 15:08:35
158
原创 ybtoj·并查集【模板】
并查集【模板】Description--代码--Description–高效进阶「图论」第1章 并查集课堂过关 例题1代码–#include <iostream>#include <cstdio>using namespace std;int n, m, z, x, y, f[11000];int find(int xx){ if (xx == f[xx]) return xx; else return f[xx] = find(f[xx]);}i
2021-06-16 16:31:51
84
原创 ybtoj·子正方形【Hash】
子正方形Description--代码--Description–高效进阶「字符串算法」第2章 Hash 和 Hash 表课堂过关 例题5代码–#include <iostream>#include <cstdio>#define ull long longusing namespace std;int n, ans, a[55][55], b[55][55];ull t1[55], t2[55], h1[55][55], h2[55][55];bool
2021-05-21 20:53:59
107
原创 ybtoj·回文子串【Hash】
回文子串Description--解题思路--代码--Description–高效进阶「字符串算法」第2章 Hash 和 Hash 表课堂过关 例题2解题思路–用前缀和的方式正反记录字符串，即可实现快速查询一个串的哈希值枚举每一个中心点i，则有两种情况：以i点为中心，回文串的长度是奇数以i点和i+1点中间的轴为中心，回文串的长度是偶数然后二分求延伸的长度代码–#include <iostream>#include <cstring> #include
2021-05-08 16:51:40
113
原创 ybtoj·字符串哈希【Hash】
字符串哈希Description--代码--Description–高效进阶「字符串算法」第2章 Hash 和 Hash 表课堂过关 例题1代码–#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int M = 1e8 + 9;int s, n, ans;bool pd[M];string o;int main(){ scan
2021-05-04 15:56:25
83
原创 ybtoj·生日相同【字符串】
生日相同Description--代码--Description–高效进阶「字符串算法」第1章 字符串处理课堂过关 例题5代码–#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>using namespace std;int a, b, t, ss[15][35];string c, s[15][35][5005];bool cmp
2021-05-04 15:56:13
86
原创 ybtoj·字符串环【字符串】
字符串环Description--代码--Description–高效进阶「字符串算法」第1章 字符串处理课堂过关 例题4代码–#include <iostream>#include <cstring>#include <cstdio>using namespace std;int ans;string a, b;int main(){ cin >> a >> b; if ((int)a.size() < (
2021-04-28 16:57:26
78
原创 ybtoj·单词替换【字符串】
单词替换Description--解题思路--代码--Description–高效进阶「字符串算法」第1章 字符串处理课堂过关 例题3解题思路–把每一个单词处理出来，输出的时候判断一下是否被换掉即可代码–#include <iostream>#include <cstring>#include <cstdio>using namespace std;int t = 1;string s, a, b, x[1005];void fen(st
2021-04-28 16:57:02
73
原创 ybtoj·移位包含【字符串】
移位包含Description--代码--Description–高效进阶「字符串算法」第1章 字符串处理课堂过关 例题2代码–#include <iostream>#include <cstring>#include <cstdio>using namespace std;string a, b;string read(){ char c = getchar(); string cc = ""; while (c < 'A' ||
2021-04-21 16:48:20
66
原创 ybtoj·数字反转【字符串】
数字反转Description--代码--Description–高效进阶「字符串算法」第1章 字符串处理课堂过关 例题1代码–#include <iostream>#include <cstring>#include <cstdio>using namespace std;int g, f;string s;int main(){ cin >> s; if (s[0] == '-') cout << '-', g
2021-04-21 16:48:04
115
原创 ybtoj·山峰和山谷【BFS】
山峰和山谷Description--解题思路--代码--Description–高效进阶「基础算法」第5章 广度搜索课堂过关 例题解题思路–把每个没有搜过的点搜一遍代码–#include <iostream>#include <cstdio>#include <queue>using namespace std;const int fx[8] = {0, 0, -1, -1, -1, 1, 1, 1};const int fy[8] = {1
2021-03-24 16:47:15
97
原创 ybtoj·走迷宫【BFS】
走迷宫Description--解题思路--代码--Description–高效进阶「基础算法」第5章 广度搜索课堂过关 例题1解题思路–暴搜ヽ(o_ _)o代码–#include <iostream>#include <cstdio>#include <queue>using namespace std;const int f[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int n, ans, k
2021-03-24 16:45:03
84
原创 ybtoj·虫食算【DFS】
虫食算Description--解题思路--代码--Description–高效进阶「基础算法」第4章 深度搜索课堂过关 例题3解题思路–剪枝：（加数x,y，和z）若当前位右边的数都确定了，判断当前位是否符合加法若当前位右边的数没有确定，判断当前位是否符合加法（进位可为0或1）判断和的位数是否大于n代码–#include <iostream>#include <cstring>#include <cstdio>using namespac
2021-03-06 11:00:42
72
原创 ybtoj·数独游戏【DFS】
数独游戏Description--解题思路--代码--Description–高效进阶「基础算法」第4章 深度搜索课堂过关 例题2解题思路–h[x][y]表示x行有没有y数，l[x][y]表示列，g[x][y]表示该小矩阵代码–#include <iostream>#include <cstring>#include <cstdio>using namespace std;int a[100];bool gg, l[10][10], h[10
2021-03-06 10:42:54
104
原创 ybtoj·拔河比赛【DFS】
拔河比赛Description--解题思路--代码--Description–高效进阶「基础算法」第4章 深度搜索课堂过关 例题1解题思路–暴搜代码–#include <iostream>#include <cstdio>#include <cmath>using namespace std;int t, n, a[50], ans;void dfs(int lev, int x, int y, int xy){ if (lev >
2021-03-06 10:40:19
92
原创 ybtoj·最大均值【二分】
最大均值Description--解题思路--代码--Description–高效进阶「基础算法」第3章 二分算法课堂过关 例题3解题思路–二分答案把所选子串每个数减去mid，若子串和仍为正数，则该子串的平均值大于mid代码–#include <iostream>#include <cstdio>#include <cmath>#define db doubleusing namespace std;const db eps = 1e-5;
2021-03-06 10:38:16
131
原创 ybtoj·防具布置【二分】
防具布置Description--解题思路--代码--Description–高效进阶「基础算法」第3章 二分算法课堂过关 例题2解题思路–设 h[i]h[i]h[i] 是 0−i0-i0−i 的防具总个数二分破绽的位置 uuu若 h[mid]h[mid]h[mid] 为奇数，则 uuu 在 0−mid0-mid0−mid 之间反之则在 mid−(231−1)mid-(2^{31} - 1)mid−(231−1) 之间代码–#include <iostream>#incl
2021-01-11 17:00:31
78
原创 ybtoj·数列分段【二分】
数列分段Description--解题思路--代码--Description–高效进阶「基础算法」第3章 二分算法课堂过关 例题1解题思路–二分答案代码–#include <iostream>#include <cstdio>#define ll long longusing namespace std;ll n, m, l, r, a[100005];bool hll(ll x){ ll s = 0, k = 1; for (ll i = 1;
2021-01-11 16:31:54
86
原创 ybtoj·雷达装置【贪心】
雷达装置Description--代码--Description–高效进阶「基础算法」第2章 贪心算法课堂过关 例题2代码–#include <algorithm>#include <iostream>#include <cstdio>#include <cmath>using namespace std;int n, d, x, y, ans;double t;struct ooo{ double l, r;}a[1005
2020-12-30 20:29:33
113
原创 ybtoj·奶牛晒衣服【贪心】
奶牛晒衣服Description--解题思路--代码--Description–高效进阶「基础算法」第2章 贪心算法课堂过关 例题1解题思路–每一次烘干当前湿度最大的衣服（用大根堆维护即可）代码–#include <iostream>#include <cstdio>#include <queue>using namespace std;priority_queue <int> q;int n, a, b, u, h, s, s
2020-12-26 11:24:02
101
原创 ybtoj·平铺方案【递推】
平铺方案Description--解题思路--代码--Description–高效进阶「基础算法」第1章 递推算法课堂过关 例题5解题思路–万恶的高精设f[i]为平铺2*i矩形的方案数2*(i-1) 矩形加一块 2*1 矩形，方案数为f[i-1]2*(i-2) 矩形加一块 2*2 矩形，方案数为f[i-2]2*(i-2) 矩形加两块 2*1 矩形（横着放），方案数为f[i-2]所以 f[i]=f[i−2]∗2+f[i−1]f[i]=f[i-2]*2+f[i-1]f[i]=f[i−2]
2020-12-26 10:33:01
110
原创 ybtoj·传球游戏【递推】
@TOCDescription–高效进阶「基础算法」第1章 递推算法课堂过关 例题4解题思路–代码–#include <iostream>#include <cstdio>#define ll long longusing namespace std;int n, m;ll f[35][35];int main(){ scanf("%d%d", &n, &m); f[1][0] = 1; for (int j = 1; j
2020-12-26 09:27:24
104
原创 ybtoj·数的划分【递推】
数的划分Description--解题思路--代码--Description–高效进阶「基础算法」第1章 递推算法课堂过关 例题3解题思路–设f[i][j]为整数i分成j份的方案数使j份中至少有一份为1（最后一份放1），则方案数为f[i-1][j-1]使j份中一份1都没有，我们先将i-j分成j份，再在每一份中加1代码–#include <iostream>#include <cstdio>#define ll long longusing namesp
2020-12-25 21:23:36
116
原创 ybtoj·奇怪汉诺塔【递推】
奇怪汉诺塔Description--解题思路--代码--Description–高效进阶「基础算法」第1章 递推算法课堂过关 例题2解题思路–首先我们思考 333 座塔（即A，B，C）的汉罗塔问题：（设 d[n]d[n]d[n] 表示 nnn 个盘子的最优步数，从A到C）将前n-1个盘子移至B塔，最优步数为d[n-1]步将A塔剩余的1个盘移至C塔，1步最后将B塔的n-1个盘移至C塔，d[n-1]步所以，d[n]=d[n−1]∗2+1d[n]=d[n-1]*2+1d[n]=d[n−1]
2020-12-23 17:41:08
95
原创 ybtoj·错排问题【递推】
错排问题Description--解题思路--代码--Description–高效进阶「基础算法」第1章 递推算法课堂过关 例题1解题思路–设 f[n]f[n]f[n] 为 nnn 个数的合法排列个数第n个数可以放在(n-1)个位置，我们称放的位置为k考虑第k个数1 放在位置n上，那么剩下的n-2个数的排列个数为f[n-2]2 不放在位置n，那么除n以外的排列个数为f[n-1]所以，f[n]=(n−1)(f[n−1]+f[n−2])，n≤3f[n] = (n - 1)(f[n-1]+
2020-12-23 17:19:52
76
原创 LG·斐波那契数列的和【矩阵乘法】
luogu U145243 斐波那契数列的和Description--Input--Output--Sample Input--Sample Output--说明--解题思路--代码--Description–> linklinklink数列 f[n]=f[n−1]+f[n−2],f[1]=f[2]=1f[n]=f[n-1]+f[n-2],f[1]=f[2]=1f[n]=f[n−1]+f[n−2],f[1]=f[2]=1 的前 nnn 项和 s[n]s[n]s[n] 的快速求法（不考虑高精度）
2020-12-19 15:48:26
170
2
原创 SSL·斐波拉契数列IV【矩阵乘法】
SSL 1531 斐波拉契数列IVDescription--Input--Output--Sample Input--Sample Output--说明--解题思路--代码--Description–求数列 f[n]=f[n−2]+f[n−1]+n+1f[n]=f[n-2]+f[n-1]+n+1f[n]=f[n−2]+f[n−1]+n+1 的第 ＮＮＮ 项,其中 f[1]=1,f[2]=1f[1]=1,f[2]=1f[1]=1,f[2]=1Input–nnnOutput–第 nnn 项结果 %
2020-12-18 22:15:11
114
1
原创 SSL·斐波拉契数列III【矩阵乘法】
SSL 1530 斐波拉契数列IIIDescription--Input--Output--Sample Input--Sample Output--说明--解题思路--代码--Description–求数列 f[n]=f[n−1]+f[n−2]+1f[n]=f[n-1]+f[n-2]+1f[n]=f[n−1]+f[n−2]+1 的第 NNN 项 f[1]=1,f[2]=1f[1]=1,f[2]=1f[1]=1,f[2]=1Input–nOutput–第 ＮＮＮ 项的结果 %9973\% 99
2020-12-18 22:10:18
119
1
原创 SSL·斐波拉契数列II【矩阵乘法】
SSL 1529 斐波拉契数列IIDescription--Input--Output--Sample Input--Sample Output--说明--解题思路--代码--Description–形如1123581321345589144....1 1 2 3 5 8 13 21 34 55 89 144....1123581321345589144....的数列,求斐波拉契数列的第 nnn 项。Input–nOutput–一个数为斐波拉契数列的第 nnn 项 %10000\% 10000
2020-12-18 22:02:18
77
1
原创 ybtoj·高效生产【SPFA】
ybtoj NOIP2020 模拟赛 A 组 Day10 高效生产Description--Input--Output--Sample Input--Sample Output--说明--解题思路--代码--Description–>linklinklink产品要从 A 部门运到 B 部门时，都要先从 A 部门送到质量检验处，检验合格后再从质量检验处运到 B 部门有些部门之间有传送带连接，厂长想知道每次将产品从一个部门运送到另一个部门最少需要多长时间Input–第一行两个整数 n,mn
2020-12-02 19:18:29
129
原创 ybtoj·偷学计划【状压DP】
@TOCDescription–Input–Output–Sample Input–Sample Output–说明–解题思路–代码–
2020-12-02 17:16:54
170
4
原创 ybtoj·区间操作【差分】
ybtoj NOIP2020 模拟赛 A 组 Day10 区间操作Description--Input--Output--Sample Input--Sample Output--说明--代码--Description–>linklinklink一个 nnn 个数的序列，一开始所有的数都是 000 ，每次可以将一个区间 l−rl - rl−r 内的数加 111 ，求到达最终状态的最少操作次数Input–第一行包含一个正整数 nnn，表示序列的长度第二行包含 nnn 个不同的正整数 ，表示
2020-12-01 20:32:53
250
原创 关于CSP2020
2020 CSP-S 总结考前一天考前半天考前一天还是没有回班上上课的一天。。。（感觉文化科要炸复习了下要考的模板，怎么说呢，会的还是会，不会的还是不会，于是打了几个较基本的练了练手下午的时候 555 点就离开机房了，要和某初中生拼车，结果去教室拿相机的时候被班主任抓到了（危），果然她并不打算放我走，然后和同学们留到了 555 点 202020 。好吧，还有十分钟得赶到初中部。结果又被劳动委员抓住了，为什么我还要值日啊啊啊啊啊（努力的扫地中。。。），3分钟扫完的地也不知道会不会被要求重值。狂奔回宿舍
2020-11-26 21:07:45
187
5
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人