比赛链接

https://codeforces.com/contest/1555

1. A. PizzaForces

1.1. 题意

6元15个物品，8元20个物品，10元25个物品

现在需要买至少n个物品，问需要多少钱

1.2. 做法

首先看单价，发现他们都相同，然后就是尽量不要多买了。

如果n比15,20,25的最小公倍数的两倍还要大，则多出的这一部分，可以考虑直接购买6元的，剩下的小范围dp即可

核心思想： 大范围贪心，小范围dp

notes: 注意一定是至少两倍以上才能贪心

比赛链接

https://codeforces.com/contest/1551

1. A. Polycarp and Coins

1.1. 题意

给你一个数n，你要把他拆为$c_1+2c_2$的形式，你需要最小化$c_1$和$c_2$的差

1.2. 做法

对模3的余数进行分类讨论

1.3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <bits/stdc++.h>

using namespace std;


int main() {
    std::ios::sync_with_stdio(false);
    cin.tie();

    int step;
    cin >> step;
    while (step--) {
        int n;
        cin >> n;
        if (n % 3 == 0) {
            cout << n / 3 << " " << n / 3 << endl;
        } else if (n % 3 == 1) {
            cout << n / 3 + 1 << " " << n / 3 << endl;
        } else {
            cout << n / 3 << " " << n / 3 + 1 << endl;
        }
    }
}
 

比赛链接

VK Cup 2021 - Elimination (Engine)

1. A. Binary Decimal

1.1. 题意

给你一个十进制数，你要把它拆成多个只由0和1组成的十进制数之和，问最少拆几个。

1.2. 做法

答案就是十进制数每个位上的数中的最大值

1.3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <bits/stdc++.h>
using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie();

    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        int mx = 0;
        while (x) {
            mx = max(mx, x % 10);
            x /= 10;
        }
        cout << mx << endl;
    }
}

题目大意：

你需要计算有多少对满足长度为n的排列$p$和$q$，满足$p$字典序>$q$ 且 $inv(p)<inv(q)$，答案取模

$inv$ 为逆序对个数

做法：

设$f(i,j)$为长度为$i$、逆序对个数为$j$的排列的个数 , 考虑第一个数字为$t$

$f(i,j) = \sum_{t \in [1,i]} f(i-1,j-t+1)$

一个填$u$，另一个填$v$ $u<v$

$$
\begin{aligned}
ans[i] \&= i * ans[i-1] + \sum_{1<=u<v<=i, x+u>y+v} f(i-1,x)\cdot f(i-1,y)
\&= i * ans[i-1] + \sum_{x-y>v-u, 1<=u<v<=i} f(i-1,x)\cdot f(i-1,y)
\&= i * ans[i-1] + \sum_{x-y>d, 1<=d<i} (i-d)*f(i-1,x)\cdot f(i-1,y)
\&= i * ans[i-1] + \sum_{x,y} f(i-1,x)\cdot f(i-1,y) \cdot \sum_{x-y>d, 1<=d<i} (i-d)
\end{aligned}
$$

比赛链接

http://codeforces.com/gym/102832

A. Krypton

题意

充游戏币，首充可以获得优惠，之后充值就没有优惠了，问你x元最多能拿到多少游戏币。
$$
\begin{array}{|c|c|c|}
\hline
\text{Price (RMB yuan)}
& \text{Normal amount (coupons)}
& \text{First recharge reward (coupons)}
\ \hline 1 & 10 & 8
\ \hline 6 & 60 & 18
\ \hline 28 & 280 & 28
\ \hline 88 & 880 & 58
\ \hline 198 & 1980 & 128
\ \hline 328 & 3280 & 198
\ \hline 648 & 6480 & 388
\ \hline
\end{array}
$$

比赛链接

http://codeforces.com/gym/102798

A. Golden Spirit

有一个桥，桥两边都有n个老人，你桥的一边，你可以花时间x把一个老人带到对面，然后你可以接着把那边的老人带回来，你也可以原地等待，所有老人移动一次以后需要休息t分钟，问你至少花费多少时间，能让所有老人都互相跑到对面，然后又回到原本的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include<bits/stdc++.h>
using namespace std;

#define ll long long
int main(){
    int T; scanf("%d", &T);
    while(T--) {
        ll n, x, t; scanf("%lld %lld %lld", &n, &x, &t);
        ll y1 = max(x + 2 * t - 2 * n * t, 0ll);
        ll y2 = max(x - 2 * n * t, 0ll);
        ll ans1 = y1 + 4 * n * t, ans2 = y2 + (4 * n + 1) * t;
        printf("%lld\n", min(ans1, ans2));
    }
}