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

题解（hdu6480 hdu6484 hdu6486 hdu6489)(待更新）"/>

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

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;
}