CodeForces - 940E Cashback

CodeForces - 940E长度为 $n$ 的数组,随意分段,每段的值是去掉前 $\frac{len}{c}$ 小后的区间和,求整个数组分段后值的和最小是多少。考虑每个分段要么长度为 $1$ 要么长度为 $c$ 一定是最优的。单调队列维护好区间最小值,然后 dp 就好了 $dp[i]=min\{dp[k]+cal(k+1, i)\ |\ 1 \leqslant k < i\}$#inc

- 阅读全文 -

CodeForces - 675D Tree Construction

CodeForces - 675D构造一个 $10^5$ 的二叉平衡树,输出每个点的父亲。直接构造是不行的,每次找第 $i$ 个数前的小于 $a[i]$ 最大的和大于 $a[i]$ 最小的位置,放过去就行了。set 搞一下#include<bits/stdc++.h> using namespace std; const int maxn = 1.2e5; int a[maxn], n

- 阅读全文 -

CodeForces - 343C Read Time

CodeForces - 343C一个有 $n$ 个磁头的线性区间,每个磁头可以随意穿过对方,单位时间移动一个格子,有一些需要读取的位置,请问最少需要多少时间能访问完。二分,验证时候先向最左再向最右看能不能在 $t$ 时间内读完所有位置。#include<bits/stdc++.h> using namespace std; const int maxn = 1.2e5; long l

- 阅读全文 -

CodeForces - 552C Vanya and Scales

CodeForces - 552C一个有两个托盘的天枰,两边都可以放砝码。但是100个砝码的重量是 $w^0$, $w^1$, $w^2$, ... , $w^{100}$询问能否称出质量为 $m$ 的物体把 $m$ 分解为 $w$ 进制,砝码能放在左右两盘,所以每一位允许是 $w-1$, $1$, $0$#include<bits/stdc++.h> using namespace

- 阅读全文 -

CodeForces - 909C Python Indentation

CodeForces - 909C给 $n$ 行的 python 语句,只有 for 语句和简单语句,计算有多少种缩进方式。比较坑在任何一个简单语句都能往里缩进,并不一定只有 for 才能往里缩进。for 语句必须缩进,简单语句可以缩进也可以不缩进。列出dp方程如下 $f[i][j]$ 表示第 i 行有 j 个缩进的种类数 $f[i + 1][j + 1] += f[i][j]$ //for语句$

- 阅读全文 -