毒瘤场。最后极限反杀 $\Delta =0$，不然就挂了。
Problem A
题意：
有 $n$ 个正整数，它们的大小在 $[a-b,a+b]$ 之间。
问存不存在一种情况，使得它们的总和在 $[c-d,c+d]$ 之间。
$1 \leq n \leq 1000,0 \leq b<a \leq 1000,0 \leq d < c \leq 1000$
做法：
显然，如果 $n$ 个数均取最小值总和仍大于 $c+d$ 或者均取最大值总和仍小于 $c-d$，则不存在。
否则必定存在一种情况。
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
| # include <bits/stdc++.h>
# define rr register
const int N=100010,INF=0x3f3f3f3f;
inline int read(void){
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-')f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
res=res*10+c-48;
return res*f;
}
int main(void){
int T=read();
while(T--){
int n,a,b,c,d;
n=read(),a=read(),b=read(),c=read(),d=read();
if((n*(a-b))<=c+d&&(n*(a+b))>=c-d){
puts("Yes");
}else
puts("No");
End:;
}
return 0;
}
|
Problem B
题意：
给定数组 $a_1,a_2,…,a_n$ 和 $k$。
你需要找出 $a$ 的一个长度为 $k$ 的子区间，使得该子区间的峰最多。
定义一个数组 $b_1,b_2,…,b_m$ 的峰的数量为 $\sum\limits_{i=2}^{m-1} [a_{i-1}a_{i+1}]$。
$3 \leq k \leq n \leq 2·10^5,0 \leq a_i \leq 10^9,a_i \neq a_{i+1}$
做法：
对原数组的峰记前缀和。然后枚举子区间起始点就可以算出每一个长度为 $k$ 的子区间中峰的数量。
注意，如果子区间的起点或终点是原数组中的峰，则要减去它们的贡献，因为它们在该子区间中不再是峰。
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
| # include <bits/stdc++.h>
# define rr register
const int N=200010,INF=0x3f3f3f3f;
int sum[N];
int a[N];
int v[N];
int T;
int n,k;
inline int read(void){
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-')f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
res=res*10+c-48;
return res*f;
}
int main(void){
T=read();
while(T--){
n=read(),k=read();
for(rr int i=1;i<=n;++i){
a[i]=read();
sum[i]=0;
v[i]=0;
}
for(rr int i=2;i<=n-1;++i){
if(a[i-1]<a[i]&&a[i]>a[i+1])
v[i]=1;
sum[i]=sum[i-1]+v[i];
}
sum[n]=sum[n-1];
int l=1,ret=0;
for(rr int i=1;i<=n-k+1;++i){
int temp=sum[i+k-1]-sum[i-1]-v[i+k-1]-v[i];
if(temp>ret){
ret=temp;
l=i;
}
}
printf("%d %d\n",ret+1,l);
}
return 0;
}
|
Problem C
吐槽：
出题人放个什么东西不好要在 C 放个结论，，，
题面：
有一个排列生成器，生成长为为 $n$ 的排列 $a$，$a$ 中每一个位置初始为空。
第 $i$ 次操作，生成器会选择 $count_{r_j}$ 最大的位置，并将 $a$ 中的该位置填上 $i$。$r,count$ 随之更新。如果有多个这样的位置，生成器会选择任意一个位置。
问，对于给定的排列 $p_1,p_2,…,p_n$，是否有可能是由生成器生成的？
$1 \leq n \leq 10^5,p$ 是 $1$ 到 $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
| # include <bits/stdc++.h>
# define rr register
const int N=100010,INF=0x3f3f3f3f;
int T;
int a[N];
int cnt[N];
int wz[N];
int n;
inline int read(void){
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-')f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
res=res*10+c-48;
return res*f;
}
int main(void){
T=read();
while(T--){
n=read();
for(rr int i=1;i<=n;++i){
a[i]=read();
wz[a[i]]=i;
}
int pt=1,last=n+1;
while(pt<=n){
int temp=wz[pt];
int ptt=temp;
for(;temp<=n&&a[temp]==pt;++temp){
++pt;
}
--temp;
if(temp!=last-1){
puts("No");
goto End;
}else{
last=ptt;
}
}
puts("Yes");
End:;
}
return 0;
}
|
Problem D
题意：
有 $n$ 个显示器，每个显示器上都有一些灯，一些是打开的，一些是关闭的。
你需要正好打开 $k$ 个灯，使得能组成数字，且数字最大。数字可以有前导零。
$1 \leq n \leq 2000,0 \leq k \leq 2000$
做法：
DP。设 $f_{i,j}$ 表示后 $i$ 位打开 $j$ 次灯，第 $i$ 位的数字为 $f_{i,j}$。
$f_{n+1,0}=0$，其余状态均为 $-\inf$。
$f_{i,j}$ 为所有满足= $f_{i+1,j-w} \neq -\inf$ 且第 $i$ 位可以被改成 $w$ 的最大的 $w$。
如果 $f_{1,k} = -\inf$，则无解。
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| # include <bits/stdc++.h>
# define rr register
const int N=2010,INF=0x3f3f3f3f;
int f[N][N];
std::string val[11]={"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
std::string p[N];
int n,k;
inline int read(void){
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-')f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
res=res*10+c-48;
return res*f;
}
int main(void){
n=read(),k=read();
for(rr int i=1;i<=n;++i){
std::cin>>p[i];
}
memset(f,0xcf,sizeof(f));
f[n+1][0]=0;
for(rr int i=n;i;--i){
for(rr int dig=0;dig<=9;++dig){
int v=0;
for(rr int j=0;j<=7;++j){
if(p[i][j]=='1'&&val[dig][j]=='0'){
goto End;
}else if(p[i][j]!=val[dig][j]){
++v;
}
}
for(rr int j=k;j>=v;--j){
if(f[i+1][j-v]>=0){
f[i][j]=dig;
}
}
End:;
}
}
int ret=0;
if(f[1][k]<0){
printf("-1");
return 0;
}
for(rr int i=1;i<=n;++i){
int smv=f[i][k],pp=0;
int v=0;
printf("%d",smv);
for(rr int j=0;j<=7;++j){
if(p[i][j]=='1'&&val[smv][j]=='0'){
return 0;
}else if(p[i][j]!=val[smv][j]){
++v;
}
}
k-=v;
}
return 0;
}
|