XCPC 寒假集训班 D3 个人笔记

讲评题

砍树

二分答案即可.

#include <bits/stdc++.h>
#define N 1000006
#define int long long

int n, m;
int a[N];

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f? x : -x;
}

bool valid(int h){
    int res = 0;
    for(int i = 1; i <= n; ++i) if(a[i] >= h) res += a[i] - h;
    return res >= m;
}

int binary_search(int l, int r){
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if(valid(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

signed main(){
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    printf("%lld\n", binary_search(1, 1e15));
    return 0;
}

三分

传送门

#include <bits/stdc++.h>
#define int long long
#define eps 1e-6

int n;
double l, r;
double a[15];

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f? x : -x;
}

double calc(double x){
    double res = 0;
    for(int i = 0; i <= n; ++i) res += a[i] * pow(x, i);
    return res;
}

signed main(){
    n = read(); scanf("%lf %lf", &l, &r);
    for(int i = n; ~i; --i) scanf("%lf", &a[i]);
    while(r - l > eps){
        double lmid = l + (r - l) / 3.0, rmid = l + (r - l) * 2.0 / 3.0;
        double lval = calc(lmid), rval = calc(rmid);
        if(rval > lval) l = lmid;
        else r = rmid;
    }
    printf("%.5lf\n", l);
    return 0;
}

国王游戏 (邻项交换)

传送门

先猜测结论: 按升序排序, 就是最优排队方案.

可使用微扰(邻项交换)证明该结论:

假设我们交换相邻的两个大臣与, 依题意, 在交换前, 他们获得的奖励分别是:

$与$

交换后, 他们获得的奖励分别是:

$与$

显然, 交换后, 其它的大臣获得的奖励不变.

故我们只需要比较这组式子最大值的大小.

把公因式扔掉, 也就是要比较

$与$

同时乘以, 也就是要比较

$与$

显然,, 所以最终就是比较:

$与$

而, 即交换前更优.

然而, 只知道结论没用. 看数据范围, 这题需要高精度.

贴一份 Python 3 AC Code:

n = int(input())
X, Y = map(int, input().split())

a = []

for i in range(n):
    x0, x1 = map(int, input().split())
    a.append((x0, x1))

a.sort(key = lambda x: x[0] * x[1])

res, ans = X, 0

for i in a:
    if ans == 0: ans = res // i[1]
    if res // i[1] > ans: ans = res // i[1]
    res = res * i[0]

print(ans)

修理牛棚 Barn Repair (边界推进)

传送门

一开始理解错题意了, 以为购置的木板长度必须相同, 那样就需要二分木板长度.

跑不出样例, 多读了好几遍题面才恍然大悟.

那就很简单了, 先假设有一块大木板刚好把所有牛棚拦住, 接着我们把没有牛的片段扔掉, 扔段, 就剩下段木板了.

既然要最小化木板总长度, 那就需要最大化扔掉的片段的长度. 所以就贪心地按牛棚间距从大到小排序, 扔掉前段即可.

AC Code:

#include <cstdio>
#include <ctype.h>
#include <algorithm>

int m, s, c;
int a[205];
int d[205];

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}


int main(){
    m = read(), s = read(), c = read();
    for(int i = 1; i <= c; ++i) a[i] = read();

    std::stable_sort(&a[1], &a[c+1]); // 把牛棚编号从小到大排序

    d[1] = 0; // 第一个牛棚和边界的间距为0
    for(int i = 2; i <= c; ++i) d[i] = a[i] - a[i-1] - 1; // 计算相邻牛棚的间距长度, 注意要-1
    std::stable_sort(&d[1], &d[c+1]); // 把间距从小到大排序, 后面逆序遍历取前m-1大值即可.
    
    long long ans = a[c] - a[1] + 1; // 一开始的大木板长度, 要刚刚好覆盖所有的牛棚
    for(int i = c, j = 1; i >= 1 and j < m; --i, ++j) ans -= d[i]; // 扔掉间距
    printf("%lld\n", ans);
    return 0^(0-0)^0;
}

Work Scheduling G (反悔贪心)

传送门

反悔贪心看这里

很容易想到这样的贪心策略: 按截止时间从小到大遍历, 每次都把能做的任务做了.

如果遇到不能做的任务怎么办? 那就比较一下的利润和之前做的利润最低的任务.

如果的利润不高于, 那还做干啥? 直接放弃.
如果的利润高于, 那就反悔了, 丢芝麻捡西瓜, 用去替换.

怎么找? 用堆就可以. 拿一个小根堆(按利润)维护已做任务即可.

AC Code:

#include <queue>
#include <cstdio>
#include <ctype.h>
#include <algorithm>

#define N 100005

int n;
struct Task{
    int d, p;
    bool operator < (const Task& b) const{
        return p > b.p; // 重载运算符, 让堆把价值小的放在堆顶.
    }
}a[N], top[N];

bool cmp(Task a, Task b){
    return a.d == b.d ? a.p > b.p : a.d < b.d; // 自定义的sort比较函数
}

std::priority_queue<Task> q;

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

int main(){
    n = read();
    for(int i = 1; i <= n; ++i) a[i].d = read(), a[i].p = read();
    std::stable_sort(&a[1], &a[n+1], cmp); // 按截止时间从小到大排序
    long long ans = 0;
    for(int i = 1; i <= n; ++i){
        if(a[i].d == q.size()){ // 思考一下为什么可以这样判断任务是否矛盾
            long long tmp = q.top().p; // 取出堆顶, 也就是利润最低的任务
            if(a[i].p > tmp){ // 如果新任务利润更大, 就替换(反悔)
                ans += a[i].p - tmp;
                q.pop();
                q.push(a[i]);
            }
        }
        else{
            ans += a[i].p; // 不矛盾就先做了.
            q.push(a[i]);
        }
    }
    printf("%lld\n", ans);
    return 0^(0-0)^0;
}

训练题

B - Brightness Begins

洛谷传送门

CF传送门

易知,

如果一个数有奇数个因子, 它会被翻转奇数次, 对应的灯泡最终关闭.
如果一个数有偶数个因子, 它会被翻转偶数次, 对应的灯泡最终打开.

哎? 因子不都是一对一对的吗? 怎样才能出现奇数个因子?

那就是其中一对因子, 两个因子相同. 也就是说这个数是完全平方数.

有盏灯中有盏灯最终打开, 也就是到中有个非完全平方数. 那完全平方数的数量就是.

而由数学知识,到中有个完全平方数. (这个就不需要证明了吧…=的解的个数就是.)

于是就有如下方程:

二分这个即可.

但我们能不能直接瞪出呢? 还真可以.

求解n

设, 则有.

把取整符号拿掉:

把根号干掉:

得到方程组:

直接求根公式:

合并一下得:

再化简一下:

又因为, 这里已经能直接瞪出:

故 .

这题要注意 sqrt或sqrtl函数的精度问题, 保险起见最好自己再写个函数二分.

我赛时没去推做法, 用的二分找的解. 代码应该不需要贴了吧 (代码太丑陋).

C - Mandarin Orange

传送门

最大只有, 直接暴力是可以通过的.

赛时AC Code ():

#include <cstdio>
#include <ctype.h>

int n, ans;
int a[10005];

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f? x : -x;
}

