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牛客多校第一场

A Equivalent Prefixes 题意给两个序列a和b，找出最大一个位置p，使得两个序列1-p的子序列中，任意区间的最小值位置相同。分析最小值的位置考虑用单调栈预处理出每个数作为最小值的最左和最右的位置，然后从1开始枚举，对于某个位置i，如果\(a_i\)和\(b_i\)作为...

单调栈数学推导积分异或线性基 dp 线段树线段树优化dp 大数题解

2019-07-25

0 583

Codeforce1196_D_F

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

题解思维前缀和最短路 floyd

2019-08-06

0 528

2019牛客多校第二场

A Eddy Walker 题意一个0到n-1的环，初始在0，每次随机前进或后退一格，当所有点都访问过就结束，问结束时站在k的概率是多少。(注意输出的是前缀积) 分析一开始站在0，最后显然不可能在0，剩下n-1格，随机数打表发现概率相同，都为\(\frac{1}{n-1}\) 代码 ...

题解概率打表 BM递推图论状压优先队列 dp 线段树矩阵暴力搜索单调栈

2019-07-25

0 591

2019杭电多校第一场

6581 Vacation 题意从右到左分别为0-n辆车，每辆车有长度l，起始位置s和速度v，0坐标在左边，不能超车，单车道，问0号车到达0坐标的最短时间。分析最短时间考虑二分时间，然后按这个时间从左边第一辆车开始依次计算最终位置，最后判断0号车的位置即可。代码 #include...

二分答案图论最短路网络流最小割字符串序列自动机贪心题解

2019-07-26

0 605

hdu3416+hdu6582(最短路+最大流)

题意 hdu3416：给一个图，边不能重复选，问有多少个最短路 hdu6582: 给一个图，问最少删除边权多少的边后，最短路长度增加分析边不能重复选这个条件可以想到边权为1，跑最大流，所以我们可以先跑出最短路，再把最短路中的边作为网络流中的边跑一遍最大流即可。最短路长度增加即最...

题解图论最大流最小割

2019-07-26

0 505

2019杭电多校第二场

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

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

2019-07-26

0 481

2019牛客多校第四场

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

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

2019-07-27

0 491

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

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

2019-08-05

0 433

2019牛客多校第七场

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

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

2019-08-09

0 523