zoj 3510 – Boring Assignment Expressions

这道题事实上搞起来是比较复杂。

题目描述:

  1. 给出一堆赋值语句,可以把一个算式赋值给一个变量。
  2. 算式可以由常数或者其他变量计算出。
  3. 所有变量及常数值均为正数,运算只有 + 和 *。
  4. 要挑选出这堆赋值语句中的一些并排序,确保所有提到的变量都被赋值,而且最后的值之和最小。

是不是很复杂?首先要解决的砖块代码就是做中缀表达式的展开,这里没有多少难的算法含量,具体看代码的 eval 函数。

关键是这一切从何处开始?下面我们先推导几个定理:

定理 1:

一个算式的左值一定大于或等于右值中出现的任意一个变量或者常数。

证明: 很明显,由于所有的符号均为正整数,并且运算符只有加法和乘法,因此这明显是成立的。

定理 2:

可以将结果集的算式按照算式值从小到大排序,而不影响算式集变量的取值。

证明: 从定理 1 可以看出,如果有一条算式 B 依赖于算式 A 左值的变量,那么算式 B 的值必然大于或等于算式 A,这实际上形成了一个偏序关系。那么总可以有一种方法,将结果集的算式从小到大排序。

定理 3:

在最终选取的结果集中,每个变量只被赋值一次,而且所获得的值就是最后的终值。

证明: 使用反证法,现将结果集按照定理 2 进行排序,如果有超过一条算式赋值给同一个变量,那么后面的一条的算式的值一定大于等于前面一条算式,那么尽可以将其忽略。

定理 4:

可以构造一张图,每一个变量及其生效的赋值算式为顶点,其依赖关系为一条有向边,那么最后形成的图一定是一个 DAG,算式的排列等同于一个拓扑排序。所有右值为常数的算式作为图的源节点。

突然发现证明好不严谨,但是这样就可以用 dijkstra 最短路的方式去计算所有变量了。

具体的实现:

数据结构定义:

  1. 用数组存下所有算式(vexp),以及算式的左值变量名(vvar);
  2. 做两个 map,记录变量名对应的值(vals),以及变量名对应的生成表达式(expr);
  3. 记录所有算式还没有获得值的前继变量集合(vreq);
  4. 记录所有变量对应的表达式编号(vidx),也就是说,如果一个变量 A 出现在第 1,3,5 条算式(编号为 vexp 和 vvar 的序号)的右值中,那么 vidx[“A”] = {1, 3, 5};
  5. 一个优先队列 q,用变量的取值作为 key,对应的算是序号作为 val。

算法流程:

  1. 初始化:遍历所有的算式 vexp,如果 vexp 的右值为常数,那么将该算式放入 q,否则,生成所有该条算式的前继集合 vreq,并且在 vidx 中加入左值变量名对应的算式序号映射,同时,对所有发现的变量名注册一个初值为 0(这样我们就知道一共出现了哪些变量)。
  2. 逐个从 q 中弹出算式,如果其左值已经有值,舍弃之,如果没有,记录变量值以及其算式,加到结果集中。
  3. 每次得到一个新的变量(X)的值,遍历其 vidx,获取算式序号 idx,然后从每个 vreq[idx] 集合中删除 X,如果该 idx 的算式 vreq 已经清空,说明其所有前继的值已经就绪,计算该条算式的值,并且将其放入优先队列 q。
  4. 执行以上操作直到优先队列 q 为空。
  5. 检查结果,如果所有变量的值 vals 都不为 0,而且途中没有发生溢出,那么输出结果集,否则,输出错误。
// http://acm.zju.edu.cn/onlinejudge/showSubmission.do?submissionId=3768689
// 3485088 2013-12-02 23:49:33 Accepted 3510 C++ 160 2956 呆滞的慢板

#include <map>
#include <set>
#include <vector>
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;

typedef unsigned long long i64;


// contains all the expressions.
vector<string> vexp;

// contains all the variable of each expressions.
vector<string> vvar;

// mapping variables to their values.
map<string, i64> vals;

// mapping variables to their expressions.
map<string, string> expr;


// contains the expressions requirement strings.
vector<set<string> > vreq;

// mapping variables to vexp indexs which requires the variables.
map<string, vector<int> > vidx;

