A - First ABC

题意

给定一个含有 A，B，C 的字符串。
求其的最短前缀，使得这个前缀同时包含 A，B 和 C。

解法

维护 A，B，C 是否出现即可。

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

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(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 s[N];
bool exist[5];

int main(){
    int n=read();
    scanf("%s",s);

    for(int i=0;i<n;i++){
        exist[s[i]-'A']=1;

        bool ok = 1;
        for(int i=0;i<3;i++){
            if(!exist[i])ok=0;
        }

        if(ok){
            printf("%d\n",i+1);
            break;
        }
    }
    return 0;
}

B - Vacation Together

题意

给定 nn 个人接下来 dd 天的日程。每个人在一天要么是空闲，要么是有事的。
求最长的一段连续时间，使每一个人都是空闲的。

解法

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

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(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;
bool bad[N];
char s[N];

int main(){
    int n=read(),d=read();
    for(int i=0;i<n;i++){
        scanf("%s",s);
        for(int i=0;i<d;i++){
            if(s[i]=='x')bad[i]=1;
        }
    }

    int ans=0,len=0;
    for(int i=0;i<d;i++){
        if(bad[i]){
            ans=max(ans,len);
            len=0;
        }else len++;
    }
    ans=max(ans,len);
    printf("%d\n",ans);
    return 0;
}

C - Find it!

题意

给定一张 nn 个点的有向图，图中每个点有且仅有一个后继。
请找出图上任意一个简单环。

解法1

不难发现从节点 11 出发一定能走到一个环。从 11 出发，不断向后走，直到走到一个重复的节点。那么这个重复的节点一定在环上。
然后直接输出环上所有点即可。

时间复杂度 O(n)O(n)，空间复杂度 O(n)O(n)。

代码略。

解法2 （Floyd 判圈算法）

从节点 11 开始跑 Floyd 判圈算法即可。

时间复杂度 O(n)O(n)，空间复杂度仍是 O(n)O(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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(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 = 2e5+5;
int nxt[N];

int main(){
    int n=read();
    for(int i=1;i<=n;i++){
        nxt[i]=read();
    }

    int slow=1,fast=1;
    do slow=nxt[slow],fast=nxt[nxt[fast]];
    while(slow!=fast);

    vector<int> ans;
    do{
        ans.push_back(fast);
        fast=nxt[fast];
    }while(slow!=fast);

    printf("%lu\n",ans.size());
    for(int v:ans){
        printf("%d ",v);
    }
    return 0;
}

D - Grid Ice Floor

题意

给定一个 n×mn\times m 的网格。网格里面有岩石（#）和冰（.）。保证最外面一圈都是墙。
一开始，你在 (2,2)(2,2)，你可以执行如下移动任意次：

  • 选定一个方向；
  • 沿着这个方向一直走，直到遇到岩石。

请问，你最多能经过几块冰？

解法 1 （暴力 BFS）

先预处理出每个格子上下左右能走到的位置。时间复杂度为 O(nm)O(nm)。
然后从 (2,2)(2,2) 开始进行 BFS，暴力将路径上的每一个点置为访问过。因为每一个节点出发最多只有上下左右四条路径，即要暴力填充 O(n+m)O(n+m) 个格子。

则总复杂度是 O(nm(n+m))O(nm(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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(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 = 205;
char a[N][N];

int u[N][N],d[N][N],l[N][N],r[N][N];
bool vis[N][N];

const int M = 305*305;
vector<int> G[M];
bool ok[M];
int xy2v(int i,int j){
    return i*300+j;
}
pair<int,int> v2xy(int val){
    return {val/300,val%300};
}

void path(pii a,pii b){
    int i=a.first,j=a.second;
    int ii=b.first,jj=b.second;
    if(i>ii)swap(i,ii);
    if(j>jj)swap(j,jj);

    for(int x=i;x<=ii;x++){
        for(int y=j;y<=jj;y++){
            vis[x][y]=1;
        }
    }
}

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

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='#')continue;

            if(a[i-1][j]=='#')u[i][j]=i;
            else u[i][j]=u[i-1][j];

            if(a[i][j-1]=='#')l[i][j]=j;
            else l[i][j]=l[i][j-1];
        }
    }

    for(int i=n;i>0;i--){
        for(int j=m;j>0;j--){
            if(a[i][j]=='#')continue;

            if(a[i+1][j]=='#')d[i][j]=i;
            else d[i][j]=d[i+1][j];

            if(a[i][j+1]=='#')r[i][j]=j;
            else r[i][j]=r[i][j+1];
        }
    }


    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='#')continue;

            G[xy2v(i,j)].push_back(xy2v(u[i][j],j));
            G[xy2v(i,j)].push_back(xy2v(d[i][j],j));
            G[xy2v(i,j)].push_back(xy2v(i,l[i][j]));
            G[xy2v(i,j)].push_back(xy2v(i,r[i][j]));
        }
    }

    int st = xy2v(2,2);
    queue<int> q;
    q.push(st);ok[st]=1;
    while(q.size()){
        int p=q.front();q.pop();
        for(int nxt:G[p]){
            path(v2xy(p),v2xy(nxt));
            if(ok[nxt])continue;

            q.push(nxt);ok[nxt]=1;
        }
    }

    int ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(vis[i][j])ans++;
        }
    }

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

