Codeforces Round #813 (Div. 2)A-D

过程

本场A，B快速签到，但C卡了一下，D做法一开始直接把小的变大，然后发现假了，把自己hack了，随后想到了三分寻找最合适的变连续的一串从小到大的数字，但还是假了，只能赛后补提了。
传送门

题目

A

统计前k个数里面有多少个大于k即可

void Solve(){
 cin>>n>>m;
 vector<int>a(n+1);
 rep(i,1,n) cin>>a[i];
 int ans=0;
 rep(i,1,m) if(a[i]>m) ans++;
 cout<<ans<<endl;
}  

B

因为n与n-1互素，所以lcm(n,n-1)=n(n-1)，而lcm(a,b)<=ab，故此时lcm为最大值，因此从大到小搭配即可。

void Solve(){
 cin>>n;vector<int>a(n+1);
 rep(i,1,n) a[i]=i;
 for(int i=n;i>1;i-=2) swap(a[i],a[i-1]);
 rep(i,1,n) cout<<a[i]<<" ";
 pts;
}  

C

如果出现\(a_i>a_{i+1}\)，n那么此时\(a_i\)之前的所有元素都要变为0，那么记录一个\(b_{a[i]}\)表示\(a_i\)这个值是否已经变为0，维护一个单调栈，变为0的次数即为答案

int n;
void Solve(){
 cin>>n;vector<int>a(n+1),b(n+1);
 rep(i,1,n) cin>>a[i],b[a[i]]=a[i];
 vector<P>c;int ans=0;
 rep(i,1,n){
  if(!c.size()) c.pb(P(b[a[i]],a[i]));
  else if(c.back().first<=b[a[i]]) c.pb(P(b[a[i]],a[i]));
  else if(c.back().first>b[a[i]]) {
   for(auto x:c) {
    if(b[x.second]) ans++;
    b[x.second]=0;
   }
   c.clear();c.pb(P(b[a[i]],a[i]));
  }
 }
 cout<<ans<<endl;
}  

D

因为是完全图，所以\(u-v\)只需要经过两次最小的\(a_i\)即可到达，这是其中一个限制。其次对于\(\max_{1\leq u<v\leq n}d(u,v)\)，因为区间最小值是单调递减的，因此上式等价于\(\max_{1\leq i\leq n-1} min(a_i,a_{i+1})\).

那么我们可以二分这个最大距离\(x\)，对于\(2*a_i<x\)的\(a_i\),将其修改为为\(1e9\),否则最大距离\(x\)不可行。
之后看\(\max_{1\leq i\leq n-1} min(a_i,a_{i+1})\)是否大于\(x\),如果大于则当前\(x\)可行，如果不大于，如果只剩一次修改机会，那就需要判断是否存在一个\(a_i\geq x\)，如果存在，将其左右的数修改即可满足条件，否则无法满足条件，对于剩两次以上修改机会，则已经满足条件，满足二分性。

至此，二分范围为\(1-1e9\)，可解决问题。

int n,k;
bool check(int x,vector<int>c){
 int num=k;
 rep(i,1,n){
  if(c[i]*2<x) num--,c[i]=1e9;
 }
 if(num<0) return 0;
 int maxx=-1;
 rep(i,1,n-1) maxx=max(maxx,min(c[i],c[i+1]));
 if(maxx>=x) return 1;
 if(num==0) return 0;
 if(num>1) return 1;
 rep(i,1,n){
  if(c[i]>=x) return 1;
 }
 return 0;
}
void Solve(){
 cin>>n>>k;
 vector<int>a(n+1),c;vector<P>b(n+1);
 rep(i,1,n) cin>>a[i];
 int l=1,r=1e9,ans=r;
 while(l<=r){
  c=a;
  int mid=(l+r)>>1;
  if(check(mid,c)) ans=mid,l=mid+1;
  else r=mid-1;
 }
 cout<<ans<<endl;
}  

E1,E2

待补