Codeforces Round 1000 (Div. 2)（前三题）
A. Minimal Coprime
翻译：
如果 l 和 r 互为同素数，则正整数 [l,r] 的一段称为同素段。
如果一个共素数段 [l,r] 不包含任何不等于它本身的共素数段，那么这个共素数段 [l,r] 就叫做最小共素数段。为了更好地理解这句话，可以参考注释。
给定正整数段 [l,r]，求 [l,r] 中包含的最小共素数段的个数。
思路：
题目要求不同整数段之间不能为包含关系。
对于一个整数x与x+1必定为互素。
因此答案为r-l+1（l与r都不为1）
实现：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// using pll = pair<ll,ll>;
void solve(){
int a,b;
cin>>a>>b;
int ans = 0;
if (a==1&&b==1){
cout<<1<<endl;
return ;
}
if (a==1){
ans+=1;
a++;
}
cout<<ans+(b-a)<<endl;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// 不使用科学计数法
// cout<<fixed;
// 中间填保留几位小数，不填默认
// cout.precision();
int t;cin>>t;
while (t--) solve();
}B. Subsequence Update
翻译：
给你一个整数序列
，和一个线段 [l,r]（1≤l≤r≤n）。
你必须对这个序列执行下面的操作一次。
- 选择序列 a 的任意子序列，并反转它。注意，子序列不一定要连续。
形式上，选择任意数量的下标
，使得
。然后，将所有 1≤x≤k 的第
个元素同时改为第
个元素的原始值。
求操作后
的最小值。
思路：
对于这只能一次的反转，可以选择要求段的左边的小值与要求段的大值交换。或要求段的右边的小值与要求段的大值交换。注意只能选一边，因为只能反转一次。
实现：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// using pll = pair<ll,ll>;
void solve(){
int n,l,r;
cin>>n>>l>>r;
ll res = 0;
vector<int> a(n+1);
for (int i=1;i<=n;i++) cin>>a[i];
priority_queue<int> tmpl_ans,tmpr_ans;
priority_queue<int,vector<int>,greater<int>> lans,rans;
for (int i=l;i<=r;i++){
res += a[i];
tmpl_ans.push(a[i]);
tmpr_ans.push(a[i]);
}
for (int i=1;i<l;i++){
lans.push(a[i]);
}
for (int i=r+1;i<=n;i++){
rans.push(a[i]);
}
ll res1 = res;
while (!lans.empty()){
int now1 = tmpl_ans.top(),now2 = lans.top();
if (now1>now2){
res -= now1-now2;
tmpl_ans.pop();
tmpl_ans.push(now2);
lans.pop();
}else{
break;
}
}
while (!rans.empty()){
int now1 = tmpr_ans.top(),now2 = rans.top();
if (now1>now2){
res1 -= now1-now2;
tmpr_ans.pop();
tmpr_ans.push(now2);
rans.pop();
}else{
break;
}
}
cout<<min(res1,res)<<endl;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// 不使用科学计数法
// cout<<fixed;
// 中间填保留几位小数，不填默认
// cout.precision();
int t;cin>>t;
while (t--) solve();
}C. Remove Exactly Two
翻译：
给您一棵有 n 个顶点的树。您必须准确执行以下操作两次。
- 选择一个顶点 v；
- 删除 v 所带的所有边，同时删除顶点 v。
请找出精确执行两次操作后的最大连通部分数。
当且仅当存在一条从 x 到 y 的路径时，两个顶点 x 和 y 位于同一个连通组件中。
根据定义，0 个顶点的图有 0 个连通成分。
思路：
记录每个点的度数，并从度数大层数的开始遍历。
那么答案有两种情况：
- 点a的度数+点b的度数-1 a与b不相连
- 点a的度数+点b的度数-2 a与b相连
实现：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve(){
int n;
cin>>n;
// 记录每个点的度数
vector<int> dus(n+1,0);
// 创建邻接表
vector<vector<int>> edge(n+1);
for (int a,b,i=1;i<n;i++){
cin>>a>>b;
dus[a]++;
dus[b]++;
edge[a].push_back(b);
edge[b].push_back(a);
}
// 记录每个度数所包含的点
map<int,vector<int>> mp;
for (int i=1;i<=n;i++) mp[dus[i]].push_back(i);
// 考虑到有的度数只有一个点增加记录点
int f=0,f_du = 0;
// 按度数从大到小遍历
for (auto iter=mp.rbegin();iter!=mp.rend();iter++){
int du = iter->first;
auto nums = iter->second;
int num_size = nums.size();
if (f){
for (int i:nums){
// 两个点不相连
if (find(edge[i].begin(),edge[i].end(),f)==edge[i].end()){
cout<<du+f_du-1<<endl;
return;
}
}
cout<<du+f_du-2<<endl;
return;
}else{
if (num_size==1){
f = nums[0];
f_du = du;
}else{
for (int i=0;i<num_size;i++){
for (int j=i+1;j<num_size;j++){
// 两个点不相连
if (find(edge[nums[i]].begin(),edge[nums[i]].end(),nums[j])==edge[nums[i]].end()){
cout<<2*du-1<<endl;
return;
}
}
}
cout<<2*du-2<<endl;
return;
}
}
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// 不使用科学计数法
// cout<<fixed;
// 中间填保留几位小数，不填默认
// cout.precision();
int t;cin>>t;
while (t--) solve();
}有建议可以评论，我会积极改进qwq。