解法 2 （优化 BFS）

事实上，如果稍作优化，本题的复杂度可以降为 O(nm)O(nm)。

考虑一个人的状态如何唯一确定。事实上，只要给定一个人的位置和它目前的运动状态，这个状态是唯一确定的。

因此，我们用一个结构体来表示这个状态。{(x,y),d}\{(x,y),d\}，表示这个人目前在 (x,y)(x,y)，运动状态是 dd。d=0,1,2,3d=0,1,2,3 的情况，代表现在在移动中，方向为上下左右，d=4d=4 的情况，代表目前停止。

接下来考虑状态怎么转移：

  • d=4d=4，如果对应方向没有岩石，可以转移到状态 {(x,y),d′}\{(x,y),d\prime\}。
  • d=0,1,2,3d=0,1,2,3：
    • 如果前进方向没有岩石，可以转移到状态 {(x′,y′),d}\{(x\prime,y\prime),d\}；
    • 如果前进方向有岩石，可以转移到状态 {(x,y),4}\{(x,y),4\}。

总共只有 5nm5nm 个状态，每个状态只会访问一次，复杂度即为 O(nm)O(nm)。

对于基本上都是冰的图优化效果显著。

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
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(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 = 205;
char a[N][N];

bool vis[N][N][5];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};

struct Node
{
    int x,y;
    int d;
};


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

    queue<Node> q;
    q.push({2,2,4});
    vis[2][2][4]=1;

    while(q.size()){
        auto o = q.front();q.pop();
        if(o.d!=4){
            int xx=o.x+dx[o.d], yy=o.y+dy[o.d], dd =o.d;
            if(a[xx][yy]=='#'){
                xx=o.x, yy=o.y;
                dd=4;
            }

            if(!vis[xx][yy][dd]){
                vis[xx][yy][dd]=1;
                q.push({xx,yy,dd});
            }
        }
        else{
            for(int dd=0;dd<4;dd++){
                int xx=o.x+dx[dd], yy=o.y+dy[dd];
                if(a[xx][yy]=='.'){
                    if(!vis[o.x][o.y][dd]){
                        vis[o.x][o.y][dd]=1;
                        q.push({o.x,o.y,dd});
                    }
                }
            }
        }
    }

    int ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ans += *max_element(vis[i][j],vis[i][j]+5);
        }
    }
    printf("%d\n",ans);
    return 0;
}

E - Defect-free Squares

题意

有一个 h×wh\times w 的网格，上面有 nn 个洞。
求没有洞的正方形数量。

解法

考虑动态规划。设 f[i][j]f[i][j] 代表以 (i,j)(i,j) 为右下角的无洞正方形数量。

