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

D. A Leapfrog in the Array （思维）

题目思路：经过模拟可以发现对于一个元素的移动每次移动量是之前一次的两倍，如果将列表倒过来从0开始，那么每次元素的位置移动便是x=2x+1，现在给出了最后的某个位置，那么我们只需逆转x=(x-1)/2直到位置为偶数就是开始移动的位置，因为列表倒置后所有元素位置会变为偶数，而每次进行x=2x+1又会...

2021-12-18

0 409

E1. Square-free division (easy version) (数论、思维)

题目思路：首先贪心的想一想，我让每一段尽可能长，则最后的段数就可能越少。再来看什么时候一个数是平方数，将一个数质因数分解 X=a^x1 * b^x2 * c^x3… 只要让一个数的x1 x2 x3…xn都为偶数即可那我们只需发现如果有相乘的两个数各自的质因数次方相加全为偶数则会组成一个平方...

2021-12-18

0 363

C - k-LCM (easy version AND hard version) (构造、思维)

题目思路：先来考虑k=3的情况，如果n为奇数则三个数分别为 1 n/2 n/2，这样最大是n/2。如果n为偶数，如果n%4==0，则三个数为 n/4 n/4 n/2，反之先将n=n/2 则又变为了奇数的情况三个数为 21 2(n/2) 2*(n/2) 对于hard情况，可以发现如果k越大...

2021-12-18

0 456

B. Binary Removals （思维）

题目思路：想要出现否的情况那一定会有0在1的后面，而我们的删除操作只能隔着删，所以当出现两个00或两个11必然会留下一个，所以从后往前遍历，如果发现出现00之后又出现11则最终无论怎么删都会留下一个…1…0…的情况。 #include<iostream> #include<c...

2021-12-18

0 401

C. Minimum Grid Path (贪心)

题目思路：贪心的想如果要使花费尽量小，那就让第一第二小的线段一个向上一个向右尽可能长，只需枚举即可。但是由于有一个每次需要转弯的限制，所以需要分为奇偶，分别记录奇偶前面最小的cost，让奇数的线段向上，偶数的线段向右，先将其余线段长度全部取为1，然后让剩下的长度分别由向上和向右的最小cost线段...

2021-12-18

0 561

E. Nezzar and Binary String（逆向思维+线段树）

题目思路：从逆向想一下，发现最后得到的一定是最后的字符串f，然后往前推，因为只能改变<len/2的元素，不难发现改变已经定下来了，即只能全改为数量大的那个字符，如果长度为偶数两种字符相等则不能达成。维护和查找用线段树覆盖。 down的一个修改 Code: #include<io...

2021-12-18

0 391

C. Basic Diplomacy （思维、贪心）

题目思路：首先为NO的情况只有，某一天只可以选一个人且某人在只可以选他的情况下被选了>⌈m2⌉次。除了这种情况，其它情况不可能为NO，看一个极端的例子，总共有8天，有两个朋友1和2，有4天全是只可以选1，其它4天都是可以选1或2。那么只要让其它的天数全选2即可，2也不会超出⌈m2⌉次。 ...

2021-12-18

0 478

C. Electrification (贪心、思维、尺取)

题目思路：对于每个有k+1个元素的区间必然会存在一个x使得第k+1个元素-x为第k+1个最大，我们要想让这个结果最小则取(lst[i]+lst[i+k]+1)/2为x。即使这样求得的x可能不会使最近的x个元素刚好为此区间的，但这个x求得的最小值在之后的区间也会被另外的最小值给替换掉（具体原因可以...

2021-12-18

0 408

2019 China Collegiate Programming Contest Qinhuangdao Onsite

F. Forest Program（图论、环的求取）思路：如果没有环的话，每个元素都没有限制，总贡献2^n。但条件是必须使剩下的图全是树，也就是说环必须去掉。那么直接dfs深度优先搜索，看有多少个环，用deep记录长度。每遍历到一个环就把乘上这个环的贡献 pow(2,环的长度)-1（这个环只有所...

2021-12-18

0 513

C. Nauuo and Cards （贪心、思维）

题目思路：首先想能不能在原有的b中出现* * * * 1 2 3 … k，如果可以的话则利用b中原有的再添上前面的即可构成1 2 3 …n，但这个构成有一个限制，对于每一个从k往后添加k+1 k+2 … n一定要连贯着一次性达成，如果中间出现k+x没取的到，要再从前面取几个用0做缓冲，则该顺序一...

2021-12-18

0 346