Codeforces Round #847 (Div. 3)A~E题解A. Polycarp and the Day of PiB. Taisia and DiceC. PremutationD. MatryoshkasE. Vlad and a Pair of Numbers

92 阅读 0 评论 61 点赞

我是靠谱客的博主聪慧钢笔，最近开发中收集的这篇文章主要介绍Codeforces Round #847 (Div. 3)A~E题解A. Polycarp and the Day of PiB. Taisia and DiceC. PremutationD. MatryoshkasE. Vlad and a Pair of Numbers，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A. Polycarp and the Day of Pi

传送门：Problem - A - Codeforces

题意：给出一串长度最多为30的数字串，问你从哪一位开始和圆周率对不上。

当时看到这题有点小疑惑，圆周率前30位是不是要自己去弄。有趣极了，想了半天直接去搜了。赛后后来发现榜前20都是直接搜了粘上去，6。

代码：

//2023.1.28
#include<math.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<map>
#include<list>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<stack>
#include<limits>
#define re register
#define iosgo() std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#define run(i,n) for (int i = 1; i <= n; i++)
#define cin std::cin
#define cout std::cout
#define ll long long
#define endl "n"
using namespace std; 
typedef pair<int, int>pll;
ll x[200005], y[200005];
pll c[200005];
char a[200005];
signed main()
{
    int t;
    scanf("%dn",&t);
    while (t--)
    {
        gets(a);
        a[strlen(a)] = -1;
        string p = "3141592653589793238462643383279";
        if (a[0] != '3')
        {
            cout << "0n"; continue;
        }
        for (int i = 0; i <strlen(a); i++)
        {
            if (a[i] != p[i])
            {
                cout << i << endl; break;
            }
        }
    }
}

B. Taisia and Dice

传送门：Problem - B - Codeforces

给出n,s,r。分别对应总色子的数量，总点数，和已经有的点数。

让你输出任意一种可能的摆布，满足摆布中除去最大的那个点数的色子后，剩下的总点数=r。

这时候咱就分两种情况就可以了。由于色子最多为6。所以就看s-r是否为6，是的话分一种，不是分另一种，然后维持序列中最大点数不超过它。（由题意知：s-r即为最大点数）。

代码：

#include<math.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<map>
#include<list>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<stack>
#include<limits>
#define re register
#define iosgo() std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#define run(i,n) for (int i = 1; i <= n; i++)
#define cin std::cin
#define cout std::cout
#define ll long long
#define endl "n"
using namespace std; 
typedef pair<int, int>pll;
ll x[200005], y[200005];
pll c[200005];
signed main()
{
    int t;
    cin >> t;
    int f[100], ff[100];
    while (t--)
    {
        memset(f, 0, sizeof(f));
        memset(ff, 0, sizeof(ff));
        int n, should, sum;
        cin >> n >> should >> sum;
        if (should - sum == 6)
        {
            int g = (sum) / (n - 1);
            int sum2 = 0;
            run(i, n - 1)
            {
                f[i] = g;
                sum2 += f[i];
            }
            sum2 += 6;
            f[n] = 6;
            run(i, n - 1)
            {
                while (sum2 < should && f[i] < 6)
                {
                    f[i]++;
                    sum2++;
                }
            }
            run(i, n)
            {
                cout << f[i] << " ";
            }
            cout << endl;
        }
        else
        {
            int sum2 = 0;
            int g = sum / (n - 1);
            run(i, n - 1)
            {
                f[i] = g;
                sum2 += f[i];
            }
            f[n] = should - sum;
            run(i, n - 1)
            {
                while (sum2 < sum && f[i] < should - sum)
                {
                    f[i]++;
                    sum2++;
                }
            }
            run(i, n)
            {
                cout << f[i] << " ";
            }
            cout << endl;
        }
    }
}

C. Premutation

传送门：Problem - C - Codeforces

题意：让你输出唯一正确的permutations序列。

由样例不难看出，每一个数只会出现在两列。其中每一列最多的数就是这个位置对应的数，但是当遇到这一列有两个数数量相同时，就会有一个先后位置问题，咱也可以发现，这一列这俩数那个数在前面出现过那么这个数位置就在前面。这是我的思路，然后码了一片。

代码：

