A - Chord

题意

给定一个字符串，判断 ss 是否是 ACE, BDF, CEG, DFA, EGB, FAC, 中 GBD 的一个。

解法

字面意思。

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<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int main(){
    string s;
    cin>>s;
    vector<string> lists={"ACE","BDF","CEG","DFA","EGB","FAC","GBD"};
    for(auto x:lists){
        if(x==s){
            Yes;
            return 0;
        }
    }
    No;
    return 0;
}

B - TaK Code

题意

如果一个 9×99\times 9 矩阵满足如下的要求（# 必须是 #，. 必须是 .，? 不确定），则称其是一个 Tak 码。

1
2
3
4
5
6
7
8
9
###.?????
###.?????
###.?????
....?????
?????????
?????....
?????.###
?????.###
?????.###

给定一个 n\time m\ (9\le n,m \le 100) 的矩阵，判断其中有多少个子矩阵是合法的Tak 码？输出所有子矩阵的左上角坐标。

解法

暴力实现即可。复杂度 O(81nm)O(81nm)，足够。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 105;
char a[N][N];

int main(){
    int n=read(),m=read();
    for(int i=1;i<=n;i++){
        scanf("%s",a[i]+1);
    }

    auto ok=[](int x,int y){
        for(int i=x;i<x+4;i++){
            for(int j=y;j<y+4;j++){
                if(i==x+3 || j==y+3){
                    if(a[i][j]=='#')return 0;
                }
                else if(a[i][j]=='.')return 0;
            }
        }

        
        for(int i=x+5;i<x+9;i++){
            for(int j=y+5;j<y+9;j++){
                if(i==x+5 || j==y+5){
                    if(a[i][j]=='#')return 0;
                }
                else if(a[i][j]=='.')return 0;
            }
        }
        return 1;
    };


    for(int i=1;i<=n-9+1;i++){
        for(int j=1;j<=m-9+1;j++){
            if(ok(i,j))printf("%d %d\n",i,j);
        }
    }
    return 0;
}

C - Invisible Hand

题意

有 nn 个人在卖苹果，mm 个人在买苹果。
卖苹果的人的预期价格为 a1,a2,…,ana_1,a_2,\ldots,a_n，他们愿意用一个不小于这个价格的价格卖出苹果。
买苹果的人的预期价格为 b1,b2,…,bnb_1,b_2,\ldots,b_n，他们愿意用一个不大于这个价格的价格买入苹果。

求出最小整数 xx，使得愿意以这个价格卖苹果的人大于等于愿意以这个价格买苹果的人。

解法

xx 一定等于 ai,ai+1,bi,bi+1a_i,a_i+1,b_i,b_i+1 中的一个。将这些全部加起来排序之后从小到大判断，动态维护愿意以这个价格买和卖苹果的人。

复杂度 O((n+m)log⁡(n+m)+n+m)O((n+m)\log(n+m)+n+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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int main(){
    int n=read(),m=read();

    vector<int> a,b,c;
    for(int i=1;i<=n;i++){
        int x=read();
        a.push_back(x);
        
        c.push_back(x);
        c.push_back(x+1);
    }
    for(int i=1;i<=m;i++){
        int x=read();
        b.push_back(x);

        c.push_back(x);
        c.push_back(x+1);
    }

    sort(all(a));
    sort(all(b));
    sort(all(c));

    int wantSell = 0;
    int wantBuy  = m;

    for(int p:c){
        if(wantBuy && b[m-wantBuy]<p){
            wantBuy--;
        }
        if(wantSell !=n && a[wantSell]<=p){
            wantSell++;
        }

        if(wantSell>=wantBuy){
            printf("%d\n",p);
            return 0;
        }
    }
    return 0;
}

D - Count Bracket Sequences

题意

一个长度为 nn 且符合规范的括号序列，其有些位置已经确定了，有些位置尚未确定，求这样的括号序列一共有多少个。

解法

典中典中典，但好像没人出过裸题？

合法的括号序列 ss 的充要条件是：

  1. 对于 ss 的任意一个前缀，( 的数量不少于 ) 的数量。
  2. ss 中 ( 和 ) 的数量一样多。

因此，设 dpi,jdp_{i,j} 为前 ii 个字符，左括号比右括号多 jj 个的合法解数量。

若 s[i]=(s[i]=\texttt{(}，则 dpi,j=dpi−1,j−1dp_{i,j}=dp_{i-1,j-1}。
若 s[i]=)s[i]=\texttt{)}，则 dpi,j=dpi−1,j+1dp_{i,j}=dp_{i-1,j+1}。
若 s[i]=?s[i]=\texttt{?}，则 dpi,j=dpi−1,j−1+dpi−1,j+1dp_{i,j}=dp_{i-1,j-1}+dp_{i-1,j+1}。

若转移方程式出现了 j−1<0j-1<0 的情况，直接忽略这一项。

时间+空间复杂度 O(n2)O(n^2)。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 3005;
const ll MOD = 998244353;
ll dp[N][N];

char s[N];

int main(){
    scanf("%s",s+1);
    int n = strlen(s+1);
    
    dp[0][0]=1;

    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++){
            if(s[i]=='?'){
                if(j==0)dp[i][j]=dp[i-1][j+1];
                else dp[i][j] = (dp[i-1][j-1]+dp[i-1][j+1])%MOD;
            }
            if(s[i]=='('){
                if(j!=0)dp[i][j] = dp[i-1][j-1];
            }
            if(s[i]==')'){
                dp[i][j] = dp[i-1][j+1];
            }
        }
    }

    printf("%lld\n",dp[n][0]);
    return 0;
}

