Luogu5246 消失的源代码

题面

简化题意

这是一个提交答案题。

给定十个问题的输入数据，还有其可执行文件。可执行文件不能运行较大的数据，你可以运行测试可执行文件。你需要猜出每个问题的题面，并得到其输出数据。

如果输入数据较大或不合法，可执行文件将并输出 $\texttt{invalid input.}$ 且不会执行你的数据。

题解

Linux 运行它给的可执行文件要先 chmod 一下不然没权限运行不了。

case 1

输入是个字符串，经过测试发现这个东西不能跑长度 $>10$ 的串。

输出也是字符串，长度与输入相等，不难发现其字符是一一对应的。

于是测试一下每个字符会变成什么就行。

namespace Type1{
    char turn[27]="yfrbkgimujvphatdsnelozcxwq";
    string a;
    inline void sol(){
        for(register int T=read();T>0;--T){
            cin>>a;
            int n=a.size();
            for(register int i=0;i<n;++i)
                cout<<turn[a[i]-'a'];
            cout<<"\n";
        }
    }
}

case 2

输入一个数字。首先发现依次输入 $1,2,3,\ldots$ ，它是递增的，但是大约在 $2\times 10^5$ 这个位置往后一点，它变小了。我们推测这是对一个数取模了。

把得到的 $2030,8082,18166,32282,50430,72610$ 作一次差分得到 $6052,10084,14116,18148,22180$ 。再作一次差分就变成了 $4032,4032,4032,4032,\ldots$ 。

所以序列的差分是一个等差数列，那么其差分的通项公式为 $6052+4032(n-1)$ 。因此原序列的通项公式为：

a_n = 2030 + 2020(n-1) + 2016n(n-1)

对什么数取模？我们发现原本的 $a_{11} = 243990$ ，而实际的 $a_{11} = 10657$ ，因此模数为 $233333$ 。

namespace Type2{
    int mod=233333;
    inline void sol(){
        for(register int T=read();T>0;--T){
            long long n=read();
            write((2030+2020LL*(n-1)%mod+2016LL*n%mod*(n-1)%mod)%mod),putchar('\n');
        }
    }
}

case 3

也是输入一个数，我们发现 $[1,3]$ 的数输出 $0$ ； $[4,12]$ 之内输出 $1$ ； $[13,28]$ 输出 $2$ ； $[29,50]$ 输出 $3$ ； $[51,78]$ 输出 $4$ ……

看了很久没找到规律，把数列丢到 OEIS 上得到：

a_n = \left\lfloor \sqrt{\frac{n}{\pi}} \right\rfloor

namespace Type3{
    const double Pi=acos(-1);
    inline void sol(){
        for(register int T=read();T>0;--T){
            int n=read();
            write(floor(sqrt(1.0*n/Pi))),putchar('\n');
        }
    }
}

case 4

输入数据非常图论，我们丢到 graph editor 上，首先可以确定图是可以不连通的，且如果它是有向图，那么也不一定要是 DAG。

图论的话可以先试试一棵树，不难发现都输出 $n^2$ ，然后尝试加一条边，发现仍然是 $n^2$ ，进一步测试，感觉在树上任意加边都输出 $n^2$ ，而且通过调换边的顺序和方向答案不变，猜想输入图是无向图。

结合第一个数据，考虑不连通图，就不难得到答案为每个连通块大小的平方和了。

namespace Type4{
    bool vis[100005];
    int n,m,cnt,sz[100005],ans;
    inline void dfs(int u){
        vis[u]=1;
        ++sz[cnt];
        for(register int i=e.hd[u];i;i=e.nx[i]){
            int v=e.to[i];
            if(!vis[v]) dfs(v);
        }
    }
    inline void sol(){
        for(register int T=read();T>0;--T){
            n=read(),m=read(),ans=cnt=0;
            e.clear(),memset(vis,0,sizeof(vis));
            for(register int i=1;i<=m;++i){
                int u=read(),v=read();
                e.add(u,v),e.add(v,u);
            }
            for(register int i=1;i<=n;++i) if(!vis[i]){
                sz[++cnt]=0;
                dfs(i);
                ans+=sz[cnt]*sz[cnt];
            }
            write(ans),putchar('\n');
        }
    }
}

