- B. Nezzar and Lucky Number
- C. Nezzar and Symmetric Array
题解：
假设一个数可以拆成 k k k个 d d d的和再加上一个余数， 如果余数与 k k k中若干个 d d d可以组成一个 lucky number，那么说明这个数就是 lucky number
还有一点就是，如果这个数大于10倍的 d d d，说明这个数就一定是 lucky number 。假设 d d d是7，10倍的 d d d就是70，那么这个数就可以拆成若干个7之和再加上70-79之间的任意一个数与余数的和
int a[N], st[10];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int T; scanf("%d", &T);
while (T -- )
{
int q, d; scanf("%d%d", &q, &d);
for (int i = 1; i <= q; i ++ ) scanf("%d", &a[i]);
for (int i = 2; i <= 9; i ++ ) st[i] = i * d;
for (int i = 1; i <= q; i ++ )
{
if (a[i] >= 10 * d) puts("YES");
else if (a[i] % d == 0) puts("YES");
else
{
bool flag = false;
int c = a[i] / d, y = a[i] % d;
for (int i = 2; i <= 9; i ++ )
{
if (d - y == st[i] % 10 && i <= c)
{
puts("YES");
flag = true;
break;
}
}
if (!flag) puts("NO");
}
}
}
return 0;
}
C. Nezzar and Symmetric Array
题目大意：
一个数组内有 2 n 2n 2n个不同的元素，且保证每一个 a i ( 1 ≤ i ≤ 2 n ) a_{i}left ( 1le ile2n right ) ai(1≤i≤2n)都有一个对应的 a j ( 1 ≤ j ≤ 2 n ) a_{j}left ( 1le jle2n right ) aj(1≤j≤2n)，使得 a i = − a j a_{i}=-a_{j} ai=−aj。 d i = ∑ j = 1 2 n ∣ a i − a j ∣ d_{i}= {textstyle sum_{j=1}^{2n}}left | a_{i}-a_{j} right | di=∑j=12n∣ai−aj∣，问是否存在一个数组 a a a使之满足数组 d d d。
题解：
通过简单打表可以发现，对于每个
d
i
d_{i}
di有
n
−
1
n-1
n−1个贡献度是
2
m
a
x
(
∣
a
i
∣
,
∣
a
j
∣
)
2max(|a_{i}|,|a_{j}|)
2max(∣ai∣,∣aj∣)，
∣
a
i
∣
!
=
∣
a
j
∣
|a_{i}|!=|a_{j}|
∣ai∣!=∣aj∣.另一个贡献度是
a
i
a_{i}
ai本身
假设数组 a = [ a , b , c , d , − a , − b , − c ] a=[a, b, c, d,-a,-b,-c] a=[a,b,c,d,−a,−b,−c]，那么 d 1 = 2 ( ∣ a ∣ + m a x ( ∣ a ∣ , ∣ b ∣ ) + m a x ( ∣ a ∣ , ∣ c ∣ ) ) d_{1}=2(|a|+max(|a|,|b|)+max(|a|,|c|)) d1=2(∣a∣+max(∣a∣,∣b∣)+max(∣a∣,∣c∣))
如果a是最大的，那么
d
1
=
2
(
∣
a
∣
+
∣
a
∣
+
∣
a
∣
)
d_{1}=2(|a| + |a| + |a|)
d1=2(∣a∣+∣a∣+∣a∣)，则
a
=
d
1
2
⋅
3
a=frac{d_{1}}{2cdot 3}
a=2⋅3d1
且如果b是次大的，那么
d
2
=
2
(
∣
b
∣
+
∣
b
∣
+
∣
a
∣
)
d_{2}=2(|b| + |b| +|a|)
d2=2(∣b∣+∣b∣+∣a∣)，则
b
=
d
2
2
−
a
2
b=frac{frac{d_{2}}{2}-a}{2}
b=22d2−a
则
d
3
=
2
(
∣
c
∣
+
∣
b
∣
+
∣
a
∣
)
d_{3}=2(|c| + |b| +|a|)
d3=2(∣c∣+∣b∣+∣a∣)，
c
=
d
2
2
−
a
−
b
1
c=frac{frac{d_{2}}{2}-a-b}{1}
c=12d2−a−b
void solve()
{
int n;
scanf("%d", &n);
map > mp;
for (int i = 0; i < 2 * n; i ++ )
{
LL x; scanf("%lld", &x);
mp[x] ++;
}
bool flag = true;
for (auto it : mp)
{
if (it.se != 2 || it.fi % 2)
{
flag = false;
break;
}
}
if (!flag)
{
puts("NO");
return;
}
LL sum = 0;
for (auto it : mp)
{
LL tmp = it.fi / 2 - sum;
if (tmp <= 0 || tmp % n)
{
flag = false;
break;
}
sum += tmp / n;//每次记录计算过的最大值，下一步去掉
n --;//计算一次去掉一次
}
if (!flag) puts("NO");
else puts("YES");
}
