算法竞赛进阶指南-0x02基本算法-递推与递归

费解的开关

题意:
25 盏灯排成一个 5×5 的方形。
每一个灯都有一个开关,游戏者可以改变它的状态。
每一步,游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应:和这个灯上下左右相邻的灯也要相应地改变其状态。
给定一些游戏的初始状态,编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。

Solution:
我们枚举第一行的点击方法,共 32 种,完成第一行的点击后,固定第一行,
从第一行开始递推,若达到第 n 行不全为 0 ,说明这种点击方式不合法。
在所有合法的点击方式中取点击次数最少的就是答案。

Code:

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int inf = 0x7f7f7f7f;

int t;
int n;
char g[6][6], b[6][6];
int dir[5][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {0, 0}};


void turn(int x, int y){
    for(int i = 0; i < 5; i ++){
        int dx = dir[i][0] + x;
        int dy = dir[i][1] + y;
        if(dx >= 0 && dx < 5 && dy >= 0 && dy < 5){
            g[dx][dy] = (g[dx][dy] == '0' ? '1' : '0');
        }
    }
}

void solve(){
    int ans = inf;
    for(int k = 0; k < 32; k ++){
        int res = 0;

        memcpy(b, g, sizeof g);
        for(int j = 0; j < 5; j ++){
            if(k >> j & 1){
                res ++;
                turn(0, j);
            }
        }

        for(int i = 0; i < 4; i ++){
            for(int j = 0; j < 5; j ++){
                if(g[i][j] == '0'){
                    res ++;
                    turn(i + 1, j);
                }
            }
        }

        int f = 0;
        for(int j = 0; j < 5; j ++){
            if(g[4][j] == '0'){
                f = 1;
                break;
            }
        }
        if(!f)  ans = min(ans, res);
        memcpy(g, b, sizeof b);
    }
    if(ans > 6)  puts("-1");
    else    printf("%d\n", ans);
}

int main(){
    __;
    cin >> t;
    while(t --){
        for(int i = 0; i < 5; i ++){
            for(int j = 0; j < 5; j ++){
                cin >> g[i][j];
            }
        }
        solve();
    }
    return 0;
}

奇怪的汉诺塔

题意:
四个塔,n 个盘子,输出一个满足条件的最小移动次数。

Solution:
如果是 3 个盘子,递推式显然是 D[n]=2 * D[n-1]+1
那么如果是 4 个盘子,我们可以先把 i 个盘子在四塔模式下,移动到一根柱子上,然后把 n-i 个盘子,移动到 D柱上。
f[i] = min(f[i], 2 * f[i] + D[n-i]), f[1]=1

Code:

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)


int n;
int f[15], d[15];

int main(){
    __;
    for(int i = 1; i <= 12; i ++){
        d[i] = d[i - 1] * 2 + 1;
    }
    memset(f, 0x3f, sizeof f);
    f[1] = 1;
    for(int i = 2; i <= 12; i ++){
        for(int j = 1; j < i; j ++){
            f[i] = min(f[i], 2 * f[j] + d[i - j]);
        }
    }
    for(int i = 1; i <= 12; i ++){
        printf("%d\n", f[i]);
    }
    return 0;
}

约数之和

题意:

有两个自然数 AB, SA^B的所有约数之和。
S \ mod \ 9901 ,其中 0 <= A,B <= 5×10^7

Solution1:
分治法:

令f\left( p,k \right) =p^0+p^1+p^2+\cdot \cdot \cdot +p^{k-1}

k偶数时:

f\left( p,k \right) =p^0+p^1+p^2+\cdot \cdot \cdot +p^{k/2-1}+p^{k/2}+p^{k/2+1}+\cdot \cdot \cdot +p^{k-1}

等价于:

f\left( p,k \right) =p^0+p^1+p^2+\cdot \cdot \cdot +p^{k/2-1}+p^{k/2}\left( p^0+p^1+\cdot \cdot \cdot +p^{k/2-1} \right)

也就是:

f\left( p,k \right) =f\left( p,k/2 \right) +p^{k/2}f\left( p,k/2 \right)

进一步化简:

f\left( p,k \right) =f\left( p,k/2 \right) \left( 1+p^{k/2} \right)

k奇数时:

f\left( p,k \right) =f\left( p,k-1 \right) +p^{k-1}

Code:

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 3e5+10;
const ll mod = 9901;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

ll a, b;
ll ans = 0;
ll p[N], c[N];
int cnt = 0;

void div(ll n){
    for(int i = 2; i <= n / i; i ++){
        if(n % i == 0){
            p[++ cnt] = i;
            while(n % i == 0){
                n /= i;
                c[cnt] ++;
            }
        }
    }
    if(n > 1){
        p[++ cnt] = n;
        c[cnt] = 1;
    }
}

