00:00
加载中……请稍等……

该比赛非常原题。一切皆可洛谷双倍经验。

护花

题面

约翰留下他的$n\in [1,10^5]\bigcap\mathbb{N^*}$只奶牛上山采木。他离开的时候,她们像往常一样悠闲地在草场里吃草。可是,当他回来的时候,他看到了一幕惨剧:牛们正躲在他的花园里,啃食着他心爱的美丽花朵!为了使接下来花朵的损失最小,约翰赶紧采取行动,把牛们送回牛棚。

牛们从$1$到$n$编号。第$i$只牛所在的位置距离牛棚$t_i\in [1,2\times 10^6]\bigcap\mathbb{N^*}$分钟的路程,而在约翰开始送她回牛棚之前,她每分钟会啃食$d_i\in [1,10^2]\bigcap\mathbb{N^*}$朵鲜花。无论多么努力,约翰一次只能送一只牛回棚。而运送第$i$只牛事实上需要$2t_i$分钟,因为来回都需要时间。试求最小的被吞食的花朵数量。

题解

考虑贪心。本题目类似于国王游戏。按照$\cfrac{t}{d}$的值从小到大贪心。考虑到误差,需要移项。

代码

#include <bits/stdc++.h>
using namespace std;
struct Cow {
    unsigned long long t;
    unsigned long long d;
    bool operator<( const Cow& that ) const {
        return t * that.d < that.t * d;
    }
} c[100005];
int main() {
    ios::sync_with_stdio( false );
    cin.tie( 0 );
    unsigned long long n, ans = 0, nowt = 0;
    cin >> n;
    for ( unsigned long long i = 1; i <= n; i++ ) {
        cin >> c[i].t >> c[i].d;
    }
    sort( c + 1, c + 1 + n );
    for ( unsigned long long i = 1; i <= n; i++ ) {
        ans += nowt * c[i].d;
        nowt += c[i].t << 1;
    }
    cout << ans << endl;
    return 0;
}

修剪草坪

题面

在一年前赢得了小镇的最佳草坪比赛后,Farm John变得很懒,再也没有修剪过草坪。现在,新一轮的最佳草坪比赛又开始了,Farm John希望能够再次夺冠。

然而,Farm John的草坪非常脏乱,因此,Farm John只能够让他的奶牛来完成这项工作。Farm John有$n\in [1,10^5]\bigcap\mathbb{N^*}$只排成一排的奶牛。每只奶牛的效率是不同的,第$i$只奶牛的效率为$e_i\in [1,10^9]\bigcap\mathbb{N^*}$。

靠近的奶牛们很熟悉,因此,如果Farm John安排超过$k$只连续的奶牛,那么,这些奶牛就会罢工去开派对。因此,现在Farm John需要你的帮助,计算FJ可以得到的最大效率,并且该方案中没有连续的超过$k$只奶牛。

题解

考虑直接进行规划比较麻烦,那么考虑将一些奶牛移除以防止她们开派对。

配合单调队列即可搞定。

代码

#include <bits/stdc++.h>
using namespace std;
const unsigned int MAXN = 100002;
long long i, j, k, n, m, f[MAXN], a[MAXN], q[MAXN];
int main() {
    long long sum = 0;
    cin >> n >> k;
    for ( i = 1; i <= n; i++ ) {
        cin >> a[i];
        sum += a[i];
    }
    int left = 1, right = 1;
    for ( i = 1; i <= n; i++ ) {
        while ( left <= right && i - q[left] > k + 1 )
            left++;
        f[i] = a[i] + f[q[left]];
        while ( left <= right && f[q[right]] >= f[i] )
            right--;
        q[++right] = i;
    }
    for ( i = n - k; i < n; i++ ) {
        f[i + 1] = min( f[i + 1], f[i] );
    }
    cout << sum - f[n] << endl;
    return 0;
}

Wormholes G

题面

John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边,并可以使你返回到过去的一个时刻(相对你进入虫洞之前)。

John 的每个农场有 $m$ 条小路(无向边)连接着 $n$ 块地(从 $1 \sim n$ 标号),并有 $w$ 个虫洞。

现在 John 想借助这些虫洞来回到过去(出发时刻之前),请你告诉他能办到吗。

题解

SPFA判断负环板子。

代码

#include <bits/stdc++.h>
#define MANX 505
using namespace std;
struct node {
    int dis, nex;
} f;
vector< node > mp[MANX];
int sum[MANX], fl[MANX] = { 0 }, flag;
void spfa( int k ) {
    if ( fl[k] == 1 ) {
        fl[k] = 0;
        flag = 1;
        return;
    }
    fl[k] = 1;
    if ( !mp[k].empty() )
        for ( int i = 0; i < mp[k].size(); i++ ) {
            if ( sum[mp[k][i].nex] > mp[k][i].dis + sum[k] ) {
                sum[mp[k][i].nex] = mp[k][i].dis + sum[k];
                spfa( mp[k][i].nex );
                if ( flag == 1 ) {
                    fl[k] = 0;
                    return;
                }
            }
        }
    fl[k] = 0;
}
int main() {
    ios::sync_with_stdio( false );
    cin.tie( 0 );
    int test, m, n = 0, w, x, y, z, k;
    cin >> test;
    while ( test-- ) {
        for(unsigned int i=1;i<=n;i++){
            mp[i].clear();
        } 
        cin >> n >> m >> k;
        for ( int i = 1; i <= m; i++ ) {  
            cin >> x >> y >> z;
            f.dis = z;
            f.nex = y;
            mp[x].push_back( f );
            f.nex = x;
            mp[y].push_back( f );
        }
        for ( int i = 1; i <= k; i++ ) {
            cin >> x >> y >> z;
            f.dis = -z;
            f.nex = y;
            mp[x].push_back( f );
        }
        memset( sum, 0, sizeof( sum ) );
        flag = 0;
        for ( int i = 1; i <= n; i++ ) {
            spfa( i );
            if ( flag ) {
                break;
            }
        }
        if ( flag == 1 ) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
    return 0;
}
Last modification:June 20th, 2020 at 04:26 pm
如果您觉得我的文章有用,给颗糖糖吧。