题解 P1431 【找出伪币】

· · 题解

这道题目是一道数论题。需要分类讨论。

当 p\neq0 时，显然答案是 \lceil\log_3n\rceil，这是比较容易的，每一次想办法把它平均分成3份，若无法平均分成3份，就将其分为 \lceil n/3\rceil,\lceil n/3\rceil,n-2\lceil n/3\rceil，最坏情况下称量次数为\lceil\log_3n\rceil。

但是别想当然，当 p=0 时，答案可不是 \lceil\log_3n\rceil+1 （我曾经这样想过，结果就听取WA声一片了），而是 \lceil\log_3(2n+3)\rceil，具体怎么证明如下（我参考了一位大佬写的博客）：
假如称一次就要找到有问题的那枚硬币，显然不可能，因为硬币要大等于3枚才可以称量。
假如称两次，只能3枚（左1，右1，余1），4枚硬币就不行了（左1，右1，余2，若左右两端平衡，则用左右两端的硬币和剩下的两枚硬币比较，先比较出轻重，接下来还要一次比较哪枚硬币出问题，要3次）。
假如称3次，左右两端最多可以各放4枚而不是3枚，因为只要有3枚标准硬币，就可以2次找到4枚硬币的问题所在，方法如下：左边放3枚标准硬币，右边放3枚可能存在问题的硬币，剩下一枚可能存在问题的硬币，若天平平衡，则问题显然出在那一枚硬币中，和标准硬币比较轻重即可，否则，可先知道轻重，问题转为知道轻重。所以3次最多可称12枚。
类似的，12枚标准硬币可以3次找到13枚硬币的问题，方法如上，所以称4次可称39枚硬币。以此类推，称 x 次可找到 \sum_{i=1}^{x-1}3^i=(3^x-1)/2-1=(3^x-3)/2 枚硬币，解 3^x-3=2n，可得 x=\log_3(2n+3)，由于要称整数次，所以要称 \lceil\log_3(2n+3)\rceil 次。

然而，知道方法了，也不一定能 A（Python 党请无视），因为它还卡高精，暴力地运算的单次时间复杂度为 O(k^2)，看上去可以卡过 (10000^2=10^8)，但是这个毒瘤的出题人还设置了多组数据，总时间复杂度为 O(Tk^2)，就是这个可恶的 T，导致暴力地运算只能得 40~60 分（虽然 T\le40），只能另外想办法。我不会其他办法，就用压位高精，每一个压 9 位，这样优化了常数，时间复杂度为 O(Tk^2/81)，别小看这个 81，它可将速度提升了 81 倍，使得这样做可以通过本题，当然，未吸氧时最慢的点跑了0.9s。上代码（有点压行）。

