AcWing 4261. 孤独的照片

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 4261. 孤独的照片原题链接简单

作者：

4_3 , 2022-02-19 16:17:54 , 所有人可见 , 阅读 5344

60

7

记录每头牛左右两边有多少连续的不同种类的牛,计算这头牛的孤独照片，分三类：
1. 这头牛在照片中间，左牛数乘右牛数，l[i] * r[i]
2. 在照片左端点，照片长度至少3，右边有一头牛的情况不合格，r[i]可能< 1 ,max(r[i] - 1, 0)
3. 在照片右端点

小tips : long long永远的痛

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5e5 + 10;

int n, l[N], r[N];
char s[N];
long long ans;

int main()
{
    scanf("%d", &n);
    scanf("%s", s);

    for (int i = 0, g = 0, h = 0; i < n; i ++ )
    {
        if (s[i] == 'H') l[i] = g, g = 0, h ++;
        else l[i] = h, h = 0, g ++;
    }
    for (int i = n - 1, g = 0, h = 0; ~i; i --)
    {
        if (s[i] == 'H') r[i] = g, g = 0, h ++;
        else r[i] = h, h = 0, g ++;
    }
    for (int i = 0; i < n; i ++)
        if (l[i] + r[i] > 1)
        {
            long long cnt = (long long)l[i] * r[i] + max(0, l[i] - 1) + max(0, r[i] - 1);
            ans += cnt;
        }

    cout << ans << endl;

    return 0;
}

19 评论

我为什么不会做 2022-12-22 12:49

大佬们，~i是什么意思，不对我知道他什么意思，他为什么可以这么写呢

4_3 2022-12-22 13:32

-1 取反后是 0（搜反码和补码）， ~i 等于 i ！= -1

Jack676 2022-10-07 17:31

你可以这样写：

#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;

const int N = 5e5 + 10;

int n, l[N], r[N];
char s[N];
long long ans;

signed main()
{
    scanf("%d", &n);
    scanf("%s", s);

    for (int i = 0, g = 0, h = 0; i < n; i ++ )
    {
        if (s[i] == 'H') l[i] = g, g = 0, h ++;
        else l[i] = h, h = 0, g ++;
    }
    for (int i = n - 1, g = 0, h = 0; ~i; i --)
    {
        if (s[i] == 'H') r[i] = g, g = 0, h ++;
        else r[i] = h, h = 0, g ++;
    }
    for (int i = 0; i < n; i ++)
        if (l[i] + r[i] > 1)
        {
            int cnt = (long long)l[i] * r[i] + max(0, l[i] - 1) + max(0, r[i] - 1);
            ans += cnt;
        }

    cout << ans << endl;

    return 0;
}

天使降临到我身边 2022-03-23 17:03

十年九夏_3 12个月前

开两个变量少写个for

#include<iostream>
using namespace std;
const int N = 5e5+10;
int l[N],r[N];
int n;
int g,h,tg=5e5+9,th=5e5+9;//把tg,th初始化到大于n的地方
//tg,th用来记录前一个g、h的位置
int main()
{
    cin>>n;
    string s;
    cin>>s;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='G')
        {
            tg=i;//更新g的位置
            g++;
            l[i]=h;
            h=0;
            r[th]++;
        }
        else
        {
            th=i;//更新h的位置
            h++;
            l[i]=g;
            g=0;
            r[tg]++;
        }
    }
        //记得开long long 
    long long ans=0;
    for(int i=0;i<=n-1;i++)
        ans+=(long long)l[i]*r[i]+max(l[i]-1,0)+max(r[i]-1,0);
    cout<<ans;
}