题解 P2838 【瓶子国的故事】

SSerxhs · 2019-04-18 21:47:08 · 题解

思维题，以下数字均指的是瓶子

task1：略，只要会IO就行

task2：利用task3可以得到min和max，后面相减即可

task3：以2为大小制造3，把1倒入3，然后1和2倒入一个无限大的瓶子4中，则4为max而3为min

证明：1多于2时，3的大小只有2，只装了2的水量；1少于2时，3只能倒进1那么多水。1、2剩下的水都进了4，由于a+b=min(a,b)+max(a,b)，所以4是max

task4：辗转相减1000次即可，这里甚至不需要task2的绝对值，直接暴力轮换减就好了，从这个task开始需要写代码输出代码

task5：前15个瓶子直接输出0，难点在于如何不使用判断处理去掉当前位的操作。考虑封装一个倍增函数（即可以任意获取2^k)（后面很有用），设当前处理x号瓶处理到二进制第k位，设y=2^k，则制造一个大小为y的瓶子z把x瓶水倒入，然后按照x剩余水量构造一个瓶子a并把它倍增到足够大，把z倒入a中再把z倒回x中即消除了第k位。证明：当第k位是0时，倍增出来的也是0等于没干；当第k为是1时，相当于瓶子z里的水被消除，大小正好为2^k

task6：利用task5转化为二进制然后暴力相乘，相乘方法：设是二进制下第i位与第j位相乘，则取min之后倍增i+j次即可，然后累加到答案瓶

task7：直接用task5+task2即可

task8：这里建议封装一个带余除法，下一个task可以用。除法很好实现（类似task5），关键也在于取模。考虑拓展task5的思路，task5相当于实现了if (x>=p) x-=p，则我们只要多做几次这个过程就可以实现取模。

task9：直接用task6和task8即可

task10：考虑a=2时b<=19，而a=1时b取几都无所谓，不妨设b\leq19。则ans=max(min(a^i,inf*[max(b-i,0)>0)])，其中i在max中枚举。a^i可以调用task6暴力算，inf*[max(b-i,0)>0)]可以取出max之后不断倍增。

献上超长代码