若 (i,j)(i,j) 是洞，f[i][j]=0f[i][j]=0。
否则 f[i][j]=min⁡{f[i−1][j],f[i][j−1],f[i−1][j−1]}+1f[i][j]=\min\{f[i-1][j],f[i][j-1],f[i-1][j-1]\}+1。（想一想，为什么?）

最终答案即为 ∑i=1h∑j=1wf[i][j]\displaystyle \sum_{i=1}^h \sum_{j=1}^w f[i][j]。

复杂度 O(hw)O(hw)。

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

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(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;
ll dp[N][N];
bool bad[N][N];


int main(){
    int n=read(),m=read(),k=read();
    for(int i=0;i<k;i++){
        int x=read(),y=read();
        bad[x][y]=1;
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(bad[i][j])continue;
        }
    }

    ll ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(bad[i][j]){
                continue;
            }

            dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1;
            ans += dp[i][j];
        }
    }

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

本题还有利用二维前缀和+二分查找的做法，效率较劣，代码略。

F - Yet Another Grid Task

题意

给定一个由 # 和 . 组成的 n×mn\times m 的矩阵。
如果所有的 # 下面和右下角（如果有）都是 #。那么这个矩阵是漂亮矩阵。

现在给出一个已经有了部分 # 的矩阵，求出有多少种填 # 的情况，使得这个矩阵是漂亮矩阵。
由于答案可能很大，输出对 998244353998244353 取余的结果。

解法

首先对其进行一些预处理，注意到一部分格子是一定要变成 # 的。我们先把初始填的 # 的下面和右下都变成 #。

例如：

.# -> .#
..    .#

....#       ....# 
...#.       ...## 
..#..   ->  ..### 
.#.#.       .#### 
#...#       #####

我们提供一个比标答实现更简单，更容易理解的动态规划方法。
我们考虑每一列。对于每一列，一定是上面几个是 .，然后下面全部是 #。
并且，左边列的最高的那个 # 最多比右边高 1。

因此，我们设 dp[i][j]dp[i][j] 表示第 ii 列，放了 jj 个 # 的方案数。

转移方程式：

dp[i][j]=∑k=0j+1dp[i−1][k]dp[i][j]=\sum_{k=0}^{j+1}dp[i-1][k]

这个随便前缀和优化一下就可以做到 O(nm)O(nm) 计算出全部状态。

初始条件：

dp[0][x]=1dp[i][j]=0 如果 mat[n−j−1][i]=#dp[0][x]=1 \\ dp[i][j]=0 \text{ 如果 } mat[n-j-1][i]=\#

第一个初始条件的意思是第一列的方案数都为 11，第二个初始条件的意思是对于已经填好的很多 #，只有最高的那个 # 对应的 dpdp 应该是有数值的，下面的全部都是 00。

最终答案即为 ∑i=0ndp[m−1][i]\displaystyle \sum_{i=0}^n dp[m-1][i]。

可以使用滚动数组优化，但由于空间充足，下面代码未使用。

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

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(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 = 2005;

char s[N][N];
ll dp[N][N];
const ll mod = 998244353;

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

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='#'){
                if(i+1<n)s[i+1][j]='#';
                if(i+1<n && j+1<m)s[i+1][j+1]='#';
            }
        }
    }

    for(int j=n;j>=0;j--){
        dp[0][j]=1;
        if(s[n-j][0]=='#')break;
    }

    for(int i=1;i<m;i++){
        int j=0;
        while(j<n && s[n-j-1][i]=='#')j++;

        for(int k=j+1;k>=0;k--){
            dp[i][j] = (dp[i][j]+dp[i-1][k])%mod;
        }
        for(int k=j+1;k<=n;k++){
            dp[i][k] = (dp[i][k-1]+dp[i-1][k+1])%mod;
        }
    }

    ll ans = 0;
    for(int i=0;i<=n;i++){
        ans += dp[m-1][i];
        ans %= mod;
    }

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