飞道的博客

Educational Codeforces Round 86 (Rated for Div. 2)(A~D)

2020-04-28 18:40 373人阅读  评论(0)

A. Road To Zero(水题)

总题目传送门

  • 思路：对两种操作的价格花费进行讨论一下相对大小，不同情况选择不同的方案

代码

#include<vector>
#include<iostream>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
using namespace std;
void fre() { freopen("A.txt","r",stdin); freopen("Ans.txt","w",stdout); }
#define ll long long 
#define INF 0x3f3f3f3f
const int mxn = 3e5;



int main()
{
    /* fre(); */
    int t;
    scanf("%d", &t);
    while(t --)
    {
        ll x, y, a, b;
        scanf("%lld %lld %lld %lld", &x, &y, &a, &b);
        if(x < y)
            swap(x, y);
        ll sum = a * (x - y); 
        if(b > 2*a)
            sum += a * 2 * y;
        else
            sum += b * y;
        printf("%lld\n", sum);
    }

    return 0;
}

B. Binary Period

思路

  • 题意

  • 分析

代码

#include<vector>
#include<iostream>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
using namespace std;
void fre() { freopen("A.txt","r",stdin); freopen("Ans.txt","w",stdout); }
#define ll long long 
#define INF 0x3f3f3f3f
const int mxn = 3e5;

int main()
{
    /* fre(); */
    int t;
    scanf("%d", &t);
    string s;
    while(t --)
    {
        cin >> s;
        int flag = 1;
        for(int i = 0; i < s.size() - 1; i ++)
        {
            if(s[i] != s[i+1])
            {
                flag = 0;
                break;
            }
        }
        if(flag)
        {
            cout << s << endl;
            continue;
        }


        for(int i = 0; i < s.size(); i ++)
            cout << "10";
        cout << endl;
    }

    return 0;
}

C. Yet Another Counting Problem（规律+周期）

思路

  • 题意: 给我们两个数a，b（ 1 = < a , b < = 200 1=<a,b<=200 ）,又给了q次询问，对于每次询问，给我在一个区间 [ l , r ]    ( l , r < = 1 e 18 ) [l,r]~~(l,r<=1e^{18}) ,让我们在这个区间中找出符合题意的x的数量（ l = < x < = r l=<x<=r ）并且 x % a % b = = x % b % a x\%a\%b==x\%b\%a ,求满足这个等式的x的数量

  • 分析：分析这一题，当时我在想数据的范围非常大，而且还是询问的次数q也比较多，明显像是规律题，但是题目给的时间 3.5s，说明这并不是一道完全的找规律题，还需要进行一些简单的计算，，，，虽然没做出来但是看到题解的做法是 通过数学中的 周期来简化问题，首先我们先统计出第一个周期 [ 1 , l c m ( a , b ) ] [1,lcm(a,b)] （lcm为最小公倍数，请自己思考第一个周期为什么是我给出的范围）内符合题目中等式的x数量，这样我们在统计有几个周期，就可以解决问题了，具体看代码

代码

