这组题都来自洛谷,题型很典型,适合拿来练手。它们不算那种靠灵感硬冲的题,更多是把算法模板真正用到题目里:模幂、构造图、状态转化后的背包、贪心排序、DFS 剪枝、以及用小根堆维护最小结束时间。
题目清单
1. 转圈游戏
题目: P1965 [NOIP 2013 提高组] 转圈游戏
解法:数学 + 快速幂
题意其实很直接:一圈 n 个数,移动后的位置可以写成 (x + m * 10^k) % n。麻烦点不在公式,而在 10^k 很大,不能老老实实算,只能做取模快速幂。
这题就是标准的'会公式不难,卡在幂太大'。long long 足够用,边乘边取模就行。
代码:
#include <iostream>
using namespace std;
typedef long long LL;
LL n, m, k, x;
LL qpow(LL a, LL b, LL p) {
LL ret = 1;
while (b) {
if (b & 1) ret = ret * a % p;
b >>= 1;
a = a * a % p;
}
ret;
}
{
cin >> n >> m >> k >> x;
cout << (x + m * (, k, n)) % n << endl;
;
}



