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)

/ 注册

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

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

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

2019-08-10

0 546

【算法学习】尺取法

基础模板求和大于等于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牛客多校第九场

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

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

2019-08-15

0 595

luoguP4578_ [FJOI2018]所罗门王的宝藏

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

题解图论差分约束

2019-08-16

0 513

2019牛客多校第十场

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

题解思维分治数论线段树

2019-08-19

0 418

luoguP3588_[POI2015]PUS

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

题解线段树图论拓扑排序

2019-08-20

0 529

uoj218_火车管理

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

题解主席树线段树

2019-08-21

0 507

luoguP2444_[POI2000]病毒

题意给定多个01模式串，问是否存在一个无限长的字符串不包含任何一个模式串。分析好像数据有点水，网上一大堆题解连样例都没过？？？多模式串，先把AC自动机建出来再说。反向考虑，若存在一个无限长的字符串不包含任何一个模式串，那就说明这个字符串可以在AC自动机上无限匹配，所以我...

题解字符串 AC自动机 dfs

2019-08-22

0 458

2018icpc宁夏邀请赛网络赛_G_Trouble of Tyrant

题意一列\(n\)个点，给定一个特殊的图，有两种边\(E(1,i)\)和\(E(i-1,i)\)，多个询问，每次给一个\(d\)，求所有路径长度加上\(d\)后1到\(n\)的最短路。分析首先这图很特殊，大胆猜测不是图论。 1到\(n\)的最短路包括\(p_i\)，即1直接到\...

题解单调栈凸包思维

2019-08-23

0 455