首页
登录 | 注册

思维-Gym - 101341B-好题(5-5-B)

给定一个字符串,问你是否可以移动两个数,让这个字符串中不出现”happiness”。如果是的话就输出两个位置。如果不能的话就输出no
如果happiness出现超过三次以上,一次只能破坏两个,所以一定是no
如果出现两次,记录每个的 h和i,将第一个的h和第二个的i调换即可。
如果出现一次,将第一个的h和i调换。
如果没有,输出 1 2
重点来了。数据可能是这样。
ahppiness,这样本来找不到,输出yes,但是移动12 后反而找到了。
很多人卡数据,应该是如果想输出固定的数,都会给你找到反例。。
怪不得我们wa了那么多次。。顺便提一下,第29个数据估计就是ahppiness
看的大神的代码,才明白了。我操,还是要读题啊。

#include <cstdio>
#include <iostream>
#include <map>
using namespace std;
int main()
{ //freopen("standard input","r",stdin);
    //freopen("output.txt","w",stdout);

    string s;
   string a="happiness";
   cin>>s;
   int link1 [200005];
   int link2[200005];
   int j=1;
   int sum=0;
   if(s.length()<=8)
   {  printf("YES\n");
     printf("1 2\n");
  return 0;
   }
   for(int i=0;i<s.length()-8;i++)
   {
       string l=s.substr(i,9);
     if(l==a)
     {   link1[j]=i+1;
          link2[j]=i+5;
          sum++;
          j++;
     }
   }
   if(sum>2)
      puts("NO");
      else if(sum==0)
      {puts("YES");
        int ans1=1;int ans2=2;
         map<char,int>mp;
         for(int i=0;i<s.length();i++)
         {  if(mp[s[i]]!=0)
             {  ans1=mp[s[i]];
                ans2=i+1;
                 break;
             }
              else mp[s[i]]=i+1;
         }
         printf("%d %d\n",ans1,ans2);

      }
   else if(sum==2)
      {   puts("YES");
          printf("%d %d\n",link1[1],link2[2]);}
   else
    {  puts("YES");
        printf("%d %d\n",link1[1],link2[1]);}
    return 0;
}


2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.008 s.
京ICP备10005923号