A - Nezzar and Colorful Balls
输出序列中出现最多次数的个数。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| ##include "bits/stdc++.h"
using namespace std;
map<int, int> mp;
void solve() {
int _; cin >> _;
while(_--) {
int n; cin >> n;
mp.clear();
int ans = -1;
for(int i = 1;i <= n; i++) {
int x; cin >> x;
mp[x]++;
ans = max(ans, mp[x]);
}
cout << ans << endl;
}
}
signed main() {
solve();
}
|
B - Nezzar and Lucky Number
题意：有一个luck数d，问能不能将一个x拆成任意多个数之和，并且每个数之中都要有一个d？
思路： 首先盲猜写$x>d*10$都是可以的，因为都可以拆成10个数，每个数无非多加了很多个10而已。 所以打表$d*10$之内的数即可，只需要判断尾部，尾部对了，并且小于x，无非就多加几个10而已。
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
| ##include "bits/stdc++.h"
using namespace std;
void solve() {
int _; cin >> _;
while(_--) {
int q, d; cin >> q >> d;
for(int i = 1;i <= q; i++) {
int x; cin >> x;
bool flag = false;
if(x >= d * 10) flag = true;
for(int j = 1;j <= 10; j++) {
int t = j * d;
if(t <= x && (t % 10 == x % 10)) {
flag = true;
break;
}
}
cout << (flag ? "YES" : "NO") << endl;
}
}
}
signed main() {
solve();
}
|
C - Nezzar and Symmetric Array
题意:给有$2*n$个数字的数组d，问能不能构造出一组“对称数组”（有一个整数a，必然有一个负数-a，0不行），并且一个数和其他所有数之差的绝对值之和都能在原数组找到。即$\sum_{j=1}^na_i-a_j=d_{某个数}$。
思路： 因为是对称数组，所以原数组中的数必须有不同的n个偶数，奇数是不行的，因为$\sum_{j=1}^na_i-a_j$得出来一定是个偶数。
加入我们设要构造的数组为$a_1,a_2…a_n,-a_1,-a_2…-a_n$，所以$\sum_{j=1}^na_i-a_j$最小的数为$2(a_1+a_2+…+a_n)$，这就是为什么一定要是偶数了，方便起见，将d数组每个数都除2判断一下，设$a_1+a_2+…+a_n=sum$那么我们可以得到所有的数： (将d数组从小到大排序)
- $第一小：sum=d[1]$
- $第二小：sum+a_2-a_1=d[2]$
- $第三小:sum+a_3-a_2+a_3-a_1=d[3]$
这样我们是看不出来什么样的，前后做一个差分可以得到：
$sum=d[1]$ $a_2-a_1=d[2]-d[1]$ $2(a_3-a_2)=d[3]-d[2]$ $3(a_4-a_3)=d[4]-d[3]$ … $(n-1)(a_n-a_{n-1})=d[n]-d[n-1]$
我们可以解这n个方程，得到a数组的n个正数，但不不好解它，我们先假设$a_1=1(不能等于0，对称数组，0是不允许的)$，然后解出所有的$a_i$，最后算出$sum$是$a_1+…+a_n$。
$a_2=d[2]-d[1]+a_1$ $a_3=\frac{d[3]-d[2]}{2}+a_2$ $a_4=\frac{d[4]-d[3]}{3}+a_3$ … $a_n=\frac{d[n]-d[n-1]}{n-1}+a_{n-1}$
如何判断YES还是NO呢？
我们发现，$a_1$每+1都会使所有数+1，即sum加了n，所以我们判断如果$sum<=d[1]，并且(d[1]-sum]\%n)==0，输出YES，反之NO。$
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;
typedef long long ll;
void solve() {
int _; cin >> _;
while(_--) {
int n; cin >> n;
vector<ll>v(n * 2);
bool flag = true;
for(int i = 0;i < n * 2; i++) {
cin >> v[i];
if(v[i] & 1) flag = false;
else v[i] /= 2;
}
if(!flag) {
cout << "NO" << endl;
continue;
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
if(v.size() != n) {
cout << "NO" << endl;
continue;
}
ll t = 1;
ll sum = t;
for(int i = 1;i < n; i++) {
if((v[i] - v[i - 1]) % i == 0) {
ll a = (v[i] - v[i - 1]) / i + t;
sum += a;
t = a;
}
else {
flag = false;
break;
}
}
if(flag && (sum <= v[0] && (v[0] - sum) % n == 0)) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
}
signed main() {
solve();
}
|
D - Nezzar and Board
题意：给n个数$x_1,x_2…x_n$，从中选择两个数x和y，将$2*x-y$放入数组中，可以操作多次，问能不能得到一个k。
思路： $2*x-y=x+x-y$，因为两个数一直辗转相减是可以得到这两个数的最大公因数，所以两个数的差即为最大公因数的倍数，所以为了每个数都可以被用到，我们先求出$n-1$个差的$gcd$，这样我们可以得到任意多个$gcd$的和，然后还剩下一个$x$，就看看$k$能不能等于$x_i+任意多个gcd$，即判断$(k-x_i)\%gcd==0$。
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
| ##include "bits/stdc++.h"
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
void solve() {
int _; cin >> _;
while(_--) {
int n;
ll k;
cin >> n >> k;
vector<ll>v(n + 1);
ll GCD;
for(int i = 1;i <= n; i++) {
cin >> v[i];
if(i == 2) {
GCD = v[i] - v[i - 1];
}
else {
GCD = gcd(v[i] - v[i - 1], GCD);
}
}
bool flag = false;
for(int i = 1;i <= n; i++) {
if((k - v[i]) % GCD == 0) {
flag = true;
break;
}
}
cout << (flag ? "YES" : "NO") << endl;
}
}
signed main() {
solve();
}
|
E - Nezzar and Binary String
题意：给两个01串，问经过q天之后能不能把s1转化成s2，每一天给一个区间，可以将该区间严格小于一半的字符数变成另一种，最后，如果可以转化输出YES，反之NO。
思路： 从第一天开始，后面的操作是基于前面的，所以我们需要时间逆序。 每一次操作，会有三种情况：
- 当前1的个数严格小于区间一半，将区间全部变成0
- 当前0的个数严格小于区间一半，将区间全部变成1
- 当前1和0的个数相同，直接输出NO
所以需要区间覆盖，想到区间问题，线段树是居家旅行的好东西。 直接用最简单的线段树模拟这个过程即可。
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
| ##include "bits/stdc++.h"
using namespace std;
const int N = 1e6 + 10;
int n, q;
string s1, s2;
##define lc u << 1
##define rc u << 1 1
##define mid (t[u].l + t[u].r) / 2
struct Tree {
int l, r;
int sum;
int tag;
}t[N << 1];
inline void push_up(int u) {
t[u].sum = t[lc].sum + t[rc].sum;
}
inline void push_down(int u) {
if(t[u].tag == -1) return ;
t[lc].sum = t[u].tag * (t[lc].r - t[lc].l + 1);
t[rc].sum = t[u].tag * (t[rc].r - t[rc].l + 1);
t[lc].tag = t[u].tag;
t[rc].tag = t[u].tag;
t[u].tag = -1;
}
void build(int u, int l, int r) {
t[u].l = l; t[u].r = r;
t[u].sum = 0;
t[u].tag = -1;
if(l == r) {
t[u].sum = s2[l - 1] - '0';
return ;
}
int m = (l + r) >> 1;
build(lc, l, m);
build(rc, m + 1, r);
push_up(u);
}
void modify(int u, int ql, int qr, int v) {
if(ql <= t[u].l && t[u].r <= qr) {
t[u].sum = v * (t[u].r - t[u].l + 1);
t[u].tag = v;
return ;
}
push_down(u);
if(ql <= mid) modify(lc, ql, qr, v);
if(qr > mid) modify(rc, ql, qr, v);
push_up(u);
}
int query(int u, int ql, int qr) {
if(ql <= t[u].l && t[u].r <= qr) {
return t[u].sum;
}
push_down(u);
int ans = 0;
if(ql <= mid) ans += query(lc, ql, qr);
if(qr > mid) ans += query(rc, ql, qr);
return ans ;
}
void solve() {
int _; cin >> _;
while(_--) {
cin >> n >> q;
cin >> s1 >> s2;
build(1, 1, n);
vector<int> l(q + 1), r(q + 1);
for(int i = 1;i <= q; i++) {
cin >> l[i] >> r[i];
}
bool flag = true;
for(int i = q;i >= 1; i--) {
int len = r[i] - l[i] + 1;
int v = query(1, l[i], r[i]);
if(v * 2 < len) modify(1, l[i], r[i], 0);
else if(v * 2 > len) modify(1, l[i], r[i], 1);
else {
flag = false;
break;
}
}
for(int i = 1;i <= n; i++) {
if(query(1, i, i) != s1[i - 1] - '0') {
flag = false;
break;
}
}
cout << (flag ? "YES" : "NO") << endl;
}
}
signed main() {
solve();
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/01/29/codeforces-round-698-div-2-a-e/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！