ll qpow(ll a, ll b){
    ll ans = 1ll % mod;
    while(b){
        if(b & 1)   ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

ll f(ll p, ll k){
    if(k == 1)  return 1;
    if(k % 2 == 0){
        return  (qpow(p, k / 2) + 1ll) * f(p, k / 2) % mod;
    }
    return qpow(p, k - 1) + f(p, k - 1) % mod;

}

int main(){
    __;
    cin >> a >> b;
    ans = 1;
    if(a == 0)  ans = 0;
    else{
        div(a);
        for(int i = 1; i <= cnt; i ++){
           ll pr = p[i], k = c[i] * b;
           ans = ans * f(pr, k + 1) % mod;
        }
    }

    printf("%lld\n", ans % mod);
    return 0;
}

Solution2:
公式法:

\left( p_1^0+p_1^1+p_1^2+\cdot \cdot \cdot +p_1^k \right) ^B\left( p_2^0+p_2^1+p_2^2+\cdot \cdot \cdot +p_2^k \right) ^B\cdot \cdot \cdot \left( p_n^0+p_n^1+p_n^2+\cdot \cdot \cdot +p_n^k \right) ^B

=\left( p_1^0+p_1^1+p_1^2+\cdot \cdot \cdot +p_1^{kB} \right) \left( p_2^0+p_2^1+p_2^2+\cdot \cdot \cdot +p_2^{kB} \right) \cdot \cdot \cdot \left( p_n^0+p_n^1+p_n^2+\cdot \cdot \cdot +p_n^{kB} \right)

=\frac{\left( 1-p_1 ^{kB+1} \right)}{1-p_1}\frac{\left( 1-p_2^{kB+1} \right) }{1-p_2}\cdot \cdot \cdot \frac{\left( 1-p_n^{kB+1} \right) }{1-p_n}

=\frac{\left( p_1^{kB+1}-1 \right)}{p_1-1}\frac{\left( p_2^{kB+1}-1 \right)}{p_2-1}\cdot \cdot \cdot \frac{\left( p_n^{kB+1}-1 \right)}{p_n-1}

注意:当 p-1 \ | \ mod 时,逆元不存在,直接计算

1+p_1+p_1^2+\cdot \cdot \cdot +p_1^k

Code:

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 3e5+10;
const ll mod = 9901;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

ll a, b;
ll ans = 0;
int p[N], c[N];
int cnt = 0;

void div(ll n){
    for(int i = 2; i <= n / i; i ++){
        if(n % i == 0){
            p[++ cnt] = i;
            while(n % i == 0){
                n /= i;
                c[cnt] ++;
            }
        }
    }
    if(n > 1){
        p[++ cnt] = n;
        c[cnt] = 1;
    }
}

ll qpow(ll a, ll b){
    ll ans = 1ll % mod;
    while(b){
        if(b & 1)   ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int main(){
    __;
    cin >> a >> b;
    ans = 1;
    if(a == 0)  ans = 0;
    else{
        div(a);
        for(int i = 1; i <= cnt; i ++){
            if((p[i] - 1) % mod == 0){
                ans = ans % mod * (1ll * c[i] * b + 1ll) % mod;
            }
            else{
                ll x = (qpow(p[i], (1ll * c[i] * b + 1ll)) % mod - 1ll + mod) % mod;
                ll y = qpow(p[i] - 1ll, mod - 2ll) % mod;
                ans = ans % mod * x % mod * y % mod;
            }
        }
    }

    printf("%lld\n", ans);
    return 0;
}

分形之城

题意: 蓝书P18

Solution:

Code:

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

const int N = 3e5+10;
const ll mod = 9901;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

int t;

P f(ll n, ll m){
    if(n == 0)  return {0, 0};
    ll len = 1ll << (n - 1);// n - 1级图构成n级图平移时的单位长度
    ll cnt = 1ll << (n - 1) * 2;// n - 1级图中所含的元素个数
    ll cnk = m / cnt; // 在n级图中,编号为m的元素所属块的编号
    ll idx = m % cnt; // 在n级图中,编号为m的元素在所属块中的编号
    P pos = f(n - 1, idx); // 在n级图中,编号为m的元素在所属块中的坐标
    // 根据n级图中某个块的编号和这个块中某个元素的坐标,确定n - 1级图的坐标变换
    ll x = pos.fi, y = pos.se;
    if(cnk == 0)   return {y, x};
    else if(cnk == 1)   return {x, y + len};
    else if(cnk == 2)   return {x + len, y + len};
    else    return {2 * len - 1 - y, len - 1 - x};
}

int main(){
    __;
    cin >> t;
    while(t --){
        ll n, a, b;
        cin >> n >> a >> b;
        P pa = f(n, a - 1);
        P pb = f(n, b - 1);
        double dis = sqrt((double)(pa.fi - pb.fi) * (pa.fi - pb.fi) + (pa.se - pb.se) * (pa.se - pb.se));
        printf("%.0lf\n", 10 * dis);
    }
    return 0;
}

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注