搜索结果
查询Tags标签： 1e9，共有 13条记录-
CF1710D Recover theTree
题意： 给定每个区间是不是连通块，还原这棵树。(\(n\leqslant 2000\)) 题解： 我肯定是做不出来，也不理解是怎么想的。不如直接讲做法，然后证明正确性，也是对 wc 题解的补充。 先贴个代码： #include<bits/stdc++.h> using namespace std; const int maxn=2e5+1…
2022/8/27 6:23:13 人评论 次浏览 -
基础算法
区间合并：#include <bits/stdc++.h>using namespace std; typedef pair <int,int> pii; vector<pii>pos; void merge(vector<pii>&pos) {vector <pii>ans;sort(pos.begin(),pos.end());int st=-1e9+10,ed=-1e9+10;for (auto ver:pos){…
2022/4/29 20:13:17 人评论 次浏览 -
ARC130 题解
A. Remove One Character 容易发现 \(i,j\) 产生贡献当且仅当 \(\forall k\in[i,j],a_i=a_k=a_j\)，于是对于每个连通块分别计算贡献即可。 #include<bits/stdc++.h> using namespace std; #define inf 1e9 const int maxn=2e5+10; const int mod=1e9+7; inline int…
2022/3/30 6:19:25 人评论 次浏览 -
算法第一次作业（递归）
A Fibonacci题目描述 定义一个数列f(i) = f(i-1)+f(i-2), f(0) = 0, f(1) = 1. 求f(n) mod (1e9+7) 输入数据 一个正整数n，n<=1e5 输出数据 f(n) mod (1e9+7)标准斐波那契问题，可以递归可以循环；可以数组保存可以直接变量保存 使用递归会超时 注意mod(1e9). 为什么…
2022/3/20 22:27:46 人评论 次浏览 -
53. 最大子序和【DP常见的模型】
https://leetcode-cn.com/problems/maximum-subarray/ 状态表示: f[i]表示以i结尾的最大子段和 即f[i]=max(f[i-1]+nums[i],nums[i]) => f[i]=max(f[i-1],0)+nums[i] class Solution { public:int f[100100];int maxSubArray(vector<int>& nums) {for(int i…
2021/11/4 23:41:24 人评论 次浏览 -
53. 最大子序和【DP常见的模型】
https://leetcode-cn.com/problems/maximum-subarray/ 状态表示: f[i]表示以i结尾的最大子段和 即f[i]=max(f[i-1]+nums[i],nums[i]) => f[i]=max(f[i-1],0)+nums[i] class Solution { public:int f[100100];int maxSubArray(vector<int>& nums) {for(int i…
2021/11/4 23:41:24 人评论 次浏览 -
子数组最小乘积的最大值
题目 一个数组的最小乘积定义为这个数组中最小值乘以数组的和 。 比方说，数组 [3,2,5] （最小值是 2）的最小乘积为 2 * (3+2+5) = 2 * 10 = 20 。 给你一个正整数数组 nums ，请你返回 nums 任意非空子数组的最小乘积的最大值。由于答案可能很大，请你返回答案对1e9+7取…
2021/11/2 6:09:43 人评论 次浏览 -
子数组最小乘积的最大值
题目 一个数组的最小乘积定义为这个数组中最小值乘以数组的和 。 比方说，数组 [3,2,5] （最小值是 2）的最小乘积为 2 * (3+2+5) = 2 * 10 = 20 。 给你一个正整数数组 nums ，请你返回 nums 任意非空子数组的最小乘积的最大值。由于答案可能很大，请你返回答案对1e9+7取…
2021/11/2 6:09:43 人评论 次浏览 -
【字符串】字符串多项式哈希 - 第2节
昨天看群里讨论哈希使用自然溢出被卡的问题，突然想到一个问题，就是为什么需要使用双模去做字符串哈希才能有效保证正确率呢？ 把n个元素放进m个桶里面，不发生冲突的概率： \[P = e^{\frac{-n(n-1)}{2m}) \]求解这个式子可以得知，要求正确率达到1e-9级别的话，m大概需…
2021/8/26 6:07:44 人评论 次浏览 -
【字符串】字符串多项式哈希 - 第2节
昨天看群里讨论哈希使用自然溢出被卡的问题，突然想到一个问题，就是为什么需要使用双模去做字符串哈希才能有效保证正确率呢？ 把n个元素放进m个桶里面，不发生冲突的概率： \[P = e^{\frac{-n(n-1)}{2m}) \]求解这个式子可以得知，要求正确率达到1e-9级别的话，m大概需…
2021/8/26 6:07:44 人评论 次浏览 -
LOJ#6342. 跳一跳(期望)
题意$n \leqslant 10^5$ Sol 随便推一推就好了吧。。 $f[i] = \frac{f[i] + f[i +1] + \dots f[n]}{n - i + 1} + 1$ 移一下项，然后化一化，就做完了。。 然而这题卡空间MMP#include<cstdio> #include<algorithm> #include<iostream> //#define int lo…
2021/6/5 10:24:28 人评论 次浏览 -
CF1030D Vasya and Triangle
原题链接题意：在 \(1 \leqslant n \leqslant 1e9, 1\leqslant m \leqslant 1e9, 1 < k \leqslant 1e9\) 的情况下，构造出 \(1\leqslant x \leqslant n, 1 \leqslant y\leqslant m\) 同时三个点构成的三角形面积等于 \(\frac{n\times m}{k}\)。 题解：主要是当在抽象…
2021/6/1 10:25:23 人评论 次浏览 -
CF1514B--AND 0, Sum Big
AND 0, Sum Big 来源：https://codeforces.com/problemset/problem/1514/B 标签：【位运算】【数论】 难度：★★☆☆☆ 题目简述 给定两个数n和k，计算出满足长度为n且满足下列条件的数列的数量：1.所有的元素都属于[0,2k-1];2.所有元素的按位与运算结果为0；3.元素和尽可…
2021/5/24 10:58:18 人评论 次浏览