#include<math.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<map>
#include<list>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<stack>
#include<limits>
#define re register
#define iosgo() std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#define run(i,n) for (int i = 1; i <= n; i++)
#define cin std::cin
#define cout std::cout
#define ll long long
#define endl "n"
using namespace std;
typedef pair<int, int>pll;
int x[2005], y[2005];
pll c[200005];
int h[150][150];
signed main()
{
    iosgo();
    int t;
    cin >> t;
    while (t--)
    {
        memset(x, 0, sizeof(x));
        memset(y, 0, sizeof(y));
        memset(h, 0, sizeof(h));
        int n; cin >> n;
        for (int i = 1; i <= n; i++)
        {
            memset(h[i], 0, sizeof(h[i]));
            for (int j = 1; j <= n - 1; j++)
            {
                int u;
                cin >> u;
                h[i][j] = u;
            }
        }
        map<int, int>k[150];//记录出现次数
        for (int i = 1; i <= n - 1; i++)
        {
            int ma = 0;
            for (int j = 1; j <= n; j++)
            {
                k[i][h[j][i]]++;
                ma = max(k[i][h[j][i]], ma);
            }
            x[i] = ma;//找到最多次数
        }
        int d[150];//记录答案
        memset(d, 0, sizeof(d));
        int i, cnt = 1;
        for (i = 1; i <= n - 1; i++)
        {
            for (int ff = 1; ff <= n; ff++)//含ff的循环都是用来返回找这个数，由于已知关系这并不复杂
            {
                if (k[i][h[ff][i]] == x[i])
                {
                    d[cnt++] = h[ff][i];
                    y[i] = h[ff][i];
                    break;
                }
            }
        }
        sort(y + 1, y + n);//看一下还有那个数没出现
        int biao = 0;
        run(i, n)
        {
            if (y[i] != i)
            {
                biao = i;//标记了
                break;
            }
        }
        int uu = 0;
        for (int i = 1; i <= n - 1; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (h[j][i] == biao)
                {
                    uu = i;//找到这个数的位置
                    break;
                }
            }
            if (uu) { break; }
        }
        run(i, n - 1)//分情况输出就好了
        {
            if (i != uu + 1)
            {
                cout << d[i] << " ";
            }
            else
            {
                cout << biao << " " << d[i] << " ";
            }
        }
        cout << endl;
    }
}

赛后我看到一群超级简单的代码，虽然我不理解但我大为震撼。举个我最想知道的例子。

源自cf参赛人员: A-SOUL_EiIeen。（排行第三）

代码：

#include <bits/stdc++.h>
#define mod 998244353 
#define int long long
using namespace std;
pair<int,int> a[1005];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        cin >> n;
        for(int i=1;i<=n;i++) a[i]={0,i};
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<n;j++)
            {
                int x;
                cin >> x;
                a[x].first+=j;
            }
        }
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++)
            cout << a[i].second << " ";
        cout << "n"; 
    }
    return 0;
}

如果有大佬明白可以留言教我，给大佬们磕头了！！！

D. Matryoshkas

传送门：Problem - D - Codeforces

题意：问你有多少个连续的子序列。

EX：

输出 2

咱把这问题想成一个动态的，一直搜索，找到一个连续的就删掉这个序列中所有的数。

我用的是multiset，构造俩迭代器。然后一直更新搜寻与删除。详情见代码注释。

代码：

#include<math.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<map>
#include<list>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<stack>
#include<limits>
#define re register
#define iosgo() std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#define run(i,n) for (int i = 1; i <= n; i++)
#define cin std::cin
#define cout std::cout
#define ll long long
#define endl "n"
using namespace std;
typedef pair<int, int>pll;
int x[200005], y[200005];
pll c[200005];
int h[150][150];
signed main()
{
    int t;
    cin >> t;
    while (t--)
    {
        multiset<int>k;
        k.clear();
        int n; cin >> n;
        run(i, n)
        {
            cin >> x[i];
            k.insert(x[i]);//插入
        }
        k.insert(INT_MAX);//给定边界，防止溢出。
        std::multiset<int>::iterator it,its;
        int cnt = 0,u;
        while (k.size()!=1)//防止溢出
        {
            it = k.begin();
            its = k.upper_bound(*it);//二分查找，返回大于*it的下一位，这里不过多介绍。
            u = *its;//u在这里起到一个关键的数字传递作用
            if (u != *it + 1)//找不到
            {
                k.erase(it);
                cnt++;//及时删除，++。
            }
            else//找到了
            {
                k.erase(it);//先删
                while (k.size() != 1)
                {
                    it = k.upper_bound(u);//以u为媒介不断更新
                    if (*it != u+1 )//找不到
                    {
                        k.erase(its);
                        cnt++;
                        break;//删了重来
                    }
                    else//找到了
                    {
                        k.erase(its);
                         u = *it;//删除并及时更新u。
                         its = k.upper_bound(u - 1);//及时更新its，这里要特别注意。
                    }
                }
            }
        }
        cout << cnt << endl;
    }
}