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++;
if(rx!=x) return 3;
while(s[rx][ry-1]=='#') ry--;
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;
}
|
