###A. Point on Spiral

模拟之。

###B. Books

用搜索一遍+二分查找做的。

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
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
#define out(v) cerr << #v << ": " << (v) << endl
#define SZ(v) ((int)(v).size())
const int maxint = -1u>>1;
template <class T> bool get_max(T& a, const T &b) {return b > a? a = b, 1: 0;}
template <class T> bool get_min(T& a, const T &b) {return b < a? a = b, 1: 0;}

int n, ans, tmp;
long long t;
long long a[100010], rec[100010];

int search(int l, int r, long long n) {
while(l != r && l != r - 1) {
if(n - rec[(l + r)/ 2] > t) {
r = (l + r) / 2;
continue;
}
if(n - rec[(l + r)/ 2] < t) {
l = (l + r) / 2;
continue;
}
if(n - rec[(l + r)/ 2] == t) {
return ((l + r) / 2);
}
}
return l;
}

int main() {
ans = 0;
cin >> n >> t;
rec[n] = 0;
for(int i = 0; i < n; i ++) {
cin >> a[i];
}
for(int i = n - 1; i >= 0; i --) {
rec[i] = rec[i + 1] + a[i];
}
for(int i = n - 1; i >= 0; i --) {
if(t >= rec[i]) {
ans = max(ans, n - i);
}
else {
tmp = search(i + 1, n - 1, rec[i]);
if(t >= rec[i] - rec[tmp]) {
ans = max(ans, tmp - i);
}
if(t >= rec[i] - rec[tmp + 1]) {
ans = max(ans, tmp + 1 - i);
}
}
}
cout << ans << endl;
return 0;
}

###C. Ladder

对这个序列做分析,求出极小值所在点,若给出的范围在两个极小值之间(包括两个极小值),则是Ladder。

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
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
#define out(v) cerr << #v << ": " << (v) << endl
#define SZ(v) ((int)(v).size())
const int maxint = -1u>>1;
template <class T> bool get_max(T& a, const T &b) {return b > a? a = b, 1: 0;}
template <class T> bool get_min(T& a, const T &b) {return b < a? a = b, 1: 0;}

bool flag = true;
int n, m, l, r, t;
int ti[100010];
long long tmp;
vector <long long> a;
vector <int> rec;

