C. Nezzar and Symmetric Array
构造，从d数组可以从大往小构造唯一的a数组。
eg：(a[ ]={-z,-y,-x,x,y,z}，d[ ]=[i,i,j,j,k,k])（已经排好序且合法），从最大的k开始可以构造出(z)和(-z)，因为其他任何数与(z)和(-z)的距离之和都为(2*z)，易知(z=k/(2*n))，这样就把z和-z确定下来了。
然后对于第二大的数(j)，它所对应的(y)和(-y)只有与(z)和(-z)连接时权值为(2*z)，其他时候都为(2*y)，因此把2*z减掉（这样(j==y*(2*n-2))了）就可以用刚刚提到的确定d中最大数对应a的方法去求。
以此类推，对每一个d数组中的数d[x]，需要先让(d[x]-=2*(d[x+1]/cnt[x+1]+d[x+2]/cnt[x+2]...+d[n]/cnt[n]))，然后检查(d[x])是否大于(0)并且对应的(a=d[x]/cnt[x])未出现过。
代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
double pi = acos(-1);
const double eps = 1e-9;
const int inf = 1e9 + 7;
const int maxn = 2e5 + 10;
ll mod = 1000000007;
bool check(vector<ll>& a)
{
int len = a.size();
if (len % 2 == 0)return 0;
for (int i = 1; 2 * i < len; i++)
if (a[2 * i] != a[2 * i - 1])
return 0;
return 1;
}
map<ll, ll>mp;
int main()
{
fastio;
int t;
cin >> t;
while (t--)
{
mp.clear();
int n;
cin >> n;
vector<ll>d(2 * n + 1);
for (int i = 1; i <= 2 * n; i++)
cin >> d[i];
sort(d.begin() + 1, d.end());
if (!check(d))
{
cout << "NO" << endl;
continue;
}
for (int i = 1, j = 1; i <= n; i++, j += 2)
d[i] = d[j];
ll tmp = 0, cnt = 2 * n;
bool flag = 1;
for (int i = n; i >= 1; i--)
{
d[i] -= tmp;
//cout << d[i] << " ";
if (d[i] % cnt != 0 || d[i] <= 0 || mp[d[i] / cnt])
{
flag = 0;
break;
}
mp[d[i] / cnt] = 1;
tmp += 2 * (d[i] / cnt);
cnt -= 2;
}
if (flag)
cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
D - Nezzar and Board
①(2*x-y)：假设(y=x+z)，则(2*x-y=x-z)，即每次选择两个数(x)和(y)，(y)都会以(x)为轴进行翻转。
②先以k为原点，确定每个点的位置。已有数（已排序）有n-1个相互之间的距离，他们通过上述操作可以凑出的最小值为所有距离gcd在一起（更相减损的推广，这个值是可以凑出所有这些值更相减损能凑出的数的），然后去遍历一发看看有没有数可以被这个数整除。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
double pi = acos(-1);
const double eps = 1e-9;
const int inf = 1e9 + 7;
const int maxn = 2e5 + 10;
ll mod = 1000000007;
ll gcd(ll a, ll b){ return b ? gcd(b, a % b) : a; }
int main()
{
fastio;
int t;
cin >> t;
while (t--)
{
ll n, k;
cin >> n >> k;
vector<ll>a(n + 1);
for (int i = 1; i <= n; i++)cin >> a[i], a[i] -= k;
sort(a.begin() + 1, a.end());
ll g = a[2] - a[1];
for (int i = 3; i <= n; i++)
g = gcd(g, a[i] - a[i - 1]);
bool flag = 0;
for (int i = 1; i <= n; i++)
if (a[i] % g == 0)
{
flag = 1;
break;
}
if (flag)
cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}