前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Marvelous Necklace Gym - 102020M

Marvelous Necklace Gym - 102020M

作者头像
Lokinli
发布2023-03-09 19:27:56
1560
发布2023-03-09 19:27:56
举报
文章被收录于专栏:以终为始以终为始

M - Marvelous Necklace

Gym - 102020M 

&:前缀和。

代码语言:javascript
复制
#include <cstdio>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

char s[200005];
struct node
{
    int A,B;
} t[200005];
int main()
{
    int a,b;
    while(~scanf("%s", s))
    {
        memset(t,0,sizeof(t));
        int n = strlen(s);
        a = 0;
        b = 0;
        for(int i = 0; i < n; i ++)
        {
            if(s[i] == 'A') a++;
            else if(s[i] == 'B')b++;
        }
        for(int i = n; i < n * 2; i ++)
        {
            s[i] = s[i - n];
        }
        if(a % 2 != 0 || b % 2 != 0)
        {
            printf("NO\n");
        }
        else
        {
            int idx,idy;
            int A, B;
            A = 0;
            B = 0;
            idx = idy = 0;
            for(int i = 0; i < 2 * n; i ++)
            {
                if(s[i] == 'A')
                {
                    if(i == 0)
                    {
                        t[i].A ++;
                        t[i].B = 0;
                    }
                    else
                    {
                        t[i].A ++;
                        t[i].A += t[i - 1].A;
                        t[i].B = t[i - 1].B;
                    }
                }
                else if(s[i] == 'B')
                {
                    if(i == 0)
                    {
                        t[i].B ++;
                        t[i].A = 0;
                    }
                    else
                    {
                        t[i].B ++;
                        t[i].B += t[i - 1].B;
                        t[i].A = t[i - 1].A;
                    }
                }
            }

            for(int i = n; i < n * 2; i ++)
            {
                t[i].A -= t[i - n].A;
                t[i].B -= t[i - n].B;
            }

            int flag = 0;

           for(int i = n / 2; i < 2 * n; i ++)
            {
                if(t[i].A - t[i - n/2].A== a / 2 &&  t[i].B - t[i - n / 2].B == b / 2)
                {
                    flag = 1;
                    idx = i;
                    break;

                }
            }

            if(!flag) printf("NO\n");
            else
            {
                idx += 2;
                if(idx > n) idx = 1;
                idy = idx + n/ 2;
                if(idy > n) {idy = idy - n;}
                int dx = min(idx,idy);
                int dy = max(idx,idy);
                printf("YES\n%d %d\n",dx,dy);
            }
        }
    }
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-02-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • M - Marvelous Necklace
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档