int main() {
a.clear();
rec.clear();
t = 0;
cin >> n >> m;
for(int i = 0; i < n; i ++) {
cin >> tmp;
if(SZ(a) != 0 && tmp == a[SZ(a) - 1]) {
ti[SZ(a) - 1] ++;
}
else {
a.push_back(tmp);
ti[SZ(a) - 1] = 1;
}
}
for(int i = 0; i < SZ(a); i ++) {
flag = true;
if(i != 0 && i != SZ(a) - 1 && a[i] < a[i - 1] && a[i] < a[i + 1]) {
t ++;
flag = false;
}
for(int j = 0; j < ti[i]; j ++) {
if(!flag) {
rec.push_back(0 - t);
}
else {
rec.push_back(t);
}
}
if(!flag) {
t ++;
}
}
/*for(int i = 0 ; i < SZ(rec); i ++) {
cout << rec[i] << " ";
}*/
for(int i = 0; i < m; i ++) {
cin >> l >> r;
if(abs(rec[r - 1]) - abs(rec[l - 1]) < 2 || (abs(rec[r - 1]) - abs(rec[l - 1]) == 2 && rec[r - 1] < 0 && rec[l - 1] < 0)) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
return 0;
}

###D. The Minimum Number of Variables

看到别人代码才想到的做法…y = x ^ 2这个函数大于0一侧的点能围成凸包,就将m个点分配在函数图像上,剩下的是n - m个点放图像y = - x ^ 2 + k的图像上。

这样只要求三点不共线就行,由(m, m ^ 2)以及(m - 1, (m - 1) ^ 2)两点,得y = x ^ 2最远能达到的点是(1, m ^ 2 - m),所以k = - m ^ 2 + m。

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
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
#define out(v) cerr << #v << ": " << (v) << endl
#define SZ(v) ((int)(v).size())
const int maxint = -1u>>1;
template <class T> bool get_max(T& a, const T &b) {return b > a? a = b, 1: 0;}
template <class T> bool get_min(T& a, const T &b) {return b < a? a = b, 1: 0;}

int n;
int a[25], f[33554432];

bool can(int st, int b) {
for(int i = 0; i < b; i ++) {
if(st & (1 << i)) {
for(int j = i; j < b; j ++) {
if((st & (1 << j)) && a[i] + a[j] == a[b])
return true;
}
}
}
return false;
}

int cnt(int st) {
int ans = 0;
for(int i = 0; i < n; i ++) {
int tmp = 1 << i;
if(st & tmp) {
ans ++;
}
}
return ans;
}

int main() {
int ans = 30;
memset(f, 0, sizeof(f));
cin >> n;
for(int i = 0; i < n; i ++) {
cin >> a[i];
}
f[1] = 1;
for(int i = 1; i < n; i ++) {
for(int j = (1 << (i - 1)); j < (1 << i); j ++) {
if(!f[j]) {
continue;
}
if(can(j, i)) {
f[j ^ (1 << i)] = 1;
for(int k = 0; k < i; k ++) {
int tmp = 1 << k;
if(j & tmp) {
tmp = tmp ^ j ^ (1 << i);
f[tmp] = 1;
}
}
}
}
}
for(int i = (1 << (n - 1)); i < (1 << n); i ++) {
if(f[i]) {
ans = min(ans, cnt(i));
}
}
if(ans != 30) {
cout << ans << endl;
}
else {
cout << -1 << endl;
}
return 0;
}

###E. Beautiful Decomposition

我是用贪心做的,讲数分组,组与组之间隔至少两个0,每组的操作数等于组内0的数量+2,有一种特殊情况,若遇到单独的101,操作数为2。

这题代码写的惨不忍睹Orz。

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
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
#define out(v) cerr << #v << ": " << (v) << endl
#define SZ(v) ((int)(v).size())
const int maxint = -1u>>1;
template <class T> bool get_max(T& a, const T &b) {return b > a? a = b, 1: 0;}
template <class T> bool get_min(T& a, const T &b) {return b < a? a = b, 1: 0;}

string s, tmp;
int ans;

int main() {
ans = 0;
cin >> s;
tmp = "";
int i = 0;
while(i < SZ(s)) {
//cout << i << " " << tmp << " " << ans << endl;
if(s[i] == '0' && i == SZ(s) - 1) {
i ++;
continue;
}
if(s[i] == '1' && s[i + 1] == '0' && SZ(tmp) == 0) {
ans ++;
i += 2;
while(s[i] == '0' && i < SZ(s)) {
i ++;
}
continue;
}
if(s[i] == '1') {
tmp += s[i];
i ++;
continue;
}
if(s[i] == '0' && s[i + 1] == '0') {
while(s[i] == '0' && i < SZ(s)) {
i ++;
}
if(SZ(tmp) == 0) {
continue;
}
if(SZ(tmp) == 1) {
ans ++;
}
else {
for(int j = 0; j < SZ(tmp); j ++) {
if(tmp[j] == '0') {
ans ++;
}
}
ans += 2;
}
tmp = "";
continue;
}
if(s[i] == '0' && s[i + 1] == '1') {
tmp += s[i];
i ++;
continue;
}
}
if(SZ(tmp) == 1 || (SZ(tmp) == 2 && tmp[1] == '0')) {
ans ++;
}
else if(SZ(tmp) != 0) {
for(int j = 0; j < SZ(tmp); j ++) {
if(tmp[j] == '0') {
ans ++;
}
}
ans += 2;
}
cout << ans << endl;
return 0;
}