写在前面
疫情封寝室了，完全静不下心做事，索性随便写两个简单题打发时间，所以后面的内容就随便写写了，还望诸位海涵
A Medium Number
题意简述
给三个不同的数，输出中位数
思路
输出不是最大值和最小值的那个数即可
代码
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 <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
void work(){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
int maxx = max(a,max(b,c));
int minx = min(a,min(b,c));
if(a != maxx && a != minx){
printf("%d\n",a);
}
if(b != maxx && b != minx){
printf("%d\n",b);
}
if(c != maxx && c != minx){
printf("%d\n",c);
}
}
int main(){
int T;
scanf("%d",&T);
while(T--)
work();
return 0;
}
|
B Atilla’s Favorite Problem
题意简述
给一个小写英文字母字符串s，输出能表示它的最小字母表大小。使用的字母表一定是26个字母表的一个前缀部分。
思路
找到字母中顺序最靠后的字母在字母表中的位置，取它和它之前的所有字母组成字母表即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
char s[100100];
void work(){
int n;
scanf("%d",&n);
scanf("%s",s+1);
int ans=0;
for(int i=1;i<=n;i++){
ans = max(ans,s[i]-'a'+1);
}
printf("%d\n",ans);
}
int main(){
int T;
scanf("%d",&T);
while(T--){
work();
}
return 0;
}
|
C Advantage
题意简述
n个参赛者，每个参赛者有一个能力值$s_i$，每个参赛者想知道自己的能力值减去 除了自己之外n-1个人能力值的最大值 的值，求这n个值。
思路
预处理一个前缀最大值和一个后缀最大值即可。
代码
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
| #include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int pre[200200],suf[200200],a[200200];
void work(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
suf[i] = pre[i] = a[i];
}
for(int i=2;i<=n;i++){
pre[i] = max(pre[i],pre[i-1]);
}
for(int i=n-1;i>=1;i--){
suf[i] = max(suf[i],suf[i+1]);
}
for(int i=1;i<=n;i++){
if(i==1)
printf("%d ",a[i]-suf[i+1]);
else if(i==n)
printf("%d\n",a[i]-pre[i-1]);
else
printf("%d ",a[i]-max(pre[i-1],suf[i+1]));
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
work();
}
return 0;
}
|
D Challenging Valleys
题意简述
对一个数组a[0,n-1]，定义其中的一个区间$[l,r]$为一个Valley，当且仅当其满足以下条件
现在给你一个数组，询问是否只有一个Valley。
思路
用l表示当前考虑区间的左端点，扫描一下整个数组，更新l，并且利用l和当前右端点根据条件判断是否是合法区间，计数一下即可。
代码
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
| #include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int a[200200];
void work(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int l = 1;
int cnt = 0;
for(int i=1;i<=n;i++){
if(a[i] != a[l]){
l = i;
}
if(!(l==1 || a[l-1] > a[l]))
continue;
if(!(i==n || a[i] < a[i+1]))
continue;
cnt++;
}
for(int i=1;i<=n;i++){
a[i] = 0;
}
if(cnt==1){
printf("YES\n");
}
else{
printf("NO\n");
}
}
int main(){
int T;
scanf("%d",&T);
while(T--)
work();
return 0;
}
|
E Binary Inversions
题意简述
给一个长为n的01数组，最多允许对其中一个数进行01翻转，可以不翻转，问操作后数组最多有多少个逆序对。
思路
最开始统计每个0前面有多少个1即可得到不操作的逆序对数。
计i位置前面的1的数量为$ cnt1_i $，后面的0的数量为$ cnt0_i $
将0翻转为1会造成$ -cnt1_i + cnt0_{i+1} $的贡献
将1翻转为0会造成$ -cnt0_i + cnt1_{i-1} $的贡献
扫描统计贡献最大值即可
代码
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
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
int a[200200],cnt0[200200],cnt1[200200];
void work(){
int n;
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(int i=1;i<=n;i++){
cnt1[i] = cnt1[i-1] + a[i];
}
for(int i=n;i>=1;i--){
cnt0[i] = cnt0[i+1] + (!a[i]);
}
int ans = 0;
for(int i=1;i<=n;i++){
if(a[i] == 0){
ans += cnt1[i];
}
}
int ans2 = ans;
for(int i=1;i<=n;i++){
if(a[i] == 0){
ans2 = max(ans2, ans - cnt1[i] + cnt0[i+1]);
}
else{
ans2 = max(ans2, ans - cnt0[i] + cnt1[i-1]);
}
}
for(int i=1;i<=n;i++){
cnt1[i] = cnt0[i] = 0;
}
printf("%lld\n",ans2);
}
signed main(){
int T;
scanf("%lld",&T);
while(T--)
work();
return 0;
}
|
F Quests
题意简述
有n个任务，每个任务执行一次能获得$a_i$的价值，两次任务执行之间要间隔k天。
输入n个任务、c和d两个整数，要求要在d天内获得大于等于c的价值，求k的最大值。
如果不可能获得c的价值，输出”Impossible”
如果k可以任意大，输出”Infinity”
思路
因为每个任务只有$a_i$不同，所以优先执行可以执行的$a_i$最大的任务一定最优。
说明：$a_i\ Top(t)$表示$a_i$前t大的任务
Impossible判断：连续执行d天$a_i\ Top(1)$的任务也不能满足条件（任务无间隔仍不能满足）
Infinity判断：执行$a_i\ Top(d)$即可满足c（任务间隔无限大也能满足）
二分答案：设当前判断的间隔为x
一定选择的策略是，取$a_i\ Top(x+1)$的任务反复执行，所以计算d天执行多少即可
具体为
代码
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
| #include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define int long long
int a[200200];
int n,c,d;
bool cmp(int a,int b){
return a>b;
}
bool check(int x){
int tmp = d/(x+1);
int tmp2 = d%(x+1);
int topx_1 = 0;
int topx_2 = 0;
for(int i=1;i<=min(x+1,n);i++){
topx_1 += a[i];
}
for(int i=1;i<=min(tmp2,n);i++){
topx_2 += a[i];
}
return topx_1 * tmp + topx_2 >= c;
}
void work(){
scanf("%lld %lld %lld",&n,&c,&d);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
sort(a+1,a+n+1,cmp);
int topd = 0;
for(int i=1;i<=min(n,d);i++){
topd += a[i];
}
if(topd >= c){
printf("Infinity\n");
return;
}
if(a[1]*d < c){
printf("Impossible\n");
return;
}
int l = 0, r = d;
int ans = 0;
while(l<=r){
int mid = l+r>>1;
if(check(mid)){
l = mid+1;
ans = mid;
}
else{
r = mid-1;
}
}
printf("%lld\n",ans);
}
signed main(){
int T;
scanf("%lld",&T);
while(T--){
work();
}
return 0;
}
|
G SlavicG’s Favorite Problem
题意简述
给一个n个点的无根的树，边有边权$w_i$，在树上旅行，旅行只能到达邻接节点。
开始旅行的时候有一个初始为0的权值x，每次经过一条边，权值x变为$x \oplus w_i$，$\oplus$ 表示异或
要从a到达b，一个节点能旅行到b，当且仅当满足，到达b时权值x为0
除了直接旅行，允许进行最多一次传送，可以从任意节点传送到除了b之外的节点，x不变。
给你这棵树，a，b，判断是否能够从a到达b。
思路
直接到达就是b到a的路径上异或和为0
传送就是a能到达的所有节点中，存在一个节点，其到a的路径的异或和 与 b到某个除b之外的节点的路径的异或和相等。
先用一次dfs预处理所有b能到达的节点，将其存入set
再用一次dfs检查a能到达的所有节点，是否存在和set中相同的异或和即可
代码
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
| #include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
int n,a,b,u[200200],v[200200],w[200200],fir[200200],nxt[200200],cnt,f1[200200];
set<int> S;
void addedge(int a,int b,int c){
++cnt;
u[cnt] = a;
v[cnt] = b;
w[cnt] = c;
nxt[cnt] = fir[a];
fir[a] = cnt;
}
void dfs1(int x,int f){
for(int i=fir[x];i;i=nxt[i]){
if(v[i]!=f){
f1[v[i]] = f1[x]^w[i];
dfs1(v[i],x);
}
}
}
bool dfs2(int x,int f,int val){
if(S.count(val)!=0){
return true;
}
for(int i=fir[x];i;i=nxt[i]){
if(v[i]!=f && v[i] != b){
if(dfs2(v[i],x,val^w[i])){
return true;
}
}
}
return false;
}
void work(){
scanf("%d %d %d",&n,&a,&b);
for(int i=1;i<n;i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
addedge(a,b,c);
addedge(b,a,c);
}
dfs1(b,0);
for(int i=1;i<=n;i++){
if(i != b)
S.insert(f1[i]);
}
if(f1[a] == 0){
printf("YES\n");
}
else if(dfs2(a,0,0)){
printf("YES\n");
}
else{
printf("NO\n");
}
S.clear();
for(int i=1;i<=cnt;i++){
u[i] = v[i] = w[i] = nxt[i] = 0;
}
for(int i=1;i<=n;i++){
fir[i] = f1[i] = 0;
}
cnt = 0;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
work();
}
return 0;
}
|