「NBUT 2014 校赛·网络同步赛」题解 (未完成...)

写于 2014 年 05 月 05 日 15 时 08 分
更新于 2022 年 12 月 31 日 15 时 33 分

大纲

1. Minecraft Server Bug
2. Beautiful Walls

　　这次比赛由 Hungar，8Mao 以及我负责的。明明都读研了，还诈尸回来出题——归结起来大概是因为各种面试不顺吧，想来虐虐学弟妹们怒刷存在感。结果网络赛还是被虐得死去活来。（果然我是蒟蒻 (◓Д◒)✄╰⋃╯

　　好了废话不多说，还是直接上题解吧。

Minecraft Server Bug

　　题意大概就是说一排岩浆和水，你要拿一桶水和岩浆，并且水的下标小于岩浆。

　　为了更便于理解，我们从后往前做。首先将序列读进来之后从后往前遍历——若是岩浆，那么岩浆数加一，如果是水，那么这桶水能选择后面岩浆的任意一桶，也就是说答案加上当前的岩浆数即可。

注意用 __int64。

#include <iostream>
using namespace std;

int main()
{
    int n;
    char ch[1000005];
    while(~scanf("%d\n", &n))
    {
        char tmp;
        for(int i = 0; i < n; i++)
        {
            scanf("%c%c", ch + i, &tmp);
        }
        
        __int64 ans = 0;
        int cnt = 0;
        for(int i = n - 1; i >= 0; i--)
        {
            if(ch[i] == 'L') cnt++;
            else ans += (__int64)cnt;
        }
        
        printf("%I64d\n", ans);
    }
    
    return 0;
}

Beautiful Walls

　　一堵墙，每单位高度不定。你需要选择其中任意连续的墙，使得你选择的墙每单位的高度都是唯一的——问有多少种选法。

　　先求出总的种数，然后求不满足的数量，最后用总数减去不满足数即为答案。

#include <iostream>
#include <cstring>
using namespace std;
#define lint long long
#define N 100005
int p[N], A[N];
lint solution(lint n)
{
    memset(p, -1, sizeof(p));
    lint ans = n * (n + 1) / 2, Max = 0;
    for(lint i=0; i < n; ++i)
    {
        if(~p[A[i]])
        {
            if(Max < p[A[i]]) Max = p[A[i]];
            p[A[i]] = i + 1;
        }
        else
        {
            p[A[i]] = i + 1;
        }
        ans -= Max;
    }
    return ans;
}

int main()
{
    int n, x;
    while(~scanf("%d", &n))
    {
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", A + i);
        }
        printf("%lld\n", solution(n));
    }
    return 0;
}