Rikkar

math

1024程序员节(1) C++(3) codeforces(5) dp(3) game(1) git(1) java(4) javaweb(2) 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)

/ 注册

全部文章 / math （共14篇）

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

D - Two Divisors (素数筛)

题目首先：对于gcd有 gcd(a,b)=gcd(a+b,b) 且若gcd(a,b)=1, 则gcd(a,c)=gcd(a,c*b)=gcd(a,c * b^n) 现有gcd(d1,d2)=1,->gcd(d1+d2,d1)=1,gcd(d1+d2,d2)=1 ->gcd(d1+d2...

2021-12-18

0 476

D. Pythagorean Triples (math、暴力)

题目题解：因此c=(a*a-1)/2+1 我们暴力枚举a,从a=1到（a * a-1)/2+1<=n (C需要<=n) 如果满足(a * a-1)%2==0，即b为整数，且c=b+1，C也为整数，符合条件，贡献+1 Code: #include<iostream> ...

2021-12-18

0 415

G. Old Floppy Drive (math、二分)

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

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

A. Deadline （不等式、分块整除）

题目分块整除⌈x+d/（x+1）⌉=⌊x+(d+x)/(x+1)⌋=1+⌊x+(d−1)/(x+1)⌋ Code: #include<iostream> #include<cmath> using namespace std; typedef long long...

2021-12-18

0 382

B. Yet Another Meme Problem (math)

题目 a * b+a+b=a * 10^n+b a * b+a=a*10^n b+1=10^n 故b=9 99 999 9999… 都满足情况，答案为a的个数乘1 —B中满足条件的b的数目 #include<iostream> #include<cmath> using ...

2021-12-18

0 409