redoCxz
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)
归档
标签
去牛客网
登录
/
注册
redoCxz的博客
全部文章
/ 未归档
(共70篇)
gym102215题解
A Rooms and Passages 题意 给n个数,从起点出发,一直往右走,遇到一个前面出现过其相反数的正数就停下,问对于每个起点都能走多少步。 分析 倒着递推,如果起点是正数,那么肯定可以走,ans[i]=ans[i+1]+1。 如果起点是负数,那就得看这个负数对应绝对值在...
题解
思维
贪心
LCA
交互题
二分查找
枚举
2019-10-18
0
597
Codeforces6E_Exposition
题意 给定一个序列,求有多少个最长连续子序列满足最大值减最小值之差不超过\(k\)。 分析 跟序列最大值最小值有关的可以想到单调栈,先预处理出每个数作为最大值能延伸的区间,然后枚举每个数作为最大值。 最大的满足条件的连续序列显然左边就是要在\([le[i],i-1]\)里找到大于等于...
题解
单调栈
二分
线段树
2019-10-09
0
709
Codeforces893F_Subtree Minimum Query
题意 给定一棵树和根,每个点有点权,强制在线询问\(x\)子树里离\(x\)距离不超过\(k\)的最小点权。 分析 权值线段树合并的套路题,dfs,以深度作为下标,点权作为值,对每个点建立一颗权值线段树,然后回溯的时候合并到父节点的线段树上。 合并时维护最小值,查询时也是查询区间最小...
题解
线段树合并
dfs
2019-10-09
0
369
是男人就过八题A_A String Game
题意 给一个字符串\(s\),和\(n\)个子串\(t[i]\),两个人博弈,每次取出一个串\(t[i]\),在后面加入一个字符,保证新字符串仍然是\(s\)的子串,无法操作的人输。 分析 n个子串,类比于n堆石子,如果把子串\(t[i]\)在后面加若干字符能生成的子串看出一个状态,用一...
题解
字符串
后缀自动机
博弈
SG函数
2019-10-09
0
571
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
547
gym102201E_Eat Economically
题意 给\(2n\)个物品,分别有\(a,b\)属性,对于\(i=1...n\),选择\(i\)个\(a\)属性和\(i\)个\(b\)属性,且每个物品只能作为一种属性的贡献,求最小的值。 分析 看了题解补了两天... 应该叫做可反悔的贪心,或者其实就是网络流?不过因为是特殊的图,所以可...
题解
贪心
优先队列
2019-09-29
0
390
gym102346题解
B Buffoon 判断最大值是不是第一个数,签到题。 H Hour for a Run 输出\(n*m\)的\(10\%\)到\(90\%\),签到题,注意别用浮点数和ceil,有精度问题。 M Maratona Brasileira de Popcorn 题有点难读,就是给n个数,m个...
题解
二分
贪心
dfs
找规律
网络流
费用流
模拟
2019-09-28
0
606
gym102201F_Fruit Tree
题意 给一棵带权树,多次询问路径上出现次数超过一半的数。 分析 dfs序建主席树,维护的就是根到某个节点这段路径的值域情况。 因为题目所求的不是一般的众数,而是出现次数大于一半的,所以在主席树上可以直接二分,看两个子树的值域哪个大于一半,就走哪个子树,如果都为一半,返回-1。 树...
题解
主席树
dfs
2019-09-27
0
417
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
510
bzoj2141_排队
题意 给定\(n\)个数,每次交换两个数,输出交换后的逆序数。 分析 交换两个数只会影响到对应区间内的逆序数,具体为减少区间\([l+1,r-1]\)中比\(a[r]\)大的数的个数,增加比\(a[r]\)大的数的个数,减少比大的数的个数,\(a[l]\)增加比\(a[l]\)小的数的个...
题解
树套树
树状数组
权值线段树
2019-09-10
0
413
首页
上一页
1
2
3
4
5
6
7
下一页
末页