ccbeginner

ZJ c462

Oct 13th, 2020
54
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Judge: https://zerojudge.tw/ShowProblem?problemid=c462
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. int nums[100000] = {0};
  7. int bound = 0;
  8.  
  9. // My idea is to turn the string to several numbers, such as
  10. // 'ABabaA' => [2,3,1]
  11. // 'IJjiHW' => [2,2,2]
  12. // 'dwFwGe' => [2,1,1,1,1]
  13. // 'ojojowP' => [6,1]
  14. // Got the pattern? The numbers show the amount of consecutive letters in the same case (both in lower or upper)
  15. //
  16. // Now the problem would be:
  17. //     find the maximum length in these nums satisfy the conditions:
  18. //         (nums[l] >= k, nums[r] >= k, nums[mid] == k, l < mid < r)
  19. //     Let us call the nums[l] 'head', nums[mid] 'body', and nums[r] 'tail'.
  20. int main(){
  21.     // the variable k we declare
  22.     int k;
  23.     cin >> k;
  24.     // the input string
  25.     string s;
  26.     cin >> s;
  27.     // the variable 'cnt' represent the current number of same-case-letters
  28.     int cnt = 0;
  29.     // Remember, string's indexes start with 0, not 1
  30.     for(int i = 0; i < s.size(); ++i){
  31.         // s[i] is the current letter, and s[i-1] is the previous letter
  32.         if(i == 0){
  33.             // the first one, of course cnt is 1
  34.             cnt = 1;
  35.         }else if('a' <= s[i] && s[i] <= 'z'){
  36.             if('a' <= s[i-1] && s[i-1] <= 'z'){
  37.                 // both s[i] and s[i-1] are lowercase letters
  38.                 cnt += 1;
  39.             }else if('A' <= s[i-1] && s[i-1] <= 'Z'){
  40.                 // s[i] and s[i-1] are in different case
  41.                 nums[bound++] = cnt;
  42.                 cnt = 1;
  43.             }
  44.         }else if('A' <= s[i] && s[i] <= 'Z'){
  45.             if('a' <= s[i-1] && s[i-1] <= 'z'){
  46.                 // s[i] and s[i-1] are in different case
  47.                 nums[bound++] = cnt;
  48.                 cnt = 1;
  49.             }else if('A' <= s[i-1] && s[i-1] <= 'Z'){
  50.                 // both s[i] and s[i-1] are uppercase letters
  51.                 cnt += 1;
  52.             }
  53.         }
  54.         if(i == s.size()-1){
  55.             // This step is important!!!
  56.             // At last one, you may miss to add cnt to nums[]
  57.             nums[bound++] = cnt;
  58.         }
  59.     }
  60.     // Here we have to find consecutive numbers as many as possible
  61.     // Remember, the head and the tail of the sequence could be more than k letters
  62.     int tail = 0; // 1 represents the current num could be the tail but not for body
  63.     int ans = 0; // the current best answer
  64.     int cur = 0; // the current answer
  65.     for(int i = 0; i < bound; ++i){
  66.         if(nums[i] == k){ // body
  67.             if(tail == 1){
  68.                 cur = 2;
  69.             }else{
  70.                 cur += 1;
  71.             }
  72.             tail = 0;
  73.         }else if(nums[i] > k){ // head or tail
  74.             if(cur == 0){ // no body or tail, so let nums[i] be head would be better
  75.                 cur += 1;
  76.             }else if(tail == 1){ // previous tail be head, nums[i] be tail
  77.                 cur = 2;
  78.             }else{ //
  79.                 cur += 1;
  80.             }    
  81.             tail = 1;
  82.         }else{ // nums[i] cannot be part of answer
  83.             cur = 0;
  84.             tail = 0;
  85.         }
  86.         // maintain the best answer
  87.         ans = max(ans, cur);
  88.     }
  89.     cout << ans * k << '\n';
  90.     return 0;
  91. }
  92. // It may seems that I wrote a LONG code, however I wrote lots of comments too.
  93. // You may delete all these comments and see how short the code is :-)
RAW Paste Data