[关闭]
@RabbitHu 2017-09-10T08:28:46.000000Z 字数 3543 阅读 1935

一份题解

作业

T1 括号匹配

给你一个长度为 n 的括弧序列和 m 组询问，每次询问区间[l,r]中最长合法括号子序列 合法括号序列定义如下:
1. 空序列是合法括号序列。
2. 若 S 是合法括号序列则"(S)"是合法括号序列。
3. 若 S1、S2 是合法括号序列，则"S1S2"是合法括号序列 括弧序列定义如下: 由“(”和“)”组成的序列。

离线，将询问按右端点排序，从左往右处理括号序列，左括号则入栈，右括号则匹配一个左括号，被匹配的左括号在一个数组中对应的位置 + 1。

如果当前处理到的位置是某个询问区间的右端点，则这个询问的答案是询问区间的区间和。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <iostream>
  5. #include <cstring>
  6. using namespace std;
  7. int read(){
  8.     char c;
  9.     bool op = 0;
  10.     while((c = getchar()) < '0' || c > '9')
  11.     if(c == '-') op = 1;
  12.     int ret = c - '0';
  13.     while((c = getchar()) >= '0' && c <= '9')
  14.     ret = ret * 10 + c - '0';
  15.     return op ? -ret : ret;
  16. }
  17. void write(int x){
  18.     if(x < 0) putchar('-'), x = -x;
  19.     if(x >= 10) write(x / 10);
  20.     putchar('0' + x % 10);
  21. }
  22. const int N = 400005, M = 200005;
  23. int n, m;
  24. char s[N];
  25. int stk[N], top, tree[N], ans[M];
  26. struct query {
  27.     int id, l, r;
  28.     bool operator < (const query &b) const {
  29.     return r < b.r;
  30.     }
  31. } q[M];
  32. void add(int p){
  33.     while(p <= n) tree[p] ++, p += p & -p;
  34. }
  35. int ask(int p){
  36.     int ret = 0;
  37.     while(p) ret += tree[p], p -= p & -p;
  38.     return ret;
  39. }
  40. int main(){
  41.     n = read(), m = read();
  42.     scanf("%s", s + 1);
  43.     for(int i = 1; i <= m; i++)
  44.     q[i].id = i, q[i].l = read(), q[i].r = read();
  45.     sort(q + 1, q + m + 1);
  46.     for(int i = 1, pos = 1; i <= n; i++){
  47.     if(s[i] == '(') stk[++top] = i;
  48.     else if(top) add(stk[top--]);
  49.     while(i == q[pos].r)
  50.         ans[q[pos].id] = ask(i) - ask(q[pos].l - 1), pos++;
  51.     }
  52.     for(int i = 1; i <= m; i++)
  53.     write(ans[i] << 1), putchar('\n');
  54.     return 0;
  55. }

T2 遗迹保卫战

有n个英雄等待复活，英雄复活需要在复活神坛支付一定金额才能复活。复活神坛一共
有 m 种方法复活英雄，每种方法需要支付 ai 金复活，由于复活需要支付大量法力值，所以 一种复活方法只能使用一次。
每个英雄都有 bi 非奖励金额和奖励金额 ki。由于奖励金额只能用于复活，所以英雄们 尽可能少用非奖励金额复活。为了守住高地，现在需要你用最快的时间算出最多能让多少个 英雄复活，并在复活英雄人数最多的前提下，保证花费非奖励金额最少。

考试的时候 我根本没看懂这道题的题面！