int min(int a, int b){return a < b? a : b;}
int max(int a, int b){return a > b? a : b;}

int main(){
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = 1; i <= n; ++i){
        int x = a[i];
        for(int j = i; j <= n; ++j){
            x = min(x, a[j]);
            ans = max(ans, x * (j - i + 1));
        }
    }
    printf("%d\n", ans);
    return 0;
}

但, 其实这题就是一个单调栈: 单调栈用于维护每个数前/后第一个大于/小于它的数. 单调栈模板题在这里, 我在另一篇文章里详细介绍了单调栈. 利用单调栈我们就可以解决这道题.

做法如下: 从到枚举每个盘子, 并假设他要吃的橘子数就是这个盘子中的橘子数.

然后, 我们从这个盘子开始, 向左向右分别找出第一个橘子数比小的盘子的坐标,, 那么对于这个盘子, 他最多能吃到个橘子.

找和可以用两个单调栈来完成.

这样就能做到了.

有空再提供一份代码.

D - Freefall

传送门

题目就是要求出的最小值.

显然这是一个单峰函数, 找这个极值点就可以了.

可以直接套三分板子, 但我还是用二分过的…

把函数图像看成一个“坡”, 只要, 就说明是在“下坡”, 一直找下去并用合法的更新即可.

在细节上WA了好多次, 吃了一堆罚时, 果然我还是太菜了.

check的时候不能直接判断, 因为可能溢出!!!

所以要作差来比较.

AC Code:

#include <cstdio>
#include <cmath>

long long A, B;
//long double ans = 1e18;

long double f(long long x){
    return x * B + A * 1.0 / sqrtl(x + 1); // x * B会炸
}

bool check(long long x){
    return A * 1.0 / sqrtl(x + 1) - A * 1.0 / sqrtl(x + 2) - B > 0;
}

long double min(long double a, long double b){return a < b? a : b;}

int main(){
    scanf("%lld%lld", &A, &B);
    long long l = 0, r = 1e18, ans = 0;
    while(l <= r){
        long long mid = (l + r) >> 1LL;
        if(check(mid)){
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    printf("%.9Lf\n", min(f(ans-1), min(f(ans), min(f(ans+1), A * 1.0))));
    return 0;
}

E - Buy Low Sell High

洛谷传送门
 CF传送门

这题和上面的那道Work Scheduling G一样, 是道反悔贪心.

假贪心: 先低价买入, 发现能赚钱就直接卖.

真贪心: 先低价买入, 发现能赚钱就卖, 等后面发现能更高价卖出就反悔, 撤销之前的卖出, 改为现在卖.

问题在于怎么设置反悔.

更具体地说, 在第天以价格买入, 在第天以价格卖出. 但现在第天的价格卖出更划算, 要怎么撤回 天买天卖 这个决策?

就价格而言, 天买入天卖出
等价于 天买入天卖出 且 天买入天卖出.

也就是, .

反悔的时候要把重新放到堆里面, 因为还可以被卖.

拿一个小根堆维护待卖的股票. 对于每天的价格, 直接把它扔进堆里. 然后取出堆顶比一比, 若, 就把卖出, 差价计入答案,再次回到待卖出列表里.

AC Code:

#include <queue>
#include <cstdio>
#include <ctype.h>
#define N 300005

int n;
int a[N];
long long ans;

std::priority_queue<int> q;

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

int main(){
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = 1; i <= n; ++i){
        q.push(-a[i]); // 通过取负数来实现小根堆
        if(-q.top() < a[i]){
            ans += a[i] + q.top(); // 注意q.top()是负数, 减法变加法
            q.pop();
            q.push(-a[i]);
        }
    }
    printf("%lld\n", ans);
    return 0^(0-0)^0;
}

Loading...

XCPC 寒假集训班 D3 个人笔记

讲评题

砍树

三分

国王游戏 (邻项交换)

修理牛棚 Barn Repair (边界推进)

Work Scheduling G (反悔贪心)

训练题

B - Brightness Begins

C - Mandarin Orange

D - Freefall

E - Buy Low Sell High