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)

/ 注册

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

Codeforce1196_D_F

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

题解思维前缀和最短路 floyd

2019-08-06

0 528

2019杭电多校第二场

6595 Everything Is Generated In Equal Probability 题意给定一个\(n\)，从\([1,n]\)中等概率取出一个数，再等概率生成一个\(n\)的全排列，再计算这个全排列的函数值，求这个函数值的期望。函数表达为输入一个全排列，计算其逆序数，再等...

题解概率思维主席树字符串回文树字符串哈希

2019-07-26

0 481

2019牛客多校第七场

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

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

2019-08-09

0 523

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

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

2019-08-10

0 541

2019牛客多校第十场

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

题解思维分治数论线段树

2019-08-19

0 0

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 448

2019icpc徐州网络赛

A Who is better? 题意 excrt+斐波那契博弈分析 Java的BigInteger对象默认为null，不能直接比较。代码 import java.math.BigInteger; import java.util.Scanner; public class Mai...

题解数论博弈并查集思维暴力 KMP 字符串回文树线段树树形dp 枚举

2019-09-07

0 415

2019icpc南昌网络赛_I_Yukino With Subinterval

题意给定一个序列，两种操作，单点修改，询问区间\([l,r]\)值域在\([x,y]\)范围内的连续段个数。分析原数组为\(a\)，构造一个新的数组\(b\)，\(b[i]=(a[i]==a[i-1])?0:a[i]\)，这样将连续段转化为左端点的一个数来表示。询问就可以转化...

题解树套树树状数组权值线段树思维

2019-09-10

0 511

Codeforces1093E_Intersection of Permutations

题意给定两个排列a和b，两种操作，交换b_i和b_j，询问a[l_a...r_a]和b[l_b...r_b]有多少个数相同。分析由于给的是排列，保证b的每个数都有a的对应，构造数组c，c[i]表示b[i]在a数组中的位置。所以询问就变成询问c[l_b...r_b]中有多少个值...

题解树套树思维

2019-09-11

0 501