NOIP模拟好题题解(三)

前言

考了那么多试..几乎每次都由不如意的地方…
今天又看错题+哈希种子爆炸, 感觉在这样怕是要退役了啊…

吃芝麻

有A和B两人, 一开始A有a颗芝麻, B有b颗芝麻。
接下来两个人进行K轮操作, 如果a大于b, 那么B会从A手中拿走b颗芝麻, 否然A从B手中拿走a颗芝麻。
问操作结束后min(a, b)的值。
[latex]a, b, K \le 10^9 [/latex]

解题报告

智商题…从来没想过取模。
在数轴上割补以下, 就发现原问题和以下公式是等价的:
[latex] min(a^K \pmod{a+b}, b^K \pmod{a+b}) [/latex]
然后快速幂就好了QAQ, 考试时想了一个半小时没想出来…

[BZOJ 2054]疯狂的馒头

N ≤ 10^6,M ≤ 10^7

解题报告

首先颜色从大到小涂就可以忽略覆盖问题。
考虑用链表维护馒头, 链表暴力涂色后删除的均摊复杂度是线性的, 但是不能快速看某个馒头后面第一个没有涂色的馒头是哪一个。
用并查集代替链表, 每次涂色用并查集向后合并, 那么查询某个位置第一个没涂色的馒头可以直接用root(p), 就变成线性的了。
核心代码(对区间[l, r]涂上颜色i):

if(l > r) swap(l, r);
l = root(l), r = root(r);
while(l != r) {
    if(!ans[l]) ans[l] = i;
    int x = root(l+1);
    fa[l] = x;
    l = x;
}

SURVIVE

Elaine太强辣! 居然自己想出这种难度的题(虽然已经有过这个脑洞了)!
给一条长度为N的数字长链，这条链上有些数字是相同的，有些地方是不同的，求数链有多少种可能。
数链不能有前导0, 对数链有M个要求, 第i个要求数链[a, b]区间和[c, d]区间相同。

解题报告

首先, 我们可以NM暴力用并查集处理出那些位置上的数字是相同的, 因为不能有前导0, 那么答案就等于9×10^(数字种类数-1)。
怎么优化并查集呢? 考试时就愉悦地在这里卡了2h+
我们可以像st表一样开出logN个并查集, 第i层的并查集中, 如果a和b在同一个集合内, 那么表示区间[a, a+(1<<i))和区间[b, b+(1<<i))是相同的, 那么处理M个要求时就可以像在线段树上打标记一样维护这个东东了。
最后统计答案时在st表上下传, 然后扫一遍统计即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MOD = 1000000007;
const int MAXN = 100010;
int plog[MAXN];
namespace UFS {
    int mem[19][MAXN];
    int * fa;
    int root (int u) {return fa[u] ? fa[u] = root(fa[u]) : u;}
    void merge (int a, int b, int k) {
        fa = mem[k];
        int ra = root(a), rb = root(b);
        if(ra == rb) return ;
        fa[ra] = rb;
    }
    int findRoot (int a, int k) {
        fa = mem[k];
        return root(a);
    }
}
inline int advPow (int a, int b) {
    int ret = 1;
    while(b) {
        if(b & 1) ret = (LL)ret*a%MOD;
        a = (LL)a*a%MOD;
        b >>= 1;
    }
    return ret;
}
bool vis[MAXN];
int main () {
    int N, M;
    scanf("%d%d", &N, &M);
    for(int i = 1; (1<<i)<=N; i++)
        plog[1<<i] = i;
    for(int i = 1; i<=N; i++)
        plog[i] = max(plog[i-1], plog[i]);
    for(int i = 1; i<=M; i++) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        while(a <= b) {
            int l = plog[b-a+1];
            UFS :: merge (a, c, l);
            a += (1<<l), c += (1<<l);
        }
    }
    for(int i = plog[N]; i; i--) {
        for(int j = 1; j<=N-(1<<i)+1; j++) {
            int rt = UFS :: findRoot(j, i);
            UFS :: merge(j, rt, i-1);
            UFS :: merge(j+(1<<(i-1)), rt+(1<<(i-1)), i-1);
        }
    }
    int cnt = 0;
    for(int i = 1; i<=N; i++) {
        int p = UFS :: findRoot(i, 0);
        if(vis[p]) continue ;
        vis[p] = true, cnt++;
    }
    printf("%d\n", (int)(9LL*advPow(10, cnt-1)%MOD));
}