rwbyblake的博客

Gym-102465-部分题解

2021-01-18 分类于 ACM 作者 rwbyblake ~ 4.56K 字
  1. 1. 题目大意
  2. 2. 解析
  3. 3. 代码
  4. 4. 题目大意
  5. 5. 解析
  6. 6. 代码

I - Mason’s Mark

题目大意

给出一张仅有黑白两种颜色的照片，让你分析照片中有几个ABC

解析

题目很长…要求很多…但是读明白题后没有一点思路的难度。其他要求不再赘述，这里只说最关键的一点，就是黑色像素仅有三种可能，即噪点，相框，和标记。也就是说，只要排除了相框和标记的黑色像素，剩余的黑色像素一定是一个字母上的。剩下的工作就仅剩下判断这个黑色像素所属字母是什么字母了。我用了一种非常简单粗暴的方法…具体看代码吧

代码

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

using namespace std;
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const unsigned long long P = 1e9 + 7;
const double eps = 1e-6;
char s[1005][1005];
bool vis[1005][1005];
int n,m;
int MOVE[8][2] = {1,0,0,1,-1,0,0,-1,1,1,1,-1,-1,1,-1,-1};
bool isNoise(int x,int y){
    for(int i = 0;i<8;i++){
        int kx = x + MOVE[i][0];
        int ky = y + MOVE[i][1];
        if(s[kx][ky]=='#')  return false;
    }
    return true;
}
void fill(int x,int y){
    queue<pair<int,int>> q;
    q.push({x,y});
    vis[x][y] = true;
    while(!q.empty()){
        auto u = q.front();
        q.pop();
        for(int i = 0;i<8;i++){
            int kx = u.first + MOVE[i][0];
            int ky = u.second + MOVE[i][1];
            if(kx<=n&&ky<=m&&kx>=1&&ky>=1&&!vis[kx][ky]&&s[kx][ky]=='#'){
                vis[kx][ky] = true;
                q.push({kx,ky});
            }
        }
    }
}
int check(int x,int y){
    int rx = x,ry = y;
    //走到字母框最右端
    while(s[rx][ry+1]=='#')   ry++;
    //一起向下走到最下端
    while(s[rx+1][ry]=='#')   rx++;
    while(s[x+1][y]=='#') x++;
    //如果不能一起走到最低端说明是C
    if(rx!=x)   return 3;
    //右标记走到最左端
    while(s[rx][ry-1]=='#')   ry--;
    //如果不能走到一起说明是A，否则是B
    if(y!=ry)   return 1;
    else    return 2;
}
int main() {
    cin>>m>>n;
    for(int i = 1;i<=n;i++){
        scanf("%s",s[i]+1);
    }
    fill(1,1);
    int ans1 = 0,ans2 = 0,ans3 = 0;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if(!vis[i][j]&&s[i][j]=='#'){
                if(isNoise(i,j))    vis[i][j] = true;
                else{
                    switch (check(i,j)) {
                        case 1:ans1++;break;
                        case 2:ans2++;break;
                        case 3:ans3++;break;
                    }
                    fill(i,j);
                }
            }
        }
    }
    printf("%d %d %d",ans1,ans2,ans3);
    return 0;
}

K-Dishonest Driver

题目大意

给出一个字符串，两个相邻且相同子串可以进行压缩，问压缩后字符串中有多少元素。

解析

一个区间的左半部分和右半部分可以进行合并，很自然的想到区间dp。状态为$dp[i][j]$ ，为字符串下标i到下标j间的最小压缩。

区间的合并有两种方式，一种是直接合并，最小压缩值为两段区间之和；另一种为压缩合并，最小压缩值为压缩区间的最小压缩值。

故转移可以写成:

  • $dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j])$
  • $dp[i][j] = dp[i][k]$ 当且仅当i到k为循环字符串，且k+1到j为i到k的循环节

第一种可以对每一个区间都进行判断，因为没有特殊要求。

第二种情况需要用到两个辅助数组，一个用于$O(1)$判断两段相邻同长度子串是否相等，另一个用于记录一段子串是否为循环字符串，并记录循环字符串最后一个循环节的初始下标。第一个辅助数组可以进行预处理，第二个可以在区间dp的时候进行同步更新。

代码

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

using namespace std;
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const unsigned long long P = 1e9 + 7;
const double eps = 1e-6;
int Next[N];
string s;
int dp[1005][1005],a[1005][1005],b[1005][1005];
void count(int i,int j){
    for(int k = i;k<=j;k++){
        dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]);
        int id = b[i][k];
        if(id!=-1){
            if(a[id][k]&&k-id+1==j-k){
                dp[i][j] = min(dp[i][j],dp[i][k]);
                b[i][j] = k+1;
            }
        }
    }
}
int main() {
    int n;
    cin>>n;
    cin>>s;
    memset(b,-1,sizeof b);
    memset(dp,0x3f,sizeof dp);
    for(int i = 0;i<n;i++)  dp[i][i] = 1;
    for(int i = 0;i<n;i++){
        for(int j = i;j<n;j++){
            int flag = 0;
            for(int k = 0;k<j-i+1&&j+k<n;k++){
                if(s[i+k]!=s[j+k+1]){
                    flag = 1;
                    break;
                }
            }
            a[i][j] = !flag;
            if(!flag){
                b[i][j] = i;
            }
        }
    }
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<=n-i;j++){
            count(j,j+i-1);
        }
    }
    cout<<dp[0][n-1]<<'\n';
    return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
最后编辑：2021-01-18