Codeforce Round 886（div4）E、F、G题解

E：

思路：最朴素的想法是枚举w的值看是否满足题意，但如果暴力枚举必然超时，所以可以用二分答案。

代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define lop(i,a,b) for(int i=(a);i<(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define el '\n' 
#define int long long
typedef pair<int,int> PII;
using LL = long long;
const int INF=0x3f3f3f3f;
const int N=2e5+10;
int s[N],n,c,ans;
void solve()
{
    int s1=0,s2=0;//和与平方和
    cin>>n>>c;
    rep(i,1,n)cin>>s[i];
    int l=0,r=1e9;
    while(l<r)
    {
        int mid=l+r>>1;
        int sum=0;
        rep(i,1,n)
        {
            sum+=(s[i]+2*mid)*(s[i]+2*mid);
            if(sum>c||sum<0)break;
        }
        if(sum==c)
        {
            cout<<mid<<el;
            return;
        }
        if(sum>c)r=mid;
        else l=mid+1;
    }
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t = 1;
    cin>>t;
    while(t--)
      solve();
    return 0;
}

F：

思路：可以计算出每个跳跃距离的数量（注意：只考虑<=n的，大于n的不可能抓到），然后枚举跳跃距离以及他的倍数，将他们都标记并加上他的数量，最后寻找最大值即可。

代码：

//记录每个步数的次数，遍历过去，将他的倍数
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define lop(i,a,b) for(int i=(a);i<(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define el '\n' 
#define int long long
typedef pair<int,int> PII;
using LL = long long;
const int INF=0x3f3f3f3f;
const int N=2e5+10;
int n,a;
void solve()
{
    int maxx=0;
    cin>>n;
    unordered_map<int,int>mp;
    unordered_map<int,int>ans;
    rep(i,1,n)
    {
        cin>>a;
        if(a<=n)mp[a]++;
    }
    rep(i,1,n)
    {
        if(mp[i]==0)continue;
        for(int j=i;j<=n;j+=i)
            ans[j]+=mp[i];
    }
    rep(i,1,n)maxx=max(maxx,ans[i]);
    cout<<maxx<<el;
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t = 1;
    cin>>t;
    while(t--)
      solve();
    return 0;
}

G：

思路：观察这幅图，不难发现当满足：横坐标相等，纵坐标相等，横纵坐标和为常数，横纵坐标差为常数这四种情况之一时就满足题意，所以可以将满足这四种情况分别存到四个map中，从每种中任选出其二都是满足的，通过组合数计算便是n*(n-1)

代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define lop(i,a,b) for(int i=(a);i<(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define el '\n' 
#define int long long
typedef pair<int,int> PII;
using LL = long long;
const int INF=0x3f3f3f3f;
void solve()
{
    int n,x,y,ans=0;
    cin>>n;
    map<int,int>mp1,mp2,mp3,mp4;//x相等，y相等，x+y为常数，x-y为常数
    rep(i,1,n)
    {
        cin>>x>>y;
        mp1[x]++;
        mp2[y]++;
        mp3[x+y]++;
        mp4[x-y]++;
    }
    for(auto i:mp1)ans+=i.second*(i.second-1);
    for(auto i:mp2)ans+=i.second*(i.second-1);
    for(auto i:mp3)ans+=i.second*(i.second-1);
    for(auto i:mp4)ans+=i.second*(i.second-1);
    cout<<ans<<el;
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t = 1;
    cin>>t;
    while(t--)
      solve();
    return 0;
}