题目一 ： 递归实现指数型枚举
思路 ： 从左到右遍历每一个数 ， 以选和不选两个方式进行递归搜索
运行8ms 964KB
ll n;
void dfs(ll u, ll state) {
if (u == n) {
for (int i = 0; i < n; i ++ ) {
if (state >> i & 1) writet(i + 1);
}
swrite("");
return ;
}
dfs(u + 1, state);
dfs(u + 1, state | 1 << u);
}
inline void solve() {
n = read();
dfs(0, 0);
}
题目二 ： 递归实现组合型枚举
思路 ： 在上面代码的基础上 ， 多加上一个参量记录选过的数的数量 ， 在数量为 m 时 return ， 亦要在遍历到 n 时终止
运行70ms 1032KB
ll n, m;
void dfs(ll u, ll s, ll state) {
if (s == m) {
for (int i = 0; i < n; i ++ ) {
if (state >> i & 1) writet(i + 1);
}
swrite("");
return ;
}
if (u == n) return ;
for (int i = u; i < n; i ++ ) {
dfs(i + 1, s + 1, state + (1 << i));
}
}
inline void solve() {
n = read(), m = read();
dfs(0, 0, 0);
}
题目三 ： 递归实现排列型枚举
思路 ： 以选一个数的状态进行递归搜索
运行45ms 7076KB
ll n;
vector<ll> path;
void dfs(ll u, ll state) {
if (u == n) {
for (auto x : path) writet(x);
swrite("");
return ;
}
for (int i = 0; i < n; i ++ ) {
if (!(state >> i & 1)) {
path.push_back(i + 1);
dfs(u + 1, state + (1 << i));
path.pop_back();
}
}
}
inline void solve() {
n = read();
dfs(0, 0);
}
题目四 ： 费解的开关
思路 ： 我们将操作一行一行来看 ， 进行第一行操作后 ， 紧接着的第二行操作即被固定 ， 第三行 、 第四行 ... ， 所以我们只需以改变第一行后的所以状态往下判断是否可以将第五行变为全是 1 即可 。 若可以则与 res 取小 。
运行5ms 396KB
const int INF = 0x3f3f3f3f;
char g[5][5];
int dx[5] = {0, -1, 0, 1, 0}, dy[5] = {0, 0, 1, 0, -1};
void turn(int x, int y) {
for (int i = 0; i < 5; i ++ ) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < 5 && b >= 0 && b < 5) {
g[a][b] ^= 1;
}
}
}
int work() {
int res = INF;
for (int k = 0; k < 1 << 5; k ++ ) {
int sum = 0;
char backup[5][5];
memcpy(backup, g, sizeof backup);
for (int j = 0; j < 5; j ++ ) {
if (k >> j & 1) {
sum ++ ;
turn(0, j);
}
}
bool flag = true;
for (int i = 0; i < 4 && flag; i ++ ) {
for (int j = 0; j < 5; j ++ ) {
if (g[i][j] == '0') {
sum ++ ;
if (sum > 6) {
flag = false;
break;
}
turn(i + 1, j);
}
}
}
for (int j = 0; j < 5 && flag; j ++ ) {
if (g[4][j] == '0') {
flag = false;
break;
}
}
if (flag) res = min(res, sum);
memcpy(g, backup, sizeof g);
}
if (res > 6) return -1;
return res;
}
inline void solve() {
for (int i = 0; i < 5; i ++ ) cin >> g[i];
cout << work() << endl;
}
题目五 ： Strange Towers of Hanoi
思路 ： 奇怪的汉诺塔 ， 汉诺塔的相同思路 。
d[i] 表示 n 盘 3 塔的最小步数 递推式 ： d[n] = d[n - 1] * 2 + 1
f[i] 表示 n 盘 4 塔的最小步数 递推式 ： f[n] = min(f[i] + d[n - i])
一开始有 4 塔可用 ， 可先移动 i 个到 B ， 剩下的 n - i 个有 3 塔可用 ， 移动到 D ， 最后 B 上有 4 塔可用 ， 移动到 D
运行2ms 304KB
int d[15], f[15];
inline void solve() {
d[1] = 1;
for (int i = 2; i <= 12; i ++ ) {
d[i] = 1 + d[i - 1] * 2;
}
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (int i = 1; i <= 12; i ++ ) {
for (int j = 0; j < i; j ++ ) {
f[i] = min(f[i], f[j] * 2 + d[i - j]);
}
}
for (int i = 1; i <= 12; i ++ ) writen(f[i]);
}
题目六 ： Sumdiv
思路 ： 分治法
数学知识： A^B 的约数之和为（1 ~ p1^K1B）x（1 ~ p2^K2B）.....
对于 1 + p^1 + p^2 + p^3 可以将后面提取出 p^2 ，合并成 p^2 ( 1 + p ^ 1)
对于 1 + p^1 + p^2 可以先算出 p^2 , 再将前面进行合并成 p^2 + p^1 (1 + 1)
由此实现了这块的算法复杂度降为log(n)
运行3ms 424KB
ll sum(ll p, ll k) {
if (k == 0) return 1;
if (k % 2 == 1) return (1 + qmi(p, k / 2 + 1)) * sum(p, k / 2) % mod;
return (qmi(p, k) + (1 + qmi(p, (k - 1) / 2 + 1)) * sum(p, (k - 1) / 2)) % mod;
}
inline void solve() {
ll A = read(), B = read();
mod = 9901;
if (!A) {
writen(0);
return ;
}
if (!B) {
writen(1);
return ;
}
ll res = 1;
for (int i = 2; i <= A / i; i ++ ) {
ll k = 0;
while (A % i == 0) {
k ++ ;
A /= i;
}
res = res * sum(i, k * B) % mod;
}
if (A > 1) res = res * sum(A, B) % mod;
writen(res);
}
题目七 ： Fractal Streets
思路 ： 可以每次将一个大块分成四个小块 ， 然后进行取四分之一小块的递归 ， 特别注意坐标之间的变换关系 ， 我们递归是到第一小块取的 ， 要进行适当的坐标变换变到它应该在的位置 。
运行5ms 512KB
PLL calc(ll n, ll m) {
if (n == 0) return {0, 0};
//长度规律为1,2,4,8... ，我们计算分成四块的每块len
ll len = 1ll << (n - 1);
//数量规律为4,16,64... ，我们计算分成四块的每块cnt
ll cnt = 1ll << 2 * (n - 1);
//所在的区块
ll idx = m / cnt;
//所在区块中的编号
ll num = m % cnt;
PLL pos = calc(n - 1, num);
ll x = pos.first, y = pos.second;
if (idx == 0) return {y, x};
if (idx == 1) return {x, y + len};
if (idx == 2) return {x + len, y + len};
if (idx == 3) return {len * 2 - y - 1, len - x - 1};
return {0, 0};
}
inline void solve() {
ll n = read(), a = read(), b = read();
//对于模，我们可以将坐标减去1，以便计算
auto ac = calc(n, a - 1);
auto bc = calc(n, b - 1);
double x = ac.first - bc.first, y = ac.second - bc.second;
printf("%.0f\n", sqrt(x * x + y * y) * 10);
}
