题解：CF2072E Do You Love Your Hero and His Two-Hit Multi-Target Attacks?

· · 题解

题目传送门：CF2072E。

思路

首先 p(a,b)=d(a,b) 当且仅当 x_a=x_b 或 y_a=y_b。

我们发现如果一个行有 x 个点，那么就有 \frac{x(x-1)}{2} 个满足题目要求配对。

我们按照上述性质按行构造，我们定义 a_i=\frac{i(i-1)}{2} 那么我们对于题目要求的 k 从倒序枚举 a_i，我们根据贪心思想如果可以就开一行 i 个点。

根据暴力可得，我们可以在 500 个点之内完成这个构造。

记得在每一行不要构造出相同列的节点，具体的可以查看代码。

代码


#include<bits/stdc++.h>
#define int long long
using namespace std;
int n=500;
int a[1000];
inline int read(){
    char c=getchar();
    int f=1,ans=0;
    while(c<48||c>57) f=(c==45?f=-1:1),c=getchar();
    while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
    return ans*f;
}
#define pii pair<int,int>
vector<pii>anss;
int cnt1=-1e9;
inline void print(int x,int y){
    for (int i=1;i<=y;i++) anss.push_back({x,cnt1++});
}
inline void solve(){
    cnt1=-1e9;
    int k=read();anss.clear();
    int cnt=0; 
    for (int i=n;i>=2;i--)
        while(k>=a[i]) print(++cnt,i),k-=a[i];
    printf("%lld\n",anss.size());
    for (auto i:anss) printf("%lld %lld\n",i.first,i.second);
}
main(){
    for (int i=2;i<=n;i++)  a[i]=i*(i-1)/2;
    int T=read();
    while(T--) solve();
    return 0;
}
//Codeforces Round 1006 RP++
//Codeforces Round 1006 RP++
//Codeforces Round 1006 RP++
//Codeforces Round 1006 RP++
//Codeforces Round 1006 RP++