9.12 模拟赛简明题解

5k_sync_closer · 2022-09-13 09:58:37 · 个人记录

A

设原序列为 \{A_{2n}\}，a_x=\{i,j\}\Leftrightarrow A_{i,j}=x\bigwedge i<j。特别地，a_0=\{1,1\}。

人话：a_i 是捡大小为 i 的石头时两人的位置，且 a_{i,0}<a_{i,1}。

不难发现，答案为 \sum\limits_{i=1}^n|a_{i,0}-a_{i-1,0}|+|a_{i,1}-a_{i-1,1}|。

#include <cstdio>
#include <cstdlib>
int n, a[100050][2];long long q;
int main()
{
    scanf("%d", &n);for(int i = a[0][0] = a[0][1] = 1, x;
    i <= n << 1;++i) scanf("%d", &x), a[x][a[x][0] != 0] = i;
    for(int i = 1;i <= n;++i) q += abs(a[i][0] - a[i - 1][0])
    + abs(a[i][1] - a[i - 1][1]);printf("%lld", q);return 0;
}

B

事原题罢（悲）

按照题意，两瓶体积为 2^i 的药水可以合并成一瓶体积为 2^{i+1} 的药水。

按体积 i 从小到大考虑，把所有体积为 2^i 的药水合并成尽可能多的体积为 2^{i+1} 的药水。

不难发现，答案为合并过程中剩下的药水瓶数。

#include <cstdio>
int n, x, q, a[2000050];
int main()
{
    scanf("%d", &n);while(n--) scanf("%d", &x),
    ++a[x];for(int i = 0;i <= 2000000;++i) q += a[i]
    & 1, a[i + 1] += a[i] >> 1;printf("%d", q);return 0;
}

C

注意到如果存在合法分组方案，可以确定最小数 x 的分组方案 [x,x+m-1]。考虑把序列装进桶 \{c_w\} 里，

问题转化为 \dfrac nm 次求桶内最小值 x，询问 \forall i\in[x,x+m-1] 是否满足 c_i>0，修改 \forall i\in[x,x+m-1],c_i\gets c_i-1。

考虑用 map 暴力维护，时间复杂度为 O(\dfrac{nm\log w}m)=O(n\log w)，显然能过。

好像可以用动态开点权值线段树优化成 O(\dfrac{n\log w}m) 来着，不管了。

#include <map>
#include <cstdio>
using namespace std;
int T, n, m, k, x;bool f;
int main()
{
    scanf("%d", &T);while(T--)
    {
        map<int, int> c;f = 0;scanf("%d%d", &n, &m);for(int i = 0;i
        < n;++i) scanf("%d", &x), ++c[x];if(n % m) puts("false");else
        {
            k = n / m;while(k--) {x = c.begin()->first;for(int i = x;i < x
            + m;++i) if(c.find(i) == c.end()) {puts("false");f = 1;break;}
            else if(!--c[i]) c.erase(i);if(f) break;}if(!f) puts("true");
        }
    }
    return 0;
}

D

不难发现，如果方程组有解，那么任意解可以转化为 \begin{cases}x=A\\y=B-A\end{cases}。

证明：设 X_i 为 X 的二进制第 i 位，则 A_i=1\Leftrightarrow x_i=1\bigvee y_i=1。

那么我们可以把 x,y 的二进制 1 都堆到 x 上，则 x=A,y=B-A。

则方程有解当且仅当 A|(B-A)=A。

#include <cstdio>
int T;long long a, b;
int main()
{
    scanf("%d", &T);while(T--) scanf("%lld%lld", &a, &b), puts
    ((a | b - a) == a ? "Possible" : "Impossible");return 0;
}