# Educational Codeforces Round 114 (Rated for Div. 2)

## A. Regular Bracket Sequences

Give you an integer n n n. Construct and print length 2 n 2n 2n n n n different legal bracket sequences.

Topic analysis: simulation, you might as well set the initial bracket sequence as ( ( ( ⏟ n ⋯ ) ) ) ⏟ n \underbrace{(((}_{n} \cdots \underbrace{)))}_{n} n (((​​⋯n ))), take out a pair of legal brackets and put them outside each time.

AC Code:

#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)

char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
{
int x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}

void solve()
{
down(k, n, 1)
{
rep(i, 1, k) printf("(");
rep(i, 1, k) printf(")");
rep(j, 1, n - k) printf("()");
puts("");
}
}

int main(int argc, char const *argv[])
{
while (T--)
solve();
return 0;
}


## B. Combinatorics Homework

Here are four integer values a a a , b b b , c c c and m m m .

Determine whether there is a string containing the following contents:

• a a a letter A A A
• b b b letters B B B
• c c c letters C C C
• Just contain m m m pairs of adjacent equal letters (i.e s [ i ] = s [ i + 1 ] s[i] = s[i+1] s[i]=s[i+1] ).

Topic analysis: might as well assume a ≤ b ≤ c a \leq b \leq c a ≤ b ≤ c, the upper and lower limits of adjacent equal letters shall be considered first:

• upper limit: A A A ⏟ a ⋯ B B B B ⏟ b ⋯ C C C C C ⏟ c \underbrace{AAA}_{a} \cdots \underbrace{BBBB}_{b} \cdots \underbrace{CCCCC}_{c} a AAA​​⋯b BBBB​​⋯c CCC, i.e ( a − 1 ) + ( b − 1 ) + ( c − 1 ) (a-1)+(b-1)+(c-1) (a−1)+(b−1)+(c−1)
• Lower limit: C A C A ⏟ a individual C ⋯ C B C B C B ⏟ b individual C ⋯ C C C C C \Underbrace {CACA} {a C} \ cdots \ underbrace {cbcb} {B C} \cdots CCCCC a C CACA... b C Cbcb * CCC, i.e c − ( a + b ) − 1 c - (a+b) - 1 c−(a+b)−1

It can be proved that if m i n ≤ m ≤ m a x min \leq m \leq max If min ≤ m ≤ max, such a sequence must exist.

• m i n + 1 min +1 min+1 : A C A C A ⋯ C A ⏟ a − 1 individual C C B C B C B ⏟ b individual C ⋯ C C C C C + C \Underbrace {acaca \ cdots CA} {A-1 C} \ underbrace {cbcb} {B C} \ cdots CCC + C a − 1 C ACA * CA b C CBCBCB​​⋯CCCCC+C
• m i n + 2 min +2 min+2 : C A C A ⋯ C A A ⏟ a − 1 individual C C B C B C B ⏟ b individual C ⋯ C C C C C + C \Underbrace {CACA \ cdots CAA} {A-1 C} \ underbrace {cbcb} {B C} \ cdots CCC + C a − 1 C CACA... CAA b C CBCBCB​​⋯CCCCC+C

stay m i n min On the basis of min, for each pair of adjacent equal letters, the first letter of the string is placed after the last occurrence of the letter.

AC Code:

#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)

char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
{
int x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}

bool solve()
{
if (c < a)
std::swap(a, c);
if (c < b)
std::swap(b, c);
int mx = a + b + c - 3, mn = std::max(c - (a + b) - 1, 0);
return (mn <= m && m <= mx) ? true : false;
}

int main(int argc, char const *argv[])
{
while (T--)
puts(solve() ? "YES" : "NO");
return 0;
}


## C. Slay the Dragon

A long time ago, the Dragon suddenly appeared

Do you have one n n The team of n brave people now has m m m dragons, No i i The defense of article i is x i x_i xi, attack power is y i y_i yi. For each dragon, you can choose one ability value a i ≥ x i a_i \geq x_i The brave with ai ≥ xi kill the dragon, the other brave stay to defend, and the total ability value of the defending brave s u m ≥ y i sum \geq y_i sum≥yi​ .

At the same time, you can spend 1 1 one o'clock c o s t cost cost increases the ability value of any brave person 1 1 1 point, this operation can be performed any time.

Q beat No i i What is the minimum cost of i Dragon (the ability value of all brave people is reset when fighting each dragon).

Topic analysis: adopt greedy strategy to find the first one in the sequence ≥ \geq ≥ and ≤ x i \leq x_i ≤ value of xi + a i a_i ai, then calculate the corresponding cost and output the smaller one.

AC Code:

#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
using ll = long long;
using namespace std;

char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
{
ll x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}

inline bool cmp(ll a, ll b) { return a > b; }

