首页 > 编程学习 > 2022CCPC威海:A、C、E、G、J

2022CCPC威海:A、C、E、G、J

发布时间:2022/11/9 3:37:36

2022CCPC威海:A、C、E、G、J

目前这5题让我觉着,威海这场思路倒不是多难,但是代码我觉着很难写,比如c和j。

Problem - A - Codeforces

问题解析

题目很怪,看了好多次。

题目说有个比赛,先给你n行,每行5个人,这五个人的顺序是他们比赛的位置(1~5),这n行是之前比赛的冠军,再给你m个人,每个人有对应的位置,问你最多能组成多少队伍参加比赛,每个队伍里都至少要有一个冠军,每个人的位置不能变。

一开始想的能组多少不同的队伍,这样就是每个位置的不同人数和冠军的数量来算,但是显然样例1就不对劲。后来发现是能组成的队伍数,不是不同的队伍数。

  • 那就计算每个位置的人数,如果不考虑冠军的因素,能组成的最多队伍数就等于这五个位置里人数最少的数量(比如1到4位置都有10人,但位置5只有1人,那就只能组成1个队伍,木桶原理)。
  • 如果要考虑冠军因素,那贪心的来想,就是每个队伍一个冠军,那能组成的队伍数就是冠军的数量。

答案就是两者中的最小值。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

#pragma GCC optimize(2)
#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6 + 50, MOD = 1e9 + 7;

void solve()
{
    int n, m, x;
    string s;
    unordered_map<int, int>mymap, champion;
    unordered_map<string, int>st;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= 5; j++)
        {
            cin >> s;
            st[s] = 1;
        }
    }
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> s >> x;
        mymap[x]++;
        if (st.count(s))
        {
            champion[x]++;
        }
    }
    int mn = 1e9, ans = 0;
    for (int i = 1; i <= 5; i++)mn = min(mn, mymap[i]);
    for (int i = 1; i <= 5; i++)
    {
        ans += champion[i];
    }
    cout << min(mn,ans);
}

signed main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    
    while (t--)
    {
        solve();
    }
    return 0;
}

Problem - C - Codeforces

问题解析

题目说给你n个点,问你能不能找到五个点ABCDE,让线段AB、AC、AD、AE之间不发生交叉。

很显然,要是给的点不够5个,就直接输出NO。

我们也可以想出,只要BCDE四个点不是都和A共线的,就能有结果,哪怕BCDE四个点都是共线。

在这里插入图片描述

也就说重点不在BCDE上,而是在点A上。

对于给的n个点,我们之间把前四个点记录下来,然后从剩下的点里面找第五个点。每次我们假设这五个点是答案送去判断,如果能组成答案就输出,不能我们就找下一个点当作第五个点,以此类推,要是找完了还没能出结果,说明没有答案,输出NO。

至于判断五个点是不是答案,我们枚举每个点当作是A,剩下的当作BCDE,然后看他们和A的共线情况。

这里我是判断他们和A的斜率:**(y2-y1)/(x2-x1)**是否相同。如果都不相同,说明当前枚举的点A就可以是一个合格的答案。

如果有两个斜率相同,说明这两个点和A共线,那么,当且仅当A是在这俩点中间时,才是正确的,比如:

在这里插入图片描述

而如果A不在两点之间,显然答案不对的,比如:

在这里插入图片描述

至于判断A是否在BC之间,只要看AB+AC是否等于BC即可。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

#pragma GCC optimize(2)
#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e6 + 50, MOD = 1e9 + 7;

int gcd(int a, int b)
{
    return a == 0 ? b : gcd(b % a, a);
}

