洛谷 P1335 / UOJ #123 - [NOI2013] 小Q的修炼（提交答案题）

本文主要是介绍洛谷 P1335 / UOJ #123 - [NOI2013] 小Q的修炼（提交答案题），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

洛谷题面传送门 & UOJ 题面传送门

一道相对来说难度较低的提答题。

首先碰到提答题我们肯定不能思考一般性解法，只能就事论事，对着对应的数据设计出相应的程序。纵观 10 组数据，我们可以获得一些的结论：

对于所有跳转事件，那些目标位置 \(<\) 当前位置的事件，都形如 i c 0 c 1 x 0，也就是如果 \(0<1\) 跳转到 \(x\)，否则跳转到 \(0\)，显然这种事件只能选择前者，也就是说本题的结构实际上是一个有限状态自动机，不会成环。
在第 \(2,3,7,8,9,10\) 中都出现了一个类似的结构，也就是一段 v 3 x1, v 4 x2, ..., v 12 x10 后跟一堆将变量 \(v_3,v_4,\cdots,v_{12}\) 累加到 \(v_1\) 上的操作，不难发现这可以视作，有若干个大礼包，每个大礼包可以选择或者不选择，如果选择则需要将 \(v_3,v_4,\cdots,v_{12}\) 都加上一个固定的值，隔一段时间以后令答案加上 \(\sum\limits_{i=3}^{12}|v_i|\)，我们称之为 A 结构。
在第 \(4,5,6,7,8,9,10\) 中也出现了一个类似的结构，也就是所有与 \(v_2\) 有关的操作，稍加分析可以发现这是一个背包模型，变量 \(2\) 的值就是剩余体积，即，有若干个大礼包，每个大礼包有两个三个属性 \(to_i,v_i,w_i\)，每进入一个礼包，如果剩余体积 \(<v_i\) 则直接转到 \(to_i\)，否则你可以选择到 \(i+1\)，并花费 \(w_i\) 的体积或者 \(v_i\) 的价值，也可以选择到 \(to_i\)。我们称之为 B 结构。

做出这些小观察后本题就容易许多了。

对于第一组数据，选择操作很少，直接爆搜即可。这里直接给出答案。

对于第二组数据，是一个有 25 个大礼包的 A 结构，同样直接 \(2^{25}\) 暴力即可。

const int MAXN = 3.5e5;
int n, m, pos[MAXN + 5][15];
int val[15];
struct number {
    int opt, id;
    void read() {
        static char str[5]; scanf("%s%d", str + 1, &id);
        opt = (str[1] == 'v');
    }
    int operator () () {return (opt) ? val[id] : id;}
};
struct qry {int opt, A, B; number C, D;} a[MAXN + 5];
int main() {
    freopen("train3.in", "r", stdin);
    freopen("train3.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        static char str[5]; scanf("%s", str + 1);
        if (str[1] == 'v') {
            static char op[5]; scanf("%d%s", &a[i].A, op + 1);
            a[i].B = (op[1] == '-'); // 0 for + and 1 for -
            a[i].C.read(); a[i].opt = 1;
        } else if (str[1] == 's') {
            scanf("%d%d", &a[i].A, &a[i].B);
            a[i].opt = 2;
        } else {
            a[i].C.read(); a[i].D.read();
            scanf("%d%d", &a[i].A, &a[i].B);
            a[i].opt = 3;
        }
    }
    vector<vector<int> > vec;
    for (int i = 1; i <= n; ) {
        if (a[i].opt == 2) {
            vector<int> tmp;
            for (int j = a[i].A; j < a[i].B; j++) tmp.pb(a[j].C());
            vec.pb(tmp); i = a[i].B;
        } else {
            ll mx = -1; int msk = -1;
            for (int j = 0; j < (1 << vec.size()); j++) {
                static ll ss[15]; fill0(ss);
                for (int k = 0; k < vec.size(); k++) if (j >> k & 1) {
                    for (int l = 0; l < vec[k].size(); l++)
                        ss[l] += vec[k][l];
                }
                ll sum = 0;
                for (int k = 0; k < 10; k++) sum += abs(ss[k]);
                if (sum > mx) mx = sum, msk = j;
            }
//          printf("! %lld %d %d\n", mx, msk, (int)vec.size());
            for (int j = 0; j < vec.size(); j++) {
                if (msk >> j & 1) puts("1");
                else puts("2");
            }
            vec.clear();
            i += 50;
        }
    }
    return 0;
}

