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) 蓝桥杯(20) 规律(1) 贪心(1) 资料(1) 面试题集(1) 项目(1) 题解(44)

/ 注册

全部文章 / 算法（共27篇）

1199D - Welfare State（思维）

题目题意：对于n个公民，我们知道其一开始的各自的金钱。现在我们有两种操作：1.直接将各个钱数小于k的公民的钱数转变为k。2.将第p个人的钱数抓变为k。问经过q次操作后，每个人最后的钱数为多少？思路：我们将一个人的金钱变化阶段定为两个，在q次操作中一个人在最后一次操作2，金钱直接变为了m0,后...

2021-12-18

0 503

1462E2 - Close Tuples (hard version)（组合数）

题目思路：先对数组排序，然后算出每个数的贡献，先从第一个数开始找到第一个大于它的值+k的数（二分），下表差即为可选的构成m个数元组的可选数的个数s，如果s<m贡献0，如果s>=m,贡献为从s-1个数中选出m-1个数的方法数（已经选了一个数）。但求组合数的模问题，不可以对两个相除的数先...

2021-12-18

0 403

排序算法的实现及性能测试及比较

在书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过具体数据比较各种算法的关键字比较次数和记录移动次数，以取得直观感受。要求：（1）编写程序创建一些整数文件用于排序。创建的这些文件可以根据需要生成不同的长度，如长度分别为20，200和2000，以正序、逆序...

2021-12-18

0 707

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

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

2021-12-18

0 375

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

逆元

参考于此篇博客：https://www.cnblogs.com/kongbursi-2292702937/p/10582258.html 逆元定义：对于a*b≡1(mod m)，b是a在模m下a的逆元。首先对于同余符号≡，如 a≡b%m 表示的意思是a%m=b%m,a、b模m后余数相同。 ...

2021-12-18

0 340

D. Radio Towers（dp、逆元）

题目思路：状态方程dp[i]代表从1–n都被照亮的方法数。 dp[i]=dp[i-1]+dp[i-3]+dp[i-5]+dp[i-7]… 可以看一个例子i=5，假设0表示没照亮1表示照亮 dp[5] 1到5都亮可以由以下状态转变而来 dp[4] 11110 在i=5处放亮度为1的灯 dp[2]...

2021-12-18

0 404

1372 D. Omkar and Circle (思维、前缀和)

题目思路：对于为n的奇数，可以进行(n-1)/2次让一个数取代相邻两数操作，直到最后只剩下一个数，其实每次操作就是删掉了一个数，那要如何让删除后的总和最大？首先贪心一下，我们一定不能删掉变成了两个数相加的那个数，如 1 2 3 4 5 假设第一步删掉1 -> 7 3 4 那之后删掉的数不...

2021-12-18

0 373

C. Floor and Mod (分块整除)

题目 a/b=i, a%b=i -> a=i*(b+1)，(对于一个b可以配出几个i就可以产生几个贡献)可以知道对于给出的x,y 取任意1<=b<=y，一个b产生的贡献为min(x/(b+1)，b-1) 当x>=(b+1)(b-1)时对于此时的b的贡献全取b-1 当x&...

2021-12-18

0 401