[数据结构与算法]Educational Codeforces Round 114 (Rated for Div. 2) 补题

A.Regular Bracket Sequences

Problem Analysis

题目大意： 给定整数$n$，构造$n$个长度为$2n$的合法括号序列并输出，$n\in [1,50]$。

思路： 直接按照以下规律构造$n$组。
$$\begin{array}{rl}& i=1,()()()()...\\ & i=2,(())()()...\\ & i=3,((()))()...\\ & i=4,(((())))...\end{array}$$
即先构造$i,i\in [1,n]$个嵌套括号，剩余的长度直接输出括号补齐。

Accepted Code

#include <bits/stdc++.h>
using namespace std;

signed main(){
    int t = 0; cin >> t;
    while(t--){
        int n = 0; cin >> n;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++) printf("(");
            for(int j = 1; j <= i; j++) printf(")");
            for(int j = i + 1; j <= n; j++) printf("()");
            printf("\n");
        }
    }
    return 0;
}

B.Combinatorics Homework

Problem Analysis

题目大意： 给定字符A、B、C的数量$a,b,c$，询问对于给定的常数$m$，是否存在由这$a,b,c$个A、B、C组成的字符串满足有且仅有$m$对连续相同的字母。

思路： 我们需要先处理出对于给定的$a,b,c$，最大连续相同字母对数、最小连续相同字母对数：

• 对于最大连续相同字母对数，构造的策略是相同的字母全部放在一起(也就是A...B...C...)，又由于对于连续序列，相邻相同字母对数一定等于$长度?1$，因此最大连续对数$=(a?1)+(b?1)+(c?1)$；
• 对于最小连续相同字母对数，则采取交替构造方式(也就是ABCABC...)，此时可以保证尽可能的将字母分散开来。我们认为$a,b,c$大小递减顺序排列，则先耗尽字母C，再ABAB...交替构造，则最终耗尽字母B后剩余字母A的数量$?1$即为最小连续相同字母对数。

得出最大最小值来后，判断一下$m$是否位于区间内即可。

Accepted Code

#include <bits/stdc++.h>
using namespace std;

int a[4];

