题解：P12209 [蓝桥杯 2023 国 Python B] 交易账本

· · 题解

P12209 题解

思路

记交易编号为 i 的第 j 个输出为 d_{i,j}，其是否被使用过为 g_{i,j}。

每一次处理输入的时候，如果 fromTxId（下文称 id）和 fromTxOutNumber（下文称 num） 均为 -1，则标记 flag 为 1，表示出现特殊交易，否则的话，如果 id<i 即引用的输出必须在此之前并且 g_{id,num} 为 0 即还未用过，则将 d_{id,num} 加入 add 中，并将 g_{id,num} 标为 1，如果至此还不能成为合法输入，则标记为不合法。

至此，如果合法，那么来处理交易输出，读入用户的 account 压根没用，读入 val，则从 add 中减去 val，并将 d_{i,j} 设置为 val。

处理完输出，如果已经 flag 为 1 即存在特殊交易，则无需判定无解，如果 add 不是等于 0，则无解。

代码

const int N=105;
const int M=1005;

int T,n,m;
int d[M][N];
bool g[M][N];

int main() {
    read(T);
    while (T--) {
        memset(d,0,sizeof(d));
        memset(g,0,sizeof(g));
        read(n),read(m);
        bool yes=true;
        _rep(i,0,m-1) {
            int inc;
            read(inc);
            bool flag=false;
            bool ok=true;
            int add=0;
            _rep(j,0,inc-1) {
                int id,num;
                read(id),read(num);
                if (!~id && !~num) flag=true;
                else if (id<i && !g[id][num]) add+=d[id][num],g[id][num]=true;
                else ok=false;
            }
            if (!ok) yes=false;
            int ouc;
            read(ouc);
            _rep(j,0,ouc-1) {
                int acc,val;
                read(acc),read(val);
                add-=val,d[i][j]=val;
            }
            if (flag) continue;
            if (add!=0) yes=false;
        }
        if (yes) puts("YES");
        else puts("NO");
    }
    return 0;
}