CWOI2019 暑假提高组模拟题十一

  1.  Home
  2. Text  
    3. Share to：

该场比赛的命题人和评测人员应当女装，理由如下：

  • 考试前

    • 标准程序无法正常通过
    • 数据有误（可持久化修锅）
    • 未正确配置比赛文件

  • 考试后

    • 360危险卫士将部分代码删除并判定为木马。

Problem A 电费结算

题面

WZK最近靠租房发家致富了。作为WZK老同学的你也要租房，于是WZK决定不要房租，但是电费还得付。

以下是用电价格：

T1.png

如果你用电为$10123$千瓦时，那么要付$2 \times 100 + 3 \times 9900 + 5 \times 123 = 30515$元（人民币）好贵。

到结算电费的日子了，可是WZK家里只有一个总电表，也就是统计你和WZK总共用的电量。

但是 WZK 有办法告诉你以下信息：

  • 如果按照总电表来看要交给供电局的钱$a$。（也就是两个人用电量加起来一起算钱）
  • 你和WZK如果分开付的话，你们付的钱的差值$b$。

现在你想知道如果你单独算钱的话，需要付多少钱。当然，你的用电量不会比 WZK多。

举个例子：如果你们一起算钱要付$1100$，并且如果分开来算，你们的差值是 $300$的话，那么你用了$150kwh$，WZK用了$250kwh$。让我们来验算一下：你们一共用电$400kwh$，所以要付$2 \times 100 + 3 \times 300 = 1100$，你单独要付$2 \times 100 + 3 \times 50 = 350$，WZK单独要付 $2 \times 100+ 3 \times 150 = 650$。

所以最后，你只需要告诉我你单独要付$350$元。

题解

二分答案即可。

代码

#include <iostream>
#include <cstdio>
#include <limits.h>
using namespace std;
const int LOWER[]={0,100,10000,1000000,2147483647};
const int PRICE[]={2,3,5,7};
int price(const int x){
    int ans=0;
    for(unsigned short i=0;i<4;i++){
        ans+=min(max(0,x-LOWER[i]),LOWER[i+1]-LOWER[i])*PRICE[i];
    }
    return ans;
}
int ele(int x){
    int ans=0;
    for(unsigned short i=0;i<4;i++){
        int cnt=0;
        cnt=min(x/PRICE[i],LOWER[i+1]-LOWER[i]);
        x-=cnt*PRICE[i];
        ans+=cnt;
    }
    return ans;
}
int main(){
#ifndef FILE_IN
    freopen("electric.in","r",stdin);
#endif
#ifndef FILE_OUT
    freopen("electric.out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cout<<price(1000000)<<endl;
    return 0;
}

Problem B 序列和

题面

$n$个数排成一个环，请选出不超过$k$段的连续的数，段与段间不能重叠，且使得选出的数和最大。

题解

不考虑环，直接dp即可，考虑如果答案存在$（1~i）+（j~n)$的这种情况，那么最小值一定不存在这种情况。于是不考虑环求一遍最大值$Max$和一遍最小值$Min$，于是答案为$max（sum-Min，Max）$。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 100020;
long long dp[MAXN][20][2], a[MAXN];
int n, k;
long long sum;
long long maxx = -1e18, minn = 1e18;
int main() {
    ios::sync_with_stdio( false );
    cin >> n >> k;
    for ( int i = 1; i <= n; i++ ) {
        cin >> a[i];
        sum += a[i];
    }
    memset( dp, -0x3f, sizeof( dp ) );
    dp[1][1][1] = a[1];
    dp[1][0][0] = 0;
    for ( int i = 2; i <= n; i++ ) {
        for ( int j = 0; j <= k; j++ ) {
            dp[i][j][0] = max( dp[i - 1][j][1], dp[i - 1][j][0] );
            dp[i][j][1] = max( dp[i - 1][j][1], dp[i - 1][j - 1][0] ) + a[i];
            maxx = max( max( dp[i][j][0], dp[i][j][1] ), maxx );
        }
    }
    memset( dp, 0x3f, sizeof( dp ) );
    dp[1][1][1] = a[1];
    dp[1][0][0] = 0;
    for ( int i = 2; i <= n; i++ ) {
        for ( int j = 0; j <= k; j++ ) {
            dp[i][j][0] = min( dp[i - 1][j][1], dp[i - 1][j][0] );
            dp[i][j][1] = min( dp[i - 1][j][1], dp[i - 1][j - 1][0] ) + a[i];
            minn = min( min( dp[i][j][0], dp[i][j][1] ), minn );
        }
    }
    cout << max( maxx, sum - minn ) << endl;
    return 0;
}

Problem C 树

题面

