Codeforces Round #293 (Div. 2)-白红宇

Codeforces Round #293 (Div. 2)

阅读量：5911 次

发布时间：2019-06-19

本文共 2728 字，大约阅读时间需要 9 分钟。

题意：两个字符串s，t，是否存在满足：s < r < t 的r字符串

字符转处理：字典序排序

很巧妙的方法，因为s < t，只要找比t字典序稍微小一点的和s比较就行了

具体方法和数字减1相类似，从"个位"减1，如果是0，从前面借1

!strcmp (t, s)：如果t < s 或者 t > s (不可能)则输出，t == s 则输出NO

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              using namespace std;const int MAXN = 1e6 + 10;const int INF = 0x3f3f3f3f;int main(void){ //freopen ("A.in", "r", stdin); char s[110], t[110]; while (~scanf ("%s %s", &s, &t)) { int cnt = strlen (s) - 1; while (t[cnt] == 'a' && cnt >= 0) { t[cnt] = 'z'; cnt--; } t[cnt]--; (!strcmp (t, s)) ? puts ("No such string") : printf ("%s\n", t); } return 0;}

字符串处理：字符查找

记录s，t各自的大小写字母的数量，然后累加完全匹配的cnty和不完全匹配的cntw

这道题题目我没读懂，cntw不完全匹配意思是：只是大小不相同

#include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            using namespace std;const int MAXN = 2e5 + 10;const int INF = 0x3f3f3f3f;int main(void){ //freopen ("B.in", "r", stdin); char s[MAXN], t[MAXN]; int m1[30], m2[30], m3[30], m4[30]; while (cin >> s >> t) { memset (m1, 0, sizeof (m1)); memset (m2, 0, sizeof (m2)); memset (m3, 0, sizeof (m3)); memset (m4, 0, sizeof (m4)); for (int i=0; s[i]!='\0'; ++i) { if (s[i]>='a' && s[i]<='z') m1[s[i] - 'a']++; else m2[s[i]-'A']++; } for (int i=0; t[i]!='\0'; ++i) { if (t[i]>='a' && t[i]<='z') m3[t[i] - 'a']++; else m4[t[i]-'A']++; } int cnty = 0, cntw = 0; for (int i=0; i<26; ++i) { int d = min (m1[i], m3[i]); m1[i] -= d; m3[i] -= d; cnty += d; d = min (m2[i], m4[i]); m2[i] -= d; m4[i] -= d; cnty += d; } for (int i=0; i<26; ++i) { int d = min (m1[i], m4[i]); m1[i] -= d; m4[i] -= d; cntw += d; d = min (m2[i], m3[i]); m2[i] -= d; m3[i] -= d; cntw += d; } cout << cnty << " " << cntw << endl; } return 0;}

无算法

统计划屏的次数，如果在第一屏则不用，只要每次交换与前面数字的顺序就行了

注意：ans开long long

好吧，这道题是最水的，主要是题目很难读懂，可以从Note里猜出题目意思

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           using namespace std;const int MAXN = 1e5 + 10;const int INF = 0x3f3f3f3f;int num[MAXN];int pos[MAXN];int main(void){ //freopen ("C.in", "r", stdin); int n, m, k; while (~scanf ("%d%d%d", &n, &m, &k)) { int x; for (int i=1; i<=n; ++i) { scanf ("%d", &x); pos[x] = i; num[i] = x; } long long ans = 0; for (int i=1; i<=m; ++i) { scanf ("%d", &x); int p = pos[x]; ans += (p / k); if (p % k) ans += 1; if (p == 1) continue; int y = num[p-1]; num[p-1] = x; num[p] = y; pos[y]++; pos[x]--; } printf ("%I64d\n", ans); } return 0;}