A

两者取大

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void solve(){
	int n,m;cin>>n>>m;
	int mx=max(n,m);
	cout<<mx<<'\n';
}
int main(){
	int _;cin>>_;
	while(_--)solve();
	return 0;
}

B

发现每次可以消去两个叶子结点，如果只剩一个需要多一次操作，记录叶子结点个数然后分奇偶

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
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
const int N=2e5+10;
vector<int>g[N];

void solve(){
	
	int n;cin>>n;
	for(int i=1;i<=n;i++)g[i].clear();
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(g[i].size()==1)cnt++;
		
	}
	if(cnt%2){
		cout<<cnt/2+1<<'\n';
	}else{
		cout<<cnt/2<<'\n';
	}
	
}
int main(){
	int _;cin>>_;
	while(_--)solve();
	return 0;
}

C

这道题比较有趣

首先搞清楚字典序最大的定义，把玩一下样例很容易发现，我们其实是在对最大词性子序列进行一个循环右移再把长度减一的过程（有且仅有一个），因为每次把最大的数移到右边一个之后最大词性子序列仍然以之开头，所以我们就是在求对这个最大词性的子序列完成上述操作之后是否能使整个序列有序。可以用一个单调栈的思想从前往后扫一遍得到最大词性子序列，或者也可以从后向前找，先把最后一个数加入，如果大于等于这个数的都加入也可以找到这个子序列（存下标).如果从后向前找记得要reverse。假如有一个序列ddcaa，其实我们需要右移的就是caa三个数，所以如果可以有序，答案就是最大词性子序列的长度减去最大字母的个数，在这里就是是s[v[0]]。多把玩几个样例可以发现，其实我们对这个子序列进行操作相当于中心对称交换，所以模拟一下，看看模拟交换完是否有序，有序输出cnt否则输出-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
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void solve(){
	int n;cin>>n;
	string s;cin>>s;
	string t=s;
	sort(t.begin(),t.end());
	if(t==s){
		cout<<"0"<<'\n';
		return;
	}
    vector<int>v;
    for(int i=n-1;i>=0;i--){
        if(v.empty()||s[v.back()]<=s[i]){
            v.push_back(i);
        }
    }
    reverse(v.begin(),v.end());
    int cnt=v.size();
    for(int i=0;i<v.size();i++){
        if(s[v[i]]==s[v[0]])cnt--; 
    }
    for(int i=0;i<v.size()-1-i;i++){
        swap(s[v[i]],s[v[v.size()-i-1]]);
    }
    //cout<<s<<'\n';
    if(!is_sorted(s.begin(),s.end())){
        cnt=-1;
    }
    cout<<cnt<<'\n';
	
}
int main(){
	int _;cin>>_;
	while(_--)solve();
}

D

也是有一个单调栈的思想，还没调，后面补题会再写