grade

会 T1 T2 的正解,并且都没写挂。(除了 T2 因为 map 被卡了 20 分)

A 计算异或和

给出 n 个数 p_i,求:

\bigoplus_{i = 1}^n p_i \bigoplus_{j = 1}^n (i \bmod j)

n \leq 100000


先把所有的 p_i 拿出来计算,接下来考虑如何搞:

\bigoplus_{i = 1}^n \bigoplus_{j = 1}^n (i \bmod j)

这样看貌似也只能整除分块之类的搞一搞,可是发现并没有用,转而考虑换一种枚举的顺序

\bigoplus_{j =1}^n \bigoplus_{i = 1}^n (i \bmod j)

这时,模数是固定的,只有被模数变化。发现这个东西有极强的周期性。(i \bmod j) 实际上是把 [1, n]j 为一个周期分成了若干整块与最后一个小块,每块是 0, 1\cdots j - 1。要算这些数的异或,可以对整块的出现次数的奇偶性进行讨论:

  • 整块共出现了偶数次。此时所有整块的贡献都没了,只用算最后一个小块,即 \displaystyle \bigoplus_{v = 0}^{n \bmod j} v
  • 整块共出现了偶数次。此时整块的贡献会和小块的贡献抵消,答案为 \displaystyle \bigoplus_{v = n \bmod j + 1}^{j - 1} v

这两个东西预处理一下前缀异或和就都能 O(1) 的搞出来了。

const int MAXN = 1e5 + 10;

int n, ans, sum[MAXN];

int calc(int k) {
    int cnt = (n / k), ret = 0;
    if (cnt & 1) ret = sum[k - 1] ^ sum[n % k];
    else ret = sum[n % k];
    return ret;
}

int main() {
    #ifdef LOCAL
        freopen("calcxordata.txt", "r", stdin);
    #endif
    IO::read(n);
    rep(i, 1, n) {
        int x; IO::read(x);
        ans ^= x;
        sum[i] = sum[i - 1] ^ i;
    }
    rep(k, 1, n) ans ^= calc(k);
    IO::write(ans, '\n');
    return 0;
}

B 配置香水

给出长度为 n 的整数序列 a_i 与一个 -10 \leq K \leq 10,求有多少对 l \leq r,满足:

\exist x \in \mathbb{Z}, (\sum_{i = l}^r a_i) = K^x

n \leq 10^5, |a_i| \leq 10^9。多组询问,\sum n \leq 10^5


发现这个 x 最多不会超过 48,所以直接暴力预处理出每个 K 的所有次幂,然后暴力扫 r,暴力枚举次幂,看有多少个 S_{l - 1} = S_r - K^x 就好。

时间复杂度 O(n \times 48 \times \log n)

可是 map 会在 auoj 上被卡成 80,但是用 multiset 就过了。

typedef long long ll;

const ll MAXVAL = 1e14;
const int MAXN = 1e5 + 10;

int n, k, arr[MAXN];
ll sum[MAXN], ans;
vector<ll> pows[20 + 10];

multiset<ll> cnt;

void solve() {
    IO::read(n), IO::read(k);
    cnt.clear(); ans = 0;
    rep(i, 1, n) IO::read(arr[i]), sum[i] = sum[i - 1] + arr[i];
    cnt.insert(0);
    rep(i, 1, n) {
        for (int idx = 0; idx < pows[k + 10].size(); ++idx) ans += cnt.count(sum[i] - pows[k + 10][idx]);
        cnt.insert(sum[i]);
    }
    IO::write(ans, '\n');
}

int main() {
    #ifdef LOCAL
        freopen("perfume.txt", "r", stdin);
    #endif
    rep(i, -10, 10) {
        pows[i + 10].push_back(1);
        if (0 <= abs(i) && abs(i) <= 1) continue;
        ll cur = i;
        while (abs(cur) <= MAXVAL) {
            pows[i + 10].push_back(cur);
            cur = 1ll * cur * i;
        }
    }
    pows[-1 + 10].push_back(-1);
    int t; IO::read(t);
    while (t--) solve();
    return 0;
}

C 分配

n 个人,编号为 1 \cdots n。有若干个物品。

