CF1107题解

终于有一场能上分的比赛了

A:
读完题后我们可以发现如果数字大于两位那么肯定可以
只要将第一位单独拿出来分为一段
如果数字是两位那么第一位小于第二位时就可以,反之不可以
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
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
#define P pair<int,int>
using namespace std;
template <typename T>
inline void read(T &t)
{
int f = 0, c = getchar();
t = 0;
while (!isdigit(c))
f |= c == '-', c = getchar();
while (isdigit(c))
t = t * 10 + c - 48, c = getchar();
if (f)
t = -t;
}
template <typename T, typename... Args>
inline void read(T &t, Args &... args)
{
read(t);
read(args...);
}
int main(){
int t;
read(t);
for (int i = 1; i <= t;i++){
int n;
read(n);
if(n>2){
puts("YES");
cout << 2 << endl;
cout<<(char)getchar()<<" ";
for (int i = 2;i<=n;i++)
cout<<(char)getchar();
cout << endl;
}else{
int a=getchar(),b=getchar();
if(a>=b) puts("NO");
else{
puts("YES");
puts("2");
cout << (char)a << " " << (char)b << endl;
}
}
}
}

B:
经过打表找规律我们可以发现S函数是1-9循环的
让后就可以做了

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
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
#define P pair<int,int>
using namespace std;
template <typename T>
inline void read(T &t)
{
int f = 0, c = getchar();
t = 0;
while (!isdigit(c))
f |= c == '-', c = getchar();
while (isdigit(c))
t = t * 10 + c - 48, c = getchar();
if (f)
t = -t;
}
template <typename T, typename... Args>
inline void read(T &t, Args &... args)
{
read(t);
read(args...);
}
const int maxn = 35;
int S[maxn];
int main(){
int t;
read(t);
for (int i = 1; i <= t;i++){
LL k,x;
read(k,x);
cout << (k - 1) * 9 + x << endl;
}
}

C:
读完题以后会发现这是一个很显然的贪心
对于连续的字母我们自然是要取其中前k大的
然后用priority_queue搞一下就可以了

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
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
#define P pair<int,int>
using namespace std;
template <typename T>
inline void read(T &t)
{
int f = 0, c = getchar();
t = 0;
while (!isdigit(c))
f |= c == '-', c = getchar();
while (isdigit(c))
t = t * 10 + c - 48, c = getchar();
if (f)
t = -t;
}
template <typename T, typename... Args>
inline void read(T &t, Args &... args)
{
read(t);
read(args...);
}
const int maxn = 2e5 + 5;
int a[maxn];
priority_queue<LL> q;
int main(){
int n,k;
read(n, k);
for (int i = 1;i<=n;i++) read(a[i]);
LL ans = 0;
int last = 0;
for (int i = 1;i<=n;i++) {
int ch=getchar()-'a';
if(ch!=last){
int cnt=k;
while(cnt>0 && !q.empty()){
ans+=q.top();
q.pop();
cnt--;
}
while(!q.empty())
q.pop();
last = ch;
}
q.push(a[i]);
}
int cnt=k;
while(cnt>0 && !q.empty()){
ans+=q.top();
q.pop();
cnt--;
}
while(!q.empty())
q.pop();
cout << ans;
}

D:
这题据说可以用前缀和做
我的思想是用bitset
用bitset判断每一行的相应位置是否一样
让后再暴力判每一列是否一样
让后就A了

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
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#define LL long long
#define P pair<int,int>
using namespace std;
template <typename T>
inline void read(T &t)
{
int f = 0, c = getchar();
t = 0;
while (!isdigit(c))
f |= c == '-', c = getchar();
while (isdigit(c))
t = t * 10 + c - 48, c = getchar();
if (f)
t = -t;
}
template <typename T, typename... Args>
inline void read(T &t, Args &... args)
{
read(t);
read(args...);
}
const int maxn = 5220;
bitset<maxn> b[maxn];
int main(){
int n;
read(n);
for(int i=1;i<=n;i++){
for (int j = 1; j < n;j+=4){
char ch=getchar();
while(isspace(ch))
ch = getchar();
if(ch=='8' || ch=='9' || ch=='A' || ch=='B' || ch=='C' || ch=='D' || ch=='E' || ch=='F')
b[i][j] = 1;
if(ch=='4' || ch=='5' || ch=='6' || ch=='7' || ch=='C' || ch=='D' || ch=='E' || ch=='F')
b[i][j+1] = 1;
if(ch=='2' || ch=='3' || ch=='6' || ch=='7' || ch=='A' || ch=='B' || ch=='E' || ch=='F')
b[i][j+2] = 1;
if(ch=='1' || ch=='3' || ch=='5' || ch=='7' || ch=='9' || ch=='B' || ch=='D' || ch=='F')
b[i][j+3] = 1;
}
}
for (int ans = n; ans >= 2;ans--){
if (n % ans != 0)
continue;
bool ok=true;
for (int i = 1; i < n;i+=ans){
for (int j = i+1; j < i + ans;j++){
ok &= (b[j] == b[i]);
}
if(!ok)
break;
for (int j = 1; j < n;j+=ans){
for (int k = j+1; k < j + ans;k++)
ok &= (b[i][k] == b[i][k - 1]);
if(!ok)
break;
}
}
if(ok){
cout << ans << endl;
return 0;
}
}
puts("1");
}

剩下三道不会…