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) 数据结构(2) 新手入门(1) 暴力(3) 未归档(6) 板子(7) 构造(2) 模拟(3) 比赛(1) 笔记(1) 算法(27) 蓝桥杯(20) 规律(1) 贪心(1) 资料(1) 面试题集(1) 项目(1) 题解(44)

/ 注册

全部文章 / 思维（共30篇）

B - Catch Overflow! (范围处理)

题目很容易想到用堆处理，但会有操作使得数值远大于long long.此时灵活将范围缩小，细节见代码。 #include<iostream> #include<stack> using namespace std; typedef long long ll; const ...

2021-12-18

0 371

D. GCD of an Array（数论、multiset）

题目对于n个元素的gcd，将每个元素质因数分解，对于一个质数如果每个元素都有其作为因数，那么这个质数p对答案的贡献为p^(所有元素分成质因数相乘中p的最小次方） a1=p1^b1 …* pi^c1* … pm^d1 a2=p1^b2 … * pi^c2 *… pm^d2 … an=pn ^ bn...

2021-12-18

0 402

C. Eugene and an array (区间为0前缀和处理)

题目思路：以每一个位置作为右端点取其前面为0区间的左端点的最大值为左端点，这一个字串就是以该位置为右端点，满足条件的最大长度的子串，它产生的贡献是(r-lmax-1,为了不把左端包含进去，包含进去就有为0的区间了),所有贡献相加即为答案。而对于如何判断一个区间是否为0，以及这个最大左端点的记...

2021-12-18

0 372

D. A Leapfrog in the Array （思维）

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

2021-12-18

0 409

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. Basic Diplomacy （思维、贪心）

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

2021-12-18

0 477

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

1506D Epic Transformation（思维、贪心）

题目思路：假设有只有一种数字，答案为该数字数量，两种数字，答案为大的数量减去小的数量，三种数字，假设数量从小到大排序 s1 s2 s3 ,可以知道当s1+s2<=s3, 答案为s3-(s1+s2) 当s1+s2>s3 ,如果(s1+s2+s3)%2 == 0,答案为0，(s1+s2+...

2021-12-18

0 562

1498B - Box Fitting (优先队列)

题目思路：开一个优先队列存放每一行（高度1）还剩余的长度，将所有的木块从大到小排序，1开始遍历，如果优先队列中还能容纳最大的长度比当前木块大则加入到当前高度所在行，否则另开一行存放。 Code: #include<iostream> #include<algorithm&g...

2021-12-18

0 383