实际上这道题是贪心，先贪心求出能复活多少人，之后再对于每一个复活方式，复活能复活的人中奖励金额最多的人。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <iostream>
  5. #include <cstring>
  6. #include <queue>
  7. using namespace std;
  8. typedef long long ll;
  9. int read(){
  10.     char c;
  11.     bool op = 0;
  12.     while((c = getchar()) < '0' || c > '9')
  13.     if(c == '-') op = 1;
  14.     int ret = c - '0';
  15.     while((c = getchar()) >= '0' && c <= '9')
  16.     ret = ret * 10 + c - '0';
  17.     return op ? -ret : ret;
  18. }
  19. const int N = 200005;
  20. int n, m, p[N], ans;
  21. ll tot;
  22. struct hero {
  23.     int a, b, s;
  24.     bool operator < (const hero &obj) const{
  25.         return b < obj.b;
  26.     }
  27. } h[N];
  28. priority_queue <hero> q;
  29. bool cmp(const hero &x, const hero &y){
  30.     return x.s < y.s;
  31. }
  32. int main(){
  33.     n = read(), m = read();
  34.     for(int i = 1; i <= n; i++)
  35.         h[i].a = read();
  36.     for(int i = 1; i <= n; i++)
  37.         h[i].b = read(), h[i].s = h[i].a + h[i].b;
  38.     for(int i = 1; i <= m; i++)
  39.         p[i] = read();
  40.     sort(p + 1, p + m + 1);
  41.     sort(h + 1, h + n + 1, cmp);
  42.     int i, j;
  43.     for(i = n, j = m; i > 0 && j > 0; i--, j--){
  44.         while(j > 0 && h[i].s < p[j]) j--;
  45.         if(j == 0) break;
  46.     }
  47.     ans = n - i;
  48.     for(i = n, j = ans; j > 0; j--){
  49.         while(i && h[i].s >= p[j]) q.push(h[i]), i--;
  50.         tot += max(0, p[j] - q.top().b);
  51.         q.pop();
  52.     }
  53.     printf("%d %lld\n", ans, tot);
  54.     return 0;
  55. }

T3 符文

小 Q 要在一个长度为 s 的火球符文串中学习火球术，他希望学习一个等级高的火球术，
定义火球术的等级 fire(s,p)表示火球符文串 s 中最多有多少个互不重叠的子串 p(p 是强 化符文)。
小 Q 发现如果直接学习火球符文串的话火球术等级会十分低，所以小 Q 决定在火球符文 串的任意位置删除任意个符文，使得新的火球符文串能学习到的火球术等级尽量高。 但是小 Q 希望训练你的奥术能力，于是你需要算出在删除 i 个(0<=i<=|s|)符文
后,fire(ss,p)的答案【ss 表示删除 i 个符文后的火球符文串】。

考试的时候这道题我是这样做的：

  1. 写个暴力;
  2. 写个对拍脚本;
  3. 写个“正解”;
  4. while(对拍出错)
  5.     稍作修改;
  6. 完成;

后来对拍打印了一整页的AC后我就当这道题写完了……

思路大概是这样的：f[i][j]表示到i为止最多删除j个字符能得到的最大连续子串数，g[i]表示i前面找到的第一个能做成连续子串的左侧字符位置 - 1，del[i]为形成g[i]子串需要删掉多少字符。
然后……转移一下？

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <iostream>
  5. #include <cstring>
  6. #define INF 0x3f3f3f3f
  7. using namespace std;
  9. const int N = 4005, S = 23, M = 4003;
  10. int n, m;
  11. char s[N], p[N];
  13. int f[M][M], g[M], del[M], ans2[M];
  14. void solve2(){
  15.     for(int i = n; i; i--){ // O(n ^ 2)
  16.     int x = i, y = m;
  17.     while(x && y){
  18.         while(x && s[x] != p[y]) x--;
  19.         if(s[x] == p[y]) x--, y--;
  20.     }
  21.     g[i] = x;
  22.     if(y) del[i] = INF;
  23.     else{
  24.         x++, y++;
  25.         while(x <= n && y <= m){
  26.             while(x <= n && s[x] != p[y]) x++;
  27.             if(s[x] == p[y]) x++, y++;
  28.         }
  29.         del[i] = x - g[i] - 1 - m;
  30.     }
  31.     }
  32.     for(int i = 1; i <= n; i++){
  33.         for(int j = 0; j <= n; j++){
  34.             f[i][j] = f[i - 1][j];
  35.             if(j >= del[i]) f[i][j] = f[g[i]][j - del[i]] + 1;
  36.             ans2[j] = max(f[i][j], ans2[j]);
  37.         }
  38.     }
  39.     int maxn = ans2[n], lim = n - maxn * m;
  40.     for(int i = lim; i <= n; i += m)
  41.         for(int j = 1; j <= m; j++)
  42.             ans2[i + j] = ans2[i] - 1;
  43.     for(int i = 0; i <= n; i++)
  44.         printf("%d ", ans2[i]);
  45.     printf("\n");
  46. }
  47. int main(){
  48.     scanf("%s%s", s + 1, p + 1);
  49.     n = strlen(s + 1), m = strlen(p + 1);
  50.     solve2();
  51.     return 0;
  52. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注