- 博客(116)
- 收藏
- 关注
RSS订阅原创 git使用vimdiff模式比对代码
今天看到同事用git diff看代码差异。。一整屏的凌乱的红绿色。。马上给他安利了vimdiff模式比对代码，效率高多了配置也非常简单，三个命令。第一个git config --global diff.tool vimdiff意思就是用vimdiff模式比对代码这样每次要输入git difftool，麻烦，alias一下git config --global alias.d difftool这样每次用git d 就可以了git d 发现每次会有确认的提示，一般不需要这个
2021-11-04 23:15:41
925
1
原创 Codeforces 273D Dima and Figure
链接:CF 273D大意：给你一个n*m的矩阵，让你在上面画一个凸的图形，问有多少种这样的图形。思路：n和m都是150的n4n^4n4就是5e8了不太现实，猜测复杂度是n3n^3n3的。这题初看比较复杂，其实想想要画这样一个图形，从上往下画的话，只需要保证两边都是一个单峰序列就可以了（当然可以有相等的），所以考虑设计dp状态，dp[i][j][k][l][[z]dp[i][j][k][l][[...
2020-04-01 20:50:56
302
原创 Codeforces Round #622 (Div. 2) D. Happy New Year
Problem Link:CF 1313DSolution: 无语辽，看了一遍题想了半天都不会，看着k≤8k \leq 8k≤8总感觉是要状压，想了半天也压不了啊，一个点可能有非常多线段覆盖，所以一直想能不能贪心。后面看了官方题解发现不太对劲，回头仔细看了看题发现是数据保证每个点最多有kkk条线段覆盖，而不是让你选每个点最多只能选kkk条线段。。。 害，知道了正确题意题解也相当明显了，k≤8...
2020-02-28 21:17:28
715
原创 CodeForces 506D Mr. Kitayuta's Colorful Graph
Problem Link : CF 506DSolution：这题一眼并查集，想不出啥骚操作或者高效的数据结构去维护这个东西，最初想法是对于每一个点开一个集合，用于维护各个颜色的相连关系，但是这个不好直接实现，空间时间都过不去。后来想到了可以用map代替数组进行维护，因为空间复杂度取决于边的个数，可以动态开。但是还是不会写二维的并查集。。。就百度学习了一下。对于这题，我们用fa[u][c] =...
2020-02-23 15:58:43
219
原创 CodeForces 741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
Problem Link: CF 741DSoution： 注意到字母最大是v，即最多有22种字符，看到这个数据范围就想到利用状压。那么在这题怎么用上状压呢？想到一个性质：一个简单路径可以通过打乱变成回文串，当且仅当在这个路径上出现的次数为奇数的字符个数不超过一个。 我们状压记录每个字符出现的奇偶性，偶数为0，奇数为1，那么对于以xxx为根的子树中，记stapsta_pstap为p点到x的...
2020-02-20 20:18:27
410
1
原创 寒假训练总结
好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊好无聊想出门想出门想出门想出门想出门想出门想出门想出门想出门想出门想出门想出门想出门想出门想出门想出门想出门想出门想出门想出门想出门...
2020-01-31 15:44:05
307
原创 A. Girls Band Party (From 2019 ICPC Asia Yinchuan Regional)
嘿嘿，今天终于想起来这题了，写一写。其实就是分组背包，分组背包的好处就在于分了组之后只需要考虑到当前组选了多少种，而不用记录每一种物品有没有选过。那么用dp[i][j][k]dp[i][j][k]dp[i][j][k]表示第iii组，已经选了jjj种物品，奖励为十分之kkk的情况下最大能获得的分数。答案就是max(dp[tot][j][k]∗(10+k)/10)max(dp[tot][j][k...
2019-12-09 16:31:39
638
原创 Miller-Rabin Template
// Randomized Primality Test (Miller-Rabin):// Error rate: 2^(-TRIAL)// Almost constant time. srand is needed#include<chrono>mt19937 rng((int)chrono::steady_clock::now().time_since_epo...
2019-10-10 23:15:16
143
原创 Educational Codeforces Round 73 (Rated for Div. 2) E. Game With String
E. Game With StringProblem Link :E. Game With StringSolution:翻译：分四种情况：1，当存在一个线段长度大于等于b小于a，Bob必胜；（因为这个线段只有Bob能覆盖）2，当至少有两个线段长度至少是2b，Bob永远可以划分其中的一个到情况1从而必胜；（此时Bob可以留一个b给自己）3，当没有线段长度至少是2b...
2019-09-20 15:16:55
178
原创 随手记
今天看到这样一个问题，说是能在sqrt(n)的时间里求出以下这个式子：由时间复杂度推解法，sqrt(n)就想到枚举因子，所以想到算贡献。所以其实就是把每一个均摊开，枚举因子算贡献，上式就变成了：当然这只是粗略的，很容易发现后面的本身为因子的贡献没有算进去，所以答案是：Over....
2019-09-11 12:49:40
166
原创 近期部分做题记录
近期看的东西比较多也比较杂，遇到很多想做的题目，以此博客来记录以免遗漏。2019ICPC南京网络赛D给你一个DAG，保证只有1没入边，只有n没出边。每天做一个选择：以等概率走向相邻边或者不动。第i天的花费是i。问你从1走到n的期望花费。因为是DAG，我们可以直接在上面做DP来求期望。要求花费，期望公式就是:dp[u]表示u到n的期望花费那么问题就变成了如何求cost，...
2019-09-05 12:29:49
215
原创 BM模板
#include<bits/stdc++.h>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define mp make_pair#define all(x) ...
2019-08-09 16:34:36
191
原创 线段树维护区间最大子段和
感觉线段树白学了，遇到啥不会啥。对于一个序列，要维护它的区间最大子段和，可以用线段树来做。当然，这是查询比较多的情况，比较少就直接O(n)DP了。线段树维护4个东西：1，区间答案，即该区间最大子段和2，包含左端点的最大子段和3，包含右端点的最大子段和4，区间和1是要维护的答案，2,3,4都是辅助来维护1的具体操作：区间答案可以由三种情况推出：qmax(qmax(...
2019-08-07 20:01:32
673
1
原创 网络流模板
struct Max_Flow{ int fir[maxn],nxt[maxm*2],des[maxm*2],c[maxm*2],tot; int dep[maxn];int ss,tt; Max_Flow(){ clear(); } void clear(){ memset(fir,-1,sizeof fir);tot =-1; } inline void addEdge(in...
2019-07-26 14:34:56
160
1
原创 2017 JUST Programming Contest 3.0 J. Boxes Game
Link:https://codeforces.com/gym/101502/problem/JSolution:很有意思的一道博弈区间DP首先区间dp是显然的，dp[i][j]表示在区间[i, j]先手者的最大得分然后用一点min-max search的思想，我想最大，要让对手尽可能小例如dp[1][n]可以由两种状态转移而来 : dp[2][n] 和 dp[1][n-1]这...
2019-06-06 19:15:43
279
原创 2016-2017 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) Problem B — Buggy Robot
题面：https://codeforces.com/gym/101201/attachments/download/5206/fast-en.pdfSolution：BFS维护DPdp[i][j][k]表示走完前k个字符串后，到达点（i, j）的最小改变次数数据范围很小，考虑直接bfs的时候把所有可行状态都压缩进去，然后dp更新然后一直跑到所有状态都最新就行了接下来考虑一...
2019-06-06 00:14:02
485
原创 快速乘模板
听说这个会加速乘法？其实不太理解，既然这个快那C++底层的乘法为什么不用这个。。所以一般还是用于直接乘会爆long long，所以这个分解着做ll qm(ll x, ll y, ll mod){ ll ret = 0; while(y){ if(y & 1){ ret += x; if(ret >= mod) ret -= mod; } x &l...
2019-05-31 12:46:01
255
原创 “美登杯”上海市高校大学生程序设计邀请赛 (华东理工大学) Problem E、小花梨的数组
Link:https://acm.ecnu.edu.cn/contest/173/problem/E/Solotion ：其实很容易想到维护一个区间的乘法次数以及除法次数，但是明显乘除法的顺序是对答案有影响的。所以考虑用线段树维护的时候如何更新除法标记一旦产生，是不能消除的，乘法标记是可以用除法标记等量消除的所以我们维护(push_down)的时候优先考虑除法标记下传，然后再看乘法...
2019-05-19 15:14:31
249
2
原创 2018 USP-ICMC E. Loppinha, the boy who likes sopinha
Link:https://codeforces.com/gym/101875/problem/ESolution:显然是一道动态规划题，状态也比较好想，dp[i][j][k]表示前i个用了j个转换，当前连续k个1的最小消耗值答案就是dp[n][?][?]中满足消耗值小于等于体力值的状态中j的最小值转移就分为s[i] == '1'和 s[i] == '0'了s[i] == '1'...
2019-05-16 17:04:51
341
原创 Codeforces Round #558 (Div. 2) C2 - Power Transmission (Hard Edition) （two solutions）
Link:C2. Power Transmission (Hard Edition)大致的思想是先求出所有的直线（去除重复直线），先算出两两相交答案，然后再减去平行的直线。Solution1：利用直线的斜截式(y = kx + b，应该是叫这个吧），求出每个的k, b，这样就可以轻松完成去重，平行也很好判struct P{ db x, y;}a[maxn];struct ...
2019-05-11 19:19:00
172
原创 SCUOJ 4441: Necklace （Segment Tree or BIT 优化DP）
Link:4441: NecklaceSolution:只有十个可以当中间数的，那么我们枚举中间数，然后从左从右分别进行DP，再枚举断点，维护答案最大值即可。转移方程也很好想：dp1[i] = max(dp[i-1], max{ dp1[j] | j < i, a[i] <= a[j]} + a[i]) （右半部分）dp2[i] = max(dp[i+1], max...
2019-05-09 19:41:57
226
原创 线段树模板
整理一下线段树模板。因为学的不精，复杂度是在我能力范围内最优的，以后学会了更优秀的再说吧。分两块：1：单点修改，区间查询2：区间修改，区间查询其实线段树的变种挺多的，这两个放在这方便修改。我还是比较喜欢写成结构体的形式。。1：单点修改，区间查询#define lson i << 1#define rson i << 1 | 1te...
2019-05-09 16:17:59
156
原创 KMP模板
//主串a, 模式串bchar a[maxn], b[maxn];int nxt[maxn];int la, lb;void getNext(){ int j = 0; rep(i, 2, lb){ while(j && b[i] != b[j+1]) j = nxt[j]; if(b[j+1] == b[i])j++; nxt[i] =...
2019-05-03 14:24:38
108
原创 Manacher算法模板
char s[maxn], Ma[maxn*2];int p[maxn*2];//p[i]表示在Ma数组中, 以i为中心的最长回文子串半径void Manacher(char s[], int len){ int l = 0; Ma[l++] = '$', Ma[l++] = '#'; rep(i, 0, len - 1){ Ma[l++] = s[i]; Ma[l++] ...
2019-04-27 23:03:56
137
原创 The Preliminary Contest for ICPC China Nanchang National Invitational I : Max answer
https://nanti.jisuanke.com/t/38228给你一个序列，让你求出一个连续子序列，序列最小值 乘 序列和最大, n5e5, a[i] : [-1e5, 1e5];只有正数就直接单调栈了，不会看这https://blog.csdn.net/swunHJ/article/details/89441597考虑存在负数的情况：如果a[i]是正的，那就在[l[i] -...
2019-04-22 22:09:09
263
原创 单调栈基本应用
1：给一段序列，让你求每个数的右边 第一个比它大的数离它的距离。例题：Bad Hair Day经典的单调栈题目了，把题意转换成，每头牛被看了多少次，加起来就好了。所以我们要维护一个单调增的栈。（我们一般称栈顶到栈底递增的栈为单调增的栈）代码如下：（这题数据有点问题，ans要开long long才能过）stack<int> st;int main(){ in...
2019-04-22 21:54:54
514
3
原创 POJ3666 nlogn 做法
呜呜呜我再也不会放弃一个我能理解的题了！就算花几个小时！就算手里还有很多题！给你一个序列，每次操作你可以让一个数加一或者让一个数减一，问使这个序列不减的最小操作数（具体是啥我也不想看了，大概就是这样,如果是严格递增a[i] - i就变成了不减）然后有一个结论是改变之后的序列的每个数，一定是原来序列中的某个数。那么离散化之后的n ^２ DP就很显然了但是！！有一个极其巧妙的nlogn的解...
2019-04-21 10:50:12
318
原创 BZOJ1233: [Usaco2009Open]干草堆tower 单调队列优化DP
https://www.lydsy.com/JudgeOnline/problem.php?id=1233这题我是完全一点一丢丢都不会做的，只能靠看题解维持一下容易想到n ^３的ＤＰ，其实就相当于暴力从前往后找了但其实这题倒着推要简单一点，因为正着推每一次都要重新找，然后检查是否合法，比如32 1 4只有2，1本来答案是2，加了个4答案反而只有1了但是倒着推我们就可以稍...
2019-04-20 23:39:17
204
原创 武汉游记
赛前和队友开玩笑说这次来武汉主要就是来旅游的，没想到最后真的成了旅游队。。只能说除了比赛各方面的体验都挺好的，湖北省由于竞赛环境很差，才第二届省赛，所以能很明显感受到这个比赛很水，题目是由武汉大学学生自己出的。。比赛时间因为赞助商宣讲推迟了十分钟。。比完赛连个牌子都没有。。发了个空壳红证书拍照，拍完还被收了回去。。种种种种，要吐槽的地方太多了，不过来武汉朋友和姐姐都请我吃饭还是挺开心的哈哈。...
2019-04-15 08:16:31
510
1
原创 每日一题 2019/4/11
啊，明天就要去武汉了，这个怕是要咕几天了，回来再继续吧。今天学一下三分。好像也没啥好学的，现在学的东西都是很好理解但是不容易想到或者推出来公式，就把板子整理一下吧，以前板子的常数不怎么优秀。//求凸函数最大值，答案取lwhile(r - l > eps){ double mid1 = (2 * l + r) / 3, mid2 = (l + 2 * r) / 3; if(...
2019-04-11 20:04:09
145
原创 每日一题 2019/4/10
今天写个大区间素数筛POJ3689给你一个区间[l, r]，1 <= l <= r <= 1e9, r - l < 1e6，求区间内相邻的素数差值最大值和最小值显然直接筛是不太现实的，注意到区间只有1e6。思路转换为把[l, r]的合数求出来，剩下的就是素数直接枚举就行了。如何求出区间中的合数？首先知道最小的质因子是sqrt(int) = 2 ^ 1...
2019-04-10 20:47:06
217
原创 每日一题 2019/4/9
今天学一下tarjan求强联通分量，继续整理模板好文：https://www.sohu.com/a/245954819_100201031模板：//输出所有的强联通分量struct node { int v, nxt;}edge[maxm];int dfn[maxn], low[maxn];int st[maxn], heads[maxn];bool vis[ma...
2019-04-09 22:56:55
194
原创 每日一题 2019/4/8
今天就整理模板吧感谢牛逼网友的帮助，有了这些模板整理工具:https://github.com/4thcalabash/code_libraryhttp://www.planetb.ca/syntax-highlight-wordhttps://www.cnblogs.com/palayutm/p/6444833.html#e5898de8a880_2https://githu...
2019-04-08 20:18:52
281
原创 每日一题 2019/4/7
今天学一下主席树最简单的就是给你一个序列，询问是给定区间中第k大的数。看了这篇博客，这个图讲解的真的无敌好懂https://blog.csdn.net/bestFy/article/details/78650360大概的思路就是先对数据进行离散化，主席树每一个节点都是一颗线段树，储存的信息是插入了第i个点后，主席树的状态。插入就是对离散化后的数据，当成一颗权值线段树来加...
2019-04-07 21:25:14
158
原创 每日一题 2019/4/6
今天是cf让我有点难过就差几分钟但还是要写题的一天。今天时间不多了，搞个稍微简单点的，就把天梯赛那个模拟补了吧。搞了半天也只有18分。。upd:好了，结论就是，以后无论如何，在?.size()前面加个int强转#include<set>#include<map>#include<cmath>#include<ctime>#i...
2019-04-06 23:54:57
208
原创 每日一题 2019/4/5
今天解决经典问题——TSPdp[S][v]表示，现在访问过的节点为S，当前所在顶点为v，从v出发访问所有剩余的节点，最终回到起点的最短路径长度。（起点0当做尚未访问，回来的时候访问）那么答案就是dp[0][0]初始化dp[V][0] = 0递推比较显然了，枚举最小dp[S][v] = min(dp[S|u][u] + cost[v][u]) u尚未访问过题目：V...
2019-04-05 13:51:48
144
原创 每日一题 2019/4/4 Nim博弈
今天是头疼、想看Final但是还是要做题的一天今天学一下Nim博弈首先是经典问题：n堆石子，每堆a[i]个，两个人每次至少从一堆中拿一个，谁没的拿了就输了，问谁赢答案是如果n堆石子的异或和为0，先手必败，否则先手必胜证明的思路是：对于一个a[1] ^ a[2] ^ ... ^a[n]这个状态，记为x，如果x = 0，是不可能取石子使x != 0，但是如果x != 0，是一定存在一种...
2019-04-04 23:28:26
941
3
原创 每日一题 2019/4/3
今天浅学一点计算几何，顺便整理一下模板每个东西要理解然后自己敲，再对照有没有敲错。inline int sign(db a) { return a < -eps ? -1 : a > eps; }//判断符号inline bool dcmp(db x, db y){ return fabs(x - y) < eps ? 1 : 0; }inline db add(d...
2019-04-03 23:56:21
230
原创 快速读入、输出模板
inline int read(){ char ch = getchar(); int x = 0, f = 1; while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while('0' <= ch && ch <= '9'){ x = x * 10...
2019-04-02 12:48:07
215
原创 每日一题 2019/4/2
今天学最大权闭合子图如果点权都是正的，答案就是所有的权值之和了，所以要解决的就是有负权的情况首先建模，一个超级源点和一个超级汇点，源点和正权点连边，汇点和负权点连边，权值就是点值，图中的所有关系边边权为inf，结论就是最大权闭合子图的权值为 所有正点权之和减去最小割的权值和对这个结论的证明：（该部分摘自https://www.cnblogs.com/TreeDream/p/594...
2019-04-02 12:39:33
157
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人