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)

/ 注册

全部文章（共7篇）

2019牛客多校第一场

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

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

2019-07-25

0 583

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

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

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

2019-07-27

0 491

2019牛客多校第六场

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

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

2019-08-05

0 433

gym101666题解

A Amsterdam Distance 题意求圆环上的两点距离。分析显然是沿半径方向走到内圈再走圆弧最短。代码 #include <bits/stdc++.h> using namespace std; double m,n,r,sx,sy,tx,ty; const...

题解思维博弈 gcd 最短路 dp 二分二分图 dfs 线段树

2019-10-05

0 534

Codeforces1256E_Yet Another Division Into Teams

题意 n个人，每人有一个能力值a[i]，要求分成多个队伍，每个队伍至少3个人，使得所有队伍的max(a[i])-min(a[i])之和最小。分析不会巧妙的dp，想了一天只想到了暴力的dp。先排序，设\(dp[i]\)表示到前i个数组队，所有队伍的最小极差和。转移方程为\(...

优先队列 dp 题解

2019-11-05

0 385

gym102302E_Chi's performance

题意给n个二元组(v,p)，要求排序使得v从小到大，而且总价值最大，价值定义为相邻两个v值不同的p值之差绝对值之和。分析 in a row原来是相邻的意思。对于每个相同v值的块来说，有用的数只有最大，次大，最小，次小，且如果块大小小于4，还有一些会重复，后面需要特判。所以...

dp 题解

2019-11-07

0 329