Codeforces Round #293 (Div. 2)

A. Vitaly and Strings

题意：两个字符串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 <cstdio>

#include <iostream>

#include <cstring>

#include <string>

#include <algorithm>

#include <cmath>

#include <vector>

#include <map>

#include <set>

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;

}

B. Tanya and Postcard

字符串处理：字符查找
记录s，t各自的大小写字母的数量，然后累加完全匹配的cnty和不完全匹配的cntw
这道题题目我没读懂，cntw不完全匹配意思是：只是大小不相同

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <map>

#include <cstring>

#include <string>

#include <set>

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;

}

C. Anya and Smartphone

无算法
统计划屏的次数，如果在第一屏则不用，只要每次交换与前面数字的顺序就行了
注意：ans开long long
好吧，这道题是最水的，主要是题目很难读懂，可以从Note里猜出题目意思

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <string>

#include <map>

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;

}