专栏文章

题解：P12358 [eJOI 2024] 奶酪交易 / Cheese

xxnmzyz
P12358题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipgkwcx
此快照首次捕获于
2025/12/03 11:39
3 个月前
此快照最后确认于
2025/12/03 11:39
3 个月前
查看原文

题解：P12358 [eJOI 2024] 奶酪交易 / Cheese

题意简述

  • 给定 NN 个农民和 MM 次交易记录。
  • 每次交易记录包含四个参数：i,j,A,Bi, j, A, B，表示农民 ii 和 jj 进行了交易，ii 支付了 AA 块钱，且找零的最小面额为 BB（若 B=−1B = -1，则无找零）。
  • 货币面额为 22 的幂次：1,2,4,8,…1, 2, 4, 8, \dots。
  • 判断每次交易记录是否与之前的记录一致，输出 11（一致）或 00（不一致）。
  • 数据范围：1≤N,M≤5×1051 \le N, M \le 5 \times 10^5，0≤A≤1090 \le A \le 10^9，−1≤B<216-1 \le B < 2^{16}。

解题思路

  • 交易类型：
    • 若 B=−1B = -1（无找零），则 ii 和 jj 的价格差必须为 AA，即 pj−pi=Ap_j - p_i = A。
    • 若 B≠−1B \neq -1（有找零），找零使用面额 ≥B=2k\ge B = 2^k 的货币，实际净支付 DD 满足 D≡A(mod2k)D \equiv A \pmod{2^k}，即 pj−pi≡A(mod2k)p_j - p_i \equiv A \pmod{2^k}。
  • 并查集：
    • 用于维护农民之间的连通性及相对价格差。
    • 有找零交易：使用模 2k2^k 的并查集，记录模意义下的差值。
    • 无找零交易：使用并查集，记录实际差值。
  • 位运算分解：
    • 对于有找零交易，逐步检查模 2j2^j（jj 从 11 到 1616）下的约束，确保一致性。

具体步骤

  1. 初始化：
    • 将所有交易分为两类：有找零（B≠−1B \neq -1）和无找零（B=−1B = -1）。
    • 使用两个并查集分别处理。
  2. 处理有找零交易：
    • 对于 jj 从 11 到 1616，设置模数 base=2j−1base = 2^j - 1。
    • 对每条交易 (i,j,A,B)(i, j, A, B)，若 B≤2j−1B \le 2^{j-1}，检查 pj−pi≡A(mod2j)p_j - p_i \equiv A \pmod{2^j} 是否与已有关系一致。
    • 若发现矛盾，标记该交易不一致。
  3. 处理无找零交易：
    • 对每条交易 (i,j,A,−1)(i, j, A, -1)，检查 pj−pi=Ap_j - p_i = A 是否成立。
    • 若与已有差值矛盾，标记不一致。
  4. 输出：
    • 对于每条交易，输出 11（一致）或 00（不一致）。

主要代码

码风稀烂，勿喷
CPP
const int MAXN=5e5+5;
const int K=16;     //最大模数位数
int n,m,base;
int p[MAXN],s[MAXN],w[MAXN],e1[MAXN][4],e2[MAXN][3];
//  父节点   大小    模差值  所有交易     无找零交易
LL w2[MAXN];
bitset<MAXN> ans;

// 有找零交易并查集
int getp(int x) {
    if (p[x] != x) 
        getp(p[x]),w[x]+=w[p[x]],w[x]&=base,p[x]=p[p[x]];
    return p[x];
}
// 合并有找零交易
int uni(int a, int b, int c) {
    getp(a),getp(b);
    c += w[b] + base + 1 - w[a],c &= base;// 计算合并后的差值
    a = p[a]; b = p[b];
    if (a == b) return c;// 已连通，检查差值是否为 0
    if (s[a] > s[b]) {
        swap(a, b);
        c = (base + 1 - c) & base;// 调整方向
    }
    p[a] = b;
    w[a] = c;
    s[b] += s[a];
    return 0;
}

// 无找零交易并查集
int getp2(int x) {
    if (p[x] != x) {
        getp2(p[x]);
        w2[x]+=w2[p[x]];
        p[x]=p[p[x]];
    }
    return p[x];
}
// 合并无找零交易
int uni2(int a, int b, LL c) {
    getp2(a), getp2(b);
    c+=w2[b]-w2[a],
    a=p[a],
    b=p[b];
    if (a == b)
        return (c != 0ll);
    if (s[a] > s[b]) 
        swap(a, b),
        c = -c;
    p[a] = b,
    w2[a] = c,
    s[b] += s[a];
    return 0;
}
void Main() {
    read(n),read(m);
    For(i, 0, m - 1) {
        int a,b,c,d;//i,j,A,B具体见题目描述
        read(a),read(b),read(c),read(d);
        e1[i][0]=a-1;//改为0-index
        e1[i][1]=b-1;
        e1[i][2]=c;
        e1[i][3]=(d==-1)?(1<<18):d;
        if (d == -1) {
            e2[i][0]=a-1;
            e2[i][1]=b-1;
            e2[i][2]=c;
        }
        else
            e2[i][0]=-1;// 标记非无找零交易
    }
    // 处理有找零交易
    For(j,0,K-1) {
        For(i, 0, n - 1) 
            s[i]=1,
            p[i]=i,
            w[i]=0;
        base |= (1 << j);// 逐步增加模数
        For(i, 0, m - 1) {
            if (ans[i] || e1[i][3] == 1) continue;
            if (uni(e1[i][0], e1[i][1], e1[i][2] & base))
                ans[i] = 1;
            e1[i][3] >>= 1;// 更新约束
        }
    }
    // 处理无找零交易
    For(i,0,n-1) 
        s[i]=1,
        p[i]=i,
        w2[i]=0;
    For(i,0,m-1){
        if (ans[i] || e2[i][0] == -1) continue;
        if (uni2(e2[i][0], e2[i][1], e2[i][2]))
            ans[i] = 1;
    }
    For(i, 0, m - 1) 
        putchar(!ans[i]+'0'),
        putchar('\n');
}

时间复杂度

O(MKα(N))O(MK\alpha(N))，其中 K=16K = 16，α(N)\alpha(N) 为并查集单次操作复杂度，可视为常数。可通过该题。
record
参考文献：eJOI官方题解

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...