A. Regular Bracket Sequences
题意
输出$n$个不同的长度为$2n$的合法括号序列.
分析
先输出一个”()()()…”序列.
然后依次输出”(())()”, “()(())”,…，也就是每次把第$i$个和第$i+1$个交换，其中$i$从下标2到n-2，这样恰好$n-1$个，加上最开始的共$n$个。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
using namespace std;
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
string s;
for(int i = 0; i < n; ++i){
s += '(';
s += ')';
}
cout << s << endl;
for(int i = 1; i + 1 < s.size(); i += 2){
s[i] = '(';
s[i + 1] = ')';
cout << s << endl;
s[i] = ')';
s[i + 1] = '(';
}
}
return 0;
}
|
B. Combinatorics Homework
题意
你需要判断是否存在一个字符串：
- 恰好a个’A’，b个’B’，c个‘C’
- 没有其他字符
- 恰好m对相邻且相同的字符对（如”AA”）
分析
目标是寻找可以满足要求的$m$取值范围。
将三种字符的数量排序，找到其个数最多的，假设为’A’，记’B’和’C’的数量和为$s$。
$m$最大取值显然是$a+b+c-3$.
找$m$的最小值。把$s$个字符排开，其有$s+1$个位置可以插入’A’。若’A’的数量不超过$s+1$，那么肯定可以达到最小状态，即不存在相邻且相同的字符对。可能会想到’A’没有填满所有空缺时有可能’B’或者’C’会出现连续的情况，但其实这种情况发生的话’A’肯定就不是个数最多的了。反之，若’A’的数量超过了$s+1$，那么至少出现的相同字符对就是$s+1-a$对。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
using namespace std;
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
int t;
cin >> t;
while(t--)
{
int a, b, c, m;
cin >> a >> b >> c >> m;
int mx = a + b + c - 3;
int p[3] = {a, b, c};
sort(p, p + 3);
int r2 = p[0] + p[1] + 1, r1 = p[2];
int mn = max(0LL, r1 - r2);
if(mx >= m && mn <= m){
cout << "YES" << endl;
}
else cout << "NO" << endl;
}
return 0;
|
C. Slay the Dragon
题意
有$m$条龙和$n$个勇士，每个勇士的力量是$a_i$，每个龙的防御力为$x_i$，攻击力为$y_i$。对每条龙$i$，你需要派遣一个勇士，要求力量大于等于$x_i$，如果不足$x_i$，需要支付等量的金币补足差值；同时要求剩余的勇士力量总和大于等于$y_i$，不足用金币补足。问击杀每条龙需要支付的金币至少是多少（每条龙之间分别计算，相互独立）
分析
贪心，对勇士力量升序排序。对每条龙，lower_bound(a+1,a+1+n, x[i])查找出一个勇士$s$，如果要派遣一个大于等于$x_i$的勇士去，那么必定是派$s$去。
但又有可能这个$s$超过$x_i$很多而其他的总和不足$y_i$，这个时候$s-1$也可能是答案。
所以答案要么是派$s$去，要么是派$s-1$去。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
int x[maxn], y[maxn];
int pre[maxn];
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
int t;
t = 1;
a[0] = 0;
while(t--)
{
int n;
cin >> n;
fors(i, 1, n) cin >> a[i];
int m;
cin >> m;
fors(i, 1 , m) cin >> x[i] >> y[i];
sort(a + 1, a + 1 + n);
pre[0] = 0;
fors(i, 1, n) pre[i] = pre[i - 1] + a[i];
fors(i, 1, m){
int now = lower_bound(a + 1, a + 1 + n, x[i]) - a;
int ans = 0;
if(now == n + 1){
ans += x[i] - a[n];
ans += (pre[n - 1] >= y[i] ? 0 : y[i] - pre[n - 1]);
cout << ans << endl;
}
else{
ans = (pre[n] - a[now] >= y[i] ? 0 : y[i] - (pre[n] - a[now]));
if(now == 1){
cout << ans << endl;
continue;
}
int res = 0;
now--;
res += x[i] - a[now];
res += (pre[n] - a[now] >= y[i] ? 0 : y[i] - (pre[n] - a[now]));
ans = min(ans, res);
cout << ans << endl;
}
}
}
return 0;
}
|
D. The Strongest Build
题意
有$n(n\leq 10)$个单调不下降数组，每个数组长$c_i$，第$i$个数组的第$j$个元素表示为$a_{ij}$，保证$\sum c_i\leq2·10^5$，你需要从每个数组中选一个元素，但约定有$m(m\leq 10^5)$个选择方案是不允许的。求一个方案使得所有选择的元素和最大，输出方案。
分析
暴力枚举。首先考虑所有数组都选最后一个元素（最大的），如果这个方案不行，那就枚举所有被禁止的方案。例如，假如某个方案{a,b,c}是禁止的，那么就看{a-1,b,c},{a,b-1,c},{a,b,c-1}有没有禁止，没有就更新答案，这样枚举出来的一定是最优解。
贪心思路：
若$\{a_{c_1},a_{c_2},…\}$这个在没有限制条件下的方案被限制了的话，可能的最优解就从$\{a_{c_1-1},a_{c_2},…\},\{a_{c_1},a_{c_2-1},…\}$里面产生。如果这些方案中也有被限制的，那么就再从这些中枚举每个位置分别将其减一再更新答案。这样可以保证每次都是“退而求其次”，但一定是可选择的里面最优的。毕竟$m\leq 10^5$，故最多需要枚举$mn$次。加上二分查找，时间复杂度为$O(mn\log m)$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
using namespace std;
const int maxn = 2e5 + 10;
int a[12][maxn];
int n;
set<vector<int> > v;
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
cin >> n;
fors(i, 1, n){
cin >> a[i][0];
fors(j, 1, a[i][0]) cin >> a[i][j];
}
int m, p;
cin >> m;
vector<int> tmp;
fors(I, 1, m){
fors(j, 1, n){
cin >> p;
tmp.pb(p);
}
v.insert(tmp);
tmp.clear();
}
vector<int> ideal; fors(i, 1, n) ideal.pb(a[i][0]);
if(v.find(ideal) == v.end()){
for(auto x : ideal) cout << x << ' ';
cout << endl; return 0;
}
else{
int ans = 0;
vector<int> f;
for(auto x : v){
tmp = x;
int sum = 0;
for(int i = 0; i < x.size(); ++i){
sum += a[i + 1][x[i]];
}
for(int j = 0; j < x.size(); ++j){
if(x[j] - 1 == 0) continue;
sum -= a[j + 1][x[j]];
sum += a[j + 1][x[j] - 1];
x[j]--;
if(v.find(x) == v.end() && sum > ans) ans = sum, f = x;
x[j]++;
sum += a[j + 1][x[j]];
sum -= a[j + 1][x[j] - 1];
}
}
for(auto x : f) cout << x << ' ';
cout << endl;
}
return 0;
}
|
