【题解】牛客IOI周赛27-普及组

D题出了一点锅，抱歉给大家带来的不便，现在已经rejudge了，可以在比赛的提交页面查看自己之前的提交。

小H的小猫

$n\le10$

瞎枚举全排列一下就行了。

时间复杂度： $\mathcal{O}(n!)$

$n\le1000$

发现答案一定是两根 在坐标轴上 的柱子间的连线。

可以用两点之间线段最短来证明。

枚举一下就好了。

如果 $x$ 轴或 $y$ 轴上没有柱子，则无解。

时间复杂度： $\mathcal{O}(n^2)$

$n\le10^5$

假设有最优解（如果有解的话）所连的柱子为 $A(0,a)$ 和 $B(b,0)$ ，则有 $|AB|=\sqrt{(0-b)^2+(a-0)^2}=\sqrt{a^2+b^2}$ 。

由于 $A$ 和 $B$ 是相互独立的，所以 $A$ 为在 $y$ 轴上纵坐标最小的柱子，而 $B$ 为在 $x$ 轴上横坐标最小的柱子。

排个序就好了。

时间复杂度： $\mathcal{O}(n\log n)$

~~如果卡卡常没准能过~~

为了防止卡常能过出题人用心良苦地加上了 空间限制，从此卡常再见。 $\rm$

~~但这样无法防止部分分 $x$ 轴和 $y$ 轴上均只有 $1$ 根柱子能过~~ 好像这样在这个部分分本来时间复杂度就是对的。

所有柱子均在 $x$ 轴和 $y$ 轴上

这块建议先跳过，最后看你才能明白。

就是没想到答案一定是两根 在坐标轴上 的柱子间的连线但其它都想到了（还有一部分详见无特殊限制时的解决方法）的部分分。

时间复杂度： $\mathcal{O}(n)$

$x$ 轴和 $y$ 轴上均只有 $1$ 根柱子

用 $n\le10^3$ 的做法扫一遍做就行了。

时间复杂度： $\mathcal{O}(n)$

$n\le10^6$

发现在 $n\le10^5$ 的部分分中，求最小值这步可以 $\mathcal{O}(n)$ 扫一遍就行了，不用 $\mathcal{O}(n\log n)$ 排序，所以直接扫一遍就行了。~~强行凑部分分系列~~

时间复杂度： $\mathcal{O}(n)$

$\rm Code:$

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int res=0;
    bool zf=0;
    char c;
    while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c=='-')zf=1;
    else res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0';
    if(zf)return -res;
    return res;
}
const double eps=1e-6;
signed main(){
    int n=read();
    double m1=3e9,m2=3e9;
    while(n--){
        double x,y;
        scanf("%lf%lf",&x,&y);
        if(fabs(x)<eps)m2=min(m2,y);
        if(fabs(y)<eps)m1=min(m1,x);
    }
    if(m1>2e9||m2>2e9){
        puts("Poor Little H!");
        return 0;
    }
    printf("%.10lf",sqrt(m1*m1+m2*m2));
    return 0;
}

小H的数列

对于前 $50$ 分，根据题意依次求值即可。

现在开始推到原来的公式：

由递推关系可以写到：

$(a_n+a_{n+1}-2\sqrt{a_n a_{n+1}}-1)(a_n+a_{n+1}+2\sqrt{a_n a_{n+1}}-1)=0$ ，

因为第二个式子不可能为 $0$ ，所以：

$(a_n+a_{n+1}-2\sqrt{a_n a_{n+1}}-1)=0$

$a_n+a_{n+1}-2\sqrt{a_n a_{n+1}}=1$

即 $\sqrt{a_{n+1}}-\sqrt{a_n}=1$ 。

注意到：

$\sqrt{a_{n+1}}=1+\sqrt{a_n}=2+\sqrt{a_{n-1}}=......=n+\sqrt{a_1}=n+1$ ，即 $a_n$ 就等于 $n^2$ 。

因此，只需要一个高精模板即可。

代码：

#include<bits/stdc++.h>
using namespace std;
char a1[1000001],b1[1000001];
int a[1000001],b[1000001],i,x,len,j,c[1000001];
int main(){
    cin>>a1;
    int lena=strlen(a1);
    for(int i=0;i<lena;i++) b1[i]=a1[i]; 
    int lenb=strlen(b1);
    for(i=1;i<=lena;i++) a[i]=a1[lena-i]-'0';
    for(i=1;i<=lenb;i++) b[i]=b1[lenb-i]-'0';
    for(i=1;i<=lenb;i++){
        for(j=1;j<=lena;j++){
            c[i+j-1]+=a[j]*b[i];
        }
    }
    for(i=1;i<lena+lenb;i++){
        if(c[i]>9){
            c[i+1]+=c[i]/10;
            c[i]%=10;
        }
    }
    len=lena+lenb;
    while(c[len]==0&&len>1) len--;
    for(i=len;i>=1;i--) cout<<c[i];
    return 0;
}