给定一棵$n$个节点的树，树根为$1$，起初所有节点权值为$0$,现有$m$个操作如下：

  • 1 x: 把$x$以及$x$为根的子树的点的权值修改为$1$。
  • 2 x：把$x$结点到根路径上的点修改为$0$。
  • 3 x：查询结点$x$的值。

题解

裸的树链剖分。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const long long MAXN = 500005;
struct node {
    long long v, next;
} a[MAXN << 2];
long long head[MAXN], cnt;
long long num, id[MAXN], siz[MAXN], fa[MAXN], dep[MAXN], top[MAXN], son[MAXN];
long long tree[MAXN << 2], lazy[MAXN << 2];
long long n, m;
void adde( long long u, long long v ) {
    cnt++;
    a[cnt].v = v;
    a[cnt].next = head[u];
    head[u] = cnt;
}
void dfs1( long long u, long long f, long long deep ) {
    long long maxson = -1;
    dep[u] = deep;
    fa[u] = f;
    siz[u] = 1;
    for ( long long i = head[u]; i != -1; i = a[i].next ) {
        long long v = a[i].v;
        if ( v == f )
            continue;
        dfs1( v, u, deep + 1 );
        siz[u] += siz[v];
        if ( siz[v] > maxson ) {
            son[u] = v;
            maxson = siz[v];
        }
    }
}
void dfs2( long long u, long long from ) {
    num++;
    top[u] = from;
    id[u] = num;
    if ( !son[u] )
        return;
    dfs2( son[u], from );
    for ( long long i = head[u]; i != -1; i = a[i].next ) {
        long long v = a[i].v;
        if ( v == fa[u] || v == son[u] )
            continue;
        dfs2( v, v );
    }
}
void build( long long l, long long r, long long rt ) {
    long long mid = ( l + r ) >> 1;
    if ( l == r ) {
        tree[rt] = 0;
        return;
    }
    build( l, mid, rt << 1 );
    build( mid + 1, r, rt << 1 | 1 );
}
void pushdown( long long rt ) {
    lazy[rt << 1] = lazy[rt << 1 | 1] = lazy[rt];
    tree[rt << 1] = lazy[rt];
    tree[rt << 1 | 1] = lazy[rt];
    lazy[rt] = -1;
}
void change( long long L, long long R, long long k, long long l, long long r, long long rt ) {
    long long mid = ( l + r ) >> 1;
    if ( L <= l && R >= r ) {
        lazy[rt] = k;
        tree[rt] = k;
    }
    else {
        if ( lazy[rt] != -1 )
            pushdown( rt );
        if ( L <= mid )
            change( L, R, k, l, mid, rt << 1 );
        if ( R > mid )
            change( L, R, k, mid + 1, r, rt << 1 | 1 );
    }
}
long long query( long long tar, long long l, long long r, long long rt ) {
    long long mid = ( l + r ) >> 1;
    if ( l == r )
        return tree[rt];
    else {
        if ( lazy[rt] != -1 )
            pushdown( rt );
        if ( tar <= mid )
            return query( tar, l, mid, rt << 1 );
        else
            return query( tar, mid + 1, r, rt << 1 | 1 );
    }
}
void region_change( long long x, long long y, long long k ) {
    while ( top[x] != top[y] ) {
        if ( dep[top[x]] < dep[top[y]] )
            swap( x, y );
        change( id[top[x]], id[x], k, 1, n, 1 );
        x = fa[top[x]];
    }
    if ( dep[x] > dep[y] )
        swap( x, y );
    change( id[x], id[y], k, 1, n, 1 );
    return;
}
int main() {
#ifndef FILE_IN
    freopen( "tree.in", "r", stdin );
#endif
#ifndef FILE_OUT
    freopen( "tree.out", "w", stdout );
#endif
    ios::sync_with_stdio( false );
    memset( lazy, -1, sizeof( lazy ) );
    memset( head, -1, sizeof( head ) );
    cin >> n;
    long long x, y, sign;
    for ( long long i = 1; i < n; i++ ) {
        cin >> x >> y;
        adde( x, y );
        adde( y, x );
    }
    dfs1( 1, -1, 1 );
    dfs2( 1, 1 );
    build( 1, n, 1 );
    cin >> m;
    for ( long long i = 1; i <= m; i++ ) {
        cin >> sign >> x;
        if ( sign == 1 ) {
            change( id[x], id[x] + siz[x] - 1, 1, 1, n, 1 );
        }
        else if ( sign == 2 ) {
            region_change( x, 1, 0 );
        }
        else {
            cout << query( id[x], 1, n, 1 ) << endl;
        }
    }
    return 0;
}

版权属于：来自星星的薇薇安

本文链接：https://www.starroad.top/archives/447.html

如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！

Last modification：August 22nd, 2019 at 07:22 pm
© 允许规范转载
如果您觉得我的文章有用，请赏一颗糖糖。

Leave a Comment