对于第三组数据，相当于几百个 A 类结构，每个 A 类结构里有大概 \(10\) 个大礼包，对每个 A 类结构暴力求解加起来即可。

const int MAXN = 3.5e5;
int n, m, val[15];
struct number {
    int opt, id;
    void read() {
        static char str[5]; scanf("%s%d", str + 1, &id);
        opt = (str[1] == 'v');
    }
    int operator () () {return (opt) ? val[id] : id;}
};
struct qry {int opt, A, B; number C, D;} a[MAXN + 5];
int id[MAXN + 5], idcnt = 0, bel[MAXN + 5], nxt[MAXN + 5];
ll dp[2005][10005]; int to[2005][10005], cst[MAXN + 5], v[MAXN + 5];
vector<int> vec;
void work(int cur, int lft) {
    if (cur > idcnt) return;
    if (to[cur][lft]) vec.pb(1), work(cur + 1, lft - cst[cur + 1]);
    else {
        if (lft >= cst[cur + 1]) vec.pb(2);
        work(nxt[cur], lft);
    }
}
int main() {
    freopen("train6.in", "r", stdin);
    freopen("train6.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        static char str[5]; scanf("%s", str + 1);
        if (str[1] == 'v') {
            static char op[5]; scanf("%d%s", &a[i].A, op + 1);
            a[i].B = (op[1] == '-'); // 0 for + and 1 for -
            a[i].C.read(); a[i].opt = 1;
        } else if (str[1] == 's') {
            scanf("%d%d", &a[i].A, &a[i].B);
            a[i].opt = 2;
        } else {
            a[i].C.read(); a[i].D.read();
            scanf("%d%d", &a[i].A, &a[i].B);
            a[i].opt = 3;
        }
    }
    for (int i = 1; i <= n; i++) if (a[i].opt == 2) id[i] = ++idcnt;
    bel[n + 1] = idcnt + 1;
//  cerr << idcnt << endl;
    for (int i = n; i; i--) bel[i] = ((a[i].opt == 2) ? id[i] : bel[i + 1]);
    for (int i = 1; i <= n; i++) if (a[i].opt == 2) nxt[id[i]] = bel[a[i].B];
    for (int i = 4; i <= n; i++) if (a[i].opt == 1) {
        if (a[i].A == 2) cst[bel[i]] = a[i].C();
        else v[bel[i]] = a[i].C();
    }
    for (int i = idcnt; i; i--) for (int j = 0; j <= 10000; j++) {
        if (j < cst[i + 1]) dp[i][j] = dp[nxt[i]][j];
        else {
            if (dp[nxt[i]][j] < dp[i + 1][j - cst[i + 1]] + v[i + 1]) {
                dp[i][j] = dp[i + 1][j - cst[i + 1]] + v[i + 1];
                to[i][j] = 1;
            } else dp[i][j] = dp[nxt[i]][j];
        }
    }
    ll mx = 0; int mxp = -1;
    for (int i = 0; i <= 10000; i++) if (mx < dp[1][i]) mx = dp[1][i], mxp = i;
    work(1, mxp); cerr << mx << endl;
    for (int x : vec) printf("%d\n", x);
    return 0;
}

对于第四、五、六组数据，相当于一个 B 类结构，从后往左背包即可。

