- 博客(220)
- 收藏
- 关注
RSS订阅
原创 关于欧拉定理的一些知识
欧拉定理aφ(n)≡1(modn),gcd(a,n)=1aφ(n)≡1(modn),gcd(a,n)=1a^{\varphi(n)}\equiv 1(mod\:n),\:gcd(a,n)=1 对于正整数nnn，代表小于等于nnn的与nnn互质的数的个数，记作φ(n)φ(n)\varphi(n)。 比如φ(6)=2φ(6)=2\varphi(6)=2，因为与666互质并且小于等于666的正整...
2018-08-07 12:59:05
793
原创 初识网络流(Ford-Fulkerson算法，Edmonds-Karp 最短增广路算法，Dinic 快速网络流算法)
今天！蒻终于知道了什么是网络流！！ 对于一个源点和一个汇点，之间有许多条有一定容量的边，问单位时间内从源点到汇点最多可以流过多少流量。 就拿这张图来说，就是问从源点sss到汇点ttt单位时间内的最大流量。 那对于最大流问题，有什么解决方法呢？Ford-Fulkerson算法基本思想就是每次用dfsdfsdfs从源点开始搜索，直到汇点停止，这之间所经过的边中容量最小的一条边就是...
2018-08-01 01:37:41
1142
1
原创 Termux定时运行python脚本
Termux定时运行python脚本步骤安装Termux更换镜像源安装Zsh安装VimVim简单配置安装Python安装Requests创建脚本使用crontab进行定时任务注意事项更详细的Termux教程及配置步骤本文主要是记录和方便初次使用termux的人。安装Termux如果可以科学上网的话，直接去Google Play搜索Termux下载即可。这里丢一个酷安的下载链接。点击链接下载更换镜像源(当然科学上网玩家可以忽略这一步。)如果会用vi的话，先更换编辑器export EDITOR
2021-01-17 23:38:57
8072
6
原创 Python + selenium + crontab实现每日定时自动打卡
Python + selenium实现自动打卡欢迎使用Markdown编辑器安装selenium库安装chromdriver编写脚本脚本定时执行欢迎使用Markdown编辑器近几日迫于被辅导员三番五次的提醒每日一报打卡，就想着去写个脚本挂在服务器上定时执行。经过我不懈的努力，最终选择了seleniumseleniumselenium，因为简单(安装selenium库$ sudo pip i...
2020-03-29 11:38:52
4176
3
原创 CF 721C - C. Journey(拓扑排序+DP)
C. Journey(拓扑排序+DP)一点不相关的话：好久没有更新博客了，当我再次看到这些，甚至都想象不到这些都是我写的。嗳，可能这就是命运多舛吧。去年打完最后一场ICPC后，就开始抉择是考研还是继续打下去，但是好像没有人陪我打下去了，ACM一个人真的很难坚持（其实有很多话想说，但是，我现在不想再回忆，这样只会消沉自己的情绪。）。最终，在询问过已经毕业的学长之后，我选择了去考研。今天考研视频网课...
2020-02-15 21:06:53
536
原创 POJ 1556 The Doors（计算几何+最短路）
POJ 1556 The Doors题意：在一个矩形里，从(0,5)→(10,5)(0,5)\rightarrow(10,5)(0,5)→(10,5)的最路径，中间会有n座墙，每个墙有两个门。题解：把所有的门的点坐标预处理出来，把墙看成线段，从起点开始往后连边建图，对于没有被墙阻隔的连边，然后跑个最短路即可。代码/**************************************...
2019-11-02 13:27:14
308
原创 CF 933A - A Twisty Movement(DP)
933A - A Twisty Movement题意：给出一个只有111和222组成的序列，有一次可以将区间[l,r][l,r][l,r]逆置的机会，询问最长不下降子序列长度。题解：dp[i][j][k]dp[i][j][k]dp[i][j][k]求出以kkk结尾的区间[i,j][i,j][i,j]的最长不上升子序列长度。然后答案就是pre[i−1]+max(dp[i][j][1],dp[i]...
2019-10-04 21:22:09
436
原创 Codeforces Round #590 (Div. 3) F - Yet Another Substring Reverse(状压dp)
F - Yet Another Substring Reverse题意：给出一个字符串，有一次逆置任意子串的机会，询问一个最长子串的长度，要求子串每一个字母都不相同。题解：问题可以看成找两个不相交的子串，不同字母个数之和最大。因为不同字符个数最大为202020，考虑预处理出每一个区间的值，并维护每一个子集的最大值（也就是连续且不同字符个数最多），然后枚举两两子集之和即可。代码#includ...
2019-10-04 18:32:39
443
原创 The Preliminary Contest for ICPC Asia Xuzhou 2019 G Colorful String(回文树 | manacher)
G. Colorful String题意: 给出一个字符串，询问不同回文子串的权值之和。每个回文子串的权值为回文子串不同字母的个数。题解: 回文树预处理出所有本质不同的回文子串及其出现次数，对于区间不同字母个数，可以对26个字母做前缀和。预处理后，计算方式就是每一个本质不同的回文子串的区间不同字母数量乘以出现次数。代码const int N = 3E5+10;struct PAM{ i...
2019-09-09 18:41:13
302
原创 2018-2019 ACM-ICPC, Asia Shenyang Regional Contest C. Insertion Sort（打表找规律）
C. Insertion Sort题意：给出n,kn,kn,k，询问nnn的全排列中，有多少个排列在给前kkk个元素排完序后满足最长递增子序列长度大于等于n−1n-1n−1。题解：实际上好像是有公式的。但是我的做法比较蠢。打表肉眼找规律。可以发现当kkk固定不变，nnn递增的时候是有规律的。代码先贴一份打表的int dp[100];int main() {#ifndef ONLINE...
2019-09-06 15:15:45
531
原创 GYM101879 2018 USP Try-outs G - Running a penitentiary（线段树）
G. Running a penitentiary题意：每个人都有相应的管理区间[l,r][l,r][l,r]，两个操作：询问第a,a+1,a+2...,ba,a+1,a+2...,ba,a+1,a+2...,b个人的管理区间交集。将第iii个人的管理区间变为[x,y][x,y][x,y]题解：多个区间的交集为[max(l),min(r)][max(l),min(r)][max(l),...
2019-09-04 23:24:47
282
原创 The Preliminary Contest for ICPC Asia Nanjing 2019 B super_log(欧拉降幂)
super_log题意求aaa...a^{a^a} ...aaa...，一共有bbb个aaa。题解由扩展欧拉定理可得ab(modc)={ab%ϕ(c)+ϕ(c)b ≥ ϕ(c) abb < ϕ(c)a^b\pmod c=\begin{cases}a^{b\%\phi(c)+\phi(c)}& \text{b...
2019-09-02 11:32:40
283
原创 2019牛客暑期多校训练营（第九场）D Knapsack Cryptosystem（折半搜索）
Knapsack Cryptosystem题意：给出一个序列{ai}\{a_i\}{ai}和一个指定的子集和sss，输出子集（用01表示）。题解：问题就在于aia_iai的值最大有2×10172\times 10^{17}2×1017，0<s<9×10180<s < 9\times 10^{18}0<s<9×1018，因此...
2019-08-15 22:10:05
175
原创 2019牛客暑期多校训练营（第二场）H Second Large Rectangle（单调栈）
Second Large Rectangle题意：求第二大的全为1的矩形。题解：将矩形分为mmm个竖条，记录每一行1的高度，然后维护一个递增的单调栈，每当新的竖条的高度小于栈顶高度时，维护栈的单调性，在弹出竖条的同时更新答案。如果最大值由x×yx \times yx×y更新，那么求第二大我们还需要通过x×(y−1)x \times (y - 1)x×(y−1)和(x−1)×y(x-1)\tim...
2019-07-24 19:10:17
155
原创 2050 Programming Competition 1006 冰水挑战(DP)
冰水挑战一开始想错了方程。。。导致最后没有做出来。题解：通过题意我们就可以知道这是一类很基础的背包问题，第iii项选与不选，时刻保持体力大于零。dp[i][j]dp[i][j]dp[i][j]表示对于前iii个挑战选了jjj个的最大剩余体力，那么就有，如果不选，则dp[i][j]=max(dp[i][j],dp[i−1][j]+c[i])dp[i][j] = max(dp[i][j],dp[...
2019-04-18 20:17:57
341
原创 Codeforces Round #552 (Div. 3) G. Minimum Possible LCM(埃氏筛法枚举GCD)
G. Minimum Possible LCM题意：求nnn个数中最小公倍数数值最小的两个数的下标。题解：参考于https://blog.csdn.net/qq_41157137/article/details/89353527，因为LCM(x,y)=x×ygcd(x,y)LCM(x,y) = \frac{x\times y}{gcd(x,y)}LCM(x,y)=gcd(x,y)x×y对于...
2019-04-17 23:50:33
264
原创 Codeforces Round #552 (Div. 3) F - Shovels Shop(DP + 贪心)
F - Shovels Shop题意：有nnn件物品每个价值aia_iai，mmm个offer(x,y)offer(x,y)offer(x,y)，对于每个offerofferoffer即，买xxx件物品，可以优惠掉其中yyy件最便宜的。问买kkk个物品的最少花费。题解：首先，对于每个offerofferoffer，xxx相同时，肯定yyy越大越好。其次，这些优惠肯定是从这nnn个物品中前...
2019-04-17 21:41:44
348
原创 Codeforces Round #267 (Div. 2) C. George and Job(DP)
C. George and Job题意：在序列aia_iai中选出kkk个不相交大小为mmm的区间，使其区间和最大。题解：dp[i][j]dp[i][j]dp[i][j]表示在前jjj个数里选iii个区间的最大区间和。则有dp[i][j]=max(dp[i−1][j−m]+sum[j]−sum[j−m],dp[i][j−1])dp[i][j] = max(dp[i - 1][j - m] +...
2019-04-15 23:38:30
190
原创 Codeforces Round #551 (Div. 2) D. Serval and Rooted Tree 树形dp
D. Serval and Rooted Tree题意：含有nnn个节点，并且以111为根节点的树的每个节点都有一个操作，用010101表示，如果为111，那么就取这个节点的孩子中的最大值，否则取孩子的最小值。问，如何安排可以使得根节点111的值最大。注意如果叶节点有kkk个，那么取值必须是1→k1\rightarrow k1→k。题解：如果去枚举叶子节点的取值肯定是不可以的了，复杂度过于高，...
2019-04-15 16:15:45
240
原创 Codeforces Round #547 (Div. 3) C D E F G
C. Polycarp Restores Permutation题意：给你序列相邻两项的差值，现在要求你恢复这个序列。题解：我们给差值序列qiq_iqi做前缀和，明显qiq_iqi最小的位置就是111的位置，因此我们就可以通过111的位置来推出其它位置。代码#include<bits/stdc++.h>#define DEBUG(x) std::cerr <<...
2019-03-21 18:16:33
303
原创 Codeforces Round #545 (Div. 2) D. Camp Schedule(KMP next匹配)
D. Camp Schedule今天！终于学会KMPKMPKMP了！！题意：给你010101串sss,ttt，任意改变串sss的字符顺序，求构造一个字符串ccc满足ttt在ccc中的出现次数最多。题解：首先求出串sss的000和111数量，其次利用KMPKMPKMP里的nextnextnext数组，如果会KMPKMPKMP的话，就知道，实际上nextnextnext数组就是模式串的公共前缀后...
2019-03-11 23:42:29
217
原创 HDU 1540 Tunnel Warfare(线段树区间合并)
Tunnel Warfare题意：有nnn个村庄，如果对于村庄iii和jjj都存在，那么我们就称其关系为连续，然后会有三个操作：D&ThickSpace;&ThickSpace;XD\;\;XDX摧毁第XXX个村庄。Q&ThickSpace;&ThickSpace;XQ\;\;XQX询问包含村庄XXX的最大连续村庄的长度。R&ThickSpace;...
2019-03-09 17:20:42
208
原创 Educational Codeforces Round 61 (Rated for Div. 2) F. Clear the String(区间DP)
F. Clear the String题意：给出一个串，每次消去连续相同的子串，问最少多少次能把这个串消完。题解：入门区间dpdpdp。两种做法。做法一：记忆化dfsdfsdfs。首先肯定可以知道对于 一段区间[i,j][i,j][i,j]，它只有两种情况，里面的字符全部相同，或者分成若干段相同区间。那么我们就可以暴力枚举区间里的中点，累加每段的区间贡献即可。对于每段区间里的字符，只要它和...
2019-03-09 11:55:41
189
原创 Codeforces Round #541 (Div. 2) D. Gourmet choice(并查集+拓扑) F. Asya And Kittens(启发式合并+链表)
D. Gourmet choice题意：给出两个序列aia_iai和bjb_jbj的大小关系，问能否恢复这两个序列，如果可以则输出，否则输出NoNoNo。题解：因为有等于号的存在，所以导致建图会形成环，因此我们考虑用并查集将等于关系的缩成一个点，然后去建图，跑一遍拓扑即可。代码#include<bits/stdc++.h>#define DEBUG(x) std::ce...
2019-03-02 15:27:12
238
原创 牛客练习赛41 A B C D E
传送门：https://ac.nowcoder.com/acm/contest/373#questionA. 翻硬币问题题解：很明显如果不能一次拿走，那么BobBobBob总是能翻转其中一枚硬币来破坏nnn与mmm的奇偶性。代码#include<bits/stdc++.h> #define DEBUG(x) std::cerr << #x << '=...
2019-03-02 15:11:52
338
原创 ZOJ - 1610 Count the Colors(线段树区间更新)
Count the Colors题意：每次对区间染色，注意不染端点，然后问最后每种颜色有多少段。题解：用线段树维护每个区间的颜色信息，然后因为不染端点，因此如果染0→40\rightarrow40→4，只会染444个区间那么我们将左端点加一即可。其它就是经典线段树lazylazylazy标记下放了。代码#include<bits/stdc++.h>#define DEBUG...
2019-02-27 16:42:08
201
原创 牛客练习赛40 C-小A与欧拉路(树形dp | 两次dfs 求树的直径)
C-小A与欧拉路题意：求图中最短的欧拉路。题解：因为是一棵树，因此当从某一个节点遍历其子树的时候，如果还没有遍历完整个树，一定还需要再回到这个节点再去遍历其它子树，因此除了从起点到终点之间的路，其它路都被走了两次，而我们要求总的路程最短，那么我们就让从起点到终点的路最长即可，也就是树的直径。所以答案就是所有边权的两倍再减去树的直径。代码两次dfs#include<bits/st...
2019-02-16 10:20:11
286
原创 CCPC-Wannafly Winter Camp Day3 (Div2, onsite) A 二十四点*（bfs爆搜）
二十四点*题解：没啥好办法，只有暴力搜答案咯～而且只有两组数据代码#include<bits/stdc++.h>using namespace std;vector<double> S;struct node{ vector<double> v;};int bfs(){ queue<node> q; n...
2019-02-04 15:05:30
405
2
原创 CCPC-Wannafly Winter Camp Day3 (Div2, onsite) I 石头剪刀布(按秩合并并查集)
石头剪刀布题解：每次有两个事件：yyy去挑战xxx，如果赢了可以坐在xxx的位置，打平或者输了就要被淘汰。询问在进行所有一类事件后，有多少种情况可以让xxx现在还没有被淘汰。对于第二类事件，我们假设xxx挑战了别人aaa次，被挑战了bbb次，那他没有被淘汰的概率就是3n⋅(13)a⋅(23)b3^n\cdot (\frac{1}{3})^a\cdot (\frac{2}{3})^b3n...
2019-02-04 15:01:27
330
原创 CCPC-Wannafly Winter Camp Day3 div2 F. 小清新数论* 莫比乌斯反演
小清新数论心情：蒻蒻的第一道莫比乌斯反演！！看了好几个小时QAQ，终于看懂些了！开心！^_^题解：(1)∑i=1n∑j=1nμ(gcd(i,j)) \sum_{i = 1}^n\sum_{j = 1}^n \mu(gcd(i,j)) \tag 1i=1∑nj=1∑nμ(gcd(i,j))(1)(2)∑d=1n∑i=1n∑j=1nμ(d)[gcd(i,j)==d]\sum_{d = 1}^...
2019-02-02 22:57:33
397
原创 CCPC-Wannafly Winter Camp Day1 (Div2, onsite) I 起起落落(dp)
起起落落题解：画一下图我们就可以发现要求的序列是波浪并且整体下降趋势的。pa[2k−1]&gt;pa[2k+1]&gt;pa[2k]p_{a[2k-1]}&gt;p_{a[2k+1]}&gt;p_{a[2k]}pa[2k−1]>pa[2k+1]>pa[2k]因此我们考虑dp[j]dp[j]dp[j]表示以jjj结尾的并且满足要求的子序列个数。那...
2019-02-02 10:53:05
365
原创 CCPC-Wannafly Winter Camp Day1 (Div2, onsite) J 夺宝奇兵(贪心)
夺宝奇兵现场时：一开始我有点纠结，因为不知道是优先当前数量最多的还是优先当前最便宜的。然后我起初的想法就是维护一个当前数量最多并且最便宜的堆，直到当前已拥有的宝物数量大于堆顶的宝物的数量。后来想了想，是不对的，因为我维护的第一关键字是数量最多，所以花费可能并不是最少的，有可能我买另两个个较便宜的宝物从而成为了数量最高，并且此时花费最少。题解：实际上可以枚举最后成为全场数量最高后的数量，我们设其...
2019-02-01 21:07:04
490
原创 Codeforces Round #536 (Div. 2) A B C D E(dp)
这可能是我做div2div2div2以来做的最好的一次？它居然unratedunratedunrated了！哼╭(╯^╰)╮不给力的服务器！关键时刻拓机！虽然这次的D比较水。但是是我一次过了四题QAQ…A. Lunar New Year and Cross Counting题解：数交叉XXX个数，O(N2)O(N^2)O(N2)枚举中点即可。代码#include&lt;bits/stdc+...
2019-02-01 15:48:03
370
原创 CCPC-Wannafly Winter Camp Day1 (Div2, onsite) E 流流流动(树形dp)
流流流动题解：题目是点的选与不选的问题，并且有连边，因此我们很容易想到树形dpdpdp，但是题目图的并不是联通的，因此我们可以将000与每一个连通集建边。然后考虑dp[u][1]dp[u][1]dp[u][1]表示选取以点uuu为根节点所能获得的最大收益，dp[u][0]dp[u][0]dp[u][0]表示不选uuu作为根节点所能获取的最大收益。所以有{dp[u][1]=dp[u][1]+max...
2019-01-31 20:29:23
281
原创 CCPC-Wannafly Winter Camp Day1 (Div2, onsite) B 吃豆豆(dp)
吃豆豆题解：不妨反向考虑，题目问到达并且至少获得CCC个糖果所需的最少时间，那么我们考虑位置为(i,j)(i,j)(i,j)时间为ttt的状态时所能获取的最大糖果数。那么答案就是dp[ex][ey][t]&gt;=Cdp[ex][ey][t] &gt;= Cdp[ex][ey][t]>=C时的ttt。然后dp[i][j][t]dp[i][j][t]dp[i][j][t]可以...
2019-01-31 20:15:44
367
原创 CCPC-Wannafly Winter Camp Day1 (Div2, onsite) F 爬爬爬山(dijkstra)
爬爬爬山题解：因为降低山需要花费l∗ll * ll∗l的代价，因此我们可以将这部分花费加到边上。然后跑最短路就好了。#include<bits/stdc++.h>#define P pair<LL,int>typedef long long LL;using namespace std;const int N = 2E5+10;LL dis[N];prior...
2019-01-31 20:05:32
267
原创 CCPC-Wannafly Winter Camp Day4 (Div2, onsite) A C F G I
比赛链接：https://zhixincode.com/contest/17A 夺宝奇兵题解：因为是先从1->n再从n->1，所以我们可以考虑当成一遍走，即每次的选择无非[ai→ai+1,bi→bi+1]或者[ai→bi+1,bi→ai+1][a_i\rightarrow a_{i+1},b_i\rightarrow b_{i+1}]或者[a_i\rightarrow b_{i+1...
2019-01-30 14:42:20
504
原创 Codeforces Round #535 (Div. 3) A B C D E1
A. Two distinct points题解：特判判断一下两个区间的左右关系即可。直接输出边界。#include<bits/stdc++.h>using namespace std;int main(){#ifndef ONLINE_JUDGE freopen("input.in","r",stdin);#endif int q; cin >&g...
2019-01-28 01:37:22
213
原创 HDU 5685 (前缀+逆元)
Problem A题意：给出你哈希值的计算方式，然后多次询问子串的哈希值。题解：我们通过观察哈希值的计算式子就可以发现是连乘，又是多次询问，因此我们可以想到打表的方式。前缀积即可。ans[a,b]=dp[b]dp[a−1]ans[a,b] = \frac{dp[b]}{dp[a - 1]}ans[a,b]=dp[a−1]dp[b]然后要注意到取模，所以需要乘法逆元。用扩欧或者费马小定理都可...
2018-12-22 16:38:08
330
原创 Codeforces Round #527 (Div. 3)A B C D1 D2
A. Uniform String题意：给出n,kn,kn,k，输出长度为nnn满足循环节的字符串。比如k=3k = 3k=3，就是abcabcabcabcabcabc，不足循环节长度的也要输出。代码#include<bits/stdc++.h>using namespace std;int main(){#ifndef ONLINE_JUDGE freope...
2018-12-22 13:11:54
865
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人