Educational Codeforces Round 114 (Rated for Div. 2) 補題

😊 | Powered By HeartFireY

A.Regular Bracket Sequences

Problem Analysis

題目大意： 給定整數 n n n，構造 n n n個長度為 2 n 2n 2n的合法括号序列并輸出， n ∈ [ 1 , 50 ] n \in [1, 50] n∈[1,50]。

思路： 直接按照以下規律構造 n n n組。

i = 1 , ( ) ( ) ( ) ( ) . . . i = 2 , ( ( ) ) ( ) ( ) . . . i = 3 , ( ( ( ) ) ) ( ) . . . i = 4 , ( ( ( ( ) ) ) ) . . . \begin{aligned} &i = 1, ()()()()... \\ &i = 2, (())()()... \\ &i = 3, ((()))()... \\ &i = 4, (((())))... \\ \end{aligned} ​i=1,()()()()...i=2,(())()()...i=3,((()))()...i=4,(((())))...​

即先構造 i ,   i ∈ [ 1 , n ] i,\ i \in [1,n] i, i∈[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 a,b,c a,b,c，詢問對于給定的常數 m m m，是否存在由這 a , b , c a,b,c a,b,c個

A

、

B

、

C

組成的字元串滿足有且僅有 m m m對連續相同的字母。

思路： 我們需要先處理出對于給定的 a , b , c a,b,c a,b,c，最大連續相同字母對數、最小連續相同字母對數：

• 對于最大連續相同字母對數，構造的政策是相同的字母全部放在一起(也就是

  A...B...C...

  )，又由于對于連續序列，相鄰相同字母對數一定等于 長 度 − 1 長度-1 長度−1，是以最大連續對數 = ( a − 1 ) + ( b − 1 ) + ( c − 1 ) =(a - 1) + (b - 1) + (c - 1) =(a−1)+(b−1)+(c−1)；
• 對于最小連續相同字母對數，則采取交替構造方式(也就是

  ABCABC...

  )，此時可以保證盡可能的将字母分散開來。我們認為 a , b , c a,b,c a,b,c大小遞減順序排列，則先耗盡字母

  C

  ，再

  ABAB...

  交替構造，則最終耗盡字母

  B

  後剩餘字母

  A

  的數量 − 1 -1 −1即為最小連續相同字母對數。

得出最大最小值來後，判斷一下 m m 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 n n個英雄、 m m m條龍。

• 英雄具有一個屬性：力量 a i a_i ai​
• 龍具有兩個屬靈：血量 x i x_i xi​，攻擊力 y i y_i yi​

遊戲規則為：

• 派出一位英雄屠龍，若目前龍的血量為 x i x_i xi​，則英雄的力量 a i a_i ai​應滿足 a i ≥ x i a_i \geq x_i ai​≥xi​；
• 剩餘英雄守家，若龍的攻擊力為 y i y_i yi​，則這堆英雄的總血量 ∑ a i ≥ y i \sum a_i \geq y_i ∑ai​≥yi​；
• 可以選擇花費一枚金币，使某個英雄力量增加 1 1 1。

要求求出殺死第 i i i條龍所需花費的最小金币數量。

思路： 貪心問題，首先考慮如何采取最佳政策。

根據題目要求，我們選取一個英雄來屠龍，剩餘英雄守家。那麼顯然守家的英雄一般會有多個，是以對守家英雄采取貪心政策并不怎麼友善。那麼考慮對選取的一個屠龍英雄采取貪心政策：對與第 i − t h i-th i−th條龍而言：

• 首先找有沒有與該龍血量 x i x_i xi​相等的 a i a_i ai​，如果有，則派該英雄屠龍，剩餘英雄守家；
• 如果沒有與該龍血量 x i x_i xi​相同的龍：
  • 找到小于 x i x_i xi​的最大 a i a_i ai​，選擇對應的英雄屠龍；
  • 找到大于 x i x_i xi​的最小 a i a_i ai​，選擇對應的英雄屠龍；
  • 對以上兩種選擇方案取最小值。

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 n n個槽位，每個槽位有若幹個卡片，每個卡片上的數值都可以提升英雄的實力（數值已經升序排好）

告訴你，有一些卡片的序号被禁用，要求求出剩下的卡片組合，可以使得英雄的實力總和最大。輸出卡片的序号。

用廣搜+ m a p map map标記搞一下就過了，開一個優先隊列儲存節點，節點記憶體目前的狀态(最多 10 10 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;
}