每一轮,由局面上编号最大的人进行提出一个分配方案。即,把这若干个物品分配给还在局面上的人。

接下来,局面上所有人会进行投票。一个人会支持,当且仅当满足下列三者条件至少其一:

  • 他是提出方案的人。
  • 该方案中他获得的物品个数,严格 大于以后的所有方案中获得的物品个数。
  • 在以后的所有方案中,他会出局。

如果一个方案有大于等于 \big \lfloor \dfrac{局面人数}{2} \big \rfloor 个人支持,那么会结束分配。局面上所有人都不出局。

否则,提出该方案的人会出局。

现在,有两问需要你回答。

  • 如果第 n 号人必须获得至少 1 个物品,至少需要多少物品使得存在至少一种分配方案使得他能不出局?
  • 如果第 n 号人可以获得任意多的物品,至少需要多少物品使得存在至少一种分配方案使得他能不出局?

n \leq 10^9


先考虑第一个问。

  • 一个人,只需要 1 个。
  • 两人,也只需要 1 个。因为这样 支持-反对 比是 1:1 的。
  • 三人,因为如果 3 号出局,2 不会给 1 号任何物品;所以 3 号只需要给 11 个物品再加上自己的 1 个物品,共 2 个物品即可。
  • 四人,因为如果 4 号出局,3 不会给 2 号任何物品;所以 4 号只需要给 21 个物品再加上自己的 1 个物品,共 2 个物品即可。
  • n 人,只要 n 给所有 n - 1 不会给的人 1 个物品,他们就会支持。容易发现编号与 n 同奇偶的人都不会收到 n - 1 的物品,所以只需要给和自己同奇偶的人即可。答案就是 \big\lceil \dfrac{n}{2}\big\rceil

再考虑第二个问。

第二个问,考虑对于有 k 个物品的局面,能让哪些 n 成功。

  • k = 0n = 1, 2, 4, 8, 16\cdots 2^x
  • k = 1n = 1, 2, 3, 4, 6, 10, 18 \cdots 2^x + 2
  • k = 2n = 1, 2, 3, 4, 5, 6, 8, 12, 20 \cdots 2^x + 4

有理由猜测,k = n 时,n = 1, 2, 3 \cdots 2k, 2k + 1, 2k + 2^1, 2k + 2^2 \cdots 2n+2^x

下面我们来证明一下。

首先,对于 n \in [1, 2k + 1],你只需要给所有 n - 1 不会给的人就好,而你只需要给 \big\lceil \dfrac{n}{2}\big\rceil - 1 个人,所以这些 n 是足够的。

对于后面的那些 n,考察是哪些人支持了。例如当 n = 2k + 3 时,必死,所以直到下一个能让 2k + 3 活命的人,他都会支持。之后,他都会不支持(除非他那个人给了他若干物品)。

事实上,令 a_i 是在 2k + 1 后第 i 个可以存活的 n,令 a_i + \Delta_i 个人又可以存活,那么我们有

\Delta_i + k = \big\lceil\dfrac{a_i + \Delta_i}{2} \big\rceil

因为每个 x \in (a_i, a_i + \Delta_i] 都会在 n = a_i + \Delta_i 时支持,其他人都不会投(因为他们能在 n = a_i 时存活);同时,你还可以通过把物品给那些在上一个局面中没有得到物品的人来获得他们的支持(这些人的人数一定不会少于 k)。当这些两部分的和达到一半后,n = a_i + \Delta_i 就活了。

那么有两个解

\Delta_{i1} = a_i - 2k, \Delta_{i2} = a_i - 2k + 1

由于 \Delta_{i1} < \Delta_{i2},所以 \Delta_{i2} 一定是不合法的。

综上所述,\Delta_i = a_i - 2k

由此,我们可以得到一个一阶的递推式:a_{i + 1} = 2a_i - 2k。并且 a_i + 1 = 2k + 1。通过一些数学手段(特征方程啥的),可以求出 a_i = 2k + 2^{i - 1}

所以对于所有 n = 2k + 2^{x - 1},都可以用 k 个物品存活。

