CWOI2019 暑假提高组模拟题十一

Author：薇薇安
发布时间：August 20, 2019
354views
No comments
1020 words
Categories：题解

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

- 考试前
  - 标准程序无法正常通过
  - 数据有误（可持久化修锅）
  - 未正确配置比赛文件
- 考试后
  - `360危险卫士`将部分代码删除并判定为木马。

## Problem A 电费结算

### 题面

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

以下是用电价格：

![T1.png][1]

如果你用电为$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$元。

### 题解

二分答案即可。

### 代码

```cpp
#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）$。

### 代码

```cpp
#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$的值。

### 题解

裸的树链剖分。

### 代码

```cpp
#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;
}
```

[1]: https://www.oss.starroad.top/usr/uploads/2019/08/2991627800.png<hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal">版权属于：淡淡的路瑶本文链接：<a class="content-copyright" href="https://www.starroad.top/archives/447.html">https://www.starroad.top/archives/447.html</a>如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！</blockquote>

Last modification：August 22nd, 2019 at 07:22 pm

如果您觉得我的文章有用，给颗糖糖吧~