竞赛讨论区 > 【题解】牛客IOI周赛27-普及组

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

头像
Aledrew_Killer
编辑于 2021-07-05 16:44:18 APP内打开
赞 3 | 收藏 0 | 回复1 | 浏览701

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

小H的小猫

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

时间复杂度:

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

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

枚举一下就好了。

如果 轴或 轴上没有柱子,则无解。

时间复杂度:

假设有最优解(如果有解的话)所连的柱子为 ,则有

由于 是相互独立的,所以 为在 轴上纵坐标最小的柱子,而 为在 轴上横坐标最小的柱子。

排个序就好了。

时间复杂度:

如果卡卡常没准能过

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

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

  • 所有柱子均在 轴和 轴上

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

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

时间复杂度:

  • 轴和 轴上均只有 根柱子

的做法扫一遍做就行了。

时间复杂度:

发现在 的部分分中,求最小值这步可以 扫一遍就行了,不用 排序,所以直接扫一遍就行了。强行凑部分分系列

时间复杂度:

#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的数列

对于前 分,根据题意依次求值即可。

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

由递推关系可以写到:

因为第二个式子不可能为 ,所以:

注意到:

,即 就等于

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

代码:

#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的糖果

瞎爆搜一下就行了。

注意特判 ,此时最小次数为 (使用 无中生有)。

时间复杂度:

剪枝一下,记忆化或 一下就好了。

时间复杂度:

  • 所有的 皆相同且

和上面的做法类似,只需要发现记忆化或 可以过单组 就行了。

读入 然后记忆化或 一下。

递推式:

时间复杂度:

容易发现

,输出

否则,发现可以贪心,从 倒着考虑,也即若原变换路径为 ,则有

可以设计出以下算法

每次 加上 变为 ,如果 就退出循环,最后输出 即可。

时间复杂度:

正难则反。

考虑当 时的算法

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

有一个初始值为 的变量 ,每次操作可以 除以 (如果能整除)(称为 仓陈度暗) 或 减去 (称为 有生中无),求使 变为 的的最少步数。

做法就显然了:

初始

加上 (因为后面只能用 有生中无,也即只能一直减 ),退出循环。

否则, 加上 除以 的余数(有生中无 的余数次)加 仓陈度暗),再将 设置为 除以 向下取整后的值,并继续循环。

时间复杂度:

#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个点,由于会重复消毒,所以可以用标记数据标记一下, 没宽松过才宽松,复杂度是

#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;    
}

1条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