#include <stdio.h>
#include <string.h>
const int N=1002,inf=1e9;
int n,ps,i,j,x,y,z,k,ans,kk;
int a[N],b[N];
inline void I()
{
    printf("I\n");++ps;
}
inline void O(int x)
{
    printf("O %d\n",x);
}
inline void C(int x)
{
    printf("C %d\n",x);++ps;
}
inline void F(int x)
{
    printf("F %d\n",x);
}
inline void E(int x)
{
    printf("E %d\n",x);
}
inline void M(int x)
{
    printf("M %d\n",x);++ps;
}
inline void T(int x,int y)
{
    printf("T %d %d\n",x,y);
}
inline void minmax(int a,int b,int &c,int &d)
{
    M(b);
    T(a,ps);c=ps;
    C(inf);
    T(a,ps);T(b,ps);d=ps;
}
inline void min(int a,int b,int &c)
{
    M(b);
    T(a,ps);c=ps;
}
inline void fb(int x)
{
    M(x);F(ps);T(ps,x);
}
inline void toer(int x,int *a)
{
    M(x);F(ps);
    C(n);
    while (n)
    {
        M(ps-1);x=ps;
        C(n-1);
        T(ps-3,ps-2);
        T(ps-2,ps);
        M(ps-2);
        F(ps);a[20-j]=ps;
        if (n==1) break;
        T(ps-1,ps-3);
        C(1);
        F(ps);
        T(ps,ps-4);C(inf);T(ps-1,ps);z=ps;
        for (i=1;i<=j;i++) fb(z);
        M(z);
        F(x);
        T(x,ps);
        M(x);
        F(ps);
        n>>=1;--j;
        C(n);
    }
}
inline void times(int x,int y,int &z,int l1,int l2,int spe,int nosplit)
{
    int i,k;
    C(inf);
    z=ps;n=l1;j=l2;
    toer(x,a);
    if (!nosplit)
    {
        n=l1;j=l2;toer(y,b);
    }
    for (i=20-l2;i<=20;i++) for (j=20-l2;j<=20;j++) if (i+j>=21)
    {
        if ((spe)&&(40-i-j>=18)) continue;
        M(a[i]);F(ps);
        min(ps,b[j],x);
        C(inf);T(x,ps);x=ps;
        for (k=1;k<=40-i-j;k++) fb(x);
        T(x,z);
    }
}
inline void yfb(int x,int &y)
{
    M(x);F(ps);C(inf);T(x,ps);T(ps-1,ps);y=ps;
}
inline void divide(int w,int x,int &y,int lim,int anj)
{
    int cz;
    int kkk,sc;
    C(inf);y=ps;
    for (i=1;i<=lim;i++)
    {
        C(x);a[i]=ps;
        T(w,ps);if (anj==0) continue;
        M(ps);F(ps);C(x);T(ps-1,ps);C(1);F(ps);T(ps,ps-1);M(ps);F(ps);
        cz=ps;
        for (j=1;j<=7;j++) yfb(cz,cz);
        C(anj);F(ps);
        min(ps,cz,kkk);
        M(kkk);
        T(kkk,y);
    }
    if (x==10) return;
    for (i=1;i<=lim;i++)
    {
        C(x);F(ps);M(a[i]);T(ps-1,ps);M(a[i]);F(ps);
        min(ps-2,ps,kkk);
        for (j=1;j<=8;j++) yfb(kkk,kkk);
        M(kkk);
        T(a[i],ps);T(ps,w);T(a[i],ps);T(ps,w);T(a[i],ps);T(ps,w);T(a[i],ps);T(ps,w);
    }
}
int main()
{
    scanf("%d",&n);
    if (n==10)
    {
        I();I();
        C(1);F(3);y=3;
        C(1);ans=ps;M(1);F(ps);n=524288;j=19;toer(ps,b);
        for (k=1;k<=19;k++)
        {
            times(y,ps,y,524288,19,0,1);
            M(y);x=ps;F(x);
            C(1);T(2,ps);
            C(inf);T(ps-1,ps);z=ps;
            for (i=1;i<=20;i++) fb(z);
            min(x,z,x);
            minmax(x,ans,x,ans);
        }
        O(ans);
        return 0;
    }
    if (n==1)
    {
        I();
        I();
        printf("C 100000000\n");
        printf("T 1 3\n");
        printf("T 2 3\n");
        printf("O 3\n");
        return 0;
    }
    if (n==2)
    {
        I();
        I();
        printf("M 2\n");
        printf("T 1 3\n");
        printf("C 99999999\n");
        printf("T 1 4\n");
        printf("T 2 4\n");
        printf("M 3\n");
        printf("T 4 5\n");
        printf("O 4\n");
        return 0;
    }
    if (n==3)
    {
        I();
        I();
        printf("M 2\n");
        printf("T 1 3\n");
        printf("C 99999999\n");
        printf("T 1 4\n");
        printf("T 2 4\n");
        printf("O 4\n");
        return 0;
    }
    if (n==4)
    {
        n=2;
        I();I();
        for (i=1;i<N;i++)
        {
            printf("M %d\n",n++);
            printf("T %d %d\n",n-2,n);
            printf("C 99999999\n");++n;
            printf("T %d %d\nT %d %d\n",n-3,n,n-2,n);
            printf("M %d\n",n-1);++n;
            printf("T %d %d\n",n-1,n);
            printf("M %d\n",n-1);++n;
            printf("F %d\n",n);
        }
        printf("O %d\n",n);
        return 0;
    }
    if (n==5)
    {
        n=65536;j=16;
        I();
        C(inf);
        for (i=1;i<=15;i++) O(2);
        toer(1,a);
        for (i=4;i<=20;i++) O(a[i]);
        return 0;
    }
    if (n==6)
    {
        I();
        I();
        times(1,2,x,512,9,0,0);
        O(x);
        return 0;
    }
    if (n==7)
    {
        n=65536;j=16;
        I();
        I();
        C(inf);
        toer(1,a);
        n=65536;j=16;
        toer(2,b);
        for (i=4;i<=20;i++)
        {
            minmax(a[i],b[i],x,y);
            M(x);M(y);
            F(ps);T(ps,ps-1);C(inf);T(ps-1,ps);
            z=ps;
            for (j=1;j<=20-i;j++) fb(z);
            M(z);F(ps);T(ps,3);
        }
        O(3);
        return 0;
    }
    if (n==8)
    {
        I();
        divide(1,1000,x,10,100);
        divide(1,100,y,10,10);
        T(y,x);
        divide(1,10,y,10,1);
        T(y,x);
        O(x);
        return 0;
    }
    if (n==9)
    {
        I();I();
        times(1,2,x,65536,16,1,0);
        divide(x,262144,y,100,0);
        O(x);
        return 0;
    }
}