AtCoder Beginner Contest 043 D - アンバランス / Unbalanced
题目链接:http://abc043.contest.atcoder.jp/tasks/arc059_b
Time limit : 2sec / Memory limit : 256MB
Score : 400 points
Problem Statement
Given a string t, we will call it unbalanced if and only if the length of t is at least 2, and more than half of the letters in t are the same. For example, both voodoo
andmelee
are unbalanced, while neither noon
nor a
is.
You are given a string s consisting of lowercase letters. Determine if there exists a (contiguous) substring of s that is unbalanced. If the answer is positive, show a position where such a substring occurs in s.
Constraints
- 2≦|s|≦105
- s consists of lowercase letters.
Partial Score
- 200 points will be awarded for passing the test set satisfying 2≦N≦100.
Input
The input is given from Standard Input in the following format:
s
Output
If there exists no unbalanced substring of s, print -1 -1
.
If there exists an unbalanced substring of s, let one such substring be sasa+1…sb (1≦a<b≦|s|), and print a b
. If there exists more than one such substring, any of them will be accepted.
Sample Input 1
needed
Sample Output 1
2 5
The string s2s3s4s5 = eede
is unbalanced. There are also other unbalanced substrings. For example, the output 2 6
will also be accepted.
Sample Input 2
atcoder
Sample Output 2
-1 -1
The string atcoder
contains no unbalanced substring.
题意:给定一个序列,如果某个子序列中的有一个字母的数量大于子序列长度的一半则为平衡序列。
题解:其实本题只要判断了相邻两个字母是否一样或者间隔一个的字母是否相同就能判断出是否有子序列满足平衡。在往后判断只是重复了上述的情况
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;
#define lowbit(x) (x&(-x))
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.141592653589793238462
#define INF 0x3f3f3f3f3f
#define mem(a) (memset(a,0,sizeof(a)))
typedef long long ll;
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
bool cmp(int x,int y)
{
return x>y;
}
const int N=;
const int mod=1e9+;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie();
int flag=;
string s;
cin>>s;
for(int i=;i<s.size()-;i++){
if(s[i]==s[i+]){
cout<<i+<<" "<<i+<<endl;
flag=;
break;
}
else if(i<s.size()-&&s[i]==s[i+]){
cout<<i+<<" "<<i+<<endl;
flag=;
break;
}
}
if(!flag)
cout<<-<<" "<<-<<endl;
return ;
}
最新文章
- json返回数据时提示字符串超出长度
- compile vim with lua &; python support
- php随机生成验证码
- 网页设计中常用的19个Web安全字体
- javaweb回顾第一篇servlet的学习和理解
- [分享]运维分享一一阿里云linux系统mysql密码修改脚本
- NYOJ 士兵杀敌(三)
- TortoiseSVN文件夹及文件图标不显示解决方法 [转]
- hadoop 2.2.0 编译报错: [ERROR] class file for org.mortbay.component.AbstractLifeCycle not found
- java注释 命名 数据类型 基本类型转换 位运算符 逻辑运算符 三目运算符
- php实现无限级树型菜单(函数递归算法)
- popen3
- 【原创】Android 系统稳定性 - ANR(二)
- TCP的三次握手(建立连接)与 四次挥手(关闭连接)
- CSS之 absoulte 属性
- UE3中的时间
- TP5调用微信JSSDK 教程 —— 之异步使用
- Scala笔记
- JS 解析JSON实现导序
- bzoj5068: 友好的生物