#880 div2

A：

题目：

现在给出一个数组，能否用这些元素，凑到任意个·符合 0 1 2 3 的序列

思路：

首先保证 0 1 2 3 4 都存在， 并且当前数字比前一个数字的个数要小。

做法：

首先去重，找到左右 0 1 2 3 的种类，判断是否都存在，然后个数是否冲突

代码

void solved()
{
    a.clear();
    cnt.clear();
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int x; cin >> x; a.push_back(x);
        cnt[x]++;
    }


    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());

    bool flag = true;

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

        if(i == 0)
        {
            if(a[0] != 0)
            {
                flag = false;
                break;
            }
            continue;
        }

        if(a[i] != i)
        {
            flag = false;
            break;
        }

        if(cnt[i - 1] < cnt[i])
        {
            flag = false;
            break;
        }
    }

    if(flag) cout << "YES" << endl;
    else cout << "NO" << endl;
}

B：

题目：

现在存在 k * g 金币，存在 n 个人，现在你可以分配这些金币给 n 个人，

如果分配给当前这个人 x 个金币，我们定义 r = x % g

如果 r >= g / 2上取整，那么最终他收到 x + (g - r) 否则收到 x - r 个。

问你在分配后，最终最多剩下多少金币。

思路：

不难发现，在这两种中，如果我们的分配的金币 x < g 并且 x < g / 2 上取整，那么我们这 x 个金币都可以剩下。

其他情况都会多给金币。 所以，尽可能的都分配 g / 2 个金币，然后剩下的金币都分给最后一个人。

人是可以分配给 0 个金币的，只需要分配完金币就行。所以存在有些人分配不到金币的情况。

做法：

首先 n - 1个人，优先分配 (g + 1) / 2 - 1 个金币，如果剩下金币的话都给最后那一个人。

如果有金币剩下，那么计算最后一个人剩下的金币，否则金币都剩下了、

思路：

void solved()
{
    cin >> n >> m >> q;

    int sum  = m * q - ((q + 1) / 2 - 1) * (n - 1);

    int r = sum % q;
    int ans = ((q + 1) / 2 - 1) * (n - 1);

    if(ans >= m * q)
    {
        cout << m * q << endl;
        return;
    }

    if(r >= (q + 1) / 2)
    {
        ans += sum - (sum + (q - r));
    }else ans += sum - (sum - r);

    cout << ans << endl;
}

C：

题目：

现在给出 A B C 三个整数，分别代表 a + b = c, 三个数字的位数，用字典序排序，第 k 个式子是什么，如果不存在给出 -1。

思路：

三个数字的范围给出，既然要求字典序最小，那么肯定保证 a b 从小到大枚举，我们枚举 a，自然得到 b 的数据范围。

然后计算 b 的个数，最终接近 k 得到答案。

做法：

枚举 a，然后根据 b的位数 c 的位数，求两者的交集，判断区间交集是否合法，然后计算个数，接近 k 时候，计算答案

代码

void solved()
{
    init();
    int a, b, c, d;
    cin >> a >> b >> c >> d;


    int sum = 0;
    bool flag = false;

    for(int i = wei[a - 1]; i <= wei[a] - 1; i++)
    {
        int lb = wei[c - 1] - i, rb = wei[c] - 1 -  i;

        lb  = max(lb, wei[b - 1]), rb = min(rb, wei[b] - 1);

        if(lb > rb) continue;

//        cout << sum - d<<endl;

        sum += rb - lb + 1;

        if(sum >= d)
        {

            cout << i << " + " << lb + d - (sum - (rb - lb + 1)) - 1<< " = " << i + (lb + d - (sum - (rb - lb + 1)) - 1) << endl;
            flag = true;
            break;
        }
    }

    if(!flag) cout << -1 << endl;

}