CodeForces - 1181C （思维）

110 阅读 0 评论 73 点赞

我是靠谱客的博主迷路凉面，这篇文章主要介绍CodeForces - 1181C （思维），现在分享给大家，希望可以做个参考。

题目链接：https://vjudge.net/contest/349554#problem/A

思路：

当时想统计一列中的连续出现的国旗，但是后来发现连续不一定编号一致，那样统计只会少统计。

eg：

abva

bbtb

aaaa

bbbb

cccc

得到就不对。

所以以每个元素作为国旗的左上角，统计这个单元所拥有的国旗的数量就好了。

如果一个角可以统计多个国旗，就利用前缀和的思想就能统计所有连续出现的合法的国旗了。

参考文章：https://www.cnblogs.com/wzj-xhjbk/p/11040092.html

代码：

复制代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
char ss[N][N];
int n,m,a[N][N] = {0};
int main(void)
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",ss[i]+1);
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<=m;j++)
        {
            if(ss[i][j] == ss[i+1][j]) a[i][j] = a[i+1][j] + 1;
            else a[i][j] = 1;
        }
    }
    long long ans = 0;
    for(int i=1;i<=n;i++)
    {
        int tp = 0;
        for(int j=1;j<=m;j++)
        {
            int d = a[i][j];
            if(i+3*d-1<=n && a[i][j] == a[i+d][j] && a[i][j] <= a[i+d*2][j] && ss[i][j] != ss[i+d][j] && ss[i+d][j] != ss[i+2*d][j])
            {
                //注意一定要考虑间距相同。
                if(tp>0 && ss[i][j] == ss[i][j-1] && ss[i+d][j] == ss[i+d][j-1] && ss[i+d*2][j] == ss[i+d*2][j-1]
                   && a[i][j-1] == d && a[i+d][j-1] == d && a[i+d*2][j-1] >= d) tp++;
                else tp = 1;
                ans += tp;
            }
            else tp = 0;
        }
    }
    printf("%lldn",ans);
    return 0;
}

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
char ss[N][N];
int n,m,a[N][N] = {0};
int main(void)
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",ss[i]+1);
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<=m;j++)
        {
            if(ss[i][j] == ss[i+1][j]) a[i][j] = a[i+1][j] + 1;
            else a[i][j] = 1;
        }
    }
    long long ans = 0;
    for(int i=1;i<=n;i++)
    {
        int tp = 0;
        for(int j=1;j<=m;j++)
        {
            int d = a[i][j];
            if(i+3*d-1<=n && a[i][j] == a[i+d][j] && a[i][j] <= a[i+d*2][j] && ss[i][j] != ss[i+d][j] && ss[i+d][j] != ss[i+2*d][j])
            {
                //注意一定要考虑间距相同。
                if(tp>0 && ss[i][j] == ss[i][j-1] && ss[i+d][j] == ss[i+d][j-1] && ss[i+d*2][j] == ss[i+d*2][j-1]
                   && a[i][j-1] == d && a[i+d][j-1] == d && a[i+d*2][j-1] >= d) tp++;
                else tp = 1;
                ans += tp;
            }
            else tp = 0;
        }
    }
    printf("%lldn",ans);
    return 0;
}