2018多校第一场 题解

发表于 | 分类于 |
字数统计: 621 字

题目链接

A

一个很神奇的数学题…
我个人只会观察，发现当$n=3k$时可以利用均值不等式直接输出最大值，$n=4k$时答案就是$2k^3$，其他的手算了几个，估计没有，就直接$-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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
ll n;
void init(){
    n = read();
}
void solve(){
    if(n % 3 == 0)
        n /= 3, printf("%lld\n", n * n * n);
    else if(n % 4 == 0)
        n >>= 2, printf("%lld\n", n * n * n * 2ll);
    else printf("-1\n");
}
int main(){
    int T = read();
    while(T--){
        init();
        solve();
    }
    return 0;
}

B

首先先把可以匹配的弄掉，最后剩一堆$pair(a, b)$，表示该字符串有$a$个’)’，$b$个’(‘。
然后贪心，用一种迷之方法排序。。。排序的中心要求是让)少(多的在前面，)多(少的在后面，由前者过渡到后者。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
typedef pair<int, int> pp;
int n, st[100005], top, ans;
pp p[100005];
char s[100005];
void init(){
    ans = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        scanf("%s", s);
        int r = 0, l = 0, len = strlen(s);
        top = 0;
        for(int j = 0; j < len; ++j){
            if(s[j] == ')'){
                if(top && st[top - 1] == '(')
                    top--, l--, ans += 2;
                else st[top++] = ')', r++;
            }else
                st[top++] = '(', l++;
        }
        p[i].first = r, p[i].second = l;
    }
}
bool cmp(const pp& p1, const pp& p2){
    if(!p1.first) return 1; 
    if(!p2.first) return 0;
    int f1 = p1.first - p1.second, f2 = p2.first - p2.second;
    if(f1 * f2 <= 0) return f1 < f2;
    if(f1 < 0) return p1.first <= p2.first;
    return p1.second >= p2.second;
}
void solve(){
    sort(p, p + n, cmp);
    int l = p[0].first, r = p[0].second;
    for(int i = 1; i < n; ++i){
        int ll = p[i].first, rr = p[i].second;
        ans += min(r, ll) * 2;
        if(r > ll) r = r - ll + rr;
        else l = ll - r + l, r = rr;
    }
    printf("%d\n", ans);
}
int main(){
    int T = read();
    while(T--){
        init();
        solve();
    }
    return 0;
}

C