#include<vector>
#include<iostream>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
using namespace std;
void fre() { freopen("A.txt","r",stdin); freopen("Ans.txt","w",stdout); }
#define ll long long 
#define INF 0x3f3f3f3f
const int mxn = 3e5;
ll n;
ll gcd(ll a, ll b) { return b == 0 ?  a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll f[mxn];

ll get_ans(ll x)
{
    return 1LL * f[n - 1] * (x/n) + f[x % n];
}

int main()
{
    /* fre(); */
    int t;
    scanf("%d", &t);
    while(t --)
    {
        ll a, b, q;
        scanf("%lld %lld %lld", &a, &b, &q);
        n = lcm(a, b);       //最小公倍数
        for(int i = 1; i < n; i ++)         //统计在第一个周期[1, n] 中出现的符合题是的数字的数量,i < n是因为 n一定不符合题意所以不用讨论了;
        if(i%a%b != i%b%a) f[i] = 1;
        else f[i] = 0;

        for(int i = 1; i < n; i ++)
            f[i] += f[i - 1];               //对当前周期求前缀和
        while(q --)
        {
            ll l, r;
            scanf("%lld %lld", &l, &r);
            ll ans = get_ans(r) - get_ans(l - 1);
            printf("%lld ", ans);
        }
        printf("\n");
    }

    return 0;
}

D. Multiple Testcases

思路

  • 题意：给我们n个数 a 1 , a 2 , , , a n a_1,a_2,,,a_n ，这数的的范围是 [ 1 , k ] [1,k] ,又给了k个限制条件 c 1 , c 2 , , , c k     c 1 > = c 2 > = c 3 . . . > = c n c_1,c_2,,,c_k~~~c_1>=c_2>=c_3...>=c_n ,对于第i个限制条件表示的意思是：在一个组中元素大于等于i的数要不多于 c i c_i 个；先我们要把这个n个数分成尽可能少的组，而对于分成的每一组都要满足所给的k个限制条件，输出最小分组数量q，并输出每个分组的元素

  • 分析：当时自己做的时候觉得很难，但是看完题解之后，并没有什么难的。

    • 第一种思路：这中的思路就是从右往左将n个元素依次进行分组，如果 “组”不够了，就添加一个新“组”，接着继续对元素分组，，，分析这种方法，因为从左往右限制条件越来越严格（即： c i c_i 越来越小），那么我们就先安排后面的数，之后由于越靠前限制条件越来越宽松，我们就可以让靠前的数进行插空，，整个过程的用优先级队列维护空位
    • 第二种思路：
    1. 引入数组 b b , b [ i ] b[i] 表示大于等于i的数字有多少个，之后用当 1 < = i < = k 1<=i<=k 时用 b [ i ] / c [ i ] b[i]/c[i] 向上取整，得出每个位置的最小分组数量 q 1 , q 2 , , , q n q_1,q_2,,,q_n ,找出这些最小分组中找出最大的分组数量q，这个q就是我们需要分的最小数量的组数。
    2. 接下来就是确定每一组中元素分别是啥，我们用贪心的思路去考虑一下，既然最k个位置中最大的分组数量才是q，那么必然 q 1 < = q q_1<= q ,      q 1 ~~~~q_1 表示的意思是大于等于1的元素（其实就是所有元素）最少可以分成 q 1 q_1 组，那么我们分成更多数量的组q组，那么肯等是可以的，那么有了这个思路之后，那么就是把 n个元素均分成q组，具体看代码

思路1代码

#include<vector>
#include<iostream>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
#include<queue>
using namespace std;
void fre() { freopen("A.txt","r",stdin); freopen("Ans.txt","w",stdout); }
#define ll long long 
#define INF 0x3f3f3f3f
const int mxn = 3e5;
struct Node
{
    int cnt;
    vector<int> v;
    bool operator <(const Node b) const
    {
        return cnt > b.cnt;
    }
    Node(){ cnt = 0, v.clear(); }
} st;

int ar[mxn], cr[mxn];

int main()
{
    /* fre(); */
    int n, k;
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; i ++)
        scanf("%d", &ar[i]);
    for(int i = 1; i <= k; i ++)
        scanf("%d", &cr[i]);

    sort(ar + 1, ar + 1 + n);
    priority_queue<Node> q;
    q.push(st);
    for(int i = n; i >= 1; i --)
    {
        st = q.top(); q.pop(); 
        if(st.cnt < cr[ar[i]])
        {
            while(i && st.cnt < cr[ar[i]])
            {
                st.v.push_back(ar[i]);
                st.cnt ++;
                i --;
            }
            i ++;
            q.push(st);
        }
        else
        {
            Node ed;
            q.push(ed);
            q.push(st);
            i ++;
        }
    }

    printf("%lu\n", q.size());
    while(! q.empty())
    {
        st = q.top(); q.pop();
        printf("%d", st.cnt);
        for(auto x : st.v)
            printf(" %d", x);
        printf("\n");
    }

    return 0;
}

思路2代码

#include<vector>
#include<iostream>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
using namespace std;
void fre() { freopen("A.txt","r",stdin); freopen("Ans.txt","w",stdout); }
#define ll long long 
#define INF 0x3f3f3f3f
const int mxn = 3e5;
int ar[mxn], br[mxn], cr[mxn];      //ar存放原始数据，br[i]存放大于等i所有元素数量，即后缀数组，cr存限制条件
vector<int> res[mxn];

int main()
{
    /* fre(); */
    int n, k; 
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; i ++)
    {
        scanf("%d", &ar[i]);
        br[ar[i]] ++;
    }

    for(int i = 1; i <= k; i ++)
        scanf("%d", &cr[i]);
    int q = 0;                              //分组数量
    for(int i = k; i >= 1; i --)
    {
        br[i] += br[i + 1];
        q = max(q, (int)ceil((double)br[i]/cr[i]));
    }

    sort(ar, ar + n);
    for(int i = 0; i < n; i ++)
        res[i%q].push_back(ar[i]);

    printf("%d\n", q);
    for(int i = 0; i < q; i ++)
    {
        printf("%d ",res[i].size());
        for(auto x : res[i])
            printf("%d ", x);
        printf("\n");
    }


    return 0;
}

转载：https://blog.csdn.net/qq_34261446/article/details/105800914
查看评论
* 以上用户言论只代表其个人观点，不代表本网站的观点或立场