Codeforces 801 A.Vicious Keyboard & Jxnu Group Programming Ladder Tournament 2017江西师大新生赛 L1-2.叶神的字符串

Tonio has a keyboard with only two letters, "V" and "K".

One day, he has typed out a string s with only these two letters. He really likes it when the string "VK" appears, so he wishes to change at most one letter in the string (or do no changes) to maximize the number of occurrences of that string. Compute the maximum number of times "VK" can appear as a substring (i. e. a letter "K" right after a letter "V") in the resulting string.

Input

The first line will contain a string s consisting only of uppercase English letters "V" and "K" with length not less than 1 and not greater than 100.

Output

Output a single integer, the maximum number of times "VK" can appear as a substring of the given string after changing at most one character.

Examples

Input

VK

Output

Input

VV

Output

Input

Output

Input

VKKKKKKKKKVVVVVVVVVK

Output

Input

KVKV

Output

Note

For the first case, we do not change any letters. "VK" appears once, which is the maximum number of times it could appear.

For the second case, we can change the second character from a "V" to a "K". This will give us the string "VK". This has one occurrence of the string "VK" as a substring.

For the fourth case, we can change the fourth character from a "K" to a "V". This will give us the string "VKKVKKKKKKVVVVVVVVVK". This has three occurrences of the string "VK" as a substring. We can check no other moves can give us strictly more occurrences.

这个题和师大的新生赛的一个题好像好像。。。

Jxnu Group Programming Ladder Tournament 2017

L1-2 叶神的字符串

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 23 Accepted Submission(s) : 10

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

众所周知，ACS协会会长叶神学习特别好，算法能力也强，作为一个弱渣的大豪哥特别崇拜叶神，觉得‘Y’‘S’这两个字符特别厉害，所以大豪哥的一个键盘上就只有Y,S两个键，大豪哥用这个键盘打出了一个字符串s，但是他特别的不满意，所以他想改变字符串s中的一个字符（也可以不改变），使得字符串s中可以截取出最大数量的“YS”

Input

多组输入至文件结尾。
每组测试数据输入一串由'Y','S'组成的字符串。（字符串长度最多为10000）

Output

输出至多一次修改后最多有多少个“YS”

Sample Input

YYYS

Sample Output

唉，真是让人无语。首先是这个师大的。

代码1:

#include<stdio.h>
#include<string.h>
int main(){
    char a[10050];
    int i,flag[10050],len,num1,num2;
       while(gets(a)){
          len=strlen(a);
          for(i=0;i<len;i++)
            flag[i]=0;
            num1=0;
          for(i=1;i<len;i++){
            if(a[i]=='S'&&a[i-1]=='Y'){
                num1++;
                flag[i]=1;
                flag[i-1]=1;
            }
          }
            num2=0;
            for(i=1;i<len;i++){
                if(flag[i]==0&&flag[i-1]==0){
                       num2++;
                       flag[i]=1;     //其实这里去掉更好
                       flag[i-1]=1;   //楼上+1。。。
                       if(a[i]=='Y'&&a[i-1]=='S')
                        num2--;
                }
            }
        if(num2>=1)
            printf("%d
",num1+1);
        else
            printf("%d
",num1);
    }
    return 0;
}

修改了一下:

代码2:

#include<stdio.h>
#include<string.h>
int main(){
    char a[10050];
    int i,flag[10050],len,num1,num2;
    while(gets(a)){
    len=strlen(a);
    for(i=0;i<len;i++)flag[i]=0;
    num1=0;
    memset(flag,0,sizeof(flag));
    for(i=1;a[i]!='';i++){
        if(a[i]=='S'&&a[i-1]=='Y'){
            num1++;
            flag[i]=1;
            flag[i-1]=1;
        }
    }
    num2=0;
    for(i=1;i<len;i++){
        if(flag[i]==0&&flag[i-1]==0){
            num2++;
            flag[i]=1;
            flag[i-1]=1;
            if(a[i]=='Y'&&a[i-1]=='S')num2--;
            else break;
        }
    }
    if(num2>=1)
        printf("%d
",num1+1);
    else
        printf("%d
",num1);
    }
    return 0;
}

其实还有一个代码，但是少了个判断条件，想法是一样的，不贴了。。。

然后！！！在做了cf的这个类似题之后发现了新的问题。。。

等会再说吧，要贴cf的代码了。。。

代码1:

#include<stdio.h>
#include<string.h>
int main(){
    char a[105];
    int i,flag[105],len,num1,num2;
    while(gets(a)){
    len=strlen(a);
    for(i=0;i<len;i++)flag[i]=0;
    num1=0;
    memset(flag,0,sizeof(flag));
    for(i=1;a[i]!='';i++){
        if(a[i]=='K'&&a[i-1]=='V'){
            num1++;
            flag[i]=1;
            flag[i-1]=1;
        }
    }
    num2=0;
    for(i=1;i<len;i++){
        if(flag[i]==0&&flag[i-1]==0){
            num2++;        //这里和那个师大的不一样了。
            if(a[i]=='V'&&a[i-1]=='K')num2--;
            else break;
        }
    }
    if(num2>=1)
        printf("%d
",num1+1);
    else
        printf("%d
",num1);
    }
    return 0;
}

VKKVVVKVKVK这组数据如果改成师大的那个字母就wa了，因为flag[]那里错了，(第二个循环里的标记去掉就可以了) 师大的数据水过了。。。

然后！！！cf的这个可以暴力写。

代码2:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<cstdlib>
#include<string>
#define eps 0.000000001
typedef long long ll;
typedef unsigned long long LL;
using namespace std;
const int N=1005000;
char str[N];
char b[N];
int main(){
    while(gets(str)){
        int len=strlen(str);int maxx=0;
        if(len==1){cout<<0<<endl;continue;}
        for(int i=0;i<len-1;i++)if(str[i]=='V'&&str[i+1]=='K')
        maxx++;
        for(int i=0;i<len;i++){
            char c=str[i];int ans=0;
            if(str[i]=='V')str[i]='K';
            else str[i]='V';
            for(int j=0;j<len-1;j++){
                if(str[j]=='V'&&str[j+1]=='K')ans++;
            }
            maxx=max(maxx,ans);
            str[i]=c;
        }
        cout<<maxx<<endl;
    }
}

一开始有点没太懂

以VKVKVKVVVV这个为例:第一次变成 KKVKVKVVVV，第二次 VVVKVKVVVV，还是3。。。VKKKVKVVVV ，VKVVVKVVVV，3

每次看他有几个Vk，就这样，最后取最大的，到后面的时候maxx=4，ans=4 所以还是4，但是用暴力写师大的就会超时。

暴力写时间复杂度是O(n^2)，那个flag[]的时间复杂度是O(n)，

因为师大的字符串长度是10000，所以暴力过不了，会超时。而cf的这个题是100，所以没超时。。。