Rikkar

分类

1024程序员节(1) C++(3) codeforces(5) dp(3) game(1) git(1) java(4) javaweb(2) math(14) maven(2) mysql(1) VS(2) 二分(5) 区域赛(1) 图(2) 思维(30) 数据结构(2) 新手入门(1) 暴力(3) 未归档(6) 板子(7) 构造(2) 模拟(3) 比赛(1) 笔记(1) 算法(27) 蓝桥杯(20) 规律(1) 贪心(1) 资料(1) 面试题集(1) 项目(1) 题解(44)

/ 注册

全部文章（共199篇）

C. The Hard Work of Paparazzi (dp)

题目思路：这是一道最长递增子序列的变式。 dp[i] 代表前i个名人中第i个名人被访问所能访问的最大名人数目先看暴力的方法，那么我们直接遍历前面所有情况当abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j] i<j 时dp[i]=max(dp[i...

2021-12-18

0 483

E. Accidental Victory （思维、二分）

题目思路：首先将数组排个序，容易知道要看一个数能不能成为冠军，其实就是将这个数从小到大不断与比他小于等于的数合并相加如果最终能够合并为一个数则其有成为冠军的机会。在这我们先看看暴力的思路，就是遍历每一个数然后让它与最小的数开始相加直到最终它不能再和后面的数相加（前面所有的总和都比后面的某个数...

2021-12-18

0 365

F. Equalize the Array (map、思维)

题目思路：看一个例子 x:y 表示拥有x个相同的数有y个(2:3 1 1 2 2 3 3) 现在有 4:5 3:3 1:8 即有5个数量为4的数 3个数量为3的数 8个数量为1的数现在我们要求使得剩下的数的数量都相同的最少删去数的个数，即让剩下数的个数最大我们假设要让最后所有的数...

2021-12-18

0 337

G. Old Floppy Drive (math、二分)

题目思路：失败的情况：n个数全部相加一遍总和<=0,且前缀和的最大数max也比所询问的数x小成功的情况：因为询问的次数较多，用二分查找优化，先创造个二分的递增条件对于能在一个循环就找到符合条件的答案 x<=max(上文提及) 模拟一下过程，3 -2 2 -1 5 4 -3 ...

2021-12-18

0 378

C. Floor and Mod (分块整除)

题目 a/b=i, a%b=i -> a=i*(b+1)，(对于一个b可以配出几个i就可以产生几个贡献)可以知道对于给出的x,y 取任意1<=b<=y，一个b产生的贡献为min(x/(b+1)，b-1) 当x>=(b+1)(b-1)时对于此时的b的贡献全取b-1 当x&...

2021-12-18

0 401

C. Mind Control （暴力）

题目思路：先来看一个简化版的问题，就是对于 2 9 2 3 8 5 ，我是第3个人，那么答案其实就是前面二人取(前面两个)2，9 max(2,5)=5 前后各一个 2，5 max(9,8)=9 后面两个 8, 5 max(2,3)=3 答案为min(5,9,3)=3 即最小都能达到的先在...

2021-12-18

0 325

D. Irreducible Anagrams (思维、前缀和、构造)

题目题意：一个字符串如果只是其中字符顺序被打乱则称其和原字符串相互为字谜。对于两个互为字谜的字符串，两个字符串按相同的位置分割开成为n(n>=2)个小串，然后每个小串都互为字谜，则称这两个字符串是互为可还原的，现在给我们一个字符串，再给出q次问询，每次问询给出一个区间，要我们判断区间内的字...

2021-12-18

0 373

1438C - Engineer Artem （构造）

题目思路：如横纵坐标相加为奇数则将对应位置的数变为奇数+1或不加，如横纵坐标相加为偶则将对应位置数变为偶数。这题我觉得要培养一种感觉，看到一个题目，它给了什么条件要按给的条件那个方向去多思考一下，就像本题说可以加一或不加，那么我们想想加一其实比较容易想到的就是改变奇偶性。而有些题它给了一些数...

2021-12-18

0 316

1408D - Searchlights （思维、枚举）

题目从结果来分析，最小的步数必然是往右走多少步使一部分盗贼到达安全区域，然后再向上走一部分使余下的盗贼到达安全区域。那么我们从0到1e6+1枚举所有向右走的步数加上在该步数下最小向上走的步数，取其中最小值即为答案。那么问题来了，这个最小向上走的步数我们如何能够快速得到答案？其实只需要一个从后往前...

2021-12-18

0 370

D. Max Median （二分、思维）

题目从结果分析，答案必定是数组中的一个值，那么我们将值排个序开始二分。check的话，对于我们将要检查的值mid，将原数组中所有小于mid的值设为-1，大于等于mid的值设为1，对于一段区间看其中位数是否>=mid，只要看变化后该区间的总和，如果>0则其中位数>=mid。用一个...

2021-12-18

0 661