至此,问题转化为,对于一个 n,求出一个最小的 k

  • 如果 n 是一个奇数,显然不存在 n = 2k + 2^{x - 1}。答案为 k = \big\lfloor \dfrac{n}{2} \big\rfloor
  • 否则,将 n 最高位去掉之后(即把 2^{x - 1} 去掉)除以 2 就是答案。

时间复杂度 O(T \log n)

void solve() {
    int n, S; IO::read(n), IO::read(S);
    if (S == 1 || (n & 1)) return IO::write((n + S) >> 1, '\n'), void();
    per(_, 31, 0) if ((n >> _) & 1) return IO::write((n - (1 << _)) >> 1, '\n'), void();
}

int main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
    #endif
    int t; IO::read(t);
    while (t--) solve();
    return 0;
}

D 数列编辑器

维护一个序列与一个光标,操作涉及:

  • 在光标后加入一个数,并将光标移到加入的数后。
  • 将光标左右移动。
  • 把光标前的数删除。
  • 修改某个数。
  • 求当前序列的某个区间和。

Q \leq 3\times 10^5


块 状 链 表。

时间复杂度 O(n\sqrt n)

typedef long long ll;

const int MAXN = 3e5 + 10;

struct BlockList {
    static const int BLOCKSIZE = 830;
    static const int BLOCKNUM = MAXN / BLOCKSIZE + 10;
    static const int HEAD = 1, EMPTY = 0;

    struct Node { int data[BLOCKSIZE * 2 + 10], nxt, sz; ll sum; } t[BLOCKNUM];
    int avaliNode[BLOCKNUM], tp;

    BlockList() { per(i, BLOCKNUM - 1, 2) avaliNode[++tp] = i; t[HEAD].nxt = EMPTY, t[HEAD].sz = 0, t[HEAD].sum = 0; }

    inline void del_node(int blockNum) { avaliNode[++tp] = blockNum, t[blockNum].sz = 0, t[blockNum].sum = 0, t[blockNum].nxt = EMPTY; }
    inline int new_node() { int ret = avaliNode[tp--]; t[ret].nxt = EMPTY; return ret; }

    inline void get_pos(int& dataIdx, int& blockNum) {
        for (blockNum = HEAD; blockNum != EMPTY && dataIdx > t[blockNum].sz; blockNum = t[blockNum].nxt) dataIdx -= t[blockNum].sz;
    }
    inline void cpy(const int& blockNum, const int & s, const int data[], const int& len) { // 将 t[blockNum].data[s] 开始的 len(包含 s)个 int 赋值为从 data[0] 开始的  len 个 int
        register int ed = s + len - 1;
        for (register int i = s; i <= ed; ++i) t[blockNum].data[i] = data[i - s];
    }
    inline void link(int blockNum1, int blockNum2) { // insert blockNum2 after blockNum1
        t[blockNum2].nxt = t[blockNum1].nxt, t[blockNum1].nxt = blockNum2;
    }
    inline void calc_sum(int blockNum) { t[blockNum].sum = 0; rep(i, 1, t[blockNum].sz) t[blockNum].sum += t[blockNum].data[i]; }
    inline int split(int blockNum1, int p) { // 将 t[blockNum1].data 从 p 开始(不包括 p)到结尾分裂成 t[blockNum2],并返回 blockNum2
        if (blockNum1 == EMPTY) return EMPTY;
        if (p >= t[blockNum1].sz) return EMPTY;
        int blockNum2 = new_node();
        cpy(blockNum2, 1, t[blockNum1].data + p + 1, t[blockNum1].sz - p);
        t[blockNum2].sz = t[blockNum1].sz - p, t[blockNum1].sz = p;
        link(blockNum1, blockNum2), calc_sum(blockNum1), calc_sum(blockNum2);
        return blockNum2;
    }
    inline void merge(int blockNum1, int blockNum2) {
        cpy(blockNum1, t[blockNum1].sz + 1, t[blockNum2].data + 1, t[blockNum2].sz);
        t[blockNum1].nxt = t[blockNum2].nxt;
        t[blockNum1].sum += t[blockNum2].sum, t[blockNum1].sz += t[blockNum2].sz;
        del_node(blockNum2);
    }
    inline void maintain() {
        for (int blockNum = HEAD; blockNum != EMPTY; blockNum = t[blockNum].nxt) {
            while (t[blockNum].nxt != EMPTY && t[blockNum].sz + t[t[blockNum].nxt].sz <= BLOCKSIZE) {
                merge(blockNum, t[blockNum].nxt);
            }
        }
    }

