- 博客(296)
- 资源 (2)
- 收藏
- 关注
RSS订阅
原创 Phpstudy中使用cmd进入mysql命令行模式
找到phpstudy中的mysql可执行文件所在的位置输入命令mysql -u root -p然后输入密码（注意这里的root是phpstudy里面root数据库的用户名）成功进入cmd模式是下面的界面：
2020-11-30 22:01:03
4199
原创 【分块入门】LOJ 数列分块入门 1 - 9 (学习更新……)
dl题解_「分块」数列分块入门1 – 9 by hzwerLOJ #6277. 数列分块入门 1题意：给出一个长为n的数列，以及n个操作，操作涉及区间加法，单点查值。 时间限制：100ms分块我们将整个数列划分为很多块，暂且分为n / m块，用block[ i ]记录第 i 个数据arr[ i ]对应的块的个数。O(n)【数据读入时就可以操作完成，block[ i ] = (i ...
2020-01-16 14:49:57
1974
1
原创 T176273 Hazardous【dsu on tree】
题目链接题意：给定一棵 nnn 个结点的树，根固定为 111，每个结点有一个颜色。对于结点 uuu，它的值定义为子树 uuu 中任意两个相同颜色的结点的距离之和。我们需要得到每棵子树的值并输出。思路：对于子树 uuu，我们假设它有 xxx 个儿子，我们假定这些儿子的编号为 1,2,3,...,x1, 2, 3, ..., x1,2,3,...,x我们假设每个结点 iii 的颜色是 c[i]c[i]c[i]，深度是 d[i]d[i]d[i]我们统计一个后缀和 sum[i]sum[i]sum[i
2021-04-27 20:14:26
178
原创 Switches
2020-2021 ACM-ICPC, Asia Seoul Regional Contest - J. Switches【线性基模板】判断某个数能不能由线性基基向量异或得到
2021-04-06 19:19:35
182
原创 HDU - 3530【单调队列】
Subsequence题意给定一个长度为 nnn 的序列，给定一个范围 [m,k][m, k][m,k]。我们需要找到一个最长的连续子序列，满足这个子序列中最大值和最小值的差值在给定的范围 [m,k][m, k][m,k] 内，输出满足条件的最长连续子序列的长度。思路很显然，对于某个位置 iii 作为左端点的连续子序列，其最大值和最小值的差值是单调不减的。所以对于原始序列，我们维护一个单调增队列 INCINCINC 和一个单调减队列 DECDECDEC。显然我们要找的最值的差值就是 dif=D
2021-01-18 09:39:57
146
原创 F. Strange Memory
题目链接题意：给定一个结点个数为 nnn 的根为 111 的有根树，每个结点有一个权值 a[i]a[ i ]a[i]。我们需要找到所有满足 KaTeX parse error: Can't use function '\^' in math mode at position 6: a[u] \̲^̲{} a[v] == a[lc… 的点对 u,v{u, v}u,v ，统计所有这些点对 KaTeX parse error: Can't use function '\^' in math mode at p
2020-11-26 21:59:53
550
原创 树链剖分模板
P3384 【模板】轻重链剖分题意已知一棵包含 N 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：操作 1： 格式： 1 x y z 表示将树从 x 到 y 结点最短路径上所有节点的值都加上 z。操作 2： 格式： 2 x y 表示求树从 x 到 y 结点最短路径上所有节点的值之和。操作 3： 格式： 3 x z 表示将以 x 为根节点的子树内所有节点值都加上 z。操作 4： 格式： 4 x 表示求以 x 为根节点的子树内所有节点值之和。思路先将树轻重链剖分后，遍历整棵
2020-11-01 20:09:36
123
原创 E. Even Degree 【欧拉回路】
题目链接题意给一张图，当结点u，v的度不都是奇数时，我们可以删掉结点u，v之间的边。问：最多能删掉多少条边，并按照删除的顺序输出边的序号。题目不保证图是连通的，但是保证所有点的度在初始时都为偶数，也就是保证每个连通块都是一个欧拉回路。思路对于一个欧拉回路，我们先假装删除一条边让其变成一个欧拉通路，此时存在两个奇数度点。我们选择一个作为起点，一个作为终点。我们 dfs 从起点遍历到终点，在回溯时才往栈中存边，那么从栈底到栈顶就是正确的合法路径。问题是怎么找到这个路径呢？在欧拉通路中删边时，我
2020-10-17 10:32:08
1751
4
原创 CF 1425 - E. Excitation of Atoms
题目链接题意：给 nnn 个原子。每个原子有两种状态，静态和激发态。每个原子 iii 从静态转换到激发态需要消耗 d[i]d[i]d[i] 的能量，而在激发态会贡献的 a[i]a[i]a[i] 的能量。初始的时候，序号从 1−n1-n1−n 的原子是按照编号顺序连接在一起的，也就是原子 iii 连接到原子 i+1i + 1i+1。在激发原子时有一个连锁反应，就是被激发的原子会自动激发它连接的下一个原子，这个时候是不会消耗能量的。但是最后一个原子不能连接到任何一个原子。给定 KKK，我们必须要改变 K
2020-10-07 01:42:55
217
原创 CF - 19D【线段树】
D. Points题意：在笛卡尔坐标系上有 n 个操作，添加点 (x, y)，删除点 (x, y) 和查询点 (x, y) 的最近的右上角的点 (x1, y1) 【在保证(x1 - x)最小的基础上寻找(y1-y)最小】思路1：横纵坐标的范围很大，所以我们对横纵坐标离散化，然后对离散后的横坐标用线段树维护，线段树维护横坐标 x 对应竖直线上点的个数。我们用 set 存储横坐标 x 对应竖直线上点的集合。点的添加和删除操作直接跑到叶子节点对 set 进行insert或者erase即可。查询点 (x,
2020-09-26 10:23:15
254
原创 power oj 2885: 连续段
题目链接题意：给一个长度为 nnn 的排列，m次询问区间 [l,r][l, r][l,r] 的连续段(相邻的数构成连续段，比如1、2、3；2、3、4)的数目。题目强制在线。思路：在区间 [l,r][l, r][l,r] 中，对于区间内任意一个数 xxx 来说，如果它可以作为连续段的起始位，那么它的前驱 x−1x - 1x−1 的位置一定在区间 [l,r][l, r][l,r] 外。所以我们只需要统计，区间内所有元素中前驱的位置在区间 [l,r][l, r][l,r] 外的元素个数，即是连续段的个数
2020-09-24 15:44:23
229
原创 CF 1406-D
D. Three Sequences题意：给一个长度为 nnn 的数组 aaa ，构造两个相同长度的数组 bbb，ccc 。要求：b[i]+c[i]=a[i]b[ i ] + c[ i ] = a[ i ]b[i]+c[i]=a[i]，并且数组 bbb 单调不减，数组 ccc 单调不增。让我们最小化max(b[n],c[1])max(b[ n ], c[ 1 ])max(b[n],c[1])，并且输出。除了初始数组，会有 qqq 次区间加操作，对于每次更新完的数组 aaa，同样要输出max(b[
2020-09-16 21:46:22
124
原创 CF 1167B - Lost Numbers
CF 1167B - Lost Numbers交互题题意：猜 4,8,15,16,23,42{4, 8, 15, 16, 23, 42}4,8,15,16,23,42 的排列。至多问4次，每次询问 {i,j}\{i, j\}{i,j}，可以得到 a[i]∗a[j]a[i] * a[j]a[i]∗a[j] 的结果。输出排列。思路：依次询问{1,2}\{1, 2\}{1,2} {2,3}\{2, 3\}{2,3} {3,4}\{3, 4\}{3,4} {4,5}\{4, 5\}{4,5} 可以依次得到每一
2020-09-12 20:41:42
244
原创 CodeForce 1407C
交互题题意：猜一个排列 a[1...n]a[1...n]a[1...n] 。通过 “? i j? \ i \ j? i j” 的方式提问 a[i]%a[j]a[i] \% a[j]a[i]%a[j] 的答案是多少，最多提问 2n2n2n次。输出“!”，然后输出排列。思路：因为是排列，没有重复数字，所以a[i] 和 a[j]一定有大有小。我们通过提问 a[i]%a[j]a[i] \% a[j]a[i]%a[j] 和 a[j]%a[i]a[j] \% a[i]a[j]
2020-09-12 15:16:24
152
原创 CF 1398C
C - Good Subarrays题意：给一个长度在1e5之内的大数，把大数的每一位看成一个10以内的个位数，问区间和等于区间长度的区间个数有多少个？思路：定义 prefix[x] 表示区间 [1, x) 的前缀和。对于区间[l, r)，满足题意则有 prefix[r]−prefix[l]==r−lprefix[r] - prefix[l] == r - lprefix[r]−prefix[l]==r−l 由此可得：prefix[r]−r==prefix[l]−lprefix[r] - r == p
2020-09-04 19:49:15
234
原创 CodeForces 1399D
Binary String To Subsequences题意：给一个01串，要从里面摘出来01相间的子序列，问在满足条件的情况下最少子序列的数目是多少？思路：遍历01串，如果是0就加到结尾字符是1的子序列末尾；如果是1就加到结尾字符是0的子序列末尾。这里就只需要记录一下最新的结尾是0或1的子序列的标号，以及该标号下的上一个结尾是0或1的子序列的标号，类似链式前向星的意思。遍历过程中更新最新的标号和上一个标号即可，同时记录答案即可。#include <bits/stdc++.h>#d
2020-09-03 11:00:17
149
原创 HDU - 6755 Fibonacci Sum【Fibonacci数列的幂和】
### [题目链接](http://acm.hdu.edu.cn/showproblem.php?pid=6755)- 题意：给定 $N,C,K$，求$({F_{0}}^K+{F_{C}}^K+{F_{2C}}^K+...+{F_{NC}}^K) \ mod\ 1e9+9$，其中$F_i$是 $Fibonacci$ 数列的第 $i$ 项。---##### 思路：三个前置知识：1. $Fibonacci$ 数列的通项公式：$F_n=\frac{1}{\sqrt{5}}[(\frac{1+\sqr
2020-07-23 00:17:57
225
原创 【分块+二分】HDU 4417
Super Mario多组数据注意初始化#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <vector>#include <algorithm>#define INF 0x3f3f3f3fusing namespace std;typedef long long ll ;int read(){
2020-07-08 12:30:21
146
原创 【除法分块】power oj 2886
大力出奇迹∑i=lrx%(k∗i)=∑i=lr(x−(k∗i)∗⌊xk∗i⌋)=x∗(r−l+1)−∑i=lr(k∗i)∗⌊x/ki⌋\displaystyle \sum^{r}_{i=l}{x \% (k*i)}= \displaystyle \sum^{r}_{i=l}{(x-(k*i)*\lfloor \frac{x}{k*i} \rfloor)}\\=x*(r-l+1)-\displaystyle \sum^{r}_{i=l}{(k*i)*\lfloor \frac{x/k}{i}\rfloor}
2020-07-08 12:27:10
147
原创 POJ 3041【最小点覆盖】
POJ 3041 Asteroids最小点覆盖：选择一个点能够与它相连的所有边，选择一个最小的点集能够覆盖二分图中所有的边。最小点覆盖==最大匹配匈牙利算法求解#include <iostream>#include <cstdio>#include <cstring>#define INF 0x3f3f3f3f#define lowbit(x) x & (-x)using namespace std;typedef long long ll;
2020-06-25 16:46:17
214
原创 POJ - 1087【匈牙利匹配】
A Plug for UNIX题意：房间里有n个不同的插口，有m个设备，每个设备对应一种插口。有k个插口转换器（a, b:表示该转换器可以将插口b转为a），转换器可以插在对应的初始的n个插口，也可以插在对应的转换器上。要使得设备匹配插口最大，求未能匹配的设备数量。（转换器的数量无限）思路：如果一个设备对应的插口x可以由转换器级联得到，那么该设备实际上是对应了所有和x在一个网络中的插口。所以我们根据所有k组转换器信息做成一个有向图（由a指向b），这样的话我们从每个设备对应的插口进行深搜，即可得到设备
2020-06-17 20:14:31
132
原创 Plants vs. Zombies【二分】
ZOJ - 4062 Plants vs. ZombiesBaoBao and DreamGrid are playing the game Plants vs. Zombies. In the game, DreamGrid grows plants to defend his garden against BaoBao’s zombies.题意：植物大战僵尸一个长度为 nnn 的数组 array[1,n]array[1,n]array[1,n]，初始值为0，每个元素有各自的增长速度a[i]a[i]
2020-06-16 22:28:43
586
原创 CF1366D
## Two Divisors#### 题意：n个1e7内的数，求每个数的两个因子$d_1、 d_2$，满足$gcd(d_1+d_2, a[i])=1$. 如果$d_1、 d_2$不存在，那么输出-1##### 以下：对$a[i]$进行质因数分解：$a[i]=p_1^{s_1}p_2^{s_2}...p_k^{s_k}$我们把$p_1,p_2,...,p_k$分成两个集合$\{p_1,p_2,...,p_x\}$和$\{p_{x+1},p_{x+2},...,p_k\}$使$d_1=p_1p_
2020-06-15 21:28:09
180
原创 CodeForces - 1338A
Powered Addition题意：给一个序列，从时刻 x=1x = 1x=1 开始，每个时刻 x，我们可以从序列中选择一个子序列（不必须连续），该子序列中的每个值都加上 2x−12^{x-1}2x−1 ，当然子序列可以为空。我们需要得到一个升序的序列，问需要最少的时间是多少？思路：直接贪心使得每个 aia_iai 都等于序列 [a1,ai][a_1, a_i][a1,ai] 中的最大...
2020-04-25 09:17:15
160
原创 求和
题目链接题意：求子树结点权值和思路：得到树的dfsdfsdfs 序，将子树操作转化为区间操作。树状数组单点更新，区间查询。#include <bits/stdc++.h>#define lowbit(x) x & (-x)using namespace std;typedef long long ll;const int maxN = 1000006;int ...
2020-04-25 08:39:11
154
原创 提升vector性能的几种方法 & 线性求容器中第k小
提升 vectorvectorvector 性能的几种方法：提前分配空间向 vectorvectorvector 插入元素时使用 emplace_back()emplace\_back()emplace_back() 而非 push_back()push\_back()push_back()在填充或者拷贝 vectorvectorvector 的时候，使用赋值，而非 insert()ins...
2020-04-06 15:35:30
317
原创 【带权并查集 He 种类并查集 详详详详详详详hhh】经典例题
POJ 1182 食物链 之 两种解法 de 详解：带权并查集、种类并查集。真详解，窝窝窝，窝不骗人！要记得当初横冲直撞的那个一步步追寻的我~ 博文完结撒花撒花撒花~~~~
2020-04-04 19:02:54
275
原创 U41492 树上数颜色【dsu on tree】
题目链接题意：有一棵以 111 为根结点的树，树上每个结点有一个颜色，多组询问：问以 uuu 为根的子树上共有多少种不同的颜色。解决该题，最暴力的做法就是对于每一棵子树都dfs一遍统计出答案，统计完清空：O(n2)O(n^2)O(n2)。但“听说”可以用dsu on tree优化：dsu on tree [ O(nlogn)O(nlogn)O(nlogn) ]统计以结点 uuu 为根结点...
2020-04-04 14:45:52
647
原创 Codeforces Round #630 (Div. 2)
A. Exercising Walk题意：小猫初始位置在(x,y)(x,y)(x,y)，要求小猫左右下上各走a、b、c、da、b、c、da、b、c、d步。限制小猫咪必须在左下角为(x1,y1)(x_1, y_1)(x1,y1) 右上角为(x2,y2)(x_2, y_2)(x2,y2) 的区域内。问小猫咪是否能够完成任务？思路：首先应该判断小猫咪是否可以移动：左右任意一个方向要...
2020-04-01 17:04:51
293
原创 操作集锦
题目链接题意：长度为 nnn 的字符串中有多少个长度为 kkk 并且不同的子序列。定义 dp[i][j]dp[i][j]dp[i][j] 表示截至 s[i−1]s[i-1]s[i−1] 为止，长度为 jjj 的子序列的个数dp[i][j]=dp[i−1][j]+dp[i−1][j−1]dp[i][j]=dp[i-1][j]+dp[i-1][j-1]dp[i][j]=dp[i−1][j...
2020-03-31 20:49:09
104
原创 拉普兰德的愿望【切比雪夫距离+树状数组】
题目链接题意：给出n个点的坐标，求曼哈顿距离不小于d的点对数。我们将坐标①(x,y)(x,y)(x,y)变换为②(x+y,x−y)(x + y, x - y)(x+y,x−y)，那么①的曼哈顿距离等于②的切比雪夫距离。切比雪夫距离dis=max(x2−x1,y2−y1)dis=max(x_2-x_1, y_2-y_1)dis=max(x2−x1,y2−y1)那么对于点 iii 来...
2020-03-30 23:01:16
183
原创 P3964 [TJOI2013]松鼠聚会【切比雪夫距离】
P3964 [TJOI2013]松鼠聚会题意：给出nnn个点(xi,yi)(x_i,y_i)(xi,yi)，找到某个点，使得所有点到该点的切比雪夫距离和最小。一、A(x1,y1),B(x2,y2)A(x_1, y_1), B(x_2, y_2)A(x1,y1),B(x2,y2)三种距离：①欧几里得距离：(x2−x1)2+(y2−y1)2\sqrt{(x_2-x_1)^2 ...
2020-03-30 20:14:30
184
原创 求解逆序数
两行代码vector求逆序数（冒泡）冒泡排序是保证前面冒完的泡泡是有序的~，所以说，我们可以直接利用这一点，二分找到要插入的数值应该在哪个位置，那么原位置减去当前应该在的位置就是它的逆序数#include <iostream>#include <algorithm>#include <cstdio>#include <vector>usi...
2020-03-27 22:34:27
227
原创 计算1至n中数字x出现的次数
题目：计算1至n中数字x出现的次数直接炒栗子！如果x=[1,9]2059 5个位：205个10，205∗1+1205*1+1205∗1+1：[1,2050)+[2050, 2059] 个位9>5十位：20个100，20∗10+(9+1)20*10+(9+1)20∗10+(9+1)：[1,2000)+[2000,2059] 十位5=5百位：2个1000，2∗1002*1002∗10...
2020-03-27 16:08:41
727
原创 记录一些CF-DP题(qwq)
CodeForces 1195C Basketball Exercise题意：有两排小哥哥，每排都有nnn个小哥哥。我们要从这2n2n2n个小哥哥里选择任意个，使得这些小哥哥的身高总和最大（花痴脸）. 限制我们选择的小哥哥不能是一排中相邻的两个。思路：定义dp[ ][3]dp[ \ ][3]dp[ ][3]其中dp[pos][0]dp[pos][0]dp[pos][0]表...
2020-03-26 22:07:47
249
2
原创 CodeForces 1326D2【Manacher】
Prefix-Suffix Palindrome (Hard version)题意：给定一个串sss，找出一个回文串ttt，使得ttt = s.prefixs.prefixs.prefix + s.suffixs.suffixs.suffix，并且ttt的长度不大于sss.思路：ManacherManacherManacher算法中radius[i]radius[ i ]radius...
2020-03-20 14:51:59
259
原创 CodeForces 1326D2【前缀数组next[ ]】
Prefix-Suffix Palindrome (Hard version)题意：给定一个串sss，找出一个回文串ttt，使得ttt = s.prefixs.prefixs.prefix + s.suffixs.suffixs.suffix，并且ttt的长度不大于sss.思路：我们找到最大的ppp，使得s[0]=s[len−1],s[1]=s[len−2],...,s[p]=s[l...
2020-03-20 13:59:11
235
原创 C++_内联函数 带默认形参值的函数 重载函数 constexpr 取整 点灯
/*NO.1 内联函数（1）内联函数是在“编译时”将函数体嵌入在每一个调用处，相当于宏定义define（2）inline关键字只是表示一个要求，编译器并不承诺将inline修饰的函数作为内联（3）在现代编译器中，没有用inline修饰的函数也可能被编译为内联（4）内联函数应该是比较简单的函数，结构简单，语句少，频繁调用（5）带有递归调用或者循环的函数不能以内联方式处理*//*...
2020-03-16 21:20:53
272
原创 HDU - 4292【最大流_拆点_建图】
Food题意：有nnn个人，有fff种食物，ddd种饮料，问能拿到自己钟意的食物和饮料的人最多有多少？思路s−food−people1−people2−drink−ts - food - people1 - people2 - drink - ts−food−people1−people2−drink−t【people1people1people1和people2people2pe...
2020-03-12 18:49:34
224
MSP430G2553——中断实现按键单击与双击的识别
2020-09-24
MSP430G2553——中断实现长短按键识别
2020-09-24
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人