case 5

本来以为是一棵有边权的树，加了很多增补边，然后求一些奇怪的东西比如生成树之类的……

其实后面那些“没有边权的边”是“询问两个点”……

明确了这一点就很简单了，测试的时候考虑只放一组询问，然后看输出答案是什么，再试试多组询问的情况。就可以发现其实是查寻树上两点距离，输出所有询问答案的异或和。

namespace Type5{
    int fa[100005][22],dis[100005][22],dep[100005];
    int n,Q,ans;
    inline void dfs(int u,int f){
        fa[u][0]=f,dep[u]=dep[f]+1;
        for(register int i=1;i<=20;++i){
            fa[u][i]=fa[fa[u][i-1]][i-1],
            dis[u][i]=dis[u][i-1]+dis[fa[u][i-1]][i-1];
        }
        for(register int i=e.hd[u];i;i=e.nx[i]){
            int v=e.to[i];
            if(v==f) continue;
            dis[v][0]=e.ln[i];
            dfs(v,u);
        }
    }
    inline int dist(int x,int y){
        if(x==y) return 0;
        if(dep[x]<dep[y]) swap(x,y);
        int res=0;
        for(register int i=20;i>=0;--i)
            if(dep[fa[x][i]]>=dep[y]){
                res+=dis[x][i],
                x=fa[x][i];
            }
        if(x==y) return res;
        for(register int i=20;i>=0;--i)
            if(fa[x][i]!=fa[y][i]){
                res+=dis[x][i]+dis[y][i];
                x=fa[x][i],y=fa[y][i];
            }
        return res+dis[x][0]+dis[y][0];
    }
    inline void sol(){
        for(register int T=read();T>0;--T){
            n=read(),Q=read(),ans=0;
            e.clear();
            for(register int i=1;i<n;++i){
                int u=read(),v=read(),w=read();
                e.add(u,v,w),e.add(v,u,w);
            }
            dfs(1,0);
            while(Q--){
                int x=read(),y=read();
                ans^=dist(x,y);
            }
            write(ans),putchar('\n');
        }
    }
}

case 6

和上一个测试点非常像。用类似的方法不难得到其实就是把查寻两点距离改成了查寻两点路径边权最小值。

不过应该注意的是，询问两个相同的点时答案是多少。直接随便丢一个树，然后只查一个询问，查寻一个点到它自己，可以得到若两点相同，则答案为 $1987654321$ 。

namespace Type6{
    int fa[100005][22],dis[100005][22],dep[100005];
    int n,Q,ans;
    const int inf=1000000000000000LL;
    inline void dfs(int u,int f){
        fa[u][0]=f,dep[u]=dep[f]+1;
        for(register int i=1;i<=20;++i){
            fa[u][i]=fa[fa[u][i-1]][i-1],
            dis[u][i]=min(dis[u][i-1],dis[fa[u][i-1]][i-1]);
        }
        for(register int i=e.hd[u];i;i=e.nx[i]){
            int v=e.to[i];
            if(v==f) continue;
            dis[v][0]=e.ln[i];
            dfs(v,u);
        }
    }
    inline int dist(int x,int y){
        if(x==y) return 1987654321;
        if(dep[x]<dep[y]) swap(x,y);
        int res=inf;
        for(register int i=20;i>=0;--i)
            if(dep[fa[x][i]]>=dep[y]){
                res=min(res,dis[x][i]),
                x=fa[x][i];
            }
        if(x==y) return res;
        for(register int i=20;i>=0;--i)
            if(fa[x][i]!=fa[y][i]){
                res=min(res,min(dis[x][i],dis[y][i])),
                x=fa[x][i],y=fa[y][i];
            }
        return min(res,min(dis[x][0],dis[y][0]));
    }
    inline void sol(){
        for(register int T=read();T>0;--T){
            n=read(),Q=read(),ans=0;
            e.clear(),memset(dis,0x3f,sizeof(dis));
            for(register int i=1;i<n;++i){
                int u=read(),v=read(),w=read();
                e.add(u,v,w),e.add(v,u,w);
            }
            dfs(1,0);
            while(Q--){
                int x=read(),y=read();
                ans^=dist(x,y);
            }
            write(ans),putchar('\n');
        }
    }
}