    inline void ins(int p, int val) { // add val after position p
        int blockNum1, blockNum3;
        get_pos(p, blockNum1), split(blockNum1, p);
        t[ blockNum3 = new_node() ].sum = val, t[blockNum3].data[1] = val, t[blockNum3].sz = 1;
        link(blockNum1, blockNum3);
        maintain();
    }
    inline void del(int p) { // delete the p-th number
        int blockNum1, blockNum2, blockNum3;
        get_pos(p, blockNum1);
        if (p == t[blockNum1].sz) return t[blockNum1].sz--, calc_sum(blockNum1), void();
        blockNum2 = split(blockNum1, p - 1), blockNum3 = split(blockNum2, 1);
        t[blockNum1].nxt = blockNum3;
        del_node(blockNum2);
        maintain();
    }
    inline void modify(int p, int val) { // modify the p-th number's val
        int blockNum1, blockNum2;
        get_pos(p, blockNum1);
        if (p == t[blockNum1].sz) return t[blockNum1].data[p] = val, calc_sum(blockNum1), void();
        blockNum2 = split(blockNum1, p - 1), split(blockNum2, 1);
        t[blockNum2].data[1] = val, calc_sum(blockNum2);
        maintain();
    }
    ll query(int l, int r) { // query the sum from l to r
        int blockNum1, blockNum2, curBlock; ll ret = 0;
        get_pos(l, blockNum1), get_pos(r, blockNum2);
        if (blockNum1 == blockNum2) { rep(i, l, r) ret += t[blockNum1].data[i]; return ret; }
        for (curBlock = t[blockNum1].nxt; curBlock != EMPTY && curBlock != blockNum2; curBlock = t[curBlock].nxt) ret += t[curBlock].sum;
        rep(i, l, t[blockNum1].sz) ret += t[blockNum1].data[i]; rep(i, 1, r) ret += t[blockNum2].data[i];
        return ret;
    }
} blockList;

int n, p, tot;
char opt[10];

int main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
    #endif
    IO::read(n);
    rep(i, 1, n) {
        scanf("%s", opt + 1);
        p = min(p, tot), p = max(p, 0);
        if (opt[1] == 'I') {
            int x; IO::read(x);
            blockList.ins(p, x);
            ++p, ++tot;
        } else if (opt[1] == 'D') {
            blockList.del(p), --tot, --p;
        } else if (opt[1] == 'L') {
            --p;
        } else if (opt[1] == 'R') {
            ++p;
        } else if (opt[1] == 'Q') {
            int l, r; IO::read(l), IO::read(r);
            IO::write(blockList.query(l, r), '\n');
        } else if (opt[1] == 'C') {
            int pos, val; IO::read(pos), IO::read(val);
            blockList.modify(pos, val);
        }
    }
    return 0;
}

复盘与总结

45min 拍完了 T1,没啥问题。

50min 在厕所会了 T2。

66min 写完了 T2。

84min 拍完了 T2,拍出个小问题。改了后就拍过了。

90min ~ 110min 一直在看 T3,但是 读错题了,甚至怀疑样例的正确性,遂去写了 T4 60 分暴力。

150min 左右写完了暴力,但是发现 T4 20 分的部分分会 RE,看来自己还是不太熟悉迭代器啥的。

然后后面尝试修锅,修到了比赛结束 180min。

事实证明,对拍并花不了太多的时间。T1 T2 能快速的写出来并且拍出来是很好的,可惜 T3 读错题了,不然至少能再多个 30 分。

下次,如果觉得样例错了,一定是自己把题意理解错了或者手玩错了,不可能题错了,要再仔细读一读题。

仅有一条评论

  1. 您太强惹

None
上一篇 «
对 CSP-S T1 儒略日 的三份代码的分析与题解
» 下一篇