2018CCPC吉林区域赛 G. High Priestess

Aug 13, 2019 由 小羊

题目链接：HDU-6561

给不超过 $10^4$ 个阻值为 $1 \Omega$ 的电阻，通过串联和并联使得最后形成的电路有效阻值为 $r$。

这道题可以考虑有理逼近中的连分数。

$a_0 + \dfrac{1}{a_1 + \dfrac{1}{a_2 + \dfrac{1}{\ddots + \dfrac{1}{a_n}}}}$

我们通常将它记为 $[a_0, a_1, a_2, \cdots, a_n]$。

记 $\frac{p_k}{q_k}$ 为 $[a_0, a_1, \cdots, a_k]$，我们称 $\frac{p_k}{q_k}$ 为 $[a_0, a_1, a_2, \cdots, a_n]$ 的第 $k$ 个渐进分数。

可以证明，所有有理数都可以表示为这样的一个有限连分数。

考虑斐波那契的 $\phi = \frac{1 + \sqrt5}{2}$，我们可以令连分数序列为无限的 $[1, 1, 1, \cdots, 1, \cdots]$。而且我们可以发现，$\frac{p_k}{q_k}$ 正好等于 $\frac{F_{k+1}}{F_k}$。数论中还会研究，任何无理数也都可以用连分数来逼近。

可以看出来，将这样的一个有理数摆进来，首先将它的整数部分去掉，然后再求倒数，就变成了 $[a_1, a_2, \cdots, a_n]$，问题规模得以缩小。当我们迭代到没有小数部分的时候，这个有理数已经被精确表示了。类似于一个辗转相除法的例子，对不对？时间复杂度为 $O(\log q)$。

我们需要(cai)知(chu)道(lai)的是，渐进级数越精确，误差越小。如果我们用某个连分数来表示这道题的答案呢？

一定有 $a_0 = 0$。那么我们不妨设定一个数列 $\lbrace b_i \rbrace$，其中

$b_i = \begin{cases} \frac{1}{a_i + \frac{1}{b_{i+1}}}, & i = 2k+1 \\ a_i + b_{i+1}, & i=2k \end{cases}$

那么可以认为 $b_i$ 是由某一些电阻构成的复合电阻。当 $i$ 为奇数时，我们将 $a_i$ 个 $1 \Omega$ 的电阻与 $b_{i+1}$ 并联起来；当 $i$ 为偶数时，我们将 $a_i$ 个 $1 \Omega$ 的电阻与 $b_{i+1}$ 串联起来。注意当超过连分数长度 $n$ 时，$b_{i+1}$ 为 $0$ 或 $\infty$，取决于奇偶性。

首先题目给定的 $r$ 输入进来以后一定是一个有理数。那我们不妨先求出 $[ r - \epsilon, r + \epsilon ]$ 中分母最小的分数 $\frac{p_i}{q_i}$。

我们将 $\frac{p_i}{q_i}$ 的连分数表示出来。但是由于题目要求所用电阻数量不能超过 $10^4$，我们可以将超过的部分略去，留下一堆多余的电阻，这样比略去的逼近效果略好。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll EPS = 10000000;
const int MAXN = 10000;
int kase;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

void euclid(ll a, ll b, ll x, ll y, ll &p, ll &q)
{
    ll K = a / b; a -= K * b, x -= K * y;
    if (x > y) p = q = 1; else euclid(y, x, b, a, q, p);
    p += K * q;
}

void solve()
{
    static char buf[1000];
    static ll lfs[1000];
    scanf("%s", buf);
    ll fz = 0, fm = 1, fzm, fmm, fzM, fmM;

    for (int i = 2; buf[i]; i++)
    {
        fz = fz * 10 + buf[i] - '0';
        fm *= 10;
    }

    if (fm < EPS) fz *= EPS / fm, fm = EPS;
    fzm = fz - fm / EPS, fmm = gcd(fzm, fm), fzm /= fmm, fmm = fm / fmm;
    fzM = fz + fm / EPS, fmM = gcd(fzM, fm), fzM /= fmM, fmM = fm / fmM;
    euclid(fzm, fmm, fzM, fmM, fz, fm);
    if (fmM < fm) fz = fzM, fm = fmM;
    if (fmm < fm) fz = fzm, fm = fmm;
    int tot = 1, sum = 0, idx = 0, idg, id1, id2, idq = -1, op;

    while (fz && sum < MAXN)
    {
        swap(fz, fm);
        sum += (lfs[tot++] = min(fz / fm, MAXN - sum + 0ll));
        fz %= fm;
    }

    // printf("[ 0"); for (int i = 1; i < tot; i++) printf(", %lld", lfs[i]); printf(" ]\n");
    printf("Case %d:\n%d %d\n", ++kase, sum, sum-1);

    idg = sum-1;
    for (int j = tot-1; j > 0; j--)
    {
        op = j & 1;
        id1 = idx++;

        for (int i = 1; i < lfs[j]; i++)
        {
            id2 = idx++;
            printf("%d %d %d\n", op, id1, id2);
            id1 = ++idg;
        }

        if (~idq)
        {
            id2 = idq;
            printf("%d %d %d\n", op, id1, id2);
            ++idg;
        }

        idq = idg;
    }
}

int main()
{
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}

这道题总而言之感觉还是有点怪怪的，例如 $0.000001$ 一定是无解的，但是竟然也能 AC。就这样吧，应该是良心出题人没有出卡人数据。