2019年5月 – 🔭望远镜开启之时

洛谷P1023 税收与补贴问题

考完数电,又要开始入坑了…(●’◡’●)

这题理解题意很重要啊,我看了半天它的样例,感叹这样例都不是线性的啊,后来发现是我理解题意错了,相邻价位的销量变化是线性的,这里指的是给出的相邻价位之间的销量变化是线性的,然后中间空缺的价位销量就要依靠此求出.

要求绝对值最小,一开始[……]

题目链接:CH4201

对某个点,求前面和后面分别有多少个点的纵坐标是比它大的,两数相乘就是以该点为中间点,能构成的"v"的数量.

"^"同理.

code:

#include <algorithm>
#include <cmath>
#[......]Read More

题目链接:BZOJ 4195

在数据范围大,但实际数据个数不大的时候,采用离散化避免超出数组空间.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring[......]Read More

题目链接:BZOJ 1951

通过欧拉定理的推论得到组合数部分的模数后,用Lucas定理计算,但是模数不是质数,对模数分解质因数后发现所有质因子的指数都是1,于是用中国剩余定理合并方程.具体思路可见《算法竞赛进阶指南》172页.

调了好久,才发现是快速幂的参数写错了.不多说了,直接上代码吧…心态[……]

题目链接: POJ 2891

题意:给出\(n\)对\(a_i,r_i\), 求一个最小正整数\(m\)满足\(m \equiv r_i\pmod a_i\), 或者给出无解.

solution:

\(a_i\)并不保证两两互质, 所以不能用中国剩余定理. 但可以通过数学归纳法, 用拓展欧几里得逐步[……]

题目链接:CH3601

通过逆元计算组合数.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream&[......]Read More

题目链接:POJ 1704

题图:

这题可以转化为NIM博弈.如果棋子为偶数,则从前往后两个两个成对,每对棋子中间的空位看作是一堆石子,多少个空位就多少个石子.如果棋子数为奇数,则在第0个位置加入一个虚拟棋子,然后按偶数情况处理.

容易想到,对于每一对棋子,如果将后面一个棋子往前移,则等效于将该堆[……]

[mathjax]
题目链接:POJ 2975

题意: 问从给定局面,先手有多少种方法使其转换为必败态.

思路:典型的NIM博弈,但不是求谁必胜必败. 检查每个位置是否可以拿走若干个石子使所有堆的异或值为0,即当某一堆的石子数大于其他堆石子数的异或值时,可以通过拿走该堆石子若干,使其与其他堆石子数异[……]

[mathjax]

题目链接 :CH3301

用拓展欧几里得算法求出一组特解\(x_0,y_0\),则\(x_0\)就是原方程的一个解,通解为所有模\(b\)与\(x_0\)同余的整数.题目要求是最小正整数解,可通过取模操作把解的范围移动到\([1,b)\)之间,\([1,b)\)之间的就是最小正整[……]

[mathjax]
题目链接：POJ1845

题意:求\(A^B\)的所有约数之和\(\mod 9901\), \(1 \le A,B \le 5*10^7 \).

把A分解质因数,可以得到约数和为:
\((1+p_1+p_1^2+…+p_1^{B*c_1})*(1+p_2+p_2^2+…+[……]