bool check(vector<PII>& ans)
{
    for (int i = 0; i < 5; i++)
    {
    	//记录下每个斜率的点
        unordered_map<double, vector<PII>>res;
        bool flag = true;
        for (int j = 0; j < 5; j++)
        {
            if (i == j)continue;
            //计算斜率:(y2-y1)/(x2-x1)
            double b = (ans[j].second - ans[i].second), a = (ans[j].first - ans[i].first);
            double c = b / a;
            //如果已经有两个点与A共线,那这第三个点显然不对
            if (res[c].size() >= 2)
            {
                flag = false;
                break;
            }
            //如果已经有一个点与A共线,那看A在不在这两个点之间
            else if (res[c].size() == 1)
            {
                int x = abs(ans[i].first - res[c][0].first) + abs(ans[i].second - res[c][0].second);
                int y = abs(ans[i].first - ans[j].first) + abs(ans[i].second - ans[j].second);
                int z = abs(ans[j].first - res[c][0].first) + abs(ans[j].second - res[c][0].second);
                if (x + y == z)
                {
                    res[c].push_back(ans[j]);
                }
                else
                {
                    flag = false;
                    break;
                }
            }
            else res[c].push_back(ans[j]);
        }
        if (flag)
        {
            cout << "YES" << endl;
            cout << ans[i].first << " " << ans[i].second << endl;
            for (int j = 0; j < 5; j++)
            {
                if (i == j)continue;
                cout << ans[j].first << " " << ans[j].second << endl;
            }
            return true;
        }
    }
    return false;
}

void solve()
{
    int n;
    cin >> n;
    unordered_map<double, int>mymap;
    vector<PII>v(n + 1), ans;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i].first >> v[i].second;
        if (ans.size() < 4)
        {
        	//固定前四个点
            ans.push_back(v[i]);
        }
    }
    if (n < 5)
    {
        cout << "NO" << endl;
        return;
    }
    for (int i = 5; i <= n; i++)
    {
    	//找第五个点
        ans.push_back(v[i]);
        if (check( ans ))
        {
            return;
        }
        ans.pop_back();
    }
    cout << "NO" << endl;
}

signed main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    cin >> t;

    while (t--)
    {
        solve();
    }
    return 0;
}

Problem - E - Codeforces

问题解析

题目是说给你一个长度为n的数组和一个数k,要你找到第一个小于k的数的位置,如果数组没有,那你可以扩展数组:ai=a(i-1)*2-a(i-2);

直到找到小于k的数位置,如果永远也找不到,输出永远也找不到。

没啥想法,就想着先把数组扩展到1e6个数,如果找到了就输出位置,找不到就输出永远也找不到。

然后就过了,笑死。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

#pragma GCC optimize(2)
#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6 + 50, MOD = 1e9 + 7;

int a[N];
void solve()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] < k)
        {
            cout << "Python 3." << i << " will be faster than C++" << endl;
            return;
        }
    }
    for (int i = n + 1; i <= 1000000; i++)
    {
        a[i] = max((int)0, 2 * a[i - 1] - a[i - 2]);
        if (a[i] < k)
        {
            cout << "Python 3." << i << " will be faster than C++" << endl;
            return;
        }
    }
    cout << "Python will never be faster than C++";
}

signed main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    
    while (t--)
    {
        solve();
    }
    return 0;
}

Problem - G - Codeforces

问题解析

题目说给你一个数x和m次询问,每次询问给一个区间l~r,问你l到r里有几个数k能够满足gcd((k*x ^ x),x)=1.

找规律题,对于数字x,它的答案其实是有一个长度为2^(log2(x))的循环节(循环节长度就是第一个大于x的2的次幂)。

因为x最大也就1e6,我们可以先把循环节的答案给算出来,一个循环节的k的个数我们记作cnt,然后每次询问,根据区间的长度能分成三部分:

  1. 最左边的部分,这一部分不是一个完整的循环节。
  2. 中间的部分,包含了复数个循环节。
  3. 最右边的部分,这一部分也不是一个完整的循环节。

中间的部分,我们可以通过计算出循环节的个数*cnt得到结果。

至于左边和右边的部分,一开始我用for循环一个个找,然后t了,想了想最坏的情况每次询问我们都要搜1e6左右的长度,复杂度就变成n^2了,慢死。

我们在计算循环节的时候,顺便准备一个前缀和数组sum,sum[i]表示0到i有多少个结果。这样左边和右边的部分我们就能通过前缀和数组算出结果了。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

#pragma GCC optimize(2)
#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e6 + 50, MOD = 1e9 + 7;

