Codeforces Round 886 (Div. 4)

整体偏简单，E 二分边界想复杂了，F 一开始读错题了，以为第 $i$ 个人从第 $i$ 个位置开始跳。。。

D
不难发现答案的那一段区间一定是连续的，采用双指针扫一遍即可。

#include<bits/stdc++.h>
#define endl '\n'
#define pii pair<int,int>using namespace std;
using ll = long long;const int maxn = 2e5+3;
int a[maxn];
stack<int>q;void solve()
{int n,k; cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];if(n==1) {cout<<0<<endl;return ;}sort(a+1,a+1+n);int len=0;for(int i=2;i<=n;i++){int j=i,t=0;while(a[j]-a[j-1]<=k&&j<=n){t++;j++;}i=j;len=max(len,t);}cout<<n-len-1<<endl;
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T; cin>>T;while(T--)solve();return 0;
}

E
样例解释大概告诉怎么做了，二分答案即可，注意边界的设置，赛时边界想复杂了。

#include<bits/stdc++.h>
#define endl '\n'
#define pii pair<int,int>using namespace std;
using ll = long long;const int maxn = 2e5+3;
int s[maxn];
int n; 
ll c;
ll MAXN = 1e9;bool check(ll x)
{ll sum=0;for(int i=1;i<=n;i++){sum+=(s[i]+2*x)*(s[i]+2*x);if(sum>=c) return true; }return false;
}void solve()
{cin>>n>>c;for(int i=1;i<=n;i++)cin>>s[i];ll l=0,r=1e9;ll ans; while(l<=r){ll mid=(l+r)>>1;if(check(mid)){ans=mid;r=mid-1;}else l=mid+1;}cout<<ans<<endl;return ;
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T; cin>>T;while(T--)solve();return 0;
}

F
直接暴力就可以，由于调和级数的复杂度是 $log(n)$ 的，因此算法的总复杂度为 $nlog(n)$ 而不是 $n^2$。

#include<bits/stdc++.h>
#define endl '\n'
#define pii pair<int,int>using namespace std;
using ll = long long;const int maxn = 2e5+3;
int a[maxn];
int b[maxn];void solve()
{memset(a,0,sizeof(a));memset(b,0,sizeof(b));int n; cin>>n;for(int i=1;i<=n;i++){int x; cin>>x;if(x<=n) a[x]++;}for(int i=1;i<=n;i++){if(a[i]){for(int j=i;j<=n;j+=i){b[j]+=a[i];}            }}sort(b+1,b+1+n);cout<<b[n]<<endl;
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T; cin>>T;while(T--)solve();return 0;
}

G
鉴定为初中数学没学好，看了题解立马会了，对于两条斜着的线对应了斜率 $k=1$ 与 $k=-1$ 的情况，因此 $x+y$ 相同的点在 $k=-1$ 的线上，$x-y$ 相同的点在 $k=1$ 的线上，注意可能会爆 ll，用 map 存下来后利用排列数公式算即可，并不难。

#include<bits/stdc++.h>
#define endl '\n'
#define pii pair<int,int>using namespace std;
using ll = long long;const int maxn = 2e5+3;
struct point
{int x,y;
}a[maxn];
map<ll,ll> q1,q2,q3,q4;void solve()
{q1.clear(),q2.clear();q3.clear(),q4.clear();int n; cin>>n;for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y;}ll ans=0;for(int i=1;i<=n;i++){q1[a[i].x+a[i].y]++; // 东南到西北q2[a[i].y-a[i].x]++; // 西北到东南q3[a[i].x]++; // 横轴q4[a[i].y]++; // 纵轴}for(auto x:q1) // 东南到西北if(x.second>1)ans+=x.second*(x.second-1);for(auto x:q2) // 西北到东南if(x.second>1)ans+=x.second*(x.second-1);for(auto x:q3) // 横轴if(x.second>1)ans+=x.second*(x.second-1);for(auto x:q4) // 纵轴if(x.second>1)ans+=x.second*(x.second-1);cout<<ans<<endl;return ;
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T; cin>>T;while(T--)solve();return 0;
}