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

1358 - D. The Best Vacation (贪心+二分+前缀和)

题目思路：贪心一下，要使拥抱次数最多必然是以每一个月的末尾为最后一天时，假设b(n-3) b(n-2) b(n-1) b(n) …c(1) c(2)… c(n)…a(n-4) a(n-3) 完后挪一个 b(n-2) b(n-1) b(n) …a(n-3) a(n-2) 当a(n-2)>b(...

2021-12-18

0 422

埃拉托色尼筛法（素数筛）

列举大于等于2的整数，将其倍数划掉，往后遍历发现被划掉的直接略过，还没被划掉的则是质数（表示其不是前面任何一个数的倍数，也即没有除1和本身外的因子）。时间复杂度 O(NloglogN)，空间 O(N). Code: int prim[Max], vis[Max], x = 0; //prim...

2021-12-18

0 375

1474 - C. Array Destruction (set、思维)

题目思路：可以知道一开始所选的两个数一定要包含最大的一个，假如不包含，那么后面的任何一个数加上最大的那个不可能构成另一个数，按着这个思路走下去，后面的每一步都需要包含还剩下的数中最大的数，如果不包含，理由同上，不可能继续构造下去。所以现在我们只需枚举一开始每一个数当成最初和最大数一起排除出去的即...

2021-12-18

0 403

1301D - Time to Run（思维、模拟）

题目思路：先进行一遍全部过程的模拟储存下来，为了方便模拟尽量先将相同的方向走完，而对于多少步step，将连续的相同方向当作一步，如DDDDDULLL->5D1U3L，只需判别存储好的全部模拟字符串前后不同步数+1即可，细节见代码。 #include<iostream> #...

2021-12-18

0 303

1293C - NEKO‘s Maze Game（分块、贡献）

题目思路：可以知道每一个点要想造成一个不能通过的结果，需要它的正对面左对面右对面，1岩浆0空地故我们将其贡献算为，如果当前为x,y为1->0，则贡献减少lst[3-x][y]+lst[3-x][y-1]+lst[3-x][y+1]，如果为0->1则减少，另y=1或n时特殊判断...

2021-12-18

0 362

1399D - Binary String To Subsequences（队列）

题目思路：看数据大小1e5可以知道我们需用O(n)或O(nlogn)的算法。故开两个队列，q0,q1，一个表示存储以0结尾一个存储以1结尾，当队列空时另增加一个新的子序列，不为空时将转变一个序列从q0->q1（当遇到1且q0中还剩下xxxx0的字序列时，不剩则再增加一个子序列），细节见代码...

2021-12-18

0 356

1475C Ball in Berland (思维)

题目思路：看N为2e5可知复杂度为O(n)或O(nlogn)，在这我用两个map分别记录每个男和女各自可以和多少匹配，首先选好一组匹配，那么还可以找出多少组匹配与之组成两组呢？答案为：k - 此组匹配中男生可以匹配女生数 - 此组匹配中女生可以匹配男生数+1（他们自身匹配那条线多匹配了一次）。 ...

2021-12-18

0 284

1475E Advertising Agency(组合数)

题目思路：选出K个博主，要使得总共关注者最大，先看一个简单例子如1 2 2 3 4 4 4 4 5 6 7 7 k=6最大为4+4+5+6+7+7=33.可以知道我们一定要选最大的后面6个博主 4 4 5 6 7 7 假设换了前面一个必然导致和不为最大值，而这六个博主其实5 6 7 7也已经定...

2021-12-18

0 457

1475E - Advertising Agency（dfs、dp）

题目思路：对于一个结点有四种情况00 11 10 01，其中00 11我们不需要重新交换。然后因为每个子树都可用其父亲及往上的结点的值交换。故我们从上到下更新每一个结点的交换值，其值为min(自己，父亲)。然后从1开始dfs，先深入到最底下结点,让下面的结点先进行交换（因为越往下的结点花费越少）...

2021-12-18

0 426

1334 - C. Circle of Monsters（贪心）

题目思路：当我们选定了一个怪物作为开始先杀掉后，对于余下的怪物我们一定要按顺序一个个杀掉，因为对于一开始被杀的后一个怪物（如果没炸死的话）我们最终一定要杀掉的，如果他是在他后面一个怪物被杀之后被杀那么它的爆炸不会产生贡献，我们在贪心的决断下，一定要先杀他让它的爆炸伤害物尽其用。那么其实我们只需枚...

2021-12-18

0 424