A. Minimal Coprime
观察样例发现右减左即为答案，左右为 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
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;
int l,r;
void solve(){
cin>>l>>r;
if(l==1&&r==1){
cout<<1<<endl;
return;
}
cout<<r-l<<endl;
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
B. Subsequence Update
必须且仅操作一次，将目标位置中的小的置换到外面，因为只能操作一次，要么移动到左侧，要么移动到右侧，看哪一侧能得到更大的值即可。
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>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;
int n,l,r;
ll a[N];
ll sum;
void solve(){
cin>>n>>l>>r;
sum=0;
for(int i=1;i<=n;i++)cin>>a[i];
vector<int>t,la,ra;
for(int i=l;i<=r;i++)t.push_back(a[i]);
for(int i=1;i<l;i++)la.push_back(a[i]);
for(int i=r+1;i<=n;i++)ra.push_back(a[i]);
sort(t.begin(),t.end());
sort(la.begin(),la.end());
sort(ra.begin(),ra.end());
for(int i=0;i<t.size();i++)sum+=t[i];
ll ans=sum,tmp=0;
for(int i=0;i<la.size()&&i<t.size();i++){
tmp+=(la[i]-t[t.size()-1-i]);
ans=min(ans,sum+tmp);
}
tmp=0;
for(int i=0;i<ra.size()&&i<t.size();i++){
tmp+=(ra[i]-t[t.size()-1-i]);
ans=min(ans,sum+tmp);
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
C. Remove Exactly Two
必须且仅能删除两个点，要将树分成森林，树的数目尽量多，一定是删度数大的两个点。
但是删一个点后，其他点的度数也可能发生变化，所以可以固定删除的一个点，遍历其他所有点的度数，答案即为两点度数和 - 1，如果当前点和固定点之间有边就多减 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=2e5+7, mod=1e9+7;
struct Node{
int id,dep=0;
bool operator<(const Node &t){
return dep<t.dep;
}
}a[N];
int n;
map<pair<int,int>,int>vis;
void solve(){
cin>>n;
vis.clear();
for(int i=1;i<=n;i++){
a[i].id=i;
a[i].dep=0;
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
a[u].dep++;
a[v].dep++;
vis[{u,v}]=vis[{v,u}]=1;
}
if(n<=2){
cout<<0<<endl;
return;
}
sort(a+1,a+1+n);
int ans=0;
for(int i=1;i<n;i++){
ans=max(ans,a[n].dep+a[i].dep-1-vis[{a[n].id,a[i].id}]);
}
for(int i=1;i<n-1;i++){
ans=max(ans,a[n-1].dep+a[i].dep-1-vis[{a[n-1].id,a[i].id}]);
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
D. Game With Triangles
可以确定，每次取都是取一条线上两侧的点和另一条线上任意一个点，会使得能取的线段越来越短，即所求函数的增幅越来越小，但始终单调递增。
随着 k 增大，不能完全按照最大策略来取，即函数值为变为单凸函数，可以确定用三分来解决。
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
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=2e5+7, mod=1e9+7;
int n,m,k;
ll a[N],b[N],f[N];
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)cin>>b[i];
sort(a+1,a+1+n);
sort(b+1,b+1+m);
for(int i=1;i<=n/2;i++)a[i]=a[n-i+1]-a[i];
for(int i=1;i<=m/2;i++)b[i]=b[m-i+1]-b[i];
for(int i=1;i<=n/2;i++)a[i]+=a[i-1];
for(int i=1;i<=m/2;i++)b[i]+=b[i-1];
for(k=1;;k++){
int l=max(k-m/2,max(0,k*2-m)),r=min(n/2,min(k,n-k));
while(l+1<r){
int mid=(l+r)>>1;
ll x=a[mid-1]+b[k-mid+1];
ll y=a[mid+1]+b[k-mid-1];
if(x<y)l=mid;
else r=mid;
}
f[k]=-1;
for(int i=l;i<=r;i++)f[k]=max(f[k],a[i]+b[k-i]);
if(f[k]<0)break;
}
cout<<k-1<<endl;
for(int i=1;i<k;i++)cout<<f[i]<<" ";
cout<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|