//mymap[i]表示循环节内i是不是正确的答案。
//sum是前缀和数组
int mymap[N], sum[N];
int gcd(int a, int b)
{
    return a == 0 ? b : gcd(b % a, a);
}
void solve()
{
    int x, n, y = 1, cnt = 0;
    cin >> x >> n;
    //求出循环节的长度
    while (y < x)
    {
        y *= 2;
    }
    //求出循环节内的答案数
    for (int i = 0; i < y; i++)
    {
        if (gcd((i * x)^x, x) == 1)
        {
            mymap[i] = 1;
            cnt++;
        }
        if (i == 0)sum[i] = mymap[i];
        else sum[i] = sum[i - 1] + mymap[i];
    }

    while (n--)
    {
        int l, r;
        cin >> l >> r;
        //l2是区间内第一个循环节的开头,r2是区间内最后一个循环节的结尾
        int l2 = ceil((double)l / y), r2 = r / y;
        int res = 0;
        if (l2 * y <= r2 * y)
        {
            res = (r2 - l2) * cnt;
            res += sum[r % y];
        }
        res += sum[min(l2 * y - 1, r) % y] - sum[(l - 1) % y];   
        cout << res << endl;
    }
}

signed main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    
    while (t--)
    {
        solve();
    }
    return 0;
}

Problem - J - Codeforces

问题解析

题目是说给你n个数,以及m个限制,每个限制有两个数x和y,表示数x最多只能同时出现y个,每次两个玩家会选一个数-1,最先做不出操作的就输了。

一开始看见博弈吓得很,但是看了题目发现他们每轮的操作并没有多花哨,根据奇偶性就能求出结果。

按照限制中,y=0的地方分割数,如果x最多出现次数为0,说明比他大的数都只能停在x+1上了,不能更小。

然后剩下的数则能删多小删多小。

但是可能会出现x出现次数为0,x+1出现次数为1的限制。

(个人感觉思路不难,但是代码有点麻烦,文字不好说,看代码注释罢)

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

#pragma GCC optimize(2)
#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6 + 50, MOD = 1e9 + 7;

void solve()
{
    int n, m, x, y;
    cin >> n >> m;
    //lim只记录y=0的情况
    vector<int>v(n), lim;
    //mymap记录每个数的限制,cnt记录操作之后每个数出现了几次
    unordered_map<int, int>mymap, cnt;
    for (int i = 0; i < n; i++)cin >> v[i];
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y;
        mymap[x] = y;
        //如果y=0,则把当前x存入数组lim中
        if (y == 0)
        {
            lim.push_back(x);
        }
    }
    //为了方便,lim额外存上x=-1和x=(任意一个很大的数)的情况
    mymap[-1] = 0;
    lim.push_back(-1);
    mymap[1e18] = 0;
    lim.push_back(1e18);
    sort(v.begin(), v.end());
    sort(lim.begin(), lim.end());
    //res记录结果,ans记录当前能减小到的最小值,idx表示我们当前要减小的是哪个数,l表示当前是第几个限制。
    int res = 0, ans = 0, idx = 0, l = 0, len = lim.size();
    while (idx < n)
    {
    	//lim[l]当作上界,要保证当前要减小的数小于lim[l](所以要加一个很大的数
    	//如果当前进行操作的数大于lim[l],则l后移,并更新ans
        while (l < len && v[idx] > lim[l])
        {
        	//既然lim[l]出现次数为0,那么大家能减小到的最小值就为ans
            ans = lim[l] + 1;
            l++;

        }
        
        while (idx < n && v[idx] < lim[l])
        {
        	//如果ans的出现次数也有限制,那么当减小到ans的数到限制后,ans要++。
            while (mymap.count(ans) && cnt[ans] == mymap[ans])
            {
                ans++;
            }
            //计算能减小的次数
            res += v[idx] - ans;
            cnt[ans]++;
            idx++;
        }
    }
    //根据奇偶性判断输赢
    if (res % 2 == 1)cout << "Pico" << endl;
    else cout << "FuuFuu" << endl;
}

signed main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    cin >> t;
    
    while (t--)
    {
        solve();
    }
    return 0;
}
Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式