题解(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;
}
更多推荐
2018黑龙江ACM省赛部分题解(hdu6480 hdu6484 hdu6486 hdu6489)(待更新)
发布评论