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

C2. Guessing the Greatest (hard version) (二分、思维)

题目对于easy情况的做法是，对每个范围都询问两次第二大值，借用第二大值确定最大值所在范围，然后缩小范围。 hard情况的做法是，先询问第二大值所在位置p，然后根据最大值所在其左还是右分情况进行二分，其比easy询问次数少了一半是因为每次问询都使用mid—p（假设最大值在p左边），如果第二大值...

2021-12-18

0 598

二分模板

第一个>=x的位置 l while (l <= r) { int mid = (l + r) / 2; if (lst[mid] < x) l = mid + 1; else r = mid - 1; } 最后一个=x的位置 l-1 while (l <= r) { ...

2021-12-18

1 361

C. Maximum width (贪心、思维)

题目思路：对于答案我们只需求取每相邻的两个元素的最大相差再从所有的最大相差取最大的即可，那么贪心一下假如要求取的是第一个和第二个元素的最大相差，那么就是第一个元素第一次出现的位置和第二个元素最大的能使得后面能完全匹配第二个数组的位置。简单来说就是—在前面匹配好了的情况，后一个元素取最后面那个刚好...

2021-12-18

0 403

D. Genius‘s Gambit (构造、细节)

题目这一道题思路其实都有，主要细节比较多，我就wa了很多次… 对于x的构造前面b个a后面全是0 如 3 6 6 x:111111000 再看b的构造首先当k<=a 前面1—b-1全为1，第b+k个元素为1，其余0 如 4 3 2 x:1110000 y:1100100 当a&l...

2021-12-18

0 409

C. Long Beautiful Integer (构造)

题目思路：先构造成最小的情况，从前k个数的每个数开始，之后每隔k个数令其等于前面的该数，如 lst[3]=2 i=3(k=4) lst[7] lst[11] lst[15]…=lst[3]=2，如果此时构造出来的数满足大于原数，则输出。如果不满足则把lst[k] lst[2k] lst[3k]...

2021-12-18

0 343

B. Berland Crossword (构造)

题目对于下面这个图可以知道当U涂中间三个时是不会对其它的三种产生限制的，而如果涂了4个则必然会占到L R其中一个相邻的格子，涂了5个必然会占掉相邻的L R两个格子，这样就产生了限制，我们只需把不满足限制的情况为NO，其余为YES即可。我们来看满足条件的情况，假如U<mark>n,D&...

2021-12-18

0 378

D. Domino for Young （黑白染色）

题目运用黑白染色，求出的最少颜色的棋子就是答案。因为当把棋盘用黑和白染色后，每放一个格子必然会占掉黑格和白格各一个，看能最多占掉多少个相邻的黑白格。 Code: #include<iostream> using namespace std; typedef long long l...

2021-12-18

0 476

C. Division （质因数分解）

题目思路：首先如果a%b!=0,那答案直接为a。如果a%b==0，我们只需给a除以一个最小的数让a%b!=0即可。将a b质因数分解 a=a1^n1 * a2^n2 * a3^n3 * a4^n4 …an^nn b=b1^n1 * b2^n2 * b3^n3 * b4^n4 …bn^nn 可...

2021-12-18

0 334

D. Divide and Sum (组合数、思维)

添加链接描述对于任意分组可以发现其实差值是一样的，将绝对值拆开，会发现都是后面n个大的-前面n的小的。看例子 a1 a2 a3 a4 a5 b1 b2 b3 b4 b5 （已按大小排序）假设对于第一组取了前面3个，后面2个，然后其从很小到大排序，后面一组只可能是取前面2个，后面3个，从...

2021-12-18

1 442

D. Santa‘s Bot (概率、逆元)

题目首先每个礼物被抽到的概率不是均等的，是先从n个人里等概率选出一个人，再从k个礼物等概率选出一个礼物，第1个人每个礼物选中概率1/(nk1) 第二人 1/(nk2)。对于一个礼物c产生的贡献= (1/(nki))【其被选中的概率】(num[c]/n)【正确给到孩子的概率】，需要先记录出每个礼物...

2021-12-18

0 373