Good Bye 2018(A-C) D待补（暑假训练8.7）-阿里云开发者社区

Good Bye 2018(A-C) D待补（暑假训练8.7）

2022-04-18 86

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 算法

机票

战绩and总结

被兴哥吊锤的一天呢x压哨开出C，然后B把自己做破防了，告诉自己一万遍不要上头无脑提交然而并没有啥用:)

A. New Year and the Christmas Ornament

题意:有三种颜色的装饰，已知他们的数量分别是a，b，c。要求是你去装饰圣诞树时满足a=b+1=c+2，求最大的a。

思路：因为数据范围很小，所以从大到小暴力遍历即可

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int y,b,r;
    cin>>y>>b>>r;
    for(int i=r;i>=3;i--)
    {
        if(b>=i-1&&y>=i-2)
        {
            cout<<3*i-3<<endl;
            break;
        }
    }
    return 0;
}

B. New Year and the Treasure Geolocation

题意：读入一个正整数n，接下来读入2n行，一共2n个向量，保证存在一个向量，定于v，使得n∗2个向量两两相加，加出来的n个向量等于v。

思路①：兴哥的思路是看题目的式子就能知道了，把n个坐标与另外n个坐标以某种排列一一对应使每一组对应的坐标x,y分别相加得到的新坐标 (Tx,Ty) (Tx,Ty )是一样的对于任意一组对应的坐标 ,所以只要把所有x,y分别加起来并除以n就可以了…

思路②：因为凑成的新坐标都是相同的，并且xi+xj=Tx,y1+y2=Ty,那么假设题目只要求横坐标，那么确保答案一定存在的情况下那不就是最小的加上最大的就行了，考虑纵坐标同理

思路③：此题不难想到O(n^2)的做法，即将所有的(x,y)和(a,b)一一配对，用map统计每种(x+a,y+b)出现的次数，出现n次的即为答案。

我的做法：用O(n^2)去暴力的找出现最多的个数，不断的更新查询，超时了，以后注意如果是纯暴力得开unordered_map。

C. New Year and the Sphere Transmission

题意:就是n个人围成一圈，从第一个人开始，每次可以往后跳k步(1<= k <= n)最后跳回第一个人那里, 对于每个k把它经过的人的编号加起来，假设为fk , 把fk排序后去重然后输出。

思路：不管是画图还是自己找规律都不难发现每一次选的数的个数都是n的约数，所以枚举约束用等差数列求和公式计算即可（不用会t！）

假设每次跳k步，能够到的点就是1+k,1+2k,1+3k,所以n的约数。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5;
int a[maxn];
long long sum(int a,int n)
{
    long long sum1=0;
    long long nn=(n%a==0?n/a:n/a+1);
    sum1=nn+(nn*(nn-1))/2*a;
    return sum1;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,i,j,cnt=0;
    cin>>n;
    for(i=2;i<=n/i;i++)
    {
        if(n%i==0)
        {
            a[cnt++]=i;
            if(n/i!=i)
                a[cnt++]=n/i;
        }
    }
    sort(a,a+cnt);
    cout<<1<<" ";
    for(i=cnt-1;i>=0;i--)
    {
        cout<<sum(a[i],n)<<" ";
    }
    cout<<sum(1,n)<<endl;
    return 0;
}