2018黑龙江ACM省赛部分题解（hdu6480 hdu6484 hdu6486 hdu6489)(待更新）

新博客地址：https://blackbatty.github.io/

A - A Count Task

本题大概题意就是输入一个字符串，求它有多少个子字符串只包含一种小写字母。

我们大可以进行一次遍历，统计他相同的小写字母个数cnt，在求出它cnt+1的组合数。C(cnt + 1)取2,~~我也不知道这个正确的读法是怎么读的23333。~~

AC代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;
char s[maxn];

int main() {
    int t, len;
    ll ans = 0, cnt = 0;
    scanf("%d", &t); //数据组数
    while (t--) {
        ans = 0;
        scanf("%s", s);
        len = strlen(s);
        for (int i = 0; i < len; i++) {
            cnt = 1; //初始化次数
            while (i + 1 < len) {
                if (s[i] == s[i + 1]) {
                    cnt++;
                    i++;
                } else break;
            }
            ans += cnt * (cnt + 1) / 2;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

E - A Hard Allocation

~~这题才是真正的签到题！！！然而我却读错了题目。~~

这题思路没啥说的，就是看它的摸是否为0，是的话就输出0，否则输出1。因为它求的是获得最多蛋糕的人x与获得最少蛋糕的人u的差值是多少，我们稍微模拟下就知道如果不能平均分的话，最小就是相差1了。

AC代码：

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t, m, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        if (n % m == 0) printf("0\n");
        else printf("1\n");
    }
    return 0;
}

G - Flower

题目大致意思：给你n盆花的高度，问你修剪n - 1盆的高度，每次只能修剪1高度，能否最终修剪至所有花高度相同。

我们可以这么去想，找到最高的那一盆H_MAX不动，其他的每次加一，加到最高的那盆花的高度所需次数cnt，假如cnt大于等于H_MAX，则无法使所有花的高度相同，否则输出cnt。

AC代码：

#include <bits/stdc++.h>

using namespace std;
const int maxn = 100000 + 5;
int a[maxn] = {0};

int main() {
    int t, n, maxx, cnt = 0;
    scanf("%d", &t);
    while (t--) {
        maxx = -1, cnt = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            if (maxx < a[i]) maxx = a[i];
        }
        for (int i = 0; i < n; i++) {
            if (i == maxx) continue;
            cnt += (maxx - a[i]);
        }
        if (cnt >= maxx) printf("-1\n");
        else printf("%d\n", cnt);
    }
    return 0;
}

J - The puzzle

大致题意：给你一个1～n的序列，求它排成递增序列所需要的最小次数。

一开始我也WA了几发，因为我看到这题后我第一反应就是想到了CF当中一道思维题CodeForces - 605A

~~又是一道因为读错题二引发的惨案。~~注意是给你一个1～n的序列，而不仅仅是一个大小为n的数组。

既然是一个1～n的序列，那么自然当a[i] == i的时候为正确位置。所以我们只需要判断下a[i] 是否等于 i，若不相等，则交换次数cnt加一，然后再更新，交换位置。存储数据所在位置我用的是map。

AC代码：

#include <bits/stdc++.h>

using namespace std;
const int maxn = 100000 + 5;
int a[maxn] = {0};

int main() {
    int t, n, temp, cnt = 0;
    map<int, int> ans;
    scanf("%d", &t);
    while (t--) {
        cnt = 0;
        ans.clear();
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &temp);
            a[i] = temp;
            ans[temp] = i;
        }
        for (int i = 1; i <= n; i++) {
            if (a[i] != i) {
                cnt++;
                ans[a[i]] = ans[i];
                temp = ans[i];
                ans[i] = i;
                swap(a[i], a[temp]);
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}