Good Bye 2018题解

题解 CF1091A 【New Year and the Christmas Ornament】

打完cf都忘记写题解了qwq

题意就是：给你一些黄，蓝，红的球，满足蓝的数量恰比黄的多一，红的数量恰比蓝的多一

容易发现黄的数量恰是\(\min{y,b-1,r-2}\)

输出这个值\(*3+3\)即可

# include <bits/stdc++.h>

int main()

{

    int y, b, r;

    scanf("%d%d%d", &y, &b, &r);

    int ans = std::min(std::min(y, b - 1), r - 2);

    printf("%d\n", ans * 3 + 3);

    return 0;

}

题解 CF1091B 【New Year and the Treasure Geolocation】

打cf时网速感人qwq

容易想到一个\(O(n^3)\)的做法：枚举每一对\((x,y)\)与每一对\((a,b)\)配对，再判断是否满足条件，满足就输出

但是这样会超时，怎么办？

可以发现我们只要把每一个\((x,y)\)与第一个\((a,b)​\)配对即可

原因？因为每一对\((x,y)\)与每一对\((a,b)\)配对都要导致第一个\((a,b)\)与某一个\((x,y)\)配对，而任意一对这样的配对即可唯一确定\(T\)的位置，故只要枚举一遍每一个\((x,y)\)与第一个\((a,b)\)配对就能遍历所有情况。

时间复杂度\(O(n^2)\)

# include <bits/stdc++.h>

# define p std::pair<int, int> 

p pos[1010], change[1010];

std::map<p, int> m, tmp;

int main()

{

    int n;

    scanf("%d", &n);

    for(int i = 1; i <= n; i++)

        scanf("%d%d", &pos[i].first, &pos[i].second);

    for(int i = 1; i <= n; i++)

        scanf("%d%d", &change[i].first, &change[i].second), m[change[i]]++;

    for(int i = 1; i <= n; i++)

    {

        p T;

        T.first = pos[i].first + change[1].first;

        T.second = pos[i].second + change[1].second;

        tmp = m;

        int flag = true;

        for(int j = 1; j <= n; j++)

        {

            p tem;

            tem.first = T.first - pos[j].first;

            tem.second = T.second - pos[j].second;

            if(!tmp[tem])

                flag = false;

            --tmp[tem];

        }

        if(flag)

            return 0 * printf("%d %d\n", T.first, T.second);

    }

    return 0;

}

题解 CF1091C 【New Year and the Sphere Transmission】

这个C真烧脑qwq

可以发现每一次选的数的个数都是\(n\)的约数

枚举所有约数，计算答案即可（等差数列求和好评！）

#include <bits/stdc++.h>

#define ll long long

std::vector<ll> v, ans;

void prime(ll n)

{

    for (int i = 1; i * i <= n; ++i)

    {

        if (n % i == 0)

        {

            v.push_back(i);

            if (i * i != n)

            {

                v.push_back(n / i);

            }

        }

    }

}

std::map<ll, int> m;

int main()

{

    ll n;

    scanf("%I64d", &n);

    prime(n);

    for (int i = 0; i < v.size(); i++)

    {

        m[v[i]] = 1;

    }

    for(std::map<ll, int>::iterator it = m.begin(); it != m.end(); it++)

    {

        ll x = n / it->first;

        ans.push_back((1 + (x * (it->first - 1) + 1)) * (it->first) / 2);

    }

    std::sort(ans.begin(), ans.end());

    for(int i = 0; i < ans.size(); i++)

        printf("%I64d\n", ans[i]);

    return 0;

}