T1 扩淏

题目

给定了一个由 [ , ] , ( , ) 构成的序列,请添加最少的括号使得其变成一个括号序列。

\(n\le 100\)

Solution

显然的区间 \(\texttt{DP}\) 题。不过一种很巧妙的做法就是将 \(dp\) 数组内存储的信息由数字转换为一个字符串,具体下面提到。

设一个 string 类型的数组 \(f[i][j]\) 表示将原序列中 \([l,r]\) 部分用最少的括号补全后得到的字符串,不难发现,答案就存储在 \(f[1][n]\) 的位置。现在来讨论怎么转移。

按照区间长度从小到大枚举左右端点 \(i,j\),如果 \(i,j\) 两个位置上的括号刚好能匹配,那么有 \(f[i][j] = ‘(‘ + f[i+1][j-1] + ‘)’\)(此处就不分括号类型了,代码中注意就行)。然后枚举分割点 \(k\),如果将 \(f[i][k]\)\(f[k+1][j]\) 拼起来的长度比 \(f[i][j]\) 小,那么就用 \(f[i][k] + f[k+1][j]\) 去更新 \(f[i][j]\) 即可。

时间复杂度是 \(\mathcal O(n^3)\) 级别的。

#include<bits/stdc++.h>
using namespace std;
constexpr int _SIZE = 1e2;
char st[_SIZE + 5];
string f[_SIZE + 5][_SIZE + 5];
int n;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> (st + 1);
    n = strlen(st + 1);
    for (int i = 1; i <= n; i++) {
        if (st[i] == '(') f[i][i] = "()";
        if (st[i] == ')') f[i][i] = "()";
        if (st[i] == '[') f[i][i] = "[]";
        if (st[i] == ']') f[i][i] = "[]";
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1, j = len; j <= n; i++, j++) {
            if (st[i] == '(' && st[j] == ')') f[i][j] = '(' + f[i + 1][j - 1] + ')';
            if (st[i] == '[' && st[j] == ']') f[i][j] = '[' + f[i + 1][j - 1] + ']';
            for (int k = i; k < j; k++) {
                if (f[i][j].empty() || f[i][j].size() > f[i][k].size() + f[k + 1][j].size())
                    f[i][j] = f[i][k] + f[k + 1][j];
            }
        }
    }
    cout << f[1][n] << '\n';
    return 0;
}

T2 禤耙

题目

\(n\) 个人进行比赛,比赛分为很多轮,每轮选出 \([l,r]\) 中最强的人保留,其他人退出。
有一个人可以任意选择初始位置,求他最多赢几轮。

Solution

很好的一道数据结构题,细节也不算多。

可以将每场比赛影响的区间 \([l,r]\) 直接缩成一个点,用链表维护缩点后的序列,然后每次加入新比赛的时候用树状数组维护 \(l\) 的位置并在树状数组上倍增找到。缩点的时候,根据规则,可以计算出这个点中的最优的位置以及需要的最小的能力值,再开一个树状数组维护就行了。

#include<bits/stdc++.h>
#define lowbit(_) (_ & -_)
using namespace std;
constexpr int _SIZE = 1e6;
int n, m;
pair<int, int> A[_SIZE + 5], D[_SIZE + 5];
int pre[_SIZE + 5], nxt[_SIZE + 5];
void checkmax(pair<int, int> &x, pair<int, int> y) {x = max(x, y);} // pair取max
namespace BIT_Rank { // 查询排名
    int s[_SIZE + 5];
    void init() { // 初始化
        for (int i = 1; i <= n; i++) s[i] = lowbit(i);
    }
    void add(int x, int v) { // 单点加,用于实现删点操作
        for (; x <= n; x += lowbit(x)) s[x] += v;
    }
    int ask(int x) { // 倍增查询 x 的位置
        int res = 0;
        for (int i = 19; ~i; i--)
            if (res + (1 << i) <= n && x > s[res + (1 << i)])
                res += (1 << i), x -= s[res];
        return res + 1;
    }
}
namespace BIT_Value { // 查询答案
    pair<int,int> s[_SIZE + 5]; // key值表示最小能力值,first表示比赛轮数,second表示编号(为了与first的大小关系保持一致方便使用定义的 < 号,因此取了相反数)
    void init() { // 全部初始化为一个极小值
        for (int i = 1; i <= n; i++) s[i].first = -1;
    }
    void add(int x, pair<int, int> v) { // 对 x 进行更改,表示能力值为 x 的时候属性为 v
        for (; x <= n; x += lowbit(x)) checkmax(s[x], v);
    }
    auto ask(int x) { // 查询小于等于 x 的所有的 s
        pair<int, int> res = make_pair(0, -1);
        for (; x; x -= lowbit(x)) checkmax(res, s[x]);
        return res;
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    BIT_Rank::init(), BIT_Value::init(); // 别写了函数搞忘调用!!!初始化
    for (int i = 1; i < n; i++) cin >> A[i].second;
    for (int i = 1; i <= n; i++) {
        pre[i] = i - 1, nxt[i] = i + 1; // 链表
        D[i].second = -i; // 编号取负
    }
    nxt[0] = 1, pre[n + 1] = n;
    while (m--) {
        int opt; cin >> opt;
        if (opt == 1) {
            int l, r; cin >> l >> r;
            r = r - l + 1; // 转换为长度,因为链表不能用左右端点计算
            for (int p = l = BIT_Rank::ask(l); p = nxt[p], --r;) { // 先在树状数组上找到位置
                A[l].first = max({A[l].first, A[l].second, A[p].first}); // 将这个点的信息合并到最右边的端点上
                A[l].second = A[p].second; // second 内记录的是当前缩的点的最后一个位置的值
                D[l] = max(D[l], D[p]); // 取两边最大的比赛轮数
                nxt[pre[p]] = nxt[p], pre[nxt[p]] = pre[p]; // 链表上删去 p 点
                BIT_Rank::add(p, -1); // 在树状数组上删去 p 点
            }
            D[l].first++; // 当前比赛加入贡献
            BIT_Value::add(A[l].first, D[l]); // 计入到树状数组中
        } else {
            int x; cin >> x;
            cout << -BIT_Value::ask(x - 1).second << '\n'; // 小于 x 的能力值的最大轮数
        }
    }
    return 0;
}

T4 觞朲

题目

给定一棵树,每一个点有点权 \(a_i\),每一条边有边权 \(b_i\),第一次经过一个点可以获得 \(a_i\) 的钱,第一次经过一条边需要花费 \(b_i\) 的钱,任意时刻钱不能为负数。给定若干个不同的初始资金,问从 \(1\) 出发最多能赚到多少钱。
对于每一个前缀输出答案。

Solution

感觉像是一道树形 \(\texttt{DP}\) 的题,那就先按照树形 \(\texttt{DP}\) 的思路先试一下。

对每一个点维护一个 pair 集合,内部每个元素形如 \((x_i,y_i)\),表示如果初始有 \(x_i\) 的钱可以赚到 \(y_i\) 的钱。容易发现这个信息用可并堆很好维护以及合并,因此对每个点建一个小根堆。如果用 \(a_i\) 表示 \(i\) 的点权,\(b_i\) 表示 \(i\) 与父节点直接的连边,那么一个点的初始元素就是 \((b_i,a_i-b_i)\),因为可能这个元素并不会是最终的,所以需要做一些变化。

