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
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#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搞一下就可以了

```cpp
#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了

#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");
}

剩下三道不会…