比赛链接：
https://codeforces.com/gym/102770
A. AD 2020
题目大意：
输入两个日期（日期范围是从 20000101 到 99991231），判断这两个日期及它们中间有多少个日期包含 202 这个子串。
思路：
预处理出每一个日期是否包含 202，然后做一个前缀和，询问的时候直接输出就行。
代码：
#include <bits/stdc++.h>
using namespace std;
int T, a, b, c, d, e, f, t[10000][13][32], s[10005 * 14 * 35];
int cal(int x){
while (x > 100){
if (x % 1000 == 202) return 1;
x /= 10;
}
return 0;
}
void init(){
int day[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31}, cnt = 0;
for (int y = 2000; y <= 9999; y++)
for (int m = 1; m <= 12; m++){
int k = day[m];
if (m == 2 && ((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0))) k++;
for (int d = 1; d <= k; d++){
t[y][m][d] = ++cnt;
s[cnt] = s[cnt - 1] + cal((y * 100 + m) * 100 + d);
}
}
}
void solve(){
cin >> a >> b >> c >> d >> e >> f;
cout << s[t[d][e][f]] - s[t[a][b][c] - 1] << "\n";
}
int main(){
init();
cin >> T;
while (T--)
solve();
return 0;
}
B. Bin Packing Problem
题目大意：
有 \(n\) 个物品，第 \(i\) 个物品为 \(a[i]\)，有无限个容量为 \(c\) 的空箱子，现有两种装箱的方法。
第一种：选择最前面的能放下物品的箱子放入物品
第二种：选择能放下物品且剩余容量最小的箱子放物品
问两种装箱方法各需要多少个箱子才能装完所有物品。
思路：
第一种装箱方法我们可以通过线段树来做，每个节点的值就是该箱子的容量，通过查询前面的箱子有没有足够的容量去存放物品，如果有就向左递归，没有就向右。
第二种装箱方法可以用 multiset 来做，因为 multiset 是有序的，可以用 lower_bound() 二分查找，直接将物品放入能放下该物品的最小容量的那个箱子。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int T, n, a[N], c, tr[N << 2];
void pushup(int u){
tr[u] = max(tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r){
if (l == r) tr[u] = c;
else {
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void update(int u, int l, int r, int p, int k){
if (l > p || r < p) return;
if (l == r) tr[u] -= k;
else {
int mid = l + r >> 1;
update(u << 1, l, mid, p, k);
update(u << 1 | 1, mid + 1, r, p, k);
pushup(u);
}
}
int query(int u, int l, int r, int k){
if (l == r){
if (tr[u] >= k) return l;
return n + 1;
}
int mid = l + r >> 1;
if (tr[u << 1] >= k) return query(u << 1, l, mid, k);
else return query(u << 1 | 1, mid + 1, r, k);
}
void ff(){
build(1, 1, n);
for (int i = 1; i <= n; i++)
update(1, 1, n, query(1, 1, n, a[i]), a[i]);
cout << query(1, 1, n, c) - 1 << " ";
}
void bf(){
multiset <int> s;
for (int i = 1; i <= n; i++){
auto it = s.lower_bound(a[i]);
if (it == s.end()) s.insert(c - a[i]);
else {
int x = *it;
s.erase(it); //multiset 可以存放重复数据，如果是删除某个值的话，会去掉多个箱子，导致答案错误，所以直接删除对应位置的元素
s.insert(x - a[i]);
}
}
cout << s.size() << "\n";
}
void solve(){
cin >> n >> c;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
ff();
bf();
}
int main(){
cin >> T;
while (T--)
solve();
}
E.Easy DP Problem
题目大意：
给了一个 dp 转移方程，以及一个序列，进行 q 次询问，要求输出询问的区间中，执行该 dp 方程的某个状态的答案。
思路：
举个栗子，当 m = 2，k = 2 时。
dp[2][2] = \(2^2\) + max(dp[1][2], dp[1][1] + b[2]) = \(2^2\) + max(\(1^2\) + max(dp[0][2], dp[0][1] + b[1]), \(1^2\) + max(dp[0][1], dp[0][0] + b[1]) + b[2]) = \(2^2\) + max(\(1^2\) + max(0, b[1]), \(1^2\) + max(0, b[1]) + b[2]) = \(2^2 + 1^2\) + b[2] + b[1]
通过一些例子，我们可以推得 \(dp[m][k] = \sum_{i = 1}^m i^2 + \sum_{i = m - k + 1}^m b[i]\)。
问题就变成了找 \([l, r]\) 这个区间中最大的 \(m\) 个数，可以通过主席树实现。
代码：
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
LL T, n, q, idx, root[N], a[N], b[N], l, r, k;
struct node{
LL l, r, cnt, sum;
}tr[N * 20];
LL update(LL p, LL l, LL r, LL k) {
LL x = ++ idx;
tr[x].l = tr[p].l;
tr[x].r = tr[p].r;
tr[x].cnt = tr[p].cnt + 1;
tr[x].sum = tr[p].sum + b[k];
if (l < r) {
LL mid = l + r >> 1;
if(k <= mid) tr[x].l = update(tr[p].l, l, mid, k);
else tr[x].r = update(tr[p].r, mid + 1, r, k);
}
return x;
}
LL query(LL p,LL q,LL k,LL l,LL r) {
if(l == r) return b[l] * k;
LL x = tr[tr[q].r].cnt - tr[tr[p].r].cnt, mid = l + r >> 1;
if (k <= x) return query(tr[p].r, tr[q].r, k, mid + 1, r);
return tr[tr[q].r].sum - tr[tr[p].r].sum + query(tr[p].l, tr[q].l, k - x, l, mid);
}
LL c(LL x) {
return x * (x + 1) / 2 * (2 * x + 1) / 3;
}
void solve(){
idx = 0;
cin >> n;
for(int i = 1; i <= n; ++ i) {
scanf("%lld", &a[i]);
b[i] = a[i];
}
sort(b + 1, b + 1 + n);
LL len = unique(b + 1, b + 1 + n) - b - 1;
for(int i = 1; i <= n; ++ i) {
a[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;
root[i] = update(root[i - 1], 1, len, a[i]);
}
scanf("%lld", &q);
while(q--) {
scanf("%lld%lld%lld", &l, &r, &k);
cout << c(r - l + 1) + query(root[l - 1], root[r], k, 1, len) << "\n";
}
}
int main() {
cin >> T;
while(T--)
solve();
return 0;
}
K. Killing the Brute-force
题目大意：
给定标程和暴力方法在 \(n\) = 1,2,3... 所花的时间，找到最小的 \(n\) 使得三倍标程的时间可以卡掉暴力方法，即暴力方法的时间大于三倍标程时间。
思路：
就是判断 b 有没有大于 3 * a，简单地遍历一遍判断就行
代码：
#include <bits/stdc++.h>
using namespace std;
int T, n;
void solve(){
cin >> n;
vector <int> a(n), b(n);
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
cin >> b[i];
for (int i = 0; i < n; i++)
if (a[i] * 3 < b[i]){
cout << i + 1 << "\n";
return;
}
cout << "-1\n";
}
int main(){
cin >> T;
while (T--)
solve();
return 0;
}
题目大意：
思路：
代码：