CF

概述

​ CF #700 A-D2

​ 27min切 A 1:26切B C做出来了,然后因为某个非常非常非常弱智的错误

​ 2C WA5 了4发 改了就过了 (我直呼氧化钙

A

​ 对于给定的字符串,分别对于奇数和偶数位置的字符串进行修改,字符串的位置从0开始,故而偶数位置的字符尽可能小,奇数位置的字符串尽可能大

​ 显然一眼贪心,对于一个位置K,我们分类讨论一下

​ 1.如果这个位置为奇数,且$k \ne z$ ,那么此时的最优解是$k = z$

​ 2.如果这个位置为奇数,且$k = z$ ,那么此时的最优解是$k = y$

​ 3.如果这个位置为偶数,且$k \ne a$ ,那么此时的最优解是$k = a$

​ 4.如果这个位置为奇数,且$k = a$ ,那么此时的最优解是$k = $b

​ 然后噼里啪啦一顿码就完事了

Code

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
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define RE register

string p;

inline void fread(int &x) {
x = 0;
int f = 1;
char ch = getchar();
while(ch < '0'||ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0'&&ch <= '9') {
x = (x<<3) + (x<<1) + (ch^48);
ch = getchar();
}
x = x * f;
}

inline void work() {
string ch;
cin>>ch;
for(RE int i = 0 ;i < ch.length(); i++) {
if(i % 2 == 0) {
//char x = p[ch[i] - 'a' ];
if(ch[i] == 'a') cout<<'b';
else cout<<'a';
}else {
if(ch[i] == 'z') cout<<'y';
else cout<<'z';
}
}
cout<<endl;
}

int main() {
int n;
fread(n);
p = "abcdefghijklmnopqrstuvwxyz";
for(RE int i = 1; i <= n; i++) {
work();
}
return 0;
}

B

​ 题目太长了,戳这里

​ 看似这里直接模拟即可,其实不是的(没错我就是这样子WA了

​ 考虑一个攻击力最大的K且英雄血量小于K,如果前面英雄叨叨叨剩余1滴血

​ 他可以和K同归于尽,也就是“YES”

​ 但是如果不在最后一个打,而是第一个第二个….

​ 一刀下去,啪,没了,答案就会变成”NO”

​ 所以应该给怪物排序,攻击力越大越往后打

​ 然后一个个减去即可qwq

Code

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
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define RE register

struct node {
ll a,b;
}f[100010];

inline void fread(ll &x) {
x = 0;
int f = 1;
char ch = getchar();
while(ch < '0'||ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0'&&ch <= '9') {
x = (x<<3) + (x<<1) + (ch^48);
ch = getchar();
}
x = x * f;
}

inline bool cmp(node x,node y) {
return x.a < y.a;
}

inline void work() {
ll x,y,n;
fread(x);
fread(y);
fread(n);
for(RE int i = 1;i <= n ;i++) fread(f[i].a);
for(RE int i = 1;i <= n ;i++) fread(f[i].b);
sort(f+1,f+1+n,cmp);
int i = 1;
int flag = 0;
while(y >= 0) {
while(f[i].b > 0) {
if(i == n && f[i].b - x <= 0) {
//cout<<f[i].b<<"qwq";
flag = -1;
break;
}
f[i].b -= x;
y -= f[i].a;
if(y < 0) break;
}
if(flag == -1) break;
i++;
}
if(y >= 0 || flag == -1) printf("YES\n");
else printf("NO\n");
}

int main() {
ll n;
fread(n);
for(RE int i = 1; i <= n; i++) {
work();
}
return 0;
}

C

​ 做的第一道交互题(虽然说以前了解过

​ 有一个未知的排列f,对于一个下标 i 你可以知道f[i]的值,最多询问100次

​ (n < 1e5然后询问该数组的谷底,也就是存在一个pos 他两边相邻的值都大于他

​ 一眼二分 但是因为奇奇怪怪的输入和输出格式一直 WA/TLE

​ 要特判 n == 1的情况(不然WA6/TLE 43

Code

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
73
74
75
76
77
78
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define RE register

int f[100010];

inline void fread(int &x) {
x = 0;
int f = 1;
char ch = getchar();
while(ch < '0'||ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0'&&ch <= '9') {
x = (x<<3) + (x<<1) + (ch^48);
ch = getchar();
}
x = x * f;
}

int main() {
int n;
fread(n);
if(n == 1) {
printf("! 1\n");
return 0;
}
memset(f,0,sizeof(f));
cout<<"? "<<"1"<<endl;cout.flush();
fread(f[1]);
cout<<"? "<<"2"<<endl;cout.flush();
fread(f[2]);
if(f[1] < f[2]) {
cout<<"! 1"<<endl;
return 0;
}
cout<<"? "<<n-1<<endl;cout.flush();
fread(f[n-1]);
cout<<"? "<<n<<endl;cout.flush();
fread(f[n]);
if(f[n] < f[n-1]) {
cout<<"! "<<n<<endl;
return 0;
}
int l = 2;
int r = n - 1;
while(1) {
int mid = (l + r) / 2;
cout<<"? "<<mid<<endl;cout.flush();
fread(f[mid]);
if(f[mid] < f[mid+1]&& f[mid] < f[mid-1]) {
cout<<"! "<<mid<<endl;
break;
}
cout<<"? "<<mid-1<<endl;cout.flush();
fread(f[mid-1]);
if(f[mid] < f[mid+1]&& f[mid] < f[mid-1]) {
cout<<"! "<<mid<<endl;
break;
}
cout<<"? "<<mid+1<<endl;cout.flush();
fread(f[mid+1]);
if(f[mid] < f[mid+1]&& f[mid] < f[mid-1]) {
cout<<"! "<<mid<<endl;
break;
}
if(f[mid-1] < f[mid+1]) {
r = mid;
}else {
l = mid;
}
}
return 0;
}

D-1

​ 给我们一个长度为n的序列,现在可以染色黑白,抽出来形成a0序列和a1序列

​ 现在合并相邻的相同值,最终序列剩下的元素个数就是贡献,D1询问我们最大贡献,D2询问我们最小贡献

​ 注意,a0不记录下标而是记录ai的值

​ 具体手玩一下样例和参考题目

​ 应该是一道贪心,如果要贡献最大,那么我们要让相邻的相同的数尽可能得少

​ 考虑维护a0和a1的最后一个元素,记为x,y

​ 此时我们要插入一个新的值k,如果k不等于x,y

​ 那么随便插都一样 (这里优先y

​ 如果等于x或y,就插入与之相反的那个

​ 这样子我们一直维护就好了

Code

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
#include <bits/stdc++.h>

#define ll long long
#define RE register

int n,x,y,ans;
int f[100010];

inline void fread(int &x) {
x = 0;
int f = 1;
char ch = getchar();
while(ch < '0'||ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0'&&ch <= '9') {
x = (x<<3) + (x<<1) + (ch^48);
ch = getchar();
}
x = x * f;
}

int main() {
fread(n);
for(RE int i = 1 ;i <= n; i++) fread(f[i]);
x = f[1];
ans = 1;
for(RE int i = 2 ;i <= n; i++) {
if(f[i] != x) {
ans++;
if(f[i+1] != x && f[i] != y) {
y = f[i];
}else {
x = f[i];
}
}else if(f[i] != y) {
ans++;
y = f[i];
}
}
std::printf("%d\n",ans);
return 0;
}

D - 2

     题目和D1一样,只不过这个是求最小

​ 都差不多,拿到序列,我们先把能合并的都合并了

​ 用vector维护一下就得到了目前无重复的A 数组

​ 然后用一个map标记一下,一个个放,如果目前没有重复的ans++

​ 如果目前序列内重复了,就代表可以有一种放法能使其合并

​ 我们就尽可能地让他们合并

​ 这里还有点没明白 挖个坑

Code

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
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define RE register

ll n,x,y,ans;
ll f[100010];

vector<long long>p;
map<ll,ll> v;

inline void fread(ll &x) {
x = 0;
int f = 1;
char ch = getchar();
while(ch < '0'||ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0'&&ch <= '9') {
x = (x<<3) + (x<<1) + (ch^48);
ch = getchar();
}
x = x * f;
}

int main() {
ans = 0;
f[n] = 0;
fread(n);
for(RE int i = 0 ;i < n; i++) fread(f[i]);
for(RE int i = 0 ;i < n;i++) {
if(f[i] != f[i+1]) {
p.push_back(f[i]);
}
}
for(RE int i = 0 ;i < p.size(); i++) {
if(v[p[i]] == 0) {
ans++;
v[p[i]]++;
}else {
v.clear();
v[p[i]]++;
if(i >= 1)v[p[i-1]]++;
}
}
printf("%lld\n",ans);
return 0;
}

0%