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

1481C Fence Painting (list、map)

题目思路：对于失败有两种情况： 1.统计所有的需要修正成各种颜色的数目，如果发现对于一种颜色我们所拥有的画师数少于所需修正的数目，则失败。 2.我们会发现其实可能有画师会画不属于b[i]中所有的颜色，如果这个画师是最后一位画师（最后画）那么没有任何的画师可以在之后将他的画修改为正确颜色，失败。...

2021-12-18

0 354

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 - AB Graph (构造、图)

题目思路：分为两种情况： 1.当m为奇数时，直接12121212…构造出的一定是回文。 2.当m为偶数时，可以知道n>=3时一定可以构造出。证明如下：当1，2，3三个点中出现来回字母一样，只需两个点不断循环即可。当无上述情况，来回必然是a,b交叉，因此我们一定可以找到如下的图。其实...

2021-12-18

0 387

逆元

参考于此篇博客：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

1368 D. AND, OR and square sum (贪心、位运算)

题目思路：看一个例子对于两个二进制数 1100101 0100100 AND结果：0100100 OR结果：1100101 如果两个二进制位都为1或0，AND OR 中结果不变还是1或0，如果一个是0 一个1，就会把1转到OR结果中AND中的那个位变为0。我将这个过程看作是一个让1往一个数(O...

2021-12-18

0 298

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

C. Minimum Ties (构造)

题目当n为奇数，构造第一人获胜情况前(n-1)/2项为1，后(n-1)/2项为-1，其余人的获胜情况就是前一人往后滚动一位如：n=5 第一人对第二三四五人的情况 1 1 -1 -1 第二人对第一三四五人的情况 -1 1 1 -1 第三人对第一二四五人的情况 -1 -1 1 1 第四人对第...

2021-12-18

0 397

F. Zero Remainder Sum（四维dp）

题目状态：dp[i][j][k][o] 代表第i行前j个数已经选定k个数余o最大总和的值首先来单独看一行，lst[i][j] 代表第i行第j个数 dp[i][j][k][o]=dp[i][j-1][k][o] , 此代表在第i行我们不选第j个数，所以选定的个数k不变，余数也不变 dp[i...

2021-12-18

0 416