小H的糖果

$k,n\le10$ ：

瞎爆搜一下就行了。

注意特判 $k=1$ ，此时最小次数为 $n-1$ （使用 $n-1$ 次 无中生有）。

时间复杂度： $\mathcal{O}(\text{玄学})$

$k,n\le 100$ ：

剪枝一下，记忆化或 $\rm dp$ 一下就好了。

时间复杂度： $\mathcal{O}(Tn)$

所有的 $k$ 皆相同且 $n\le10^8$

和上面的做法类似，只需要发现记忆化或 $\rm dp$ 可以过单组 $10^8$ 就行了。

读入 $k$ 然后记忆化或 $\rm dp$ 一下。

递推式：

$f_i=\begin{cases}0&i=1\\\min(f_{\frac{i}{k}},f_{i-1})+1&k=1\text{ 且 }k|i\\f_{i-1}+1&\rm otherwise\end{cases}$

时间复杂度： $\mathcal{O}(n+T)$

$k\le2$

容易发现 $k\in\{1,2\}$ 。

若 $k=1$ ，输出 $n-1$ 。

否则，发现可以贪心，从 $n$ 倒着考虑，也即若原变换路径为 $1\rightarrow a_1\rightarrow a_2\rightarrow\cdots\rightarrow a_{n-1}\rightarrow n(a_n)$ ，则有 $a_i=\left\lfloor\dfrac{a_{i+1}}{2}\right\rfloor$ 。

可以设计出以下算法：

每次 $\rm ans$ 加上 $1+n\bmod 2$ ， $n$ 变为 $\left\lfloor\dfrac{n}{2}\right\rfloor$ ，如果 $n=1$ 就退出循环，最后输出 $\rm ans$ 即可。

时间复杂度： $\mathcal{O}(T\log n)$

$n,k\le10^{18}$

正难则反。

考虑当 $k\le2$ 时的算法。

发现也就是将题目转化为：

有一个初始值为 $n$ 的变量 $x$ ，每次操作可以除以 $k$ （如果能整除）（称为 仓陈度暗）或减去 $1$ （称为 有生中无），求使 $x$ 变为 $1$ 的的最少步数。

做法就显然了：

初始 ${\rm ans=1},x=n$ 。

若 $x<k$ 则 $\rm$ 加上 $x-1$ （因为后面只能用 有生中无，也即只能一直减 $1$ ），退出循环。

否则， $\rm ans$ 加上 $x$ 除以 $k$ 的余数（有生中无 $x\bmod k$ 的余数次）加 $1$ （仓陈度暗），再将 $x$ 设置为 $x$ 除以 $k$ 向下取整后的值，并继续循环。

时间复杂度： $\mathcal{O}(T\log n)$

$\rm code:$

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int res=0;
    bool zf=0;
    char c;
    while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c=='-')zf=1;
    else res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0';
    if(zf)return -res;
    return res;
}
signed main(){
    int T=read();
    while(T--){
        int k=read(),n=read(),ans=0;
        if(k==1){
            printf("%lld\n",n-1);
            continue;
        }
        while(n>=k){
            ans+=n%k+1;
            n/=k;
        }
        ans+=n-1;
        printf("%lld\n",ans);
    }
    return 0;
}

旅游

第四题是floyd的考察，做法是每次消毒一个点以这个点为中间转移点宽松一次，虽然q范围大，但是一共只有n个点，由于会重复消毒，所以可以用标记数据标记一下，没宽松过才宽松，复杂度是 $O(n^3+q)$

#include<bits/stdc++.h>
using namespace std;
inline int read() 
{
    int x = 0 , f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; } 
    while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; } 
    return x * f ;
}
int f[400][400];
int v[1000];
int n,m,q,s;
void floyd(int k)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(f[i][j]>f[i][k]+f[k][j])
            {
                    f[i][j]=f[i][k]+f[k][j];
            }

        }
    }
}
int main()
{
    //freopen("10.in","r",stdin);
    //freopen("10.out","w",stdout);
    cin>>n>>m>>s>>q;
    v[s]=1;
    floyd(s);
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=n;i++)
    {
        f[i][i]=0;
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        f[x][y]=min(z,f[x][y]);
    }
        floyd(s);
    while(q--)
    {
        int xx,yy;
//        cin>>x>>y;
        scanf("%d%d",&xx,&yy);
        if(xx==1)
        {
            if(!v[yy])
            {
                floyd(yy);
            }v[yy]=1;

        }else
        {
            if(f[s][yy]==0x3f3f3f3f||v[yy]==0)
            {
                puts("-1");
                continue;
            }else
            {
                printf("%d\n",f[s][yy]);
                s=yy;
            }

        }    
    }
    return 0;    
}