redoCxz

分类

ACM练习赛(18) ACM练习题(418) BZOJ刷题(5) C++算法模板(20) codeforce(4) hdu(8) java(16) Java算法模板(24) kotlin(1) Leetcode(12) Lintcode(26) 剑指offer(1) 拓展欧几里德(1) 最小生成树(1) 未归档(70) 杂七杂八(41) 水题(1) 牛客网(2) 牛客网错题总结(1) 算法四(2) 题解(1)

/ 注册

全部文章（共388篇）

luoguP4578_ [FJOI2018]所罗门王的宝藏

题意一个n*m的矩阵，初始值全为0，每一行每一列操作一次可以加1或者减1，问能否操作得到给定矩阵。分析行和列的分别的加减是可以相互抵消的，因此我们只需要考虑行的加和列的减。对于给定矩阵每一个数\(x\)，假设对应行\(u\)加上\(r_u\)次，对应列\(v\)减去\(c_v...

题解图论差分约束

2019-08-16

0 508

2019牛客多校第九场

D Knapsack Cryptosystem 题意求一个有唯一解的超大01背包的方案。分析使用折半搜索，前18个数先dfs爆搜求出所有可能的方案，存到map里，再爆搜后18个数，从map里查询即可。代码 #include <bits/stdc++.h> using ...

题解主席树二分答案超大背包搜索

2019-08-15

0 577

【算法学习】尺取法

基础模板求和大于等于S的最小子段 ll sum=0; int l=1,r=1; while(true){ //全速推进r指针 while(r<=n && sum<s){ sum+=a[r++]; } //r走...

算法题解尺取法

2019-08-15

0 405

2019牛客多校第八场

A All-one Matrices 题意求所有极大全一矩阵的个数。分析预处理每个点向下延伸的高度值，同一行再用单调栈预处理每个高度作为最小值能延伸的左右边界。枚举每个1的点，先判断这个点的高度左右延伸覆盖的区间是否在前面已被覆盖过(即已统计过)，如果否，再判断对应这段覆盖...

题解单调栈思维贡献构造模拟

2019-08-10

0 541

2019牛客多校第五场

digits 题意给定一个n，要构造一个数，本身是n个倍数，每一位的数加起来也是n的倍数。分析输出n个n即可，显然可以整除得到1..0..1..0..1，而且无论每一位上的数是什么，个数都是n个倍数，因此和可以整除n。代码 #include <bits/stdc++.h&g...

题解思维快速幂拓扑排序

2019-08-09

0 444

2019牛客多校第七场

A String 题意给定一个01串，求最少的划分次数，使得每部分的01串都是循环字典序最小。分析从最长的整个串贪心，暴力判断是否是循环字典序最小，若是，直接输出前面的串，然后后面的串再进行新一轮判断。代码 #include <bits/stdc++.h> using...

题解贪心字符串模拟前缀和线段树思维权值线段树

2019-08-09

0 523

Codeforce1196_D_F

D RGB Substring 题意给定一个只含RGB三种字符的字符串，问最少修改多少个字符，能使得修改后的字符串存在一个长度为\(k\)的子串是...RGBRGB...这个循环字符串的子串。分析只含有3种字符，考虑从...RGBRGB...这个循环字符串大力枚举。子串要和...

题解思维前缀和最短路 floyd

2019-08-06

0 528

2019牛客多校第六场

A Garbage Classification 题意给定一个字符串代表垃圾，26个字符每个字符代表某种组成成分，根据题意判断垃圾类别。分析温暖的签到题，注意别写成除法就行。代码 #include <bits/stdc++.h> using namespace std...

题解模拟字符串模拟字符串回文树 dfs dp 枚举二分蔡勒公式全排列前缀和

2019-08-05

0 433

2019牛客多校第三场

B Crazy Binary String 题意给一个01字符串，求0和1个数相同的最长子序列和子串长度。分析子序列长度就是\(min(cnt(0),cnt(1))*2\)，子串的长度也是原题，记录一下0和1个数差的前缀和，然后用一个数组记录前面扫过的0个数和1个数差值的最左位置，前缀...

题解前缀和字符串单调队列模拟

2019-07-28

0 496

2019牛客多校第四场

A meeting 题意给一棵树，以及树上的\(k\)个点，要求一个点使得这k个点到这个点的最大距离最小。分析简单的做法就是求出这\(k\)个点在树上的最远距离，类似于求树直径的做法，然后点肯定取在直径一半处。代码 #include <bits/stdc++.h> u...

题解字符串后缀数组回文树单调队列线段树 dfs 最短路分层图最短路 dp 树的直径

2019-07-27

0 491