int main(int argc, char const *argv[])
{
ll sum = 0;
vector<ll> a(n + 1), b(n + 1);
rep(i, 1, n) sum += (a[i] = b[i] = read());
sort(a.begin() + 1, a.begin() + n + 1);
sort(b.begin() + 1, b.begin() + n + 1, cmp);
while (m--)
{
int pos1 = lower_bound(a.begin() + 1, a.begin() + n + 1, x) - a.begin();
int pos2 = lower_bound(b.begin() + 1, b.begin() + n + 1, x, greater<ll>()) - b.begin();
if (pos1 > n)
pos1 = n;
if (pos2 > n)
pos2 = n;
ll ans1 = 0, ans2 = 0;
if (x > a[pos1])
ans1 += x - a[pos1];
if (y > sum - a[pos1])
ans1 += y - (sum - a[pos1]);
if (x > b[pos2])
ans2 += x - b[pos2];
if (y > sum - b[pos2])
ans2 += y - (sum - b[pos2]);
printf("%lld\n", min(ans1, ans2));
}
return 0;
}


## D. The Strongest Build

Here you are n n n equipment slots, each with c c c pieces of equipment can be selected, and the attribute value of each piece of equipment is a i , j a_{i,j} ai,j, existing m m m illegal schemes, find the combination scheme that maximizes the attribute value under this condition.

Topic analysis: at the beginning d f s dfs dfs search results M L E MLE MLE. Here's a greedy strategy. Give priority to better equipment, the second i i For i equipment slot, only the best part that can make the scheme legal shall be considered j j j equipment, take out the current optimal scheme from the priority queue each time, if this scheme has been b a n ban ban, divide it into n n There are n follow-up schemes (the follow-up of one scheme is to replace a slot in the current combination with equipment just one gear short), but the separated follow-up schemes may be repeated, so we choose to use them s e t set set de duplication. Since the priority queue adopts a large root heap, this method will get the optimal solution.

AC Code:

#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i < (y); i++)
#define down(i, x, y) for (register int i = (x); i > (y); i--)
#define piv std::pair<int, std::vector<int>>

char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
{
int x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}

std::vector<int> v, g;
std::map<std::vector<int>, int> mp;
std::priority_queue<piv> q;
std::vector<std::vector<int>> f;
std::set<std::vector<int>> s;

int main(int argc, char const *argv[])
{
int n = read(), sum = 0;
rep(i, 0, n)
{
v.push_back(c);
g.clear();
rep(j, 0, c)
{
g.push_back(k);
}
f.push_back(g);
sum += g[c - 1];
}
q.push(std::make_pair(sum, v));
rep(i, 0, m)
{
g.clear();
rep(j, 0, n)
{
g.push_back(k);
}
++mp[g];
}
while (!q.empty())
{
piv ans = q.top();
q.pop();
sum = ans.first;
g = ans.second;
if (mp[g])
{
rep(i, 0, n)
{
if (g[i] <= 1)
continue;
int cur = f[i][g[i] - 1];
--g[i];
int nxt = f[i][g[i] - 1];
if (!s.count(g))
{
q.push(std::make_pair(sum - cur + nxt, g));
s.insert(g);
}
++g[i];
}
continue;
}
for (auto x : g)
printf("%d ", x);
puts("");
break;
}
return 0;
}

// #include <bits/stdc++.h>
// #define rep(i, x, y) for (register int i = (x); i <= (y); i++)
// #define down(i, x, y) for (register int i = (x); i >= (y); i--)
// #define pii pair<int, int>
// using namespace std;

// char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// {
//     int x = 0, f = 1;
//     char ch = getchar();
//     while (!isdigit(ch))
//     {
//         if (ch == '-')
//             f = -1;
//         ch = getchar();
//     }
//     while (isdigit(ch))
//     {
//         x = x * 10 + ch - '0';
//         ch = getchar();
//     }
//     return x * f;
// }
// inline char qrc()
// {
//     char c;
//     while (!isdigit(c = getchar()))
//         ;
//     return c;
// }

// int n, ans;
// map<vector<int>, int> mp;
// vector<int> output;
// vector<pii> a[11];

// void dfs(int id, vector<int> v)
// {
//     if (v.size() == n)
//     {
//         if (mp[v])
//             return;
//         int ans = 0;
//         rep(i, 1, n)
//             ans += a[i][v[i - 1] - 1].second;
//         if (ans > ans)
//             ans = ans, output = v;
//         return;
//     }
//     for (auto x : a[id])
//     {
//         v.push_back(x.first);
//         dfs(id + 1, v);
//         v.pop_back();
//     }
// }

// int main(int argc, char const *argv[])
// {
//     rep(i, 1, n)
//     {
//         rep(j, 1, c)
//         {
//             a[i].push_back(make_pair(j, k));
//         }
//     }
//     rep(i, 1, m)
//     {
//         vector<int> v;
//         rep(j, 1, n)
//         {
//             v.push_back(k);
//         }
//         ++mp[v];
//     }
//     vector<int> v;
//     dfs(1, v);
//     for (auto x : output)
//         printf("%d ", x);
//     puts("");
//     return 0;
// }


Tags: Algorithm C++

Posted by timolein on Wed, 22 Sep 2021 20:45:43 +0530