比赛链接 / 官方题解链接
A. Sequence with Digits
Solution
一直算到某一位出现 $0$ 为止。
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
int T;
LL n, k;
int main(){
for(read(T); T; T--){
read(n, k);
LL ans = n;
for(int i = 1; i < k; i++){
LL mn = 1e18, mx = -1e18;
LL t = ans;
while(t){
mn = min(mn, t % 10);
mx = max(mx, t % 10);
t /= 10;
}
if(mn == 0) break;
ans += mn * mx;
}
printf("%lld\n", ans);
}
return 0;
}
|
B. Young Explorers
Solution
贪心，从小到大排序，依次遍历，能构成 group 就构成 group。
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 200005;
int T, n, a[N];
int main(){
for(read(T); T; T--){
read(n);
for(int i = 1; i <= n; i++) read(a[i]);
sort(a+1, a+n+1);
int cnt = 0;
for(int i = 1; i <= n; i++){
int mx = a[i];
int j = i;
while(j <= n){
mx = max(mx, a[j]);
if(j - i + 1 >= mx){
cnt++;
break;
}
j++;
}
i = j;
}
printf("%d\n", cnt);
}
return 0;
}
|
C. Count Triangles
Solution
枚举 $z$，对于每个 $z$，需要 $O(1)$ 地找到 $(x,y)$ 的对数，满足：$x\in[A,B]$，$y\in[B,C]$，$x+y>z$.
推这个表达式的过程太过恶心（主要是边界恶心），先不写了，心累～
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
LL A, B, C, D;
LL cal(LL r, LL l){
return (l + r) * (r - l + 1) / 2;
}
int main(){
read(A, B, C, D);
LL ans = 0;
for(int z = C; z <= D; z++){
if(z-C >= B) continue;
ans += cal(B-z+C, max(1ll, B-z+B));
if(z - C < A - 1)
ans -= cal(A-1-z+C, max(1ll, A-1-z+B));
}
printf("%lld\n", ans);
return 0;
}
|
D. Game With Array
Solution
当 $S\geq2n$ 时，构造 $2,2,\cdots,2,S-2n+2$，取 $K=1$ 即可。
当 $S<2n$ 时，可以证明无解。
证明：取前缀和，那么一段连续数字的和就是前缀和序列中两个数字的差值。在前缀和序列中，如果出现数字 $x$，就不能出现数字 $y=(x+K)\%S$，因为如果 $x+K<S$，那么 $y-x=K$；如果 $x+K\geq S$，那么 $y=x+K-S$，$x-y=S-K$，均不符合条件。所以数字 $x$ 相当于占据了两个位置：$x$ 和 $(x+K)\%S$，而最多有 $S$ 个位置，不够 $n$ 个数分。
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
int n, s;
int main(){
read(n, s);
if(s >= 2 * n){
puts("YES");
for(int i = 1; i < n; i++)
printf("%d ", 2);
printf("%d\n", s - 2 * (n - 1));
printf("1\n");
return 0;
}
puts("NO");
return 0;
}
|
E. Restorer Distance
Solution
如果确定了最终的高度的话，我们容易 $O(n)$ 地求出花费的代价。
然后比赛的时候猜测代价是高度的单峰函数，所以套个三分就惊喜地过了……
Code
>folded1
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
49
50
51
52
53
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 100005;
int n, A, R, M;
LL h[N];
LL func(LL mid){
LL inc = 0, dec = 0;
for(int i = 1; i <= n; i++){
if(h[i] > mid) dec += h[i] - mid;
else inc += mid - h[i];
}
LL res = M * min(inc, dec);
if(inc > dec) res += A * (inc - dec);
else res += R * (dec - inc);
return res;
}
LL tripartition(LL l, LL r){
int mid1 = l, mid2 = r;
while(mid1 < mid2){
mid1 = l + (r - l) / 3;
mid2 = r - (r - l) / 3;
if(func(mid1) > func(mid2)) l = mid1 + 1;
else r = mid2 - 1;
}
return func(l);
}
int main(){
read(n, A, R, M); M = min(M, A + R);
LL mn = 1e18, mx = -1e18;
for(int i = 1; i <= n; i++){
read(h[i]);
mn = min(mn, h[i]);
mx = max(mx, h[i]);
}
printf("%lld\n", tripartition(mn, mx));
return 0;
}
|
F. Guess Divisors Count
留坑……待填