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) 杂七杂八(41) 水题(1) 牛客网(2) 牛客网错题总结(1) 算法四(2) 题解(1)

/ 注册

全部文章 / 未归档（共70篇）

uoj218_火车管理

题意 \(n\)个位置，每个位置一个栈，三种操作，询问区间栈顶的和，区间入栈某个数，单点出栈某个数。分析用一个线段树来维护栈顶的和，区间(单点)更新和区间询问。用一个主席树来维护每个位置最新一次入栈的时间，即主席树存的是时间，然后取出的时间也能作为主席树的下标来访问对应时间的版...

题解主席树线段树

2019-08-21

0 507

luoguP3588_[POI2015]PUS

题意有一个\(n\)个数的序列，已知其中的\(k\)个数，然后有\(m\)个信息，每个信息给出区间\([l,r]\)，和\(k\)个数，表示区间\([l,r]\)中这\(k\)个数大于剩下的\(r-l+1-k\)个数，求出一个方案。分析抄做的第一题线段树优化建图的题目，很巧妙。 ...

题解线段树图论拓扑排序

2019-08-20

0 529

2019牛客多校第十场

B Coffee Chicken 题意定义一个字符串的斐波那契数列，求从第k位开始的后面十个字符。分析把第n项求出来是不可能的。斐波那契数列的增长是很快的，而且由于题目保证\(k<=min(|S(n)|,10^{12})\)，且只输出十个字符，因此其实只有前几十项是有...

题解思维分治数论线段树

2019-08-19

0 418

luoguP4578_ [FJOI2018]所罗门王的宝藏

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

题解图论差分约束

2019-08-16

0 513

2019牛客多校第九场

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

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

2019-08-15

0 595

【算法学习】尺取法

基础模板求和大于等于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 408

2019牛客多校第八场

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

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

2019-08-10

0 546

2019牛客多校第五场

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

题解思维快速幂拓扑排序

2019-08-09

0 463

2019牛客多校第七场

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

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

2019-08-09

0 524

Codeforce1196_D_F

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

题解思维前缀和最短路 floyd

2019-08-06

0 531