D题明天补一下
A
看样例就懂了
1
2
3
4
5
6
7
8
| void solve(){
int a,b;cin>>a>>b;
if(a!=b) cout<<b-a<<"\n";
else{
if(a==1) cout<<1<<"\n";
else cout<<0<<"\n";
}
}
|
B
可以发现我们想要换取[l,r]的某几个数，一定是只能从[1,l-1]或者[r+1,n]中的某一个里选
因为如果两段都存在数的话，由于反转的对称性，最左边的数和最右边的数交换，以此类推，所以一定会使得某个区间的数在和[l,r]区间内的数交换之前被另一个区间消耗掉
贪心的考虑区间和，选择[l,r]内最大的几个数和两端最小的几个数交换
容易用优先队列实现
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
| void solve(){
int n,l,r;cin>>n>>l>>r;
priority_queue<int>a;
priority_queue<int,vector<int>,greater<int>>lmn,rmn;
int ans=0;
for(int i=1;i<=n;i++){
int x;cin>>x;
if(i>=l&&i<=r){
ans+=x;
a.push(x);
}
else if(i<l) lmn.push(x);
else rmn.push(x);
}
auto work=[&](char c){
auto pq=lmn;auto a1=a;
if(c=='l') pq=lmn;
else pq=rmn;
int res=0;
while(a1.size()&&pq.size()){
auto t1=a1.top();a1.pop();
auto t2=pq.top();pq.pop();
if(t1>t2){
res+=t1-t2;
}else{
break;
}
}
return res;
};
cout<<ans-max(work('l'),work('r'))<<"\n";
}
|
C
思路很简单，选择度数最大的两个点然后删除他们
对于一棵树中的任意一个点来说，每删除它的一条边都会使得图中的连通分量+1
但是本题要求删边之后将点也删去,这会使得连通分量-1，即每删除一个点，会增加度数-1的连通分量数
正常的思路就是选择度数最大的两个点删去
唯一问题是当最大的度数的点不唯一时，是有限制的
当三个度数最大的点相连时，此时删去中间的点会使得两边度数最大的点度数都-1,即会使得答案变差,此时应该避开中间点
解决方法就是选取任意两个点数最大的点（此时必有一个点为最优解的点），对他们相连的边依次度数-1后取最大值
最终答案就是两个点度数和-2+最开始的联通量(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
| void solve(){
int n;cin>>n;
vector<int>de1;
vector<vector<int>>g(n+1);
vector<int>in(n+1);
priority_queue<array<int,2>>pq;
for(int i=0;i<n-1;i++){
int u,v;cin>>u>>v;
g[u].push_back(v);g[v].push_back(u);
in[u]++;in[v]++;
}
for(int i=1;i<=n;i++){
pq.push({in[i],i});
}
auto t=pq.top();
de1.push_back(t[1]);
pq.pop();
if(pq.top()[0]==t[0]){
de1.push_back(pq.top()[1]);
pq.pop();
}
int ans=0;
for(auto i:de1){
int res=in[i];
auto in1=in;
for(auto j:g[i]){
in1[j]--;
}
priority_queue<array<int,2>>pq1;
for(int j=1;j<=n;j++){
if(i!=j) pq1.push({in1[j],j});
}
res+=pq1.top()[0];
ans=max(ans,res-1);
}
cout<<ans<<"\n";
}
|