const int MAXN = 3.5e5;
int n, m, val[15];
struct number {
    int opt, id;
    void read() {
        static char str[5]; scanf("%s%d", str + 1, &id);
        opt = (str[1] == 'v');
    }
    int operator () () {return (opt) ? val[id] : id;}
};
struct qry {int opt, A, B; number C, D;} a[MAXN + 5];
int id[MAXN + 5], idcnt = 0, bel[MAXN + 5], nxt[MAXN + 5];
ll dp[2005][10005]; int to[2005][10005], cst[MAXN + 5], v[MAXN + 5];
vector<int> vec;
void work(int cur, int lft) {
    if (cur > idcnt) return;
    if (to[cur][lft]) vec.pb(1), work(cur + 1, lft - cst[cur + 1]);
    else {
        if (lft >= cst[cur + 1]) vec.pb(2);
        work(nxt[cur], lft);
    }
}
int main() {
    freopen("train6.in", "r", stdin);
    freopen("train6.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        static char str[5]; scanf("%s", str + 1);
        if (str[1] == 'v') {
            static char op[5]; scanf("%d%s", &a[i].A, op + 1);
            a[i].B = (op[1] == '-'); // 0 for + and 1 for -
            a[i].C.read(); a[i].opt = 1;
        } else if (str[1] == 's') {
            scanf("%d%d", &a[i].A, &a[i].B);
            a[i].opt = 2;
        } else {
            a[i].C.read(); a[i].D.read();
            scanf("%d%d", &a[i].A, &a[i].B);
            a[i].opt = 3;
        }
    }
    for (int i = 1; i <= n; i++) if (a[i].opt == 2) id[i] = ++idcnt;
    bel[n + 1] = idcnt + 1;
//  cerr << idcnt << endl;
    for (int i = n; i; i--) bel[i] = ((a[i].opt == 2) ? id[i] : bel[i + 1]);
    for (int i = 1; i <= n; i++) if (a[i].opt == 2) nxt[id[i]] = bel[a[i].B];
    for (int i = 4; i <= n; i++) if (a[i].opt == 1) {
        if (a[i].A == 2) cst[bel[i]] = a[i].C();
        else v[bel[i]] = a[i].C();
    }
    for (int i = idcnt; i; i--) for (int j = 0; j <= 10000; j++) {
        if (j < cst[i + 1]) dp[i][j] = dp[nxt[i]][j];
        else {
            if (dp[nxt[i]][j] < dp[i + 1][j - cst[i + 1]] + v[i + 1]) {
                dp[i][j] = dp[i + 1][j - cst[i + 1]] + v[i + 1];
                to[i][j] = 1;
            } else dp[i][j] = dp[nxt[i]][j];
        }
    }
    ll mx = 0; int mxp = -1;
    for (int i = 0; i <= 10000; i++) if (mx < dp[1][i]) mx = dp[1][i], mxp = i;
    work(1, mxp); cerr << mx << endl;
    for (int x : vec) printf("%d\n", x);
    return 0;
}

对于第七、八、九、十组数据，相当于一个 B 类结构，但 B 类结构每个礼包内部又是一个 A 类结构，同样道理，先对每个 A 类结构跑一遍第三组数据的求解方法找出其代价，然后再跑四、五、六即可。

