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

xnmzyz · 2025-04-29 17:25:40 · 题解

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

题意简述

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

解题思路

• 交易类型：

  • 若 B = -1（无找零），则 i 和 j 的价格差必须为 A，即 p_j - p_i = A。
  • 若 B \neq -1（有找零），找零使用面额 \ge B = 2^k 的货币，实际净支付 D 满足 D \equiv A \pmod{2^k}，即 p_j - p_i \equiv A \pmod{2^k}。

• 并查集：

  • 用于维护农民之间的连通性及相对价格差。
  • 有找零交易：使用模 2^k 的并查集，记录模意义下的差值。
  • 无找零交易：使用并查集，记录实际差值。

• 位运算分解：

  • 对于有找零交易，逐步检查模 2^j（j 从 1 到 16）下的约束，确保一致性。

具体步骤

1. 初始化：

   • 将所有交易分为两类：有找零（B \neq -1）和无找零（B = -1）。
   • 使用两个并查集分别处理。

2. 处理有找零交易：

   • 对于 j 从 1 到 16，设置模数 base = 2^j - 1。
   • 对每条交易 (i, j, A, B)，若 B \le 2^{j-1}，检查 p_j - p_i \equiv A \pmod{2^j} 是否与已有关系一致。
   • 若发现矛盾，标记该交易不一致。

3. 处理无找零交易：

   • 对每条交易 (i, j, A, -1)，检查 p_j - p_i = A 是否成立。
   • 若与已有差值矛盾，标记不一致。

4. 输出：

   • 对于每条交易，输出 1（一致）或 0（不一致）。

主要代码

码风稀烂，勿喷

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');
}

时间复杂度