AtCoder Regular Contest 059

C - いっしょ / Be Together

数据比较小，暴力就挺好的。O(n^2)可过的好题

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 110;

int nums[MAXN],n;

int main()

{

	scanf("%d",&n);

	for(int i = 0; i < n; ++i)

		scanf("%d",&nums[i]);

    int res = 999999999,cost = 0;

    for(int i = -100; i <= 100; ++i)

    {

        cost = 0;

        for(int j = 0; j < n; ++j)

            cost += (nums[j]-i)*(nums[j]-i);

        res = min(res,cost);

    }

    printf("%d\n",res);

	return 0;

}

####D - アンバランス / Unbalanced
也比较水。
思路：假设当前字符串长度为偶数，字符x占了一半，另一半是别的字符，用 * 代替，则字符相邻的方式有两种，x和 * 交错排列；或者x和 * 不交错排列，这种情况下至少有两个x挨着。在交错排列的情况下，若x占了一半以上的话，则必定至少有两个x是挨着的，有种抽屉原理的感觉。对于长度为奇数的情况，即len为奇数，则当x字符占了一半以上，x字符至少有len/2+1个，这种情况下，有两种排列的方式，即交错排列和不交错的排列，也就是至少有两个x是挨着的或者两个x隔着一个字符。

综上，一个字符串的子串如果是不平衡的，则必定有某种字符两个挨在一块或者中间隔着一个。扫一遍判断下即可。

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5+10;

char str[MAXN];

int len;

int main()

{

    int s = -1, e = -1;

    scanf("%s",str);

    len = strlen(str);

    for(int i = 0; i < len-1; ++i)

    {

        if(str[i] == str[i+1])

        {

            s = i+1;

            e = i+2;

            break;

        }

        if(i+2 < len && str[i] == str[i+2])

        {

            s = i+1;

            e = i+3;

            break;

        }

    }

    printf("%d %d\n",s,e);

    return 0;

}

####E - キャンディーとN人の子供 / Children and Candies
感觉D和E的难度差距太大了，感觉一下子突然难了好多，可能是我dp太水了。
参考：http://kmjp.hatenablog.jp/entry/2016/08/13/1030
https://arc059.contest.atcoder.jp/submissions/1550056

思路：dp[k][n]表示把n个糖果分给k个孩子所得到的x[i]^a[i]的乘积的加和，就是题目要求的那玩意，感觉还挺绕呢。dp[k-1][n-m]表示把n-m个糖果分给k-1个孩子得到的结果。也就是第k个孩子给了他m个糖果。先考虑A[i]==B[i]的情况，这时候dp[k][n] += dp[k-1][n-m] * (A[i]^m)。当A[i] != B[i]的时候，则dp[k][n] += dp[k-1][n-m] * (A[i]^m + (A[i]+1)^m + ... + B[i]^m)。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 405;

const LL mod = 1e9+7;

LL sum[MAXN];

LL A[MAXN],B[MAXN];

LL dp[MAXN][MAXN];

LL N,C;

LL calc(int a, int b)

{

    memset(sum,0,sizeof(sum));

    for(int i = a; i <= b; ++i)

    {

        LL t = 1;

        for(int j = 0; j <= C; ++j)

        {

            sum[j] = sum[j]+t;

            sum[j] %= mod;

            t = t*i%mod;

        }

    }

}

int main()

{

	cin >> N >> C;

	for(int i = 1; i <= N; ++i)

		cin >> A[i];

	for(int i = 1; i <= N; ++i)

		cin >> B[i];

	dp[0][0] = 1;

	for(int i = 1; i <= N; ++i)

	{

	    calc(A[i],B[i]);//计算A[i]^m + (A[i]+1)^m + ... + B[i]^m

		for(int j = 0; j <= C; ++j)

			for(int k = 0; k <= j; ++k)

				dp[i][j] = (dp[i][j] + dp[i-1][j-k]*sum[k])%mod;

	}

	cout << dp[N][C] << endl;

	return 0;

}

####F - バイナリハック / Unhappy Hacking
不会，E都吃力，F就不看了，题刷多了，回头再来一块搞F

巴特西

AtCoder Regular Contest 059

C - いっしょ / Be Together

最新文章

热门文章