- 博客(306)
- 收藏
- 关注
RSS订阅原创 平均要抛多少次硬币，才能出现连续N次正面向上？
为了计算这个期望值，我们可以使用“马尔可夫链”或“状态转移”的方法。状态 S0：当前没有连续的正面，即前一次抛掷不是正面，或者这是第一次抛掷。状态 S1：前一次抛掷是正面，但还没有连续两次正面。状态 S2：已经连续两次正面（即达到目标）。我们的目标是从 S0 开始，计算到达 S2 的期望步数。E0E_0E0：从状态 S0 开始，到达 S2 的期望抛掷次数。E1E_1E1：从状态 S1 开始，到达 S2 的期望抛掷次数。E2E_2E2。
2025-04-07 17:11:28
860
原创 PE362
为一个非递降一个序列，其中都是squarefree number，且第一项。考虑序列的长度为1和大于的情况。我们不考虑计算某一个数的。start且，序列的乘积。考虑如下序列的个数为。那么最终答案表达式为。
2024-09-06 19:10:02
743
1
原创 带删除的并查集
我们可以通过给每个元素设置一个虚拟父节点，每次移动的时候操作的是实际的节点，而不是父节点即可完成。因为这个时候操作的节点都是叶子节点，不会有副作用。也移动过去，这不是我们想要的。（这里借用luogu题解区的图片）开始，因此在输入输出的时候有特殊处理。所在的集合，会同时也把1的儿子节点。操作1和3是基本的并查集的操作.若使用朴素的并查集，把节点。
2023-12-01 20:21:35
381
原创 线段树题目
一排灯初始是关闭的，每次可翻转一个区间的等的状态，每次询问一个区间内亮的等的个数。给一个01序列，支持区间修改为0或1，区间取反，询问区间1的个数，询问区间最多连续1的个数。01序列，支持单点修改一个点，询问区间内的最长无相相邻数字连续串的长度。支持区间修改，询问区间内不同颜色个数。二维坐标系，支持添加点，删除点，询问一个点最左边的点的坐标。处减去末项. 转化为区间修改，区间求和的问题。支持区间加，询问区间平均数，询问区间方差。支持区间加，区间修改，询问区间最大值。支持区间加，区间乘，求区间和。
2023-11-21 18:45:18
121
原创 基本计算器问题
这里面设计到的一个共同的问题就是计算一个表达式的值的问题，我们可以使用递归或者栈的方式来解决这个问题。实际上递归也是栈的应用，两种方法是一样的。这个是vip题目，可以在这里。看到替代的题目，是一样的。支持加减乘除和括号操作。
2023-10-26 13:34:40
117
原创 LeetcodeN数之和问题(N sum问题)
做法: 先排序，然后枚举i, j, 然后双指针算法，时间复杂度为O(N^3)分组，然后使用哈希表统计，时间复杂度为O(N^2)排序，然后双指针. 时间复杂度为O(N^2)题目要求去掉重复的方案.
2023-10-25 17:47:07
304
原创 Leetcode股票买卖问题
Leetcode上一类股票交易问题，分为可交易一次/多次/K次等等，以及有无手续费，冷冻期等等。在每一天，你可以决定是否购买和/或出售股票。dp[i][0]表示第i天交易后手里没有股票的最大利润。dp[i][1]表示第i天交易后手里持有股票的最大利润。注意到每一个状态只和上一天有关，可以优化一下代码。你也可以先购买，然后在。即可，不间更新ans。
2023-10-25 15:52:56
156
原创 Leetcode链表问题汇总
假设链表存在环，则当第一个指针走到环入口时，第二个指针已经走到环上的某个位置，距离环入口还差 x 步。由于第二个指针每次比第一个指针多走一步，所以第一个指针再走 x步，两个指针就相遇了。用两个指针从头开始扫描，第一个指针每次走一步，第二个指针每次走两步。否则如果两个指针相遇，则说明存在环。比较简单的题目，头结点标示的个位数字，因此直接模拟就可以了。注意链表相关的题目可以添加一个虚拟头节点，用来简化一些边界情况的处理。复杂度分析，由于慢指针走的总步数小于链表总长度，复杂度为。
2023-10-24 23:04:07
336
原创 PE157
题意：求1a+1b=p10n\frac{1}{a} + \frac{1}{b} = \frac{p}{10^n}a1+b1=10np的正整数解(1≤n≤9)(1 \leq n \leq 9)(1≤n≤9)对原式进行变化1a+1b=p10n\frac{1}{a} + \frac{1}{b} = \frac{p}{10^n}a1+b1=10np1a+1b=p10n\frac{1}{a} + \frac{1}{b} = \frac{p}{10^n}a1+b1=10npabp2−10np(
2021-12-22 11:26:19
248
原创 小圆前辈的素数(FFT)
题目链接：https://ac.nowcoder.com/acm/contest/15332/B题目大意：给了两个数组a和b，任意从a中取一个数a[i]和b数组中取一个数b[i]，求满足a[i] + b[i]是素数的取法有多少种？数组长度 <= 1e5示例：a = {1, 2, 2}b = {3, 4, 6}满足条件的答案有四种:{1, 4}, {1, 6}, {2, 3}, {2, 3}解答：朴素的两重暴力枚举时间复杂度是O(N^2)无法AC本题。我们
2021-07-22 00:48:10
235
原创 隐藏Leetcode上带锁的题目
打开chrome的控制台输入一下js代码，回车执行$("tbody.reactable-data > tr > td:nth-child(3) > div > span:nth-child(2)").each(function(index, element) { $(element).hide();});
2021-06-17 01:00:54
424
原创 数组模拟几种队列的写法
1、普通队列队列数组名为q[N]初始化hh = 0, tt = -1, 队列的元素区间为[hh, tt]入队：q[++tt] = val;出队: hh++队头元素: q[hh]判空: hh <= tt 表示非空, hh > tt 队列为空2、循环队列（下列所有加减法都是在mod(N+1)的意义下）队列数组名q[N + 1], 循环队列最多存储N个元素，是为了区分队空和队满的情况初始化hh = tt = 0, 队列的元素区间为[hh, tt)，这里右侧为开.
2021-05-26 00:49:37
239
原创 Leetcode设计数据结构O(1)数据结构
LRU:struct Node { Node *l, *r; int key, val; Node(int _key, int _val) :key(_key), val(_val) {}}*head, *tail; //两个哨兵class LRUCache {public: int n; unordered_map<int, Node*> hash; //从双链表删除掉p节点 void remove(Node* p) {
2021-05-25 01:36:15
286
原创 树的迭代遍历问题
94. 二叉树的中序遍历/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector<int>
2021-05-25 01:24:39
127
原创 Leetcode一类区间问题总结
56、区间合并https://leetcode-cn.com/problems/merge-intervals/先按照左端点排序，左端点相同按照右端点排序，依次合并区间即可。class Solution {public: vector<vector<int>> merge(vector<vector<int>>& intervals) { typedef pair<int, int> PII;
2021-05-24 23:45:39
353
1
原创 acwing 3115 bzoj2054 疯狂的馒头
https://www.acwing.com/problem/content/3118/做法：并查集逆序枚举，因为最后染色的就是最后的颜色。find(f[i])表示为右边第一个没有被染色的点，通过f数组跳过已经被染色的区间。#include <bits/stdc++.h>using namespace std;//Filename: 3115.cpp////Author: dezhonger - csdisassembly@gmail.com//Create: .
2021-05-03 00:31:12
129
原创 树形dp
题单：https://www.luogu.com.cn/training/4840#problems两道类似的题目https://www.luogu.com.cn/problem/P2014#include <bits/stdc++.h>using namespace std;//Filename: 2014.cpp////Author: dezhonger - csdisassembly@gmail.com//Create: 2021-04-11 23:00:55
2021-04-12 00:02:31
120
原创 codefoces round713 div3
简要题解：A：题意：给了一堆数(n >= 3)，有一个和其他不一样，找出来这个数排序后，a[1]肯定是相同的数，找到和a[1]不同的数就是答案B:找到两个'.'变为'*'，使得四个'*'构成一个矩形讨论三种情况即可C:把问号变为0或者1，其中0的个数为a，1的个数为b首先把?能确定的字符确定好，然后每次贪心选择剩余a和b最大的那个用来替换?D:给出从a数组构造b数组的规则，给定b数组，求a数组枚举哪个数是最后添加到b数组的数即可。注意考虑细节...
2021-04-11 01:59:25
157
原创 Leetcode hard一句话题解
代码：https://github.com/dezhonger/LeetCode99.Recover Binary Search TreeMorris-traversal算法218: The Skyline Problem 扫描线算法
2021-03-30 23:07:13
205
原创 Leetcode493 Reverse Pairs
求逆序对的问题可以采用归并排序或者BIT数据结构进行求解，这里给出归并排序的做法，核心是在递归的时候，使用双指针维护左边i和右边j的位置，保证j是最小的a[i] <= 2 * a[j], 那么所有小于j的下标都是对答案的贡献红色即为贡献class Solution {public: vector<int> w; int reversePairs(vector<int>& nums) { return merge(nums,.
2021-02-23 00:00:12
91
原创 模拟退火
https://www.acwing.com/problem/content/3170/求二维平面上的费马点模拟退火：#include <bits/stdc++.h>using namespace std;#define X first#define Y secondtypedef pair<double, double> PDD;const int N = 110;//全局最优解double ans = 1e8;int n;PDD q[N.
2021-01-20 23:00:04
132
原创 P3254 圆桌问题
https://www.luogu.com.cn/problem/P3254https://www.acwing.com/problem/content/2181/网络流建模，同时求出最大流的一个可行流建模如下求可行流的方法：遍历左边的所有节点，在残留网络上跑满了流的边即为一组解#include <bits/stdc++.h>using namespace std;const int N = 430, M = (N + 150 * 270) * 2, INF =
2020-11-14 20:43:18
184
原创 acwing Dinic求最大流
https://www.acwing.com/problem/content/2174/Dinic算法的时间复杂度是O(N^2M)，N为点数，M为边数模板题：#include <bits/stdc++.h>using namespace std;//Filename: Dinic.cpp////Author: dezhonger - csdisassembly@gmail.com//Create: 2020-11-14 18:48:11//时间复杂度: O(N.
2020-11-14 19:17:57
177
原创 acwing EK求最大流
https://www.acwing.com/problem/content/2173/模板题:#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 1010, M = 20010, INF = 1e8;int n, m, S, T;int h[N], e[M], f[M], ne[M], idx;int q[N],
2020-11-14 13:22:58
136
原创 洛谷2146 软件包管理器
树链剖分的模板题#include <bits/stdc++.h>using namespace std;//Filename: 918.cpp////Author: dezhonger - csdisassembly@gmail.com//Create: 2020-11-06 23:58:17typedef long long LL;const int N = 100010;int n, m;int h[N], e[N], ne[N], idx;int id[N],
2020-11-07 00:32:42
117
原创 洛谷3391 文艺平衡树
用splay写一下，模板题。#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 100010;int n, m;struct Node { int s[2], p, v; int size, flag; void init(int _v, in.
2020-11-03 23:30:07
111
原创 java class文件解析
将java class字节码文件按照不同的区域进行解析处理。import java.io.File;import java.io.FileInputStream;import java.io.IOException;import java.io.InputStream;import java.util.Arrays;/** * Created by dezhonger on 2020/09/26 * <p> * javaClass文件解析 */public class
2020-10-01 11:29:25
1189
原创 2-SAT 模板题
题目链接：https://www.luogu.com.cn/problem/P4782讲解:todo#include <bits/stdc++.h>using namespace std;const int N = 2000010, M = 2000010;int n, m;int h[N], e[M], ne[M], idx;int dfn[N], low[N], ts, stk[N], top;int id[N], cnt;bool ...
2020-09-16 00:27:59
164
原创 P2257 YY的GCD
题意\large题意题意题目链接给定N,M，求1≤x≤N,1≤y≤M且gcd(x,y)为质数的(x,y)有多少对给定N, M，求1 \leq x \leq N, 1 \leq y \leq M且 gcd(x, y)为质数的(x, y)有多少对给定N,M，求1≤x≤N,1≤y≤M且gcd(x,y)为质数的(x,y)有多少对用式子表达出来为用式子表达出来为用式子表达出来为∑i=1n∑j=1m[gcd(i,j)=k],k∈Prime\sum_{i=1}^{n} \sum_{j=1}^{m} [gcd(i,
2020-08-02 00:34:37
137
原创 P3455 [POI2007]ZAP-Queries
题意\large题意题意题目链接求∑i=1a∑j=1b[gcd(i,j)=d]求\sum_{i=1}^{a} \sum_{j=1}^{b} [gcd(i, j) = d]求∑i=1a∑j=1b[gcd(i,j)=d]题解\large题解题解莫比乌斯函数有个性质莫比乌斯函数有个性质莫比乌斯函数有个性质∑d∣nμ(d)=[n=1]\sum_{d|n} \mu(d) = [n = 1]d∣n∑μ(d)=[n=1]我们使用gcd(i,j)代替n得到如下的式子我们使用gcd(i, j)代替n得到
2020-08-01 01:22:53
286
1
原创 洛谷4318 完全平方数
题意:题意:题意:求第k个不含平方因子的数求第k个不含平方因子的数求第k个不含平方因子的数题解:题解:题解:我们可以题目转为求给定n，求n以内的无平方因子数的个数，然后二分得到结果\qquad我们可以题目转为求给定n，求n以内的无平方因子数的个数，然后二分得到结果我们可以题目转为求给定n，求n以内的无平方因子数的个数，然后二分得到结果求n以内的无平方因子数的个数，即求求n以内的无平方因子数的个数，即求求n以内的无平方因子数的个数，即求∑k=1nμ2(k),这里μ是莫比乌斯函数\sum_{k=1}
2020-07-30 02:15:22
180
原创 洛谷2568 GCD
文章目录题意题意题意题解题解题解代码代码代码题意题意题意给定n,求∑i=1n∑j=1n[gcd(i,j)=k]，k is prime给定n,求\sum_{i=1}^{n} \sum_{j=1}^{n} [gcd(i, j) = k]， k\ is \ prime给定n,求i=1∑nj=1∑n[gcd(i,j)=k]，k is prime题解题解题解原式=∑k∑i=1n∑j=1n[gcd(i,j)=k]=∑k∑i=1n/k∑j=1n/k[gcd(i,j)=1
2020-07-30 01:15:14
192
原创 洛谷1390 公约数的和
题意:题意:题意:求∑i=1n∑j=i+1ngcd(i,j)求\sum_{i=1}^{n} \sum_{j=i+1}^{n}\gcd(i, j)求i=1∑nj=i+1∑ngcd(i,j)题解:题解:题解:原式=∑i=1n∑j=i+1ngcd(i,j)=∑d=1nd⋅∑i=1n∑j=i+1n[gcd(i,j)=d]=∑d=1nd⋅∑i=1n/d∑j=i+1n/d[gcd(i,j)=1]=∑d=1nd⋅∑j=1n/dϕ(j)\begin{aligned}\qquad\qquad\qquad 原式
2020-07-30 00:57:54
152
原创 P2303 [SDOI2012] Longge 的问题
输入一个数据nnn，求∑i=1ngcd(i,n)\qquad \qquad \qquad \sum_{i=1}^{n}\gcd(i, n)∑i=1ngcd(i,n)其中nnn可以达到 2322^{32}232题解：原式=∑i=1ngcd(i,n)=∑d∣nd⋅∑i=1n[gcd(i,n)=d](枚举公约数,[]为单位函数)=∑d∣nd⋅∑i=1⌊n/d⌋[gcd(i,nd)=1]=∑d∣nd⋅ϕ(⌊nd⌋)\begin{aligned}\qquad\qquad\qquad 原式 &
2020-07-29 23:59:03
597
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人