#include<bits/stdc++.h>
#define int long long//压9位，不开LL见祖宗
using namespace std;
const int base = 1000000000LL; int T;//每一位都小于10^9
const int pow18 = 387420489LL;//进一步优化常数，预处理出最接近10^9的3的n次幂的数，即3^18
FILE *fin, *fout;
struct bigint {
    int a[1122];//ceil(10000.0/9)=1112，所以数组稍微开大一点即可，a[0]储存位数
    bigint(){memset(a, 0, sizeof(a));}
    inline int& operator [](int n) {//重载[]运算符，之后方便写
        return a[n];
    }
    inline friend bool operator <(bigint a, int x) {//比较bigint和int的大小
        if (a[0] > 2) return 0; int y = 0;//由于这里出现的最大整数不超过10^18，所以可以这样做节省时间
        for (int i = a[0]; i; --i) y = y * base + a[i];//最多两位
        return y < x;
    }
    inline friend bigint operator +(bigint a, int x) {//高精加低精
        int i; a[i = 1] += x;//相当于i = 1, a[i] += x;
        while (a[i] >= base) ++a[i + 1], a[i] -= base, ++i;//处理进位
        if (i > a[0]) a[0] = i; return a;
    }
    inline friend bigint operator *(bigint a, int x) {//高精乘低精
        for (int i = 1; i <= a[0]; ++i) a[i] *= x;//先暂时不管进位，乘完以后再处理进位
        for (int i = 1; i <= a[0]; ++i) a[i + 1] += a[i] / base, a[i] %= base;//处理进位
        while (a[a[0] + 1]) ++a[0], a[a[0] + 1] += a[a[0]] / base, a[a[0]] %= base;//可能出现新的一位
        while (!a[a[0]]) --a[0]; return a;
    }
    inline friend bigint operator /(bigint a, int x) {//高精除低精
        for (int i = a[0]; i; --i) {
            if (i > 1) a[i - 1] += a[i] % x * base;
            a[i] /= x;//这一位除以x，下一位加上余数的10^9倍
        }while (!a[a[0]]) --a[0]; return a;
    }
    inline friend int operator %(bigint a, int x) {//高精对低精取余，返回值int即可
        int res = 0;
        for (int i = a[0]; i; --i) res = (res * base + a[i]) % x;
        return res;
    }
};
inline int read(int &x) {//快读和快写
    char c = 0; int f = x = 0;
    while (c < 48 || c > 57) {
        if (!~c) return 0;
        if (c == '-') f = 1; c = fgetc(fin);
    }
    while (c > 47 && c < 58) x = (x << 3) + (x << 1) + (c & 15), c = fgetc(fin);
    if (f) x = -x; return 1;
}
inline int read(string &s) {
    s = "";
    char c = 0;
    while (c == 32 || c == 10 || c == 13 || c == 0) c = fgetc(fin);
    if (c == -1) return 0;
    while (!(c == 32 || c == 10 || c == 13 || c == 0 || c == -1)) s += c, c = fgetc(fin);
    return 1;
}
inline int read(bigint &x) {//压位高精最困难的地方就是读入，一定要小心，我有一次WA过
    string s; read(s);
    int len = s.length();if (s == "") return 0; x[0] = len / 9;
    if (len % 9) {//如果有多出来的一位，还要单独处理
        for (int i = 0; i < len % 9; ++i) x[x[0] + 1] = x[x[0] + 1] * 10 + s[i] - 48;
        s.erase(0, len % 9);//删掉前len%9位
    }
    for (int i = 0; i < x[0]; ++i)
        for (int j = 0; j < 9; ++j)
            x[x[0] - i] = x[x[0] - i] * 10 + s[i * 9 + j] - 48;//注意这里的下标是x[x[0]-i]，而不是x[i]
    if (len % 9) ++x[0]; return 1;//多出来的一位也要加上
}
template<class T, class... Args> inline int read(T &x, Args&... args) {
    return read(x) + read(args...);
}
inline void write(int x) {
    if (x < 0) return putchar(45), (void)write(-x);
    if (x > 9) write(x / 10);
    fputc((x % 10) | 48, fout);
}
inline void write(char c) {
    fputc(c, fout);
}
inline int solve() {
    int k, p, flag = 0, res = 0;
    bigint n; read(k, p, n);
    if (!p) n = n * 2 + 3;//若p=0，则n=2n+3
    while (!(n < pow18)) res += 18, flag |= n % pow18, n = n / pow18;//先18个18个加，这里没有定义过>=，只能用!(n<pow18)
    while (!(n < 3)) ++res, flag |= n % 3, n = n / 3;//剩余部分一个一个加
    if (!(n < 2)) ++res; else if (flag) ++res; return res;//三行压成一行，其实也很容易理解，若最终结果大于1或有出现余数的，答案要加一
}
signed main() {
    #ifdef ONLINE_JUDGE//在评测机上使用标准输入输出，在本机上使用文件输入输出，方便读入
    fin = stdin;
    fout = stdout;
    #else
    fin = fopen("P1431.in", "rb");
    fout = fopen("P1431.out", "wb");
    #endif
    read(T); while (T--) write(solve()), write('\n');//这里再次压行，对于每组数据都要处理
    return 0;
}