Educational Codeforces Round 108 (Rated for Div. 2) （A思维，Bmath，C前缀和，D枚举）

1519A. Red and Blue Beans

问题简述

给定 个红豆， 个蓝豆，差值 ，要求我们进行为红蓝豆分组，使得红豆和蓝豆绝对值差值不大于 ，即：一个红豆最多与 个蓝豆组合，反之亦然

问题分析

设数量小的豆子为 ，数量多的豆子为 所以满足 $y \le x + x · d $ 输出 YES

代码解决

using ll = long long;
void solve() {
    ll r, b, d;
    cin >> r >> b >> d;
    if (r < b) swap(r, b);
    cout << (b + b * d >= r ? "YES\n" : "NO\n");
}

1519B. The Cake Is a Lie

问题简述

求从#card=math&code=%281%2C1%29&id=VJFo7) 移动至 #card=math&code=%28n%2Cm%29&id=YkJuC) 的 Cost是否等于 ，每一步的代价：%20%5Cto%20(x%20%2B%201%2Cy)#card=math&code=%28x%2Cy%29%20%5Cto%20%28x%20%2B%201%2Cy%29&id=SzmIE) 代价为 ，$(x,y) \to (x,y + 1) $ 的代价为

问题分析

可以通过DP或者数学的方法解决

这里贴一下暴力解法 DFS

int n, m, k;
ll cnt = 0;
void dfs(int x, int y, int val) {
    if (x == n && y == m) {
        cnt = val;
        return;
    }
    if (x > n || y > m) return;
    if (x < n)
        dfs(x + 1, y, val + y);
    else
        dfs(x, y + 1, val + x);
}
void solve() {
    cnt = 0;
    cin >> n >> m >> k;
    dfs(1, 1, 0);
    cout << (cnt == k ? "YES\n" : "NO\n");
}

math：%20%2B%20m%20*%20(n%20-%201)#card=math&code=k%20%3D%20%28m%20-%201%29%20%2B%20m%20%2A%20%28n%20-%201%29&id=O3kI9) 输出 YES

using ll = long long;
void solve() {
    ll n, m, k;
    cin >> n >> m >> k;
    cout << (k == (m - 1) + m * (n - 1) ? "YES\n" : "NO\n");
}

1519C. Berland Regional

问题简述

某地方举办XCPC区域赛， 个学生，分别来自 且每人的编程能力 ，如果限定每个队伍必须 人，那么学校会安排 更大的人组队，并且每个学院可以派出多个队伍且保证每个队友刚好 人，当 时，求出所有学校参赛人的 ，当人数不够 时战力和为 .

问题分析

把每个学生存到对应的学校，并按照从大到小降序存进数组 u[] 且对每个学校的该大小位size的数组进行前缀和s[]，每个学校对 的贡献是前 size-k%size(size/k*k) 个的前缀和

using ll    = long long;
const int N = 2e5 + 7;
set<ll> st;
vector<ll> u[N];
bool cmp(pair<ll, ll> a, pair<ll, ll> b) { return a.first > b.first; }
void solve() {
    int n;
    cin >> n;
    vector<pair<ll, ll>> p(n);
    vector<ll> cnt(n + 2, 0);
    st.clear();
    for (int i = 0; i <= n; ++i) u[i].clear();
    for (int i = 0; i < n; ++i) cin >> p[i].second, st.insert(p[i].second);
    for (int i = 0; i < n; ++i) cin >> p[i].first;
    sort(p.begin(), p.end(), cmp);
    for (int i = 0; i < n; ++i) u[p[i].second].push_back(p[i].first);
    for (auto i : st) {
        int siz = u[i].size();
        for (int j = 1; j < siz; j++) u[i][j] += u[i][j - 1];
        for (int j = 1; j <= siz; j++) cnt[j] += u[i][siz - 1 - siz % j]; //关键是这里处理ans[]
    }
    for (int i = 1; i <= n; i++) cout << cnt[i] << " ";
    cout << endl;
}

1519D. Maximum Sum of Products

问题简述

至多可以反转一次 a[] ，问最大的

问题分析

T=2s，n=5000，直接枚举所有情况，所以考虑 的前缀和，枚举中点，且考虑翻转的长度奇偶，把翻转的 [l,r] 和 [l-1,r+1] 的式子展开发展不同点只有 ,左右两端用前缀和求和即可

using ll = long long;
ll a[5005], b[5005], s[5005], ans = 0;
int n;
void run1(int x) { //翻转长度位奇数
    ll res = 0;
    for (int l = x, r = x; l >= 1 && r <= n; l--, r++) {
        if (l == r) res += a[l] * b[l];
        else
            res += a[l] * b[r] + a[r] * b[l];
        ans = max(ans, res + s[l - 1] + s[n] - s[r]);
    }
}
void run2(int x) { //翻转长度位偶数
    ll res = 0;
    for (int l = x, r = x + 1; l >= 1 && r <= n; l--, r++) {
        if (l == r) res += a[l] * b[l];
        else
            res += a[l] * b[r] + a[r] * b[l];
        ans = max(ans, res + s[l - 1] + s[n] - s[r]);
    }
}
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int j = 1; j <= n; j++) cin >> b[j];
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i] * b[i];
    for (int i = 1; i <= n; i++) run1(i); //翻转长度位奇数
    for (int i = 1; i <= n; i++) run2(i); //翻转长度位偶数
    ans = max(ans, s[n]);                 //特判一下原来不翻转
    cout << ans;
}