又还是只能做到 C，太菜了
看看能不能有时间练练 D
A. The Good Array
题意
给定整数 n，k。
构造一个 0−1 序列 a1,a2,…,an，满足：
- 前 i 个元素中至少有 ⌈ki⌉ 个 1。
- 后 i 个元素中至少有 ⌈ki⌉ 个 1。
解法
正解是 O(1) 的（请查看官方题解）。
当时随便写了一个贪心，把 i 从小往大枚举，如果不够就尽量往中间放 1。
我觉得这个贪心很对，但是我不会证，反正确实是对的。
AC 代码
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
63
64
65
66
67
68
69
70
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem0(x) memset(x,0,sizeof(x))
int read(){
int f=1,x=0;
char c;
c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
const int N = 105;
int a[N];
void solve(){
mem0(a);
int n=read(),k=read();
for(int i=1;i<=n;i++){
int need = i/k;
if(i%k!=0)need++;
int s1 = 0;
for(int j=1;j<=i;j++){
s1 += a[j];
}
for(int j=i;j>0;j--){
if(s1<need && !a[j]){
a[j]=1;
s1++;
}
}
int s2 = 0;
for(int j=n;j>n-i;j--){
s2 += a[j];
}
for(int j=n-i+1;j<=n;j++){
if(s2<need && !a[j]){
a[j]=1;
s2++;
}
}
}
int ans = 0;
for(int i=1;i<=n;i++){
ans += a[i];
}
printf("%d\n",ans);
}
int main(){
int T=read();
while(T--){
solve();
}
return 0;
}
|
B. Lamps
题意
有 n 盏灯。每盏灯表示为二元组 (ai,bi)。每盏灯的状态一定是以下三个：打开，关闭，损坏。
你可以打开一盏关闭的灯（没有损坏），获得 bi 分，同时，所有 ai≤当前打开灯数 的灯会立即损坏（无论是否开关）。注意：打开然后已经损坏的灯不计入打开的灯。请问：最多可以获得多少分？
解法
我们先从 a=1 开始考虑。
不难想到，a=1 的灯开完就会坏，然后当前打开灯数变为 0。因此，对于所有 a=1 的灯，一定只能开一盏，贪心开 b 最大的。
我们尝试推广这个结论，推广得到，a=x 的灯能开且最多能开 x 盏。
我们分三种情况证明这个结论：
- a=x 的灯没有：显然成立。
- a=x 的灯大于等于 x 盏：这时候开 x 盏就全部损坏了，结论仍然成立。
- a=x 的灯小于等于 x 盏：这时候不会立即损坏，而是到后面开 a=x+1,a=x+2,… 的时候损坏，而不会影响到后面灯的开关（因为一定在后面灯没有损坏前先全部坏掉了，不占开灯的这个指标了）。
因此，最后只需统计对于每个 a，前 a 大的 b 然后累加即可。
AC 代码
这份代码用了优先队列，不使用优先队列也是完全可以的。
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
63
64
65
66
67
68
69
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
int read(){
int f=1,x=0;
char c;
c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
const int N = 2e5+5;
struct Node{
int a,b;
bool operator<(const Node&rhs)const{
return a<rhs.a;
}
};
void solve(){
int n=read();
vector<Node> v;
for(int i=1;i<=n;i++){
int a=read(),b=read();
v.push_back({a,b});
}
sort(v.begin(),v.end());
ll ans = 0;
int cur = 0;
priority_queue<int> pq;
for(int i=1;i<=n;i++){
while(cur<n && v[cur].a == i){
pq.push(v[cur].b);cur++;
}
for(int j=1;j<=i;j++){
if(!pq.size())break;
ans += pq.top(); pq.pop();
}
while(pq.size())pq.pop();
}
printf("%lld\n",ans);
}
int main(){
int T=read();
while(T--){
solve();
}
return 0;
}
|
C. Insert Zero and Invert Prefix
题意
给定一个 0−1 序列 a1,a2,…,an。
现能对空序列执行 n 次如下操作：往序列中插入一个 0，并反转前面的数。
例：对于序列 101001，往第五个元素后插入一个 0 后，序列变为 0101101 （红色的 0 为插入的 0）
请问：能否确定一个操作，使空序列等于序列 a1,a2,…,an？如果可以，请输出操作。
题解
先考虑最后一个是 1 的情况。这种情况显然是不可能的，因为没有人来反转最后一位。
我们猜想：对于任何最后一位是 0 的序列，都一定存在一个合法的操作，我们尝试构造出这个操作。
观察序列：
1,1,0,1,0,1,1,0
考虑最后的 0 是最后插入的：
0, 0, 1, 0, 1, 0, 0,0
那问题就转化成求解序列：
0,0,1,0,1,0,0
这时候有两个 0，一定先插入最后一个 0，然后构造前面的序列，然后再插入最靠前的 0。
1, 1, 0, 1, 0,0,0
就这样不断递归，直到当前求解的序列全部是 0 即可。
细节参见代码。
AC 代码
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
63
64
65
66
67
68
69
70
71
72
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem0(x) memset(x,0,sizeof(x))
int read(){
int f=1,x=0;
char c;
c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
const int N = 1e5+5;
int a[N];
void dfs(int x,bool rev){
if(x==1){
printf("0 ");
return;
}
for(int i=x;i>=1;i--){
if(i==1||
a[i]==0 && a[i-1]==1 && !rev ||
a[i]==1 && a[i-1]==0 && rev){
for(int j=i+1;j<=x;j++){
printf("0 ");
}
if(i!=1)dfs(i-1,!rev);
printf("%d ",i-1);
break;
}
}
}
void solve(){
int n=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
if(a[n]==1){
puts("NO");return;
}
puts("YES");
dfs(n,0);
puts("");
}
int main(){
int T=read();
while(T--){
solve();
}
return 0;
}
|