case 7

第二难找到规律的点。

交换任意两个数，答案不变，因此数对是无序的。

找规律发现对于同一个 $x$ ， $(3,x)-(2,x)$ 的差和余数有关。推测它是一个数论函数。

但是 $(2,2)=5$ ，因此它不应该是任何单元数论函数相加或相乘？

二元？

最后得到答案为：

\sum_{i=1}^a \sum_{j=1}^b \gcd(i,j)

枚举 $\gcd$ ，考虑莫反：

\sum_{d=1}^{\min(a,b)} d \sum_{x=1}^{\left\lfloor\frac{\min(a,b)}{d}\right\rfloor} \mu(x) \left\lfloor\frac{a}{dx}\right\rfloor \left\lfloor\frac{b}{dx}\right\rfloor

换元：

\sum_{t=1}^{\min(a,b)} \left\lfloor\frac{a}{t}\right\rfloor \left\lfloor\frac{b}{t}\right\rfloor \sum_{x\mid t} \frac{t}{x} \mu(x)

后面是 $\mu\ast\mathrm{id}=\varphi$ ：

\sum_{t=1}^{\min(a,b)} \varphi(t) \left\lfloor\frac{a}{t}\right\rfloor \left\lfloor\frac{b}{t}\right\rfloor

预处理欧拉函数的前缀和，整除分块可以做到 $\mathcal O(\sqrt{n})$ 。当然对于本题而言， $\mathcal O(n)$ 跑一遍也可以。

namespace Type7{
    int pr[1000006],cntp,phi[1000006];
    bool isp[1000006];
    inline void getpr(int n){
        memset(isp,1,sizeof(isp));isp[1]=0;
        phi[1]=1;
        for(register int i=2;i<=n;++i){
            if(isp[i]){
                pr[++cntp]=i,
                phi[i]=i-1;
            }
            for(register int j=1;j<=cntp && i*pr[j]<=n;++j){
                isp[i*pr[j]]=0;
                if(i%pr[j]==0){
                    phi[i*pr[j]]=phi[i]*pr[j];
                    break;
                }
                phi[i*pr[j]]=phi[i]*phi[pr[j]];
            }
        }
        for(register int i=1;i<=n;++i)
            phi[i]+=phi[i-1];
    }
    inline void sol(){
        getpr(1000000);
        for(register int T=read();T>0;--T){
            int a=read(),b=read(),up=min(a,b),ans=0;
            for(register int l=1,r;l<=up;l=r+1){
                r=min(a/(a/l),b/(b/l));
                ans+=(a/l)*(b/l)*(phi[r]-phi[l-1]);
            }
            write(ans),putchar('\n');
        }
    }
}

case 8

很佩服能看出规律的人。

找了很久没找到规律，开题解，题解说是求本质不同子串个数……

然后就变成后缀数组板子了……

namespace Type8{
    struct SA{
        int sm[1000006],rk[1000006],sa[1000006],tp[1000006],ht[1000006],m,n;
        SA(){m=300;memset(sa,0,sizeof(sa));}

