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篇）

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 604

gym102201F_Fruit Tree

题意给一棵带权树，多次询问路径上出现次数超过一半的数。分析 dfs序建主席树，维护的就是根到某个节点这段路径的值域情况。因为题目所求的不是一般的众数，而是出现次数大于一半的，所以在主席树上可以直接二分，看两个子树的值域哪个大于一半，就走哪个子树，如果都为一半，返回-1。树...

题解主席树 dfs

2019-09-27

0 407

gym102201E_Eat Economically

题意给\(2n\)个物品，分别有\(a,b\)属性，对于\(i=1...n\)，选择\(i\)个\(a\)属性和\(i\)个\(b\)属性，且每个物品只能作为一种属性的贡献，求最小的值。分析看了题解补了两天... 应该叫做可反悔的贪心，或者其实就是网络流？不过因为是特殊的图，所以可...

题解贪心优先队列

2019-09-29

0 384

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

是男人就过八题A_A String Game

题意给一个字符串\(s\)，和\(n\)个子串\(t[i]\)，两个人博弈，每次取出一个串\(t[i]\)，在后面加入一个字符，保证新字符串仍然是\(s\)的子串，无法操作的人输。分析 n个子串，类比于n堆石子，如果把子串\(t[i]\)在后面加若干字符能生成的子串看出一个状态，用一...

题解字符串后缀自动机博弈 SG函数

2019-10-09

0 568

Codeforces893F_Subtree Minimum Query

题意给定一棵树和根，每个点有点权，强制在线询问\(x\)子树里离\(x\)距离不超过\(k\)的最小点权。分析权值线段树合并的套路题，dfs，以深度作为下标，点权作为值，对每个点建立一颗权值线段树，然后回溯的时候合并到父节点的线段树上。合并时维护最小值，查询时也是查询区间最小...

题解线段树合并 dfs

2019-10-09

0 366

Codeforces6E_Exposition

题意给定一个序列，求有多少个最长连续子序列满足最大值减最小值之差不超过\(k\)。分析跟序列最大值最小值有关的可以想到单调栈，先预处理出每个数作为最大值能延伸的区间，然后枚举每个数作为最大值。最大的满足条件的连续序列显然左边就是要在\([le[i],i-1]\)里找到大于等于...

题解单调栈二分线段树

2019-10-09

0 675

gym102215题解

A Rooms and Passages 题意给n个数，从起点出发，一直往右走，遇到一个前面出现过其相反数的正数就停下，问对于每个起点都能走多少步。分析倒着递推，如果起点是正数，那么肯定可以走，ans[i]=ans[i+1]+1。如果起点是负数，那就得看这个负数对应绝对值在...

题解思维贪心 LCA 交互题二分查找枚举

2019-10-18

0 598

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

Codeforces1256F_Equalizing Two Strings

题意给定两个字符串，可以任意选择s串的一段和t串的相同长度的一段进行翻转，无限次数，问能否通过翻转使得两个字符串相等。分析看了题解发现思路很巧妙。无限次数的子串翻转其实就是相邻两个字符的交换。首先字符串出现次数不同的肯定不行。然后如果某个字符出现次数大于1的，肯定...

树状数组思维题解字符串

2019-11-06

0 536