嘘~ 正在从服务器偷取页面 . . .

[A_


[ARC059D] Unbalanced 题解

题目链接:[ARC059D] Unbalanced

题意

给出长度为 nn 的字符串 ss

求区间 [l,r][l,r] ,其中 l<rl<r ,使得该子串中有一种字母出现的次数严格大于该子串长度的一半

输入格式

一行,字符串 ss

输出格式

如果有解,输出 l,rl,r 。如果没有符合条件的子串,输出两个 11

数据范围

1n1051n105

容易发现形如 awaaa 的串串都合法,并且所有合法的串的子串中至少有其中一种

那么我们只需要找到这样子的串然后直接输出就好啦!

所以这题到底是 D 还是 B 啊(好像这场从 C 开始排序的)

时间复杂度 O(n)O(n)

代码:(太短了我都不知道怎么写比较好看了

cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

char s[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (s + 1);
    for(int i = 1; s[i]; i++)
    {
        if(s[i] == s[i + 1]) {
            cout << i << ' ' << i + 1 << '\n'; return 0;
        }else if(s[i] == s[i + 2]) {
            cout << i << ' ' << i + 2 << '\n'; return 0;
        }
    }
    cout << "-1 -1" << '\n';
    return 0;
}

文章作者: q779
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 q779 !
评论
你认为这篇文章怎么样?
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v3.1.3
  目录