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

小H的小猫

https://ac.nowcoder.com/acm/contest/11234/A

A.小H的小猫

题目链接

题意

以 x 轴和 y 轴为墙，原点为墙角，小猫在墙角，给出若干个点，求能否能用篱笆绕着点将小猫围在墙角，求篱笆的最短总长

思路

1.在纸上简单画图可以证明，必须要有一个点在 x 轴，一个点在 y 轴上才可以围住。
2.而离原点最近的两个点可以围成最短的
3.套一下两点距离公式

坑点

1.画图证明，不够严谨
2.精度
3.卡了cin和cout的时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
struct name
{
    double x;
    double y;
    double len;
}num[1000005];
double func (double a,double b,double c,double d)//求两点距离
{
    double dis=sqrt((c-a)*(c-a)+(d-b)*(d-b));
    return dis;
}
bool cmp(name a,name b)//自定义结构体排序
{
    return a.len<b.len;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lf%lf",&num[i].x,&num[i].y);
        num[i].len=func(num[i].x,num[i].y,0,0);
    }
    sort(num,num+n,cmp);
    int res1=-1,res2=-1;
    for(int i=0;i<n;i++)
    {
        if(num[i].x==0&&res1==-1)
        {
            res1=i;
        }
        if(num[i].y==0&&res2==-1)
        {
            res2=i;
        }
        if(res1!=-1&&res2!=-1)
        {
            break;
        }
    }
    double ans=0;
    if(res1!=-1&&res2!=-1)
    {
        ans+=func(num[res1].x,num[res1].y,num[res2].x,num[res2].y);
        printf("%.10lf\n",ans);
    }else{
        printf("Poor Little H!",ans);
    }
    return 0;
}

总结

简单题，需快速写出。

小H的数列

题目链接

题意

给出一个一元二次方程，求解。

思路

1.根据样例解释，可以简单的推一下结论
2.可知a1=1,s2=4,a3=9,an为n的平方
3.数据这么大，肯定是高精度啦

坑点

1.套个高精度模板
2.暴力过一半

代码

pow骗分,用多了有精度问题，慎有用

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    long long int n;
    cin>>n;
    cout<<pow(n,2);
    return 0;
}

高精度满分裸模板

#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &A, vector<int> &B) {
    vector<int> C(A.size() + B.size(), 0); // 初始化为 0，且999*99最多 5 位

    for (int i = 0; i < A.size(); i++)
        for (int j = 0; j < B.size(); j++)
            C[i + j] += A[i] * B[j];

    int t = 0;
    for (int i = 0; i < C.size(); i++) { // i = C.size() - 1时 t 一定小于 10
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 必须要去前导 0，因为最高位很可能是 0
    return C;
}

int main() {
    string a, b;
    cin >> a ; // a = "1222323", b = "2323423423"
    b=a;
    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i--)
        A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--)
        B.push_back(b[i] - '0');

    auto C = mul(A, B);

    for (int i = C.size() - 1; i >= 0; i--)
        cout << C[i];

    return 0;
}

总结

裸模板，结论很好猜，套个模板，2分钟就结束了

小H的糖果

题目链接

题意

给定n，两种操作，操作1：n 除以 k（如果能整除）,操作2：减去 1，求使 n 变为 1 的最少操作数。

思路

1.题目思路转换到位，就很好做了
2.先把n变为能被k整除的数（通过操作2）
3.再整除k，模拟即可

坑点

1.超时一时爽，一直超时一直爽，卡我endl，我裂开了，我就说为什么"\n"就过，endl就超时，导致比赛时没拿到分（原因：endl比"\n"多一个刷新缓存，影响效率），这件事告诉我们，endl少用...
2.从乘法和加法，推到减法和除法，需要一定的思维能力
3.学会优化，别减1就真去一个个减1

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        long long int k,n,ans=0;
        cin>>k>>n;
        if(k==1)
        {
            cout<<n-1<<"\n";
            continue;
        }
        while(n>=k)
        {
            ans+=n%k;//使之n能被k整除，所以需要把n变成能被k整除的数
            ans++;//整除则+1
            n=n/k;
        }
        ans+=n-1;//while循环结束的数小于等于k，则需要把其变为1
        cout<<ans<<"\n";
    }
    return 0;
}