提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

SDUT 2021 Autumn Individual Contest – D

2021 SDUT Contest
2023-06-13 09:12:48 时间

B – Maximize GCD（思维）

题意

给你 n​ 个数字 A_i​ ，有一个操作：任选一个数字将其+1，你可以进行这个操作至多 K​ 次(可以不操作)，问如何使得这 n​ 个数的GCD最大。

思路

首先，由于 K 很大，所以如果可以使得 n 个数相同，那么GCD就是这个数。只要判断一下能否使得在 K 次操作内，使得所有数字都一样大，即 cost = \displaystyle\sum_{i = 1}^n Max – A_i，如果 cost \leq K ，则可以使得所有数字一样大，然后算一下最终可以使得 n 个数变成多大的数：Max + (K-cost)/n​​​​。

如果，不能使得 n​​​​ 个数相同，则考虑如何使得GCD最大。可以发现，假设 gcd = x​​​​ ，那么进行完操作后，每个数都是 x​​​ 的倍数，即每个数都是在 (k-1)x < A_i \le kxk​​​ 对于每个 A_i​​​ 都不同），然后将其不断加 1 达到 kx​​​ 。我们枚举所有可能的 x​​​ ，然后计算一下对应的花费，找到最大的 x​​​ 即可。对于某个 x​​​ 一共需要的花费是 \displaystyle\sum_{i=1}^n k_ix – A_i​​​ ，拆分得到：\displaystyle \sum_{i=1}^n k_ix – \displaystyle\sum_{i = 1} ^ n A_i​​​​​ 。因此，我们可以将这 n​​ 个数字 A_i​​ 划分成若干组，第一组满足 1 \leq A_i \leq x​ ，第二组满足 x+1\leq A_i \leq 2x​ ，第 t​ 组满足 (t-1)x+1 <A_i \leq txcnt​，然后计算一下这组数的和记为sum​，则这组的花费就是 cost_t = cnt*tx – sum ，总花费就是 \sum cost_t ，然后比较总花费是否小于 K。

具体来说，你需要先统计出每种数字出现的次数cnt，以及每种数字的和sum，然后计算一下 cnt 和 sum 的前缀和，这样就可以快速算出介于某个区间内数字的个数以及他们的和是多少，然后枚举所有可能的 x ，计算出总花费验证是否可行即可。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 3e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
LL a[maxn], cnt_s[maxn], sum_s[maxn], cnt[maxn], sum[maxn];
void solve() {
    LL n, k;
    int m = -1;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        cnt_s[x]++;
        sum_s[x] += x;
        m = max(m, x);
    }
    for (int i = 1; i <= m; i++) {
        cnt[i] = cnt[i - 1] + cnt_s[i];
        sum[i] = sum[i - 1] + sum_s[i];
    }
    if (m * n - sum[m] <= k) {
        printf("%lld\n", (k - m * n + sum[m]) / n + m);
    } else {
        int ans = 1;
        for (int i = 2; i < m; i++) {
            int l = 0, r = i;
            LL cost = 0;
            while (l < m) {
                LL num = cnt[min(r, m)] - cnt[l];
                LL tot = sum[min(r, m)] - sum[l];
                cost += num * r - tot;
                l += i, r += i;
            }
            if (cost <= k) ans = i;
        }
        printf("%d\n", ans);
    }
}
int main(int argc, char const *argv[]) {
    int t = 1;

    while (t--) {
        solve();
    }
    return 0;
}

G – Greedy Division(DP)

## 题意

有 n 个橘子编号为 1- n，告诉你每个橘子的重量 w_i​ ，两个人按照这样的规则拿橘子：按照橘子摆放的顺序开始，如果第一个人现有的橘子总重量小于等于第二个人的，则第一个人拿一个橘子，否则第二个人拿一个橘子。让你找出有多少种橘子的摆放方式（即有多少种排列）。

思路

首先，如果橘子重量不能等分，则输出0。

假设橘子可以分成一样重的两堆，且第一堆有 x​ 个橘子， 则第二堆有 n-x​​ 个，并且一定能构造出可行的排列，只要构造出一个排列，让第一个人拿的时候只拿第一堆，第二个人拿的时候只拿第二堆即可（或者反过来第一人拿第二堆，但这里先假设第一人拿第一堆），且第一个人在第一堆里的拿法是任意的，一共有 x!​​ 种，所以对于这种情况，方案数为 x!(n-x)! 种。那么，我们只要算出有几种划分方式，使得两堆重量相同即可，这可以用DP解决。

设 dp[i][j][k]​​ 表示考虑前 i 堆，拿了j 个橘子，总重量为 k 的方案数。则考虑第 i+1 个橘子拿或者不拿，可以转移 ：

dp[i+1][j+1][k+w[i]] = dp[i][j][k] + dp[i+1][j+1][k+w[i]]; // 拿第 i + 1 个橘子
dp[i+1][j][k] = dp[i][j][k];//不拿

发现每次只用到第 i 个状态，可以状态压缩，加上取模得到最终状态转移，注意需要从后往前枚举：

p[j + 1][k + a[i]] = (dp[j + 1][k + a[i]] + dp[j][k]) % mod;

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;

const double PI = acos(-1.0);
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
LL mul[111];
void init() {
    mul[1] = 1;
    for (int i = 2; i <= 100; i++) {
        mul[i] = (mul[i - 1] * i) % mod;
    }
}
int a[111];
int dp[111][11111];
void solve() {
    int n, m;
    init();
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        sum += a[i];
    }
    if (sum % 2 != 0)
        puts("0");
    else {
        sum /= 2;
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = n; j >= 0; j--) {
                for (int k = sum; k >= 0; k--)
                    dp[j + 1][k + a[i]] =
                        (dp[j + 1][k + a[i]] + dp[j][k]) % mod;
            }
        }
        LL ans = 0;
        for (int i = 0; i <= n; i++) {
            ans = (ans + mul[i] * mul[n - i] % mod * dp[i][sum] % mod) % mod;
        }
        printf("%lld\n", ans);
    }
}
int main(int argc, char const *argv[]) {
    int t = 1;

    while (t--) {
        solve();
    }
    return 0;
}

相关文章