// priority queue to index.
multimap<i64, int> q;

// result index order.
bool broken;
i64 ans;
vector<int> result;


// evaluates an expression.
i64 eval(string s) {

    vector<i64> vv(0);
    vector<char> op(0);

    istringstream iss(s);
    string buf;

    while(iss >> buf) {

        if(buf == "(") continue;
        else if(buf == "+") op.push_back('+');
        else if(buf == "*") op.push_back('*');
        else if(isdigit(buf[0])) vv.push_back(atoi(buf.c_str()));
        else if(isalpha(buf[0])) vv.push_back(vals[buf]);
        else if(buf == ")") {

            i64 x = vv.back();
            vv.pop_back();
            i64 y = vv.back();

            // + case
            if(op.back() == '+') {
                vv.back() += x;
                // BROKEN: If add overflow, result will less than both.
                if(vv.back() < x || vv.back() < y) return 0;
            }
            // * case
            else if(op.back() == '*') {
                vv.back() *= x;
                // BROKEN: If mutiply overflow, division cannot recover.
                if(vv.back() / x != y) return 0;
            }

            op.pop_back();

        }
        else {
            // Unexpected case, throw OLE.
            while(1) cout << "OLE!";
        }
    }

    return vv.back();

}




int main() {

    int n;

    while(cin >> n >> ws) {

        // reset.
        vexp.clear();
        vvar.clear();

        vals.clear();
        expr.clear();

        vreq.assign(n, set<string>());
        vidx.clear();

        q.clear();

        broken = false;
        ans = 0;
        result.clear();


        // input and calculation.
        for(int i = 0; i < n; ++i) {

            //cout << "i = " << i << endl;

            string s;
            getline(cin, s);
            int p = s.find(' ');

            vvar.push_back(s.substr(0, p));
            vexp.push_back(s.substr(p + 3));

            //cout << "vvar = |" << vvar[i] << "|" << endl;
            //cout << "vexp = |" << vexp[i] << "|" << endl;


            // scratch all the reference variables.
            // add sentienl to split.
            istringstream iss(vexp.back());
            string v;

            while(iss >> v) {

                // if variable gotcha.
                if(isalpha(v[0])) {

                    // initialize variable list
                    vals[v] = 0;
                    expr[v] = "";

                    // add requirement link
                    vreq[i].insert(v);

                    // add index link, AVOID repeatly link.
                    if(vidx[v].size() == 0 || vidx[v].back() != i) { 
                        vidx[v].push_back(i);
                    }
                }

            }

            // if the value is clear.
            if(vreq[i].size() == 0) {

                i64 val = eval(vexp.back());

                q.insert(make_pair(val, i));

            }

        }

        // proccess
        while(!q.empty()) {

            // pop from priority queue.
            i64 val = q.begin()->first;
            int i = q.begin()->second;
            q.erase(q.begin());

            // get var.
            string v = vvar[i];

            if(vals[v] == 0) {

                result.push_back(i);

                vals[v] = val;
                expr[v] = vexp[i];

                for(int j = 0; j < vidx[v].size(); ++j) {

                    int k = vidx[v][j];

                    // kick the link.
                    vreq[k].erase(v);

                    // if all requirement was calculated.
                    if(vreq[k].empty()) {

                        i64 val = eval(vexp[k]);

                        if(val != 0) q.insert(make_pair(val, k));

                    }
                }

            }

        }


        // reduce..
        if(result.size() < vals.size()) broken = true;

        for(map<string, i64>::iterator it = vals.begin(); it != vals.end(); ++it) {

            // if overflow
            if(ans + it->second < ans) {
                broken = true;
                break;
            }

            ans += it->second;

        }

        if(broken) {
            cout << "stupid expressions!" << endl;
        }
        else {
            cout << ans << endl;
            for(int i = 0; i < result.size(); ++i) {
                int j = result[i];
                cout << vvar[j] << " = " << vexp[j] << endl;
            }
        }

    }

    return 0;

}

【转载请附】愿以此功德,回向 >>

原文链接:http://www.huangwenchao.com.cn/2013/12/zoj3510.html【zoj 3510 – Boring Assignment Expressions】

发表评论

电子邮件地址不会被公开。 必填项已用*标注