signed main(){
    int t = 0; cin >> t;
    while(t--){
        for(int i = 1; i <= 3; i++) scanf("%d", &a[i]);
        sort(a + 1, a + 4);
        int m; scanf("%d", &m);
        int maxx = a[1] + a[2] + a[3] - 3, minn = ((a[3] - a[2] - a[1] - 1) < 0 ? 0 : (a[3] - a[2] - a[1] - 1));
        if(m <= maxx && m >= minn) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

C.Slay the Dragon

Problem Analysis

题目大意： 有$n$个英雄、$m$条龙。

• 英雄具有一个属性：力量$a_i$
• 龙具有两个属灵：血量$x_i$，攻击力$y_i$

游戏规则为：

• 派出一位英雄屠龙，若当前龙的血量为$x_i$，则英雄的力量$a_i$应满足$a_i\ge x_i$；
• 剩余英雄守家，若龙的攻击力为$y_i$，则这堆英雄的总血量$\sum a_i\ge y_i$；
• 可以选择花费一枚金币，使某个英雄力量增加$1$。

要求求出杀死第$i$条龙所需花费的最小金币数量。

思路： 贪心问题，首先考虑如何采取最佳策略。

根据题目要求，我们选取一个英雄来屠龙，剩余英雄守家。那么显然守家的英雄一般会有多个，因此对守家英雄采取贪心策略并不怎么方便。那么考虑对选取的一个屠龙英雄采取贪心策略：对与第$i?th$条龙而言：

• 首先找有没有与该龙血量$x_i$相等的$a_i$，如果有，则派该英雄屠龙，剩余英雄守家；
• 如果没有与该龙血量$x_i$相同的龙：
  • 找到小于$x_i$的最大$a_i$，选择对应的英雄屠龙；
  • 找到大于$x_i$的最小$a_i$，选择对应的英雄屠龙；
  • 对以上两种选择方案取最小值。

Accepted Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 10;

int a[N], sum;

signed main(){
       //freopen("stdin.in", "r", stdin);
       //freopen("stdout.out", "w", stdout);
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n = 0; cin >> n; a[0] = -1;
    for(int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
    sort(a + 1, a + 1 + n);
    int m = 0; cin >> m;
    for(int i = 1; i <= m; i++){
        int x = 0, y = 0, ans = 0; cin >> x >> y;
        int pos = lower_bound(a + 1, a + n, x) - a;
        if(pos != n){
            if(a[pos] == x) //能找到跟x_i相同大小的a_i
                ans = ((y - sum + a[pos]) < 0 ? 0 : (y - sum + a[pos]));
            else if(a[pos - 1] != -1) //找不到相同的，但存在比x_i小的最大a_i和比x_i大的最小a_i，对两种方案取min
                ans = min((x - a[pos - 1]) + ((y - sum + a[pos - 1]) < 0 ? 0 : (y - sum + a[pos - 1])), ((y - sum + a[pos]) < 0 ? 0 : (y - sum + a[pos])));
            else //a_i全都比x_i大
                ans = ((y - sum + a[pos]) < 0 ? 0 : (y - sum + a[pos]));
        }
        else{ //a_i全比x_i小
            ans = (x - a[n]) + ((y - (sum - a[n])) < 0 ? 0 : (y - (sum - a[n])));
        }
        cout << ans << endl;
    }
    
    return 0;
}

D.The Strongest Build

Problem Analysis

给$n$个槽位，每个槽位有若干个卡片，每个卡片上的数值都可以提升英雄的实力（数值已经升序排好）

告诉你，有一些卡片的序号被禁用，要求求出剩下的卡片组合，可以使得英雄的实力总和最大。输出卡片的序号。

用广搜+$map$标记搞一下就过了，开一个优先队列储存节点，节点内存当前的状态(最多$10$个卡槽的状态)，然后搜到第一个未被禁止的状态即为最佳答案。

Accepted Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 20;
int n;

struct node{
    vector<int> vec;
    ll val;
    node(){ val = 0; }
    node(int n) { val = 0, vec.resize(n); }
    bool operator < (const node& obj) const { return val < obj.val; }
};

map<vector<int>, int> mp; //禁止使用的牌组
map<vector<int>, int> vis; //访问标记
vector<vector<int> > c; //类似邻接表储存
priority_queue<node> q; //BFS队列

void cal(node& now){
    now.val = 0;
    for(int i = 1; i <= n; i++) now.val += (ll)c[i][now.vec[i]];
}

int main(){
    scanf("%d", &n);
    node s(n + 1);
    c.resize(n + 1);
    for(int i = 1, num; i <= n; i++){
        scanf("%d", &num);
        s.vec[i] = num;
        c[i].resize(num + 1);
        for(int j = 1; j <= num; j++) scanf("%d", &c[i][j]);
    }
    node now(n + 1);
    int m;
    scanf("%d", &m);
    for(int i = 0; i < m; i++){
        for(int j = 1; j <= n; j++) scanf("%d", &(now.vec[j]));
        mp[now.vec] = 1; 
    }
    cal(s);
    q.push(s);
    vis[s.vec] = 1;
    while(!q.empty()){
        node now = q.top();
        q.pop();
        if(!mp[now.vec]){
            for(int i = 1; i <= n; i++) printf("%d ", now.vec[i]);
            printf("\n");
            return 0;
        }
        for(int i = 1; i <= n; i++){
            if(now.vec[i] <= 1) continue;
            ll val = now.val;
            now.vec[i]--;
            cal(now);
            if(!vis[now.vec]){
                q.push(now);
                vis[now.vec] = 1;
            }
            now.val = val;
            now.vec[i]++;
        }
    }
    return 0;
}