C. Nezzar and Symmetric Array
题意
有一个对称数组$a$,有 $2 * n$个元素,每个元素不重复,并且对任意一个元素都能找到相反数。
数组$d_i = \sum_{j=1}^{2n}{|a_i - a_j|}$,即每个点和其他所有点的差的绝对值之和。
现在给了数组$d$,问是否存在数组$a$能够构造出$d$。
思路
首先看一下$d$的表达式,因为是对称数组所以可以写成:
$$d_i = (|a_i - a_1| + |a_i + a_1|) + … + (|a_i - a_n| + |a_i + a_n|)$$
两个数的差的绝对值 加和的绝对值是绝对值更大的数的两倍,即:
$$|a_i - a_k| + |a_i + a_k| = 2 * max(a_i, a_k)$$
可以看出,$d$一定是偶数,并且每个数有且只有两个(原数组无重复元素)
对$d$排序之后,设比$a[i]$大的数有$k$个,大于$a[i]$的数的和是$sum$。
$$a_i = (d[i] - 2 * sum) / (2 * k)$$
这样就可以依次求出每一位$a$,然后判断能否整除,并且$a>0$,不符合的话就是$NO$了。
这里不能等于0也是因为原数组无重复元素,如果有$0$的话就有两个$0$.
代码
我写的稍微复杂了,有些地方可以简化,我就懒得写了
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 200010;
int n, m;
LL a[N];
void solve()
{
cin >> n;
for(int i = 0; i < n * 2; i ++)
cin >> a[i];
sort(a, a + n * 2);
vector<LL> v;
for(int i = 0; i < n * 2; i += 2)
if(a[i] != a[i + 1] || a[i] & 1 || i + 2 < n * 2 && a[i] == a[i + 2])
{
cout << "NO" << endl;
return;
}
else v.push_back(a[i]);
LL sum = 0;
for(int i = n - 1; i >= 0; i --)
{
LL x = (v[i] - 2 * sum) / (2 * (i + 1));
if(x == 0 || (v[i] - 2 * sum) % (2 * (i + 1)))
{
cout << "NO" <<endl;
return;
}
sum += x;
}
cout << "YES" <<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin >> t;
while(t --)
solve();
}
D. Nezzar and Board
题意
有n个不同的整数,每次可以任意选择两个数(可以相同)做$ 2 * x - y $,将值加入进去,并且原来的值还在。
问能否得到k。
思路
数论fw,看大佬博客学的,不是非常会。
最好自己先试着组合组合那些数,然后可以发现无论怎么组合,最后的系数和都是1。
形式如:k = a1 * (2*x1 - y1) + a2 * (2*x2 - y2) + ... + a(n-1) * (2*xn - yn) + xi
a
是系数,x,y
是给的数
通过这点,结合裴蜀定理。然后看代码
神志不清,不知道自己在说什么了┭┮﹏┭┮
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 200010;
int n;
LL a[N], k;
void solve()
{
cin >> n >> k;
for(int i = 0; i < n; i ++) cin >> a[i];
LL g = 0;
for(int i = 1; i < n; i ++)
g = __gcd(g, a[i] - a[i - 1]);
for(int i = 0; i < n; i ++)
if((k - a[i]) % g == 0)
{
cout << "YES" <<endl;
return;
}
cout << "NO" << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin >> t;
while(t --)
solve();
}
tql