const int MAXN = 3.6e5;
int n, m, val[15];
struct number {
    int opt, id;
    void read() {
        static char str[5]; scanf("%s%d", str + 1, &id);
        opt = (str[1] == 'v');
    }
    int operator () () {return (opt) ? val[id] : id;}
};
struct qry {int opt, A, B; number C, D;} a[MAXN + 5];
int id[MAXN + 5], idcnt = 0, bel[MAXN + 5], nxt[MAXN + 5];
ll dp[2005][10005]; int to[2005][10005];
ll cst[MAXN + 5], v[MAXN + 5];
vector<int> vec;
bool flg[MAXN + 5];
vector<vector<int> > tt[MAXN + 5];
int mskv[MAXN + 5];
void deal(int id) {
    for (int i = 0; i < tt[id].size(); i++)
        vec.pb((mskv[id] >> i & 1) ? 1 : 2);
}
void work(int cur, int lft) {
    if (cur > idcnt) return;
    if (to[cur][lft]) vec.pb(1), deal(cur + 1), work(cur + 1, lft - cst[cur + 1]);
    else {
        if (lft >= cst[cur + 1]) vec.pb(2);
        work(nxt[cur], lft);
    }
}
int main() {
    freopen("train10.in", "r", stdin);
    freopen("train10.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        static char str[5]; scanf("%s", str + 1);
        if (str[1] == 'v') {
            static char op[5]; scanf("%d%s", &a[i].A, op + 1);
            a[i].B = (op[1] == '-'); // 0 for + and 1 for -
            a[i].C.read(); a[i].opt = 1;
        } else if (str[1] == 's') {
            scanf("%d%d", &a[i].A, &a[i].B);
            a[i].opt = 2;
        } else {
            a[i].C.read(); a[i].D.read();
            scanf("%d%d", &a[i].A, &a[i].B);
            a[i].opt = 3;
        }
    }
    for (int i = 1; i <= n; i++) if (a[i].opt == 2) {
        flg[i] = 1;
        for (int j = 1; j <= 10; j++) flg[i] &= (a[i + j].opt == 1);
    } 
    for (int i = 1; i <= n; i++) if (a[i].opt == 2 && !flg[i]) id[i] = ++idcnt;
    bel[n + 1] = idcnt + 1;
//  for (int i = 1; i <= n; i++) cerr << id[i] << endl;
//  cerr << idcnt << endl;
    for (int i = n; i; i--) bel[i] = ((a[i].opt == 2 && !flg[i]) ? id[i] : bel[i + 1]);
    for (int i = 1; i <= n; i++) if (a[i].opt == 2 && !flg[i]) nxt[id[i]] = bel[a[i].B];
    for (int i = 1; i <= n; i++) if (a[i].opt == 2 && flg[i]) {
        vector<int> tmp;
        for (int j = 1; j <= 10; j++) tmp.pb(a[i + j].C());
        tt[bel[i]].pb(tmp);
    }
    for (int i = 4; i <= n; i++) if (a[i].opt == 1 && a[i].A == 2)
        cst[bel[i]] = a[i].C();
    for (int i = 1; i <= idcnt + 1; i++) {
        ll mx = -1; int msk = -1;
        for (int j = 0; j < (1 << tt[i].size()); j++) {
            static ll vals[15]; fill0(vals);
            for (int k = 0; k < tt[i].size(); k++) if (j >> k & 1)
                for (int l = 0; l < 10; l++) vals[l] += tt[i][k][l];
            ll ss = 0;
            for (int l = 0; l < 10; l++) ss += abs(vals[l]);
            if (ss > mx) mx = ss, msk = j;
        }
        v[i] = mx; mskv[i] = msk;
    }
    for (int i = 1; i <= idcnt; i++) cerr << v[i] << endl;
    for (int i = idcnt; i; i--) for (int j = 0; j <= 1000; j++) {
        if (j < cst[i + 1]) dp[i][j] = dp[nxt[i]][j];
        else {
            if (dp[nxt[i]][j] < dp[i + 1][j - cst[i + 1]] + v[i + 1]) {
                dp[i][j] = dp[i + 1][j - cst[i + 1]] + v[i + 1];
                to[i][j] = 1;
            } else dp[i][j] = dp[nxt[i]][j];
        }
    }
    ll mx = 0; int mxp = -1;
    for (int i = 0; i <= 1000; i++) if (mx < dp[1][i]) mx = dp[1][i], mxp = i;
    work(1, mxp); cerr << mx << endl;
    for (int x : vec) printf("%d\n", x);
    return 0;
}

这篇关于洛谷 P1335 / UOJ #123 - [NOI2013] 小Q的修炼（提交答案题）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

洛谷 P1335 / UOJ #123 - [NOI2013] 小Q的修炼（提交答案题）

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