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