E - Tangency of Cuboids

题意

空间内有 n (n≤105)n\ (n\le 10^5) 个棱与坐标轴垂直的立方体（立方体的顶点坐标非负且小于等于 100100）。这些立方体体积不存在交叉，求对于每个立方体，和它相邻的立方体有几个？（两个立方体相交，当且仅当他们六个面的面积交大于零）

解法

设坐标最大为 M=100M=100。

考虑开一个 M×M×MM\times M \times M 的数组，记录每一个空间中的格子被哪个立方体占据。看似这个的复杂度是 O(nM3)O(nM^3)，但是因为不存在交叉，最多只需要 O(M3)O(M^3) 时间就可以预处理出每一个空间的格子被哪个占据了。

对于 M×M×MM\times M \times M 的所有格子，我们依次检查其六个侧面，找出所有与其相邻的，加入 set，负责判重。

复杂度 O(M3log⁡n)O(M^3\log 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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 1e5+5;
const int M = 105;
int a[M][M][M];
set<int> ans[N];

int main(){
    int n=read();
    for(int u=1;u<=n;u++){
        int x1=read(),y1=read(),z1=read();
        int x2=read(),y2=read(),z2=read();

        for(int i=x1;i<x2;i++)
        for(int j=y1;j<y2;j++)
        for(int k=z1;k<z2;k++)
            a[i][j][k]=u;
    }

    auto check=[](int u,int v){
        if(u!=v && u && v){ 
            ans[u].insert(v);
            ans[v].insert(u);
        }
    };

    for(int i=0;i<100;i++)
    for(int j=0;j<100;j++)
    for(int k=0;k<100;k++){
        check(a[i][j][k],a[i+1][j][k]);
        check(a[i][j][k],a[i][j+1][k]);
        check(a[i][j][k],a[i][j][k+1]);
    }

    for(int i=1;i<=n;i++){
        printf("%lu\n",ans[i].size());
    }
    return 0;
}

F - Cans and Openers

题意

有 nn 个物品，从其中选 mm 个。
物品有三种：

  • 易拉罐，选择获得 viv_i 分。
  • 普通罐头，需要消耗一次开罐器，提供 viv_i 分。
  • 开罐器，能开 viv_i 个罐头。

求最高得分。

解法

简单数据结构。显然开罐器是从能开罐头数量多的开始选。我们枚举用了前 ii 个开罐器的最大得分，用一个优先队列维护当前能开的罐头，保持这个数量为 m−1m-1 即可。复杂度 O(nlog⁡n)O(n\log 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
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
70
71
72
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}


int main(){
    int n=read(),m=read();

    vector<int> norm, bad, open;

    for(int i=0;i<n;i++){
        int a=read(),b=read();
        if(a==0)norm.push_back(b);
        if(a==1)bad.push_back(b);
        if(a==2)open.push_back(b);
    }

    sort(all(norm),greater<int>());
    sort(all(bad),greater<int>());
    sort(all(open),greater<int>());

    priority_queue<int,vector<int>, greater<int> > selection;
    ll ans = 0;
    ll now = 0;

    for(int i=0;i<min((int)norm.size(),m);i++){
        selection.push(norm[i]);
        now += norm[i];
    }
    

    int nowBad = 0;

    ans = max(ans,now);
    for(int i=0;i<min((int)open.size(),m-1);i++){
        int newM = m-i-1;
        if(newM<=0)continue;
        
        for(int j=nowBad;j<min((int)bad.size(),nowBad+open[i]);j++){
            selection.push(bad[j]);
            now += bad[j];
        }
        nowBad=min((int)bad.size(),nowBad+open[i]);

        while(selection.size() && selection.size()>newM){
            now -= selection.top();
            selection.pop();
        }

        ans = max(ans,now);
    }

    printf("%lld\n",ans);   
    return 0;
}