  • 如果 \(a_i-b_i<0\),那么表示进来就会亏钱,所以就需要取出堆中的元素来尝试赚钱。

  • 如果堆中存在 \(x<b_i\),那么这个元素就是不合法的,也需要取出堆中的元素合并。

合并的方式:\((a,b),(c,d) \rightarrow (\max(a,c-b),b+d)\)

对于询问,可以先将询问离线,然后按照 \(x\) 从小到大排序,这样每个询问在堆中的位置都是逐渐向下的,因此可以逐个计算。

#include<bits/stdc++.h>
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
#define int long long
using namespace std;
template<typename T> void read(T &k)
{
	k=0;T flag=1;char b=getchar();
	while (!isdigit(b)) {flag=(b=='-')?-1:1;b=getchar();}
	while (isdigit(b)) {k=k*10+b-48;b=getchar();}
	k*=flag;
}
template<typename T> void write(T k) {if (k<0) {putchar('-'),write(-k);return;}if (k>9) write(k/10);putchar(k%10+48);}
template<typename T> void writewith(T k,char c) {write(k);putchar(c);}
constexpr int _SIZE = 1e6;
int n, m, a[_SIZE + 5];
struct EDGE{
    int nxt, to, l;
}edge[(_SIZE << 1) + 5];
int tot, head[_SIZE + 5];
void checkmax(auto &x, auto y) {x = max(x, y);}
void AddEdge(int x, int y, int l) {
    edge[++tot] = {head[x], y, l};
    head[x] = tot;
}
int ls[_SIZE + 5], rs[_SIZE + 5], dis[_SIZE + 5];
pair<int, int> val[_SIZE + 5];
void balance(int x) { // 左偏树
    if (dis[ls[x]] < dis[rs[x]]) swap(ls[x], rs[x]);
    dis[x] = dis[ls[x]] + 1;
}
int merge(int x, int y) {
    if (!x || !y) return x | y;
    if (val[x] > val[y]) swap(x, y);
    rs[x] = merge(rs[x], y), balance(x);
    return x;
}
int pop(int x) {return merge(ls[x], rs[x]);}
int dfs(int x, int fa, int from) {
    int rt = 0;
    for (int i = head[x]; i; i = edge[i].nxt) {
        int twd = edge[i].to;
        if (twd == fa) continue;
        rt = merge(rt, dfs(twd, x, edge[i].l));
    }
    val[x] = make_pair(from, a[x] - from); dis[x] = 1;
    while (rt && (val[x].second < 0 || val[rt].first < val[x].first)) {
        checkmax(val[x].first, val[rt].first - val[x].second);
        val[x].second += val[rt].second;
        rt = pop(rt);
    }
    if (val[x].second > 0) rt = merge(x, rt);
    return rt;
}
pair<int, int> que[_SIZE + 5];
long long ans[_SIZE + 5];
signed main() {
    read(n); read(m);
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 1; i < n; i++) {
        int u, v, l;
        read(u), read(v), read(l);
        AddEdge(u, v, l), AddEdge(v, u, l);
    }
    int rt = dfs(1, 0, 0);
    for (int i = 1; i <= m; i++) {
        read(que[i].first);
        que[i].second = i;
    }
    sort(que + 1, que + m + 1); // 询问离线 + 排序
    long long s = 0;
    for (int i = 1; i <= m; i++) {
        s += que[i].first - que[i - 1].first;
        while (rt && val[rt].first <= s) s += val[rt].second, rt = pop(rt);
        ans[que[i].second] =s;
    }
    for (int i = 1; i <= m; i++) writewith(ans[i], '\n');
    return 0;
}

原文地址:http://www.cnblogs.com/hanx16msgr/p/16826057.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性