现在的位置: 首页 > 综合 > 正文

NBUT 1553 Beautiful Wall

2019年02月13日 ⁄ 综合 ⁄ 共 771字 ⁄ 字号 评论关闭

这道题TLE了n次,不过A了之后反而不觉得难了。


把head作为对于每一个元素,往前能够达到最长的合法区间的最前端,则不难理解,head该如何选取。


有两种情况:

1.当前元素在前面出现过,则head就是上一次出现过的位置后的一个和head本身比较后的较大者;

2.当前元素没出现过,则head是最近一次出现过的被重复过的元素了。


那么为什么对于每一个元素,ans += i - head + 1呢?


是这样的,对于第i个元素,向前搜,则可选的方法,又不与后面选取结果重复的话,则是:

head ~ i, head+1 ~ i,head+2 ~ i,……,i;

一共i - head + 1种。


AC代码:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

const int MAXN = 100001;
bool v[MAXN];
int s[MAXN];
int wall[MAXN];
int i, j, k;
int N;
int head;
__int64 ans;

int main()
{
        #ifdef BellWind
                freopen("B.in", "r", stdin);
        #endif // BellWind

        while (~scanf("%d", &N))
        {
                ans = 0;
                head = 1;
                memset(v, 0, sizeof(v));

                for (i = 1; i <= N; i++)
                {
                        scanf("%d", &wall[i]);
                        if (v[wall[i]]) {head = max(head, s[wall[i]] + 1);}
                        ans += i - head + 1;
                        s[wall[i]] = i;
                        v[wall[i]] = true;
                }
                printf("%I64d\n", ans);
        }


        return 0;
}

抱歉!评论已关闭.