Loading... 该场比赛的命题人和评测人员应当女装,理由如下: - 考试前 - 标准程序无法正常通过 - 数据有误(可持久化修锅) - 未正确配置比赛文件 - 考试后 - `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"><p class="content-copyright">版权属于:淡淡的路瑶</p><p class="content-copyright">本文链接:<a class="content-copyright" href="https://www.starroad.top/archives/447.html">https://www.starroad.top/archives/447.html</a></p><p class="content-copyright">如果文章出现任何问题,请下方评论,紧急情况请发邮件。谢谢支持!</p></blockquote> Last modification:August 22nd, 2019 at 07:22 pm © 允许规范转载 Support 如果您觉得我的文章有用,给颗糖糖吧~ ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat