洛谷P1023 税收与补贴问题 考完数电,又要开始入坑了…(●’◡’●) 链接:洛谷P1023 这题理解题意很重要啊,我看了半天它的样例,感叹这样例都不是线性的啊,后来发现是我理解题意错了,相邻价位的销量变化是线性的,这里指的是给出的相邻价位之间的销量变化是线性的,然后中间空缺的价位销量就要依靠此求出. 要求绝对值最小,一开始[……] Read More
CH4201 楼兰图腾(树状数组(顺)逆序对) 题目链接:CH4201 对某个点,求前面和后面分别有多少个点的纵坐标是比它大的,两数相乘就是以该点为中间点,能构成的"v"的数量. "^"同理. code: #include <algorithm> #include <cmath> #[......]Read More
NOI2015/BZOJ4195 -程序自动分析 (并查集+离散化) 题目链接:BZOJ 4195 在数据范围大,但实际数据个数不大的时候,采用离散化避免超出数组空间. code: #include <algorithm> #include <cmath> #include <cstdio> #include <cstring[......]Read More
BZOJ 1951-古代猪文 (好题,Lucas+CRT+逆元+EXGCD+快速幂) 题目链接:BZOJ 1951 通过欧拉定理的推论得到组合数部分的模数后,用Lucas定理计算,但是模数不是质数,对模数分解质因数后发现所有质因子的指数都是1,于是用中国剩余定理合并方程.具体思路可见《算法竞赛进阶指南》172页. 调了好久,才发现是快速幂的参数写错了.不多说了,直接上代码吧…心态[……] Read More
POJ 2891 -Strange Way to Express Integers 题目链接: POJ 2891 题意:给出\(n\)对\(a_i,r_i\), 求一个最小正整数\(m\)满足\(m \equiv r_i\pmod a_i\), 或者给出无解. solution: \(a_i\)并不保证两两互质, 所以不能用中国剩余定理. 但可以通过数学归纳法, 用拓展欧几里得逐步[……] Read More
NOIP2011 -计算系数 题目链接:CH3601 通过逆元计算组合数. code: #include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <iostream&[......]Read More
POJ 1704 -Georgia and Bob 题目链接:POJ 1704 题图: 这题可以转化为NIM博弈.如果棋子为偶数,则从前往后两个两个成对,每对棋子中间的空位看作是一堆石子,多少个空位就多少个石子.如果棋子数为奇数,则在第0个位置加入一个虚拟棋子,然后按偶数情况处理. 容易想到,对于每一对棋子,如果将后面一个棋子往前移,则等效于将该堆[……] Read More
POJ 2975 -Nim [mathjax] 题目链接:POJ 2975 题意: 问从给定局面,先手有多少种方法使其转换为必败态. 思路:典型的NIM博弈,但不是求谁必胜必败. 检查每个位置是否可以拿走若干个石子使所有堆的异或值为0,即当某一堆的石子数大于其他堆石子数的异或值时,可以通过拿走该堆石子若干,使其与其他堆石子数异[……] Read More
NOIP 2012-同余方程 [mathjax] 题目链接 :CH3301 用拓展欧几里得算法求出一组特解\(x_0,y_0\),则\(x_0\)就是原方程的一个解,通解为所有模\(b\)与\(x_0\)同余的整数.题目要求是最小正整数解,可通过取模操作把解的范围移动到\([1,b)\)之间,\([1,b)\)之间的就是最小正整[……] Read More
POJ 1845- Sumdiv [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+…+[……] Read More