A
题目大意：有三个人和三种葡萄，三个人分别要吃$x, y, z$个葡萄，三种葡萄分别有$a, b, c$个。第一个人只吃第一种葡萄，第二个人不吃第三种葡萄，第三个人什么葡萄都能吃。问三个人能不能吃够葡萄。
模拟。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int x, y, z, a, b, c;
void init(){
x = read(), y = read(), z = read(), a = read(), b = read(), c = read();
}
void solve(){
int flag = 0;
do{
if(x > a) break;
a -= x;
if(y > a + b) break;
int res = a + b + c - y;
if(z > res) break;
flag = 1;
}while(0);
printf("%s\n", flag ? "YES": "NO");
}
int main(){
init();
solve();
return 0;
}
B
题目大意：给定长度为$n$的数列，求一种方案，将数列划分为$k$段，每一段长度不小于$m$，并且使$\Sigma \text{每一段中前}m \text{大的数的和}$最大。
可以发现答案一定是整个数列前$mk$大数的和，所以只要考虑怎么划分即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, m, k;
int a[200005], pos[200005];
int gap[200005];
pair<int, int> pp[200005];
void init(){
n = read(), m = read(), k = read();
for(int i = 1; i <= n; ++i)
a[i] = read(), pp[i].first = -a[i], pp[i].second = i;
sort(pp + 1, pp + n + 1);
for(int i = 1; i <= m * k; ++i)
pos[i] = pp[i].second;
sort(pos + 1, pos + m * k + 1);
}
void solve(){
ll ans = 0;
for(int i = 1; i <= m * k; ++i){
ans += 1ll * (-pp[i].first);
if(i % m == 0) gap[i / m] = pos[i + 1] - 1;
}
printf("%I64d\n", ans);
for(int i = 1; i < k - 1; ++i)
printf("%d ", gap[i]);
printf("%d\n", gap[k - 1]);
}
int main(){
init();
solve();
return 0;
}
C
题目大意：求$n!$在$b$进制下末尾连续0的个数。
先考虑十进制的情况。可以发现，若十进制下$n!$末尾0个数为$k$，则$n!$就有$10^k$作为约数。由于$10=2\times 5$，这时只要计算$n!$的分解中$2, 5$的次数的较小值即可算出$k$。因为这个较小值说明了$n!$中至多只有这么多$10$的次幂。
回到这一题。本题中末尾的0的个数由$b$的次幂构成，因而对$b$做分解，然后对$b$的每一个质因子$p^a$，算得$n!$分解中$p$的次数，设为$e$，得到该质因数最多可以贡献$\frac{e}{a}$个末尾0。对其取最小值即可。
时间复杂度大约为$O(\sqrt{n} \log \sqrt{n})$。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
ll n, b, ans;
ll calc(ll x){
ll res = 0;
for(ll tt = x; ; ){
res += n / tt;
if(1.0 * tt * x > 1.0 * n) break;
tt *= x;
}
return res;
}
void init(){
scanf("%I64d%I64d", &n, &b);
ans = n;
}
void solve(){
ll t = b;
for(ll i = 2; i * i <= b; ++i){
if(t % i == 0){
int al = 0;
ll res = 1;
do{
t /= i, al++, res *= i;
}while(t % i == 0);
ans = min(ans, calc(i) / al);
}
if(t == 1ll) break;
}
if(t != 1ll){
ans = min(ans, calc(t));
}
printf("%I64d\n", ans);
}
int main(){
init();
solve();
return 0;
}
D
题目大意：给定一个长度为$n$的线段，线段上每一段都染上了某种颜色，一次操作可以将一段连续的颜色转换为另一种颜色，求最少的操作次数使得整个线段都是同一种颜色。
先把段抽象成点，即把一段相同颜色的区间抽象称为一个该颜色的点。
再设$f(i, j)$为使得$[i, j]$同色最少的操作次数。考虑整个区间的颜色都和区间的左/右端点相同，就有：
1 |
|
E
题目大意：有一个长度为$n$，公差为$d(d>0)$的等差数列。每一项大小都位于$[0, 10^9]$之间。你可以有2种询问方式：询问数列的第$k$项是多少，或者询问数列中有没有严格大于$x$的项。至多询问60次。目标是找出这个数列的最小值和公差。
首先用第二个询问找出数列的