ACM模版

很少打 CF，最近开始正儿八经的打 CF 了，以前不打是因为看英语题感觉累，但是以后这个是避免不了的，平时也需要多训练才行，所以现在开始折腾 CF 了……

由于前三题都十分简单，只要看懂题，就没有什么困难的，所以题解就写在一起吧。

A - Mike and palindrome

描述

题解

只能修改一个字符，并且必须修改一个字符，然后保证回文，问，是否可行？可行输出 YES，否则 NO。

这里实际上就是判断对称，看看前后对应位置有几个不同，如果有一个不同，那么一定是 YES，如果你以为这样就能判定其他都为 NO，那就错了，比如说，abcba，这个字符串原本就回文，但是我们可以通过修改 c 为任意字符保证修改后的还是回文，所以这种情况依然是 YES，这个题也就这么一个坑。

代码

#include <iostream>
#include <string>

using namespace std;

int main(int argc, const char * argv[])
{
    string s;
    cin >> s;

    int cnt = 0;
    int mid = ((int)s.length() + 1) / 2;
    for (int i = 0; i < mid; i++)
    {
        if (s[i] != s[s.length() - 1 - i])
        {
            cnt++;
        }
    }

    if (cnt != 1)
    {
        if (cnt == 0 && s.length() % 2)
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
    }
    else
    {
        cout << "YES\n";
    }

    return 0;
}

B-Mike and strings

描述

题解

每个字符串都可以进行多次操作，每次操作将头字符放到尾，问，所有字符串一共通过多少次操作可以实现相同？

注意看，这个题 1≤n≤50且s.length()≤50 1 ≤ n ≤ 50 且 s . l e n g t h ( ) ≤ 50 ，数据十分小，别说 O(n3) O ( n 3 ) ，连 O(n4) O ( n 4 ) 都是 15ms 过。这个好像可以 dp 搞，貌似也是 O(n3) O ( n 3 ) ，我用的是暴力解题，比较直观的 O(n4) O ( n 4 ) （代码 One），可以优化到 O(n3) O ( n 3 ) （代码 Two），既然是暴力，也就不用多说什么了，就酱。

代码

One：

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

const int MAXN = 200;
const int INF = 0x3f3f3f3f;

int cnt[MAXN];
int cnt_[MAXN];
string s[MAXN];

int main(int argc, const char * argv[])
{
    int n;
    cin >> n;

    cin >> s[0];
    for (int i = 0; i < s[0].length(); i++)
    {
        cnt[s[0][i]]++;
    }
    for (int i = 1; i < n; i++)
    {
        cin >> s[i];
        memset(cnt_, 0, sizeof(cnt_));
        if (s[i].length() != s[0].length())
        {
            cout << "-1\n";
            return 0;
        }
        for (int j = 0; j < s[i].length(); j++)
        {
            cnt_[s[i][j]]++;
            if (cnt_[s[i][j]] > cnt[s[i][j]])
            {
                cout << "-1\n";
                return 0;
            }
        }
    }

    int res = INF;
    int flag = 0;
    for (int i = 0; i < n; i++)
    {
        int temp = 0;
        for (int j = 0; j < n; j++)
        {
            if (i == j)
            {
                continue;
            }
            flag = 0;
            for (int k = 0; k < s[0].length(); k++)
            {
                if (s[i][0] == s[j][k])
                {
                    flag = 1;
                    for (int l = 1; l < s[0].length(); l++)
                    {
                        if (s[i][l] != s[j][(k + l) % s[0].length()])
                        {
                            flag = 0;
                            break;
                        }
                    }
                }
                if (flag)
                {
                    temp += k;
                    break;
                }
            }
        }
        res = min(res, temp);
    }

    if (res == 0 && flag == 0 && n != 1)
    {
        cout << -1 << '\n';
    }
    else
    {
        cout << res << '\n';
    }

    return 0;
}

Two：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 55;
const int INF = 0x3f3f3f3f;

char s[MAXN][MAXN];
int cnt[MAXN];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
    }

    int len = (int)strlen(s[1]);

    int tag = 1, flag = 0;
    for (int k = 2; k <= n; k++)
    {
        flag = 0;
        for (int i = 0; i < len; i++)
        {
            if (s[k][i] == s[1][0])
            {
                int z = 0, j = i;
                for (; z < len; z++, j++)
                {
                    if (s[k][j % len] != s[1][z])
                    {
                        break;
                    }
                }
                if (z == len)
                {
                    cnt[k] = i;
                    flag = 1;
                    break;
                }

            }
        }
        if (!flag)
        {
            tag = 0;
            break;

        }
    }

    cnt[1] = 0;

    int len_ = 0;   // 循环节，比较坑
    for (int i = 1; i < len; i++)
    {
        if (s[1][i] == s[1][0])
        {
            int flag = 1;
            for (int j = 1; j < len; j++)
            {
                if (s[1][(i + j) % len] != s[1][j])
                {
                    flag = 0;
                    break;
                }
            }
            if (flag)
            {
                len_ = i;
                break;
            }
        }
    }

    if (!tag)
    {
        cout << "-1" << endl;
    }
    else
    {
        if (len_)
        {
            len = len_;
        }
        int ans = INF;
        for (int i = 0; i < len; i++)
        {
            int tmp = 0;
            for (int j = 1; j <= n; j++)
            {
                tmp += cnt[j];
                cnt[j] = (cnt[j] + 1) % len;
            }
            ans = min(tmp, ans);
        }
        cout << ans << endl;
    }

    return 0;
}

C-Mike and gcd problem

描述

题解

这个题一开始没有看懂题，以为只能修改一次，问能否实现 gcd(b1,b2,⋯,bn)>1 g c d ( b 1 , b 2 , ⋯ , b n ) > 1 ，谁知道我搞错了，原来是问最少修改多少次能够实现它。

那么我们很容易能够想到实现它 gcd(b1,b2,⋯,bn)=2 g c d ( b 1 , b 2 , ⋯ , b n ) = 2 应该可以满足修改次数最少。

那么问题来了，什么时候满足 YES 呢？

经过分析我们可以知道：
设 x=ai,y=ai+1 x = a i , y = a i + 1 ，
那么一次修改， ai=x−y,ai+1=x+y a i = x − y , a i + 1 = x + y
接着二次修改， ai=−2y,ai+1=2x a i = − 2 y , a i + 1 = 2 x

所以，这里的不管神马情况一定是 YES，那么剩下的就是分析什么时候修改一次什么时候两次呢？

根据奇偶性，我们可以知道，相邻两个都是奇数时只需要一次即可，一个奇数一个偶数时需要两次，那么这个问题直接贪心即可了。貌似这个题也能 dp……

代码

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN = 1e6 + 10;

int a[MAXN];

int gcd(int x, int y)
{
    if (!x || !y)
    {
        return x > y ? x : y;
    }
    for (int t; t = x % y, t; x = y, y = t) ;
    return y;
}

int main(int argc, const char * argv[])
{
    int n;

    while (cin >> n)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", a + i);
        }

        int gd = a[1];
        for (int i = 2; i <= n; i++)
        {
            gd = gcd(gd, a[i]);
        }

        printf("YES\n");

        if (gd != 1)
        {
            printf("0\n");
            continue;
        }

        int res = 0;
        for (int i = 1; i <= n; i++)
        {
            if (a[i] & 1)
            {
                if (i == n)
                {
                    res += 2;
                }
                else if (a[i + 1] & 1)
                {
                    res++;
                }
                else
                {
                    res += 2;
                }
                i++;
            }
        }

        cout << res << '\n';
    }

    return 0;
}