ssl_ljh-CSDN博客

原创 noip初赛复习总纲

初赛复习总纲计算机发展史1946～1957电子管1958～1964晶体管1965～1970规模集成电路1958～1964超大，大规模集成电路操作系统盘点AndroidBSDiOSLinuxMac OS XWindowsWindows Phonez/OS进制转换八进制和十进制的对应表左八进制，右十进制00...

2019-10-07 10:03:31 2468 1

原创 [游记]2022纪中重游

写在前面这次纪中集训似曾相识，但又有所不同。机房，饭堂是同往常一致的(饭堂的饭还是一如既往的一言难尽。。。宿舍倒是搬迁了，但较以往而言，内部没有什么大的变动(倒是热水倒是有了，泡泡面不愁了宿舍少了两位熟客，却又迎来了两位新客。。。转眼也初三毕业了，高中又会迎来怎样的分别？带着茫然和无措，来到了熟悉的纪中。正文Day 0到了纪中，感觉莫名的空虚。。。到了饭堂，虽然已经有预期，但...

2022-07-30 15:42:00 61

原创 [状压DP]Sculpture

题目大意给定一个 \(n*n\) 的范围，其中有 \(m\) 个点不能部署雕像。其中雕像要满足不能部署在同一行和同一列。类似于 \(sslOJ\) 上的一题 “车” (其实就一模一样分析数据范围 \(N\) 是小于等于二十的，考虑如何表达这个的状态和进行状态转移。因为只有两种情况：选于不选。所以可以考虑用 \(0,1\) 表示没选和选了。这么来，就可以用一个十进制数来二进制化来表示...

2022-07-12 22:03:00 62

原创 [爆搜]Torchbearer

题目大意给定一个正整数 \(n\) ，求最小的正整数 \(m\) 满足 \(n * m\) 的值的每位由 \(0, 1\)构成(十进制下)。思路本来看到 \(0,1\)串，想到的是用二进制搞。但是发现自己这方面存在大锅，而且人也很菜。于是转变了思考方向。对于乘积的每一位都是由 \(0,1\) 构成，那么考虑模拟乘法。因为乘法每次都是高一位的，所以每次考虑枚举 \(0\) 到 \(...

2022-07-12 21:01:00 60

原创 [纪中][线段树]矮人排队

题目大意给定一个数列。有两个操作一，调换队列中下标为 \(x\) 和 \(y\) 的元素的位置；二，询问一个数列\(D\)的 \(a, a+1, a+2......b\) 的一种排列方式为该队列的子队列。解析一，显然，取这个数列的每个元素所对应的下标的最大值 \(maxt\) 和最小值 \(mint\)。当 \(maxt - mint = b - a\) 时为子队列。二，用线段...

2022-07-12 14:28:00 32

原创 [欧拉筛][洛谷]线性筛素数

线性筛素数洛谷题目 \(Link\)解析这里运用欧拉筛。欧拉筛是埃氏筛法的改进版。例如，在埃氏筛法里，对于 \(12\) 有 &2 * 6& 和 \(3 * 4\) 两种情况筛到，如果以一种方法能够让一个数只能被筛过一次，就能够进一步提高算法效率。Code#include <bits/stdc++.h> #define N 100000008usin...

2022-02-26 11:15:00 19

原创 [51nod : 2102][位运算] 或减与

题目 \(Link\)解析按照题目说法，即输出 \(a | b - a & b\) 即可。但是按照这则运算，可以发现\(a | b - a & b = a ^ b\)这个可以举例说明，再次就不赘述了。Code#include <bits/stdc++.h>#define ll long longusing namespace std;int mai...

2022-02-19 14:46:00 19

原创 [51node : 3216] [位运算] 授勋

3216 授勋51nod 题目\(Link\)题目解析因为任意一个正整数都可以用 \(2\) 的幂次方表示，所以这道题有解。所以把这个数转化为二进制时，每一位的 "\(1\)" 对应的的就是一个二的 \(n\) 次幂。例： \(6\)(10) -> \(110\)(2)\(6 = 2^1 + 2^2\)\(110\) 对应的是 \(2\) 的 \(1\) 和 \(2\) 次幂。...

2022-02-19 09:04:00 24

原创 [51nod ： 2106] [位运算] 一个奇数次

一个奇数次51nod 题目 \(Link\)解析这里采用的是位运算异或。让 ans 每次都异或输出的数，因为 a ^ a = 0 的，所以每次异或时出现偶数次的数就可以消掉(异或符合交换律)。因为题目中指定只有一个数会出现奇数次，所以易证这个做法的正确性。Code#include <bits/stdc++.h>using namespace std;int an...

2022-02-18 20:49:00 37

原创 [sslOJ1213][计算几何]多边形面积(difficult)

题面sslOJ \(Link\)思路首先题目讲明，这个是一个由\((1, 2), (2, 3)......(n - 1, n), (n, 1)\)这些边构成的点。于是利用叉积算出这个多边形的面积。但是题目里说过，这个多边形可能是不合法的。有两种情况：1)点的数量小于等于二2)非相邻的边相交了所以再枚举每两条非相邻的边是否相交就可以了Code#include <cmat...

2022-01-20 15:06:00 18

原创 [sslOJ 1715] 计算面积

题面sslOJ \(LINK\)解析这是一个很神奇的结论：设矢量P = ( x1, y1 )，Q = ( x2, y2 )，则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积，平行四边形面积就是叉积的绝对值。但是遗憾的是，本人并不会证明。但是我们还是可以在做题的时候用到。注意：\(y0\) 是 \(cmath\) 里面的一个函数；记得处理负数情...

2022-01-19 09:03:00 17

原创 [sslOJ 1232] [ZOJ 1041] 雷达覆盖(normal)

题面sslOJ \(LINK\)ZOJ \(LINK\)解析可以考虑通过计算，算出雷达与其他的点的距离，超过半径的点判为不合法的点(因为不论怎样都无法被扫描到，贡献恒为零)。然后枚举每一个合法的点，以雷达和这个点的连线的延长线为标准，判断是属于哪个半圆的点(如果在直径上，那就是属于两个半圆的点)，然后再取所有半圆的最大值Code#include <iostream>#in...

2022-01-19 08:04:00 19

原创 [树状数组]3120 小陶的疑惑

51nod 题目\(Link\)题目解析这是一道树状数组的模板题，但是请大家注意要开long long。有关树状数组ll lowbit (ll n){ return n & (-n); } void update (ll x, ll y) // 修改{ for (; x <= n; x += lowbit (x)) c[x] += y;}ll sum...

2022-01-12 21:24:00 23

原创 [游记]在SSL的集训生活

Day -1\(2021/8/7\)因为新冠的原因，所以不能去纪中集训，改在 ssl 做纪中的狗妈\(OJ\) 的题了。逃离了纪中的宿舍，饭堂和机子，真好。明天就去集训了，于是好好地颓了一整天。水陈二技能好刮啊，快点精二开三技能玩。阿莫斯拉满了，接下来又可以刷圣遗物了。晚上看书，看到 12 点就睡了day 1\(2021/8/8\)集训真正开始了早上早上 6 点就...

2021-08-22 19:24:00 18

原创 [总结]纪中集训的总结·七月篇

纪中集训的总结在纪中，收益甚多和 SSL 的几位过得又快乐(暴切)又难受(调代码)学习学了有点挺多东西打了 excrt ，对期望DP 巩固了许多。树链剖分搞了板子，思想和原理都弄懂了。还有网络流和费用流，有时间就去做做板子。暴搜，贪心，特殊情况骗分技巧学的好好的还有好多的知识点巩固了，一向讨厌的数论的博弈论也懂了一丢丢。还是很有成效的生活本人快乐而难受的纪中集训Dr....

2021-07-22 16:27:00 14

原创 [游记]纪中集训的生活·七月传

「梦开始的地方」 Day 0 - 7/11晚抒发感情快乐，高中部的景观是真的不错。DGSSL初二的游园团(纪中观光团)都认为这就是景点,咳咳咳, 这并不是重点, 作为一名优秀的单身狗, 我与gyx, cxy等人也认同这这观点这个观点也取得了两名现充的认同, 这也可以侧面说明这所学校的景观之好关于宿舍虽然学校很大, 环境很好, 但是这个宿舍是真的不得行怎么说呢, 大家可以想象一...

2021-07-21 21:51:00 33

原创 [期望DP]彩色圆环

彩色圆环感谢名单十分感谢 JA_Ma 为我讲解了 \(T1\) 的期望DP 的思想和推论。十分感谢 SSL_LYF 为我解答了 \(T1\) 的期望DP 的概率的大小问题。十分感谢 SSL_WJ 为我讲解了高斯消元的一些判断及一些基础知识。(排名不分先后)正文这道题已经告诉你是期望DP 了，主要是状态转移方程的推导和最后的 ans 进行求值我们先预处理出每个区...

2021-07-15 22:38:00 26

原创 [并查集]B. 2.约束条件

解析由于数据太大了, \(10^9\) 的内存绝对会炸, 所以要用离散化Code#include <bits/stdc++.h>using namespace std;int n, m, z, x, y; int f[10005];int find (int x){ while (x != f[x]) x = f[x] = f[f[x]]; return x...

2021-07-09 09:13:00 16

原创 [并查集]A. 【例题1】【模板】并查集

解析这道题是一道冰茶姬的模板题, 不必多言, 直接上代码Code#include <bits/stdc++.h>using namespace std;int n, m, z, x, y; int f[10005];int find (int x){ while (x != f[x]) x = f[x] = f[f[x]]; return x;}int...

2021-07-09 07:41:00 18

原创 [Trie树]C. 【例题3】最长异或路径

解析这道题我觉得恶心的地方就是要求一整条边的边权的异或给搞出来，注意运算符不要用错了。Code#include <bits/stdc++.h>#define N 100005using namespace std;struct node{ int x, to, nxt;}hd[N * 2];struct Trie { int son [2];}trie...

2021-06-12 20:51:00 27

原创 [Trie树]B. 【例题2】最大异或对

解析这道题是\(Trie\)树, 要求异或的值最大, 就尽可能找不同的code#include <bits/stdc++.h>#define N 10000005using namespace std;int a[N][2];int n, tag = 1, ans;void fd (int t){ int now = 1, s = 0; for (int...

2021-06-11 21:33:00 24

原创 [Trie树][YbtOJ]A. 【例题1】前缀统计

解析Trie树基础题, 将 \(s\) 串全部加到Trie树里面, 然后记录以某个节点为终点的单词的个数 val[], 然后将询问串 \(T\) 搜索一遍, 遍历过完的点就讲 \(val[hhd]\) 给加上.Code#include <bits/stdc++.h>#define N 100005using namespace std;char se[N];int ...

2021-06-04 22:29:00 18

原创 [Trie树][落谷]P2580 于是他错误的点名开始了

首先是题面.落谷\(Link\)解析就是简单的Trie树模板, 由于为了进度, 就不写Trie树的插入, 搜索等操作了.这里就是每次搜的时候, 要搜得单词没有在树上, 就是 \(WRONG\) ; 要是搜的搜完了, 都在树上, 就看最后一个节点的附加信息, 如果是初始化时的0, 就是没喊过名, 然后就是 \(OK\) , 再给最后一个节点上一个附加信息 \(1\), 表示已经喊过了. 如...

2021-06-04 20:19:00 18

原创 [KMP算法]D. 【例题4】子串拆分

Code#include <bits/stdc++.h>#define N 15005using namespace std;int k, n, ans;int t1[N];char c[N], et[N];int main (){ scanf ("%s%d", c + 1, &k); n = strlen (c + 1); for (int i ...

2021-06-02 17:08:00 24

原创 [KMP算法]C. 【例题3】周期长度和

解析本题解是用KMP算法来完成此题。Code#include <bits/stdc++.h>#define N 1000005#define ll long longusing namespace std;int k[N];string s;ll len, ans; ll f (ll x){ if (k[x] != 0) return k[x] = f ...

2021-06-02 16:54:00 15

原创 [KMP算法]B. 【例题2】重复子串

解析通过KMP算法处理出一个数组 \(p\), 我们通过 \(strlen ()\) 来求出字符串的长度 \(len\), 该模式串的第 \(1\) 位到第 \(p[len]\) 位于模式串的第 \(len-p[len]\) 位到第 \(len\) 位是匹配的.所以如果 \(len \equiv 0 (mod (len - p[len]))\) , 则存在重复连续子串, 长度为 \(l...

2021-05-20 16:23:00 18

原创 [KMP算法]A. 【例题1】子串查找

题目解析这道题是比较基础的KMP模板， KMP是一种高效的字符串匹配算法。以下这个视频是我认为是讲的不错的KMP算法视频视频连接Code#include <bits/stdc++.h> using namespace std;char s1[1000005], s2[1000005];int len1, len2, j, kmp[1000005], ans;in...

2021-05-20 15:47:00 16

原创 [字符串哈希]A. 【例题1】字符串哈希

题目来源：YbtOJ「字符串算法」第2章 Hash 和 Hash 表课堂过关题面链接解题思路这道题是字符串哈希的模板题，通过哈希函数来统计有了的字符串Code#include <bits/stdc++.h>#define MOD 100000007#define N 13313#define ll long longusing namespace std;...

2021-04-14 16:48:00 21

原创 [分治]排序|

题目来源:sslOJ题面解析对于一个长度为\(n\)的序列,进行一次从小到大的排序,再进行输出排序我们考虑快速排序.快速排序介绍Code#include <stdio.h>#include <iostream>#include <algorithm>using namespace std;int n;int a[100005];v...

2021-04-10 19:31:00 12

原创 [分治]浅谈快速排序

浅谈快速排序什么是快速排序?快排每次会选取一个排序基数,将这个序列分为一边是小于这个基数的,另一边是大于这个基数的.当然,你可以决定哪一边是大于或者小于的.快速排序的期望时间复杂度为 \(O(nlogn)\) , 当然也与数据和所取的排序基数 \(key\) 有关,对于一些数据,如果 \(key\) 的取值不当,快排就会退化成一个 \(O(n^{2})\) 的算法,这个后文会提到.关...

2021-04-08 21:28:00 17

原创 [分治]二分查找

题目来源:sslOJ题面思路因为所给的数据已经是从小到大排列的了,就可以直接二分查找答案,找到就直接输出Code#include <stdio.h>#include <iostream>using namespace std;int a[10005];int n, key, ans, f; //f来判断是否有输出,避免重复的判断void hhd ...

2021-04-07 16:41:00 14

解析字符串操作,本题解采取了多关键词排序Code#include <bits/stdc++.h>using namespace std;int f, n;struct node{ int y, r; string s;}a[100005];int cmp (node x, node y){ if (x.y != y.y) return x.y < y.y; if (x.r != y.r) return x.r < y.r; if (x.s.len..

2021-03-26 20:25:11 403

原创 D. 【例题4】字符串环

解析字符串的操作，可以用函数解决这个问题s2.find (s1.substr (i, j))s2.find~(s1.substr~(i,~j))s2.find (s1.substr (i, j))在s2中查找s1中iii到jjj第一次出现的位置substr是C++语言函数，主要功能是复制子字符串，要求从指定位置开始，并具有指定的长度。如果没有指定长度_Count或_Count+_Off超出了源字符串的长度，则子字符串将延续到源字符串的..

2021-03-26 18:18:44 417

原创 C. 【例题3】单词替换

C.【例题3】单词替换C. 【例题3】单词替换C.【例题3】单词替换解析可以一个个单词读取，输入完之后，讲整个句子的每个单词遍历一次，如果这个单词是与单词aaa相同的话, 就输出bbb, 否则输出这个单词Code#include <bits/stdc++.h>using namespace std;int k; char c;string s[105], a, b;int main (){ while (1) { cin >> s[k ++]

2021-03-24 17:12:24 1686

原创 B. 【例题2】移位包含

解析判断是否是子串,可以将这个一个环#include <bits/stdc++.h>using namespace std;int f = 0;string a, b;int main() { cin >> a >> b; for (int i = 0; i < a.size (); ++ i) { char c = a[0]; a = a.substr (1, a.size() - 1); a = a + c; ..

2021-03-20 16:35:31 108

原创 C. 【例题3】单词替换

解析字符串的操作#include <bits/stdc++.h>using namespace std;int f = 0;string a, b;int main() { cin >> a >> b; for (int i = 0; i < a.size (); ++ i) { char c = a[0]; a = a.substr (1, a.size() - 1); a = a + c; if (a.fin..

2021-03-20 09:31:34 119

原创 A. 【例题1】数字反转

题目解析字符串的基础操作，注意判断零即可#include <bits/stdc++.h>using namespace std;int i;char c[15];int main (){ scanf ("%s", &c); if (c[0] == '-') { i = 1; printf ("-"); } for (int j = strlen (c) - 1; j >= i; -- j) { if (c[j] - 48 != 0) ..

2021-03-19 20:30:37 89

原创 [BFS]A. 【例题1】走迷宫

A.【例题1】走迷宫A. 【例题1】走迷宫A.【例题1】走迷宫解析简单的BFS模板题Code#include <bits/stdc++.h>#define N 1005using namespace std;const int dx[5] = {0, 1, -1, 0, 0};const int dy[5] = {0, 0, 0, 1, -1};int n, sx, sy, tx, ty;int st[N * N][4], a[N][N], f[N][N];i

2021-03-05 18:43:21 154

原创 [深搜]C. 【例题3】虫食算

C.【例题3】虫食算C. 【例题3】虫食算C.【例题3】虫食算题目解析正解 : Dfs + 剪枝依题意,把样例以加法的形式展现出来.根据加法的性质,可以得出有两种情况:有进位和没有进位的.而从百位到最高位的结果,又可能是有从上一位进过一的.因为三个字符串的长度都为nnn,所以最高位是没有进一的根据以上的结论,容易得出A+B=E ∣∣ A+B+1=EA+B=E ~~~||~~~A+B+1=EA+B=E &nb

2021-02-16 17:59:05 443

原创八年级上学期期末考试总结

八年级上学期期末考试总结八年级上学期期末考试总结八年级上学期期末考试总结我愿用四个字来形容这次考试 :死于非命死于非命死于非命为什么这么说呢,先看智学网的成绩查询:总的来说,主科考的很差,非常差.特别是语文,期中考试的时候我还在地表层,一到期末考试的时候就到地核层了,但机房的大爷们早就在大气层了/kk由于没有算口语,所以英语的总分只有90分,但按照我口语成绩之差,也是可以预算出我口语的成绩大概是在252525~282828之间徘徊了.话说我在家疯狂腐败,在学校也是没有复习到多少主科,所以这

2021-02-01 07:09:22 306

空空如也

空空如也