菜鸡的$div2$补题现场……
A:XXXXX
考虑最长子序列和不被$x$整除，当序列中每一个数都可以被$x$整除时，显然，输出$-1$。当序列和$sum$不可以被$x$整除时，显然，最长的长度为$n。
显然，还剩余一种情况，就是在开头或者结尾删除一些元素，使其$sum$不能被$x$整除。既然要求最长子序列和，我们可以考虑删除最少的，每一次删除判断一下是否满足当前$sum$能否不整除$x$.然后我们$ans$取最大就行辣
注意更新当前$sum$也就是$now$，要求最大及时$break$出来。
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
|
#include <bits/stdc++.h>
#define IOS {ios::sync_with_stdio(false);cin.tie(0);}
#define ll long long
#define SZ(X) (int)X.size()
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e5 + 5;
int t;
int a[maxn];
void solve() {
int n, x;
int ans = 0, tmp;
ll sum = 0, now = 0;
cin >> n >> x;
for(int i = 1; i <= n; i++) {
cin >> a[i];
sum += a[i];
}
if(sum % x == 0) {
tmp = n;
now = sum;
for(int i = 1; i <= n; i++) {
now -= a[i];
tmp--;
if(now % x) {
ans = max(ans, tmp);
break;
}
}
tmp = n;
now = sum;
for(int i = n; i >= 1; i--) {
now -= a[i];
tmp--;
if(now % x) {
ans = max(ans, tmp);
break;
}
}
if(ans == 0) {
cout << "-1" << endl;
} else {
cout << ans << endl;
}
} else {
cout << n << endl;
}
}
int main()
{
IOS
cin >> t;
while(t--) {
solve();
}
return 0;
}
|
B:Most socially-distanced subsequence
考虑删除某些元素,使得条件成立。
如果一个序列满足子序列的差值最大，则应该保留转折点处的值。
就如果升序，则中间的值可以删除，保证最小。如果降序，同理可以删除。于是我们只需要考虑转折点即可。
同时保留首尾元素。因为其左右没有比它更大/更小的元素了。
用一个$vector$表示，注意循环$i$的范围，避免越界。
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
|
#include <bits/stdc++.h>
#define IOS {ios::sync_with_stdio(false);cin.tie(0);}
#define ll long long
#define SZ(X) (int)X.size()
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e5 + 5;
int t, n, p[maxn];
void solve() {
vector<int> v;
vector<int>::iterator it;
v.clear();
memset(p, 0, sizeof(p));
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> p[i];
}
v.push_back(p[1]);
for(int i = 2; i <= n - 1; i++) {
if((p[i] >= p[i - 1] && p[i] >= p[i + 1]) || (p[i] <= p[i - 1] && p[i] <= p[i + 1])) {
v.push_back(p[i]);
}
}
v.push_back(p[n]);
cout << v.size() << endl;
for(it = v.begin(); it != v.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
int main()
{
IOS
cin >> t;
while(t--) {
solve();
}
return 0;
}
|
