该场比赛的命题人和评测人员应当女装，理由如下：
考试前
- 标准程序无法正常通过
- 数据有误（可持久化修锅）
- 未正确配置比赛文件
考试后
360危险卫士将部分代码删除并判定为木马。
Problem A 电费结算
题面
WZK最近靠租房发家致富了。作为WZK老同学的你也要租房，于是WZK决定不要房租，但是电费还得付。
以下是用电价格：
如果你用电为$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
如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！
