- 博客(207)
- 收藏
- 关注
RSS订阅原创 sudo service docker start显示[OK]但是* Docker is not running问题【Docker踩坑】
首先必须添加 fstab 文件，因为由于某种原因不存在或无法读取：由于网络控制器错误，所以要从nftables切换到iptables执行上述命令后重新启动docker再查看当前运行状态
2022-07-12 17:35:03
7699
15
原创 字典树（trie）数组实现模板
没啥可讲的，就是一个对于大量字符串及其前缀的快速储存和查找的数据结构。在时间复杂度上比map要小得多。直接上模板：struct node{ int num,next[26];}trie[500005];int tot=1;void inser(string c)//建树{ int len=c.size(),p=1; for(int i=0;i<len;i++) { int t=c[i]-'a'; if(trie[p].ne
2021-05-18 23:08:26
241
原创 洛谷-P1040 [NOIP2003 提高组] 加分二叉树（区间DP，二叉树，先序遍历）
题目链接题意：已知一个二叉树的中序遍历的结果是一个递增的排列，给你这些节点的权值，根节点的值等于两个子节点的乘积加上他本身的权值，如果子节点为空则视为1，求这个二叉树能达到的最大值以及在该结果下的先序遍历序列。思路：首先，我们需要知道，中序遍历的情况下，每一个节点的两边都会是它的子节点或者子节点的子节点等等，所以我们只需要用一个区间dp来维护每一个小的二叉树的最大值即可，状态转移方程为：dp[j][j+i-1] = dp[j][k-1]*dp[k+1][j+i-1]+dp[k][k];这里注意，
2021-04-21 00:17:46
199
原创 Codeforces Round #698 (Div. 2) D. Nezzar and Board（裴蜀定理，gcd）
题目链接题意：给定n个不同的数，每次操作可以选择两个数x，y新增一个数2x−y。给定k，问是否能在若干次操作后得到k。思路：首先这个题目要求是2*x-y，那么我们很容易就可以推出，不论我们怎么改变x和y的值，最终的结果表达式的系数都是1。最终的结果一定是 a[i] + ∑(aj−ak)，而∑(a[j]−a[k])可以化为∑fi(a[i]−a[i−1])。根据裴蜀定理，我们不需要考虑fi的值，我们只需要考虑给定的整数(a[i]−a[i−1])即可，所以我们只需要求出每一个i>=2的a[i]−a[
2021-02-01 12:23:17
169
原创 数论基础--欧拉函数，欧拉筛
带佬链接–>浅谈欧拉函数欧拉函数的意义：给你一个数n，求出1~n之间有多少个数和该数互质。欧拉函数通式：eula(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)……(1-1/pn)模板：求单个数的欧拉函数值：int eula(int n){ int ans=n; for(int i=2;i*i<=n;i++) { if(n%i==0) { ans=ans/i*(i-1);
2020-12-04 16:41:32
217
原创 【已解决】java提交codeforces显示Source should satisfy regex [^{}]*public\s+(final)?\s*class\s+(\w+).*
如果你在使用codeforces网站提交java代码时出现如下报错那么你只需要将你主函数所在的公共类移动到所有类的顶部即可。
2020-11-24 23:51:45
1418
原创 最长上升子序列模板（dp，二分）
普通版本，简单易懂但是时间复杂度高，O(n2)O(n^2)O(n2)，在第一次遍历的同时遍历之前的部分看新出现的元素能否加到之前出现的元素的序列之前。#include<bits/stdc++.h>using namespace std;#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=1e6+7;const int inf=0x3f3f3f3f
2020-11-16 23:45:12
154
原创 快读模板
#define gc() (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<20,stdin),fs==ft))?0:*fs++;inline int read(){ int x=0,f=1; char ch=gc(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=gc(); } while(
2020-10-06 23:17:50
149
原创 Codeforces Round #673 (Div. 2) D. Make Them Equal
题目链接题意：给你一个长度为n的数组和3n次的操作数，每次操作可以选择任意两个不同的i，j，将ai=ai−x·i，aj=aj+x·i.思路：我们不难想到，如果一个数想加上某个数，那么他可以加上不超过第一个数大小的任意数，但如果想减，就只能减去下标的倍数，所以我们只需要从第二位开始将每一个数先加到下标的倍数再减为0，这样就能将所有数全部转移到第一位上，最后将每一个数全都变成相同数即可（记得判断能否整除）。代码：#include<bits/stdc++.h>#define int lo
2020-10-02 13:33:54
135
原创 Grakn Forces 2020 B. Arrays Sum
题目链接题意：给你一个长度为n的a数组，问你这个数组最少能由几个只含k个不同数的b数组对应位置相加的得到。思路：第一个b数组可以得到a中前k个不同的数，但是从第一个b数组之后的数组必须有一个数为0来让前面已经变过的数保持不变，所以后面的每个b数组只能变出k-1个不同的数，所以我们算出a中不同的数的个数之后再用刚刚的方法算出结果即可。代码:#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_s
2020-10-02 13:02:19
237
1
原创 Codeforces Round #673 (Div. 2) B. Two Arrays
题目链接题意：给你n个数，你可以将他们分到任意的两个数组中，求怎样可以使得分别两个数组中的两两和为T的对数的数量最小。思路：遍历数组，如果该数没有被标记，那么标记该数并标记T-该数，flag数组中标记的数不同，表示这两个数不在同一个数组中，最后直接输出所有数的标记即可。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(
2020-09-28 14:06:00
174
原创 Codeforces Round #673 (Div. 2) C. k-Amazing Numbers
题目链接题意：给你两个数n，k，求从1~n之间的每一个i在长度为n的数组中的，所有连续的长度为i的数组的公共最小值，如果没有重复值则输出-1.思路：遍历求每个相同的数之间的距离，即求出i到达几时这些数成为公共值，然后遍历所有求得的公共值，输出最小值即可。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#def
2020-09-28 13:58:16
540
2
原创 Codeforces Round #667 (Div. 3) D. Decrease the Sum of Digits
题目链接思路：预处理每一位的10次方，从最末尾开始逐位上升，累计操作数，每次上升之前都计算所有位之和，如果满足条件直接break，否则继续进一升位（防止999999情况出现），输出操作数即可。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define pb push_back#define ll long
2020-09-08 01:30:37
150
原创 Codeforces Round #667 (Div. 3) B. Minimum Product
题目链接思路：要确保两个数之间的差值最大，那么我们可以从一个一直减小然后再从另一个开始，讨论两种情况谁的收益最大即可。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define pb push_back#define ll long longconst int N=2e5+5;const int M=2
2020-09-08 01:19:37
143
原创 Codeforces Round #666 (Div. 2) D. Stoned Game（博弈论）
题目链接思路：如果最大值超过其他所有值则先手赢，当石子总数为偶数时后手赢否则先手赢，因为相当于每一轮都要拿走两个。代码:#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=1e5+9;const int M=1e4+5;const double eps=1e-8;const int mod=1
2020-08-31 23:10:58
178
原创 Codeforces Round #666 (Div. 2) C. Multiples of Length
题目链接思路：如果n为1直接输出两个不改变和一个变为0即可，如果n大于1那么第一次操作就将1到n-1同时加上a[i]*(n-1)将他变成n的倍数最后再用第三次操作将所有的n个数组变成0即可。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=1e5+9;const int M=1e4+5;
2020-08-31 22:50:30
155
原创 Codeforces Round #666 (Div. 2) B. Power Sequence（暴力枚举）
题目链接思路：从1开始枚举c的大小再用一个循环从1跑到n枚举c的每一个次方，再求出需要操作的最小值即可，如果c的某个次方和a[i]的差超出1e15（数据范围内能够操作的最大值）那么这个c之后的c就不可能了，直接break然后输出之前求得的最小值即可。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const in
2020-08-31 22:34:11
153
原创 Educational Codeforces Round 94 (Rated for Div. 2) D. Zigzags
题目链接思路：遍历找相等，然后找相等的数之间的数和之后的相等数累加起来即可。代码：#include<bits/stdc++.h>#pragma GCC optimize("Ofast")#define endl '\n'#define null NULL#define ls p<<1#define rs p<<1|1#define fi first#define se second#define mp make_pair#define pb pu
2020-08-29 23:55:18
183
原创 Educational Codeforces Round 94 (Rated for Div. 2) B. RPG Protagonist（贪心）
题目链接思路：枚举每一种情况找出剩余质量最少的情况即放入的最多的情况即可。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=1e5+7;const int M=1e4+5;const double eps=1e-8;const int mod=1e9+7;const int inf=
2020-08-29 21:37:41
130
原创 Educational Codeforces Round 94 (Rated for Div. 2) C. Binary String Reconstruction
题目链接思路：字符串s[i]如果为0，那么w[i]两端也一定为0，标记完这些位置之后特判两端长度为x的位置是否有冲突即可。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=1e5+7;const int M=1e4+5;const double eps=1e-8;const int m
2020-08-29 20:28:57
145
原创 Codeforces Round #665 (Div. 2) D. Maximum Distributed Tree（dfs）
题目链接思路：dfs讨论m和n−1之间的大小关系，再计算每条边的贡献次数排序。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=2e5+7;const int M=2e4+5;const double eps=1e-8;const int mod=998244353;const in
2020-08-23 00:39:58
151
原创 Codeforces Round #665 (Div. 2) C. Mere Array（思维，gcd）
题目链接思路：所有是最小值的倍数的数都可以进行交换，其他数的位置不会发生改变，所以我们只需要看这些数排序之后与排序之前的位置是否一样即可。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=2e6+7;const int M=2e4+5;const double eps=1e-8;con
2020-08-23 00:34:06
150
原创 Educational Codeforces Round 93 (Rated for Div. 2) C. Good Subarrays
题目链接思路：将每一位上的数组-1，将问题转化为求区间和为0的问题，再维护一个前缀和即可。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=210;const int M=2e4+5;const double eps=1e-8;const int mod=998244353;cons
2020-08-21 01:52:36
163
原创 Educational Codeforces Round 93 (Rated for Div. 2) B - Substring Removal Game
题目链接思路：分析可知双方每次操作一定是取连续1最多的区间消掉，贪心即可。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=210;const int M=2e4+5;const double eps=1e-8;const int mod=998244353;const int in
2020-08-21 01:47:25
149
原创 Educational Codeforces Round 93 (Rated for Div. 2) A. Bad Triangle
题目链接思路：判断两个最小值是否大于最大值即可代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=210;const int M=2e4+5;const double eps=1e-8;const int mod=998244353;const int inf=0x7fffffff;
2020-08-21 01:41:34
104
原创 Codeforces Round #664 (Div. 2) C. Boboniu and Bit Operations
题目链接思路：暴力从0开始枚举答案，如果有一个答案满足对任意一个ai均能找到一个bj，使得(a[i] & b[j]) | x) == x，输出即可。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=210;const int M=2e4+5;const double eps=1e
2020-08-20 01:19:53
153
原创 Codeforces Round #664 (Div. 2) B. Boboniu Plays Chess
题目链接思路：走过的方格是不能再走的，每个方格都要走一遍，输出路径。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=355;const int M=2e4+5;const double eps=1e-8;const int mod=998244353;const int inf=0
2020-08-20 01:12:28
132
原创 Codeforces Round #664 (Div. 2) A. Boboniu Likes to Color Balls
题目链接思路：想要满足题意则有：所有颜色的球的数量都是偶数且至多只有一种颜色的球的数量是奇数。所以我们只需要探讨初始情况和进行一次操作后是否满足上述条件即可。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=355;const int M=2e4+5;const double eps=1
2020-08-20 01:04:50
135
原创 洛谷-构造题专项训练-P5595 【XR-4】歌唱比赛
题目链接代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=2e6+7;const int M=2e4+5;const double eps=1e-8;const int mod=998244353;const int inf=0x7fffffff;const double pi=3.1
2020-08-19 01:20:44
237
原创 【杭电多校2020】第八场1003.Clockwise or Counterclockwise
题目链接思路：如果输出结果是顺时针则叉积方向向内，当结果是逆时针时叉积方向向外。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=2e6+7;const int M=2e4+5;const double eps=1e-8;const int mod=998244353;const i
2020-08-19 00:12:00
110
原创 Codeforces Global Round 10 C. Omkar and Waterslide
题目链接题意：每次操作可以使得一个非递减区间全部++，问你最少操作几次可以使得数组递增。思路：我们只需要让每一个递增的开头都大于上一个递增的结尾即可，因为我们每次操作都可以将这个递增结尾之后的所有数都++，这样不会影响后面的判断，也不会多++。所以具体操作就是遍历然后遇到递减的情况就将结果加上s[i-1]-s[i]。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(fal
2020-08-18 02:17:50
182
原创 Codeforces Global Round 10 D. Omkar and Bed Wars
题目链接题意：枕头大战，RL分别代表攻击方向，每次操作可以修改一个人的方向使得枕头大战的所有人都满足逻辑：如果只有一个人打你那么你必须打他，如果两边的人都没有打你或者是都在打你那么你打谁都行。思路：我们可以很容易的判断出三个连续的R或者是L都是不允许的，所以我们只需要将RRR或者LLL的末尾变成L或R即可，这样可以合理的利用每一次操作，需要注意的是要从每一个连续的R或L开始判断，因为是成环的，所以我们不能直接从头开始，还要注意当三个连续的R或L之后的字母不同时要将第二个R或L改变，因为这种情况改变末
2020-08-18 01:20:24
153
原创 Codeforces Global Round 10 B - Omkar and Infinity Clock
题目链接题意：每次都用数组中的最大值减去每一个值，问你k次后的数组。思路：如果最大值固定的话，每两次是一个循环，但是在数组中有负数和没有0的情况下最大值会发生改变，所以我们将数组变为减一次之后的数组，这样数组中一定有0并且没有负数，然后以两次为一个循环判断即可。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
2020-08-18 00:41:28
115
原创 Codeforces Global Round 10 A. Omkar and Password
题目链接思路：判断是否全部相等，如果全部相等则输出n，否则输出1.代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=2e6+7;const int M=2e4+5;const double eps=1e-8;const int mod=998244353;const int inf=
2020-08-18 00:31:25
136
原创 洛谷-P2669 金币
题目链接思路：一个循环求出金币数即可。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=2e6+7;const int M=2e4+5;const double eps=1e-8;const int mod=998244353;const int inf=0x7fffffff;co
2020-08-13 01:58:52
285
原创 洛谷-P2181 对角线（思维，数学）
题目链接思路：在经过一些排列组合的技巧，就可以得出代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=2e6+7;const int M=2e4+5;const double eps=1e-8;const int mod=998244353;const int inf=0x7fffff
2020-08-13 01:49:46
301
原创 【杭电多校2020】1009.Increasing and Decreasing
题目链接思路：将整个序列分成x块，每一块找一个元素出来形成的就是最长递增子序列；而递减序列正好是某一整块元素。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=2e6+7;const int M=2e4+5;const double eps=1e-8;const int mod=998
2020-08-13 01:43:31
319
原创 2020牛客暑期多校训练营（第十场）E.Game
题目链接思路：遍历，如果新遍历到的数大于之前的平均数，那么就再次平均，注意平均时向上取整。代码：#include<bits/stdc++.h>#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=1e5+3;const int M=2e4+5;const double eps=1e-8;const int mod=998244353;co
2020-08-10 23:40:03
218
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人