        inline void sort(){
            memset(sm,0,sizeof(sm));
            for(register int i=1;i<=n;++i)
                ++sm[rk[i]];
            for(register int i=1;i<=m;++i)
                sm[i]+=sm[i-1];
            for(register int i=n;i>=1;--i){
                sa[sm[rk[tp[i]]]]=tp[i],
                --sm[rk[tp[i]]];
            }
        }
        inline void build(int a[]){
            for(register int i=1;i<=n;++i){
                rk[i]=a[i],
                tp[i]=i;
            }
            sort();
            int len=1;
            while(1){
                int cnt=0;
                for(register int i=1;i<=len;++i)
                    tp[++cnt]=n-len+i;
                for(register int i=1;i<=n;++i)
                    if(sa[i]>len)
                        tp[++cnt]=sa[i]-len;
                sort(),
                memcpy(tp,rk,sizeof(rk));
                rk[sa[1]]=cnt=1;
                for(register int i=2;i<=n;++i){
                    if(tp[sa[i]]==tp[sa[i-1]] && tp[sa[i]+len]==tp[sa[i-1]+len])
                        rk[sa[i]]=cnt;
                    else
                        rk[sa[i]]=++cnt;
                }
                m=cnt,len<<=1;
                if(cnt>=n) break;
            }
            for(register int i=1,j=0;i<=n;++i){
                if(j) --j;
                int k=sa[rk[i]-1];
                while(a[i+j]==a[j+k])
                    ++j;
                ht[rk[i]]=j;
            }
        }
    }sa;
    int n,a[1000006];
    inline void sol(){
        for(register int T=read();T>0;--T){
            n=sa.n=read();
            for(register int i=1;i<=n;++i)
                a[i]=read();
            sa.build(a);
            int ans=n*(n+1)/2;
            for(register int i=1;i<=n;++i)
                ans-=sa.ht[i];
            write(ans),putchar('\n');
        }
    }
}

case 9

输入了 $n$ 个数对？考虑 $n=2$ 的情况，发现它输出的就是两点距离。

这个时候一般有几种情况：凸包、平面最近点对、平面最远点对、某点到其它所有点的距离和。

然而这些情况都可以用一个正方形判断出来，输入一个 $(1,1),(1,2),(2,1),(2,2)$ 的正方形，它输出 $1$ 。进一步地测试，不难得到其实就是在算平面最近点对。

然而我平面最近点对一直都是 K-DTree 水过去的（不会分治.jpg），但 $10^6$ 显然跑不动。

平面最近点对加强版的题解中，最高赞题解是这么写的：

我们充分发扬人类智慧：

将所有点全部绕原点旋转同一个角度，然后按横坐标排序。

根据数学直觉，在随机旋转后，答案中的两个点在数组中肯定不会离得太远。

所以我们只取每个点向后的 $5$ 个点来计算。

（——3A17K）

可以通过。

namespace Type9{
    struct dot{
        double x,y;
        bool operator < (const dot &b) const{
            dot a=*this;
            return a.x<b.x;
        }
    }a[1000006];
    int n;
    double res;
    const double Pi=acos(-1);
    inline double dist(dot a,dot b){
        return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
    inline void calc(double ang){
        ang=ang/180.0*Pi;
        for(register int i=1;i<=n;++i){
            double x=a[i].x,y=a[i].y;
            a[i].x=x*cos(ang)-y*sin(ang),
            a[i].y=x*sin(ang)+y*cos(ang);
        }
        sort(a+1,a+1+n);
        for(register int i=1;i<=n;++i)
            for(register int j=1;j<=5 && i+j<=n;++j)
                res=min(res,dist(a[i],a[i+j]));
    }
    inline void sol(){
        srand(time(0));
        for(register int T=read();T>0;--T){
            n=read(),res=1e15;
            for(register int i=1;i<=n;++i)
                a[i].x=read(),a[i].y=read();
            calc(rand()%360);
            printf("%.3lf\n",res);
        }
    }
}

case 10

无论怎么输入都输出 $\texttt{invalid input!}$ 是为什么呢？

尝试的字符串都不合法吗？

不合法？

建议回到原题看一下，不合法的时候输出 $\texttt{invalid input.}$ （末尾是个句号），而这里输出的末尾是感叹号。

因此这个点就是随便怎么输入，反正就输出 $\texttt{invalid input!}$ 即可。

namespace Type10{
    inline void sol(){
        for(register int T=read();T>0;--T)
            puts("invalid input!");
    }
}

后记

上面的代码凑起来就是这题的主要代码了。

因为这个题是提交答案题，所以不需要交代码，只要运行一下跑出每个点就行了。

（而且你们真的会想去看一个 10k 的代码吗……）