CF 1770. GoodBye 2022, 2023 is Near
晚上十点三十五开打，十一点多就睡觉了，只做了A、C题，其他题都是VP的。感觉质量很高，签到题A题都卡了我一会。
A. Koxia and Whiteboard
签到题，赛场上写的是\(std\)的方法\(1\)。
简述一下思路：
一开始分类讨论了一下：
-
\(size_a \geqslant size_b\)，这时候就可以把所有数排序，然后取最大的。
-
\(size_b \geqslant size_a\)，这个一开始没想好，然后想到了每个数的贡献，突然灵光一现，只要每次把最小的数换掉不就行了吗？
然后又突然地发现分的第二类不是就是正解了嘛？然后就惊喜的发现分的第一类假了，于是开心的删了第一类。
\(std\)又给了一个方法\(2\)，后来发现是把我分的第一类假的做法改动了一下就对了，先将\(b_m\)加到最终的和中，而对于其他\((n+m-1)\)个数，自由选择其中的\((n-1)\)个并最大化它们的和。
\(personal\ code\)
#include <bits/stdc++.h>
using namespace std;
const int N = 2e2 + 10;
int n, m;
int a[N], b[N];
long long sum;
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
sum = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int j = 1; j <= m; j ++ ) scanf("%d", &b[j]);
sort(a + 1, a + n + 1);
for (int j = 1; j <= m; j ++ )
{
a[1] = b[j];
for(int i = 1; i < n; i++)
if(a[i] > a[i + 1]) swap(a[i], a[i + 1]);
}
for(int i = 1; i <= n; i++) sum += a[i];
printf("%lld\n", sum);
}
return 0;
}
\(std\)
// by M_99
#include <stdio.h> // ?
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000001
#define Inf64 4000000000000000001
int main(){
int _t;
cin>>_t;
rep(_,_t){
int n,m;
cin>>n>>m;
vector<long long> a(n+m);
rep(i,n+m)scanf("%lld",&a[i]);
sort(a.begin(),a.end()-1);
reverse(a.begin(),a.end());
long long ans = 0;
rep(i,n)ans += a[i];
cout<<ans<<endl;
}
return 0;
}
B. Koxia and Permutation
构造题，赛后VP。
思路：
首先，不难发现当\(k=1\)时，所有排列都成立。
由于上一题刚考虑到贡献，所以刚看到这题我依旧考虑贡献。
- \(k=1\), 贡献为\(2n\)
- \(k>=2\), 考虑极端原理，一边一定包含\(n\), 而另一边至少包含1，故最小贡献为\(n+1\)
所以不难构造出如下数列：
\({n,1,n-1,2,n-2,3,...n-\frac{n}{2}, \frac{n}{2}+1}\)，它符合题目条件。
\(personal\ code\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k, T;
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &k);
int l = 1, r = n, a = 1;
while (l <= r) cout << ((a ^= 1) ? l++ : r--) << ' ';
puts("");
}
return 0;
}
C. Koxia and Number Theory
“好题”——\(Alex\_wei\)
赛场上想了\(25min\)，改了八次没过掉，后来家长催着逐渐烦躁，就睡觉了，比完后看了\(Alex\_wei\)大神的题解才发现少了一步。
赛场思路：
-
首先，根据样例的第二个数据，我们不难发现如果存在相同的元素\(a_i\)和\(a_j\)，那么就不可能存在一个\(x\)，使得\(gcd(a_i+x,a_j+x)=1\)而是\(a_i+x\)，故此种情况为\(NO\)。
-
其次，在草稿纸上算了算之后，发现奇偶性质：
如果存在至少两个奇数与至少两个偶数，就是\(NO\)
不难理解，假设如果有两个奇数，那么如果加上一个奇数就会使之最大公约数至少为\(2\)，所以只能加偶数，但此时如果有两个偶数，那么就陷入了一个困境，反之亦然。
然而想到这里一激动就码了代码，交上去一直\(WA\)，然后就自闭了，然后就睡觉了。
但是，就是忘掉了最简单的一点：
- 除了\(2\)，其他的因数就不行了吗？
于是这题的正解就呼之欲出了，枚举所有质数（因数也可以），然后如果存在卜多宇两对同余的，就是\(YES\)，反之则是\(NO\)。代码里用的是中国剩余定理。
\(personal\ code\)（根据\(std\)稍微改了改，意思没变）
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 105, INF = 0x3f3f3f3f;
int n, cnt[N], T;
ll a[N];
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int pd = 1;
sort(a + 1, a + n + 1);
for (int i = 1; i < n; i++)
if (a[i] == a[i + 1])
{
pd = 0;
break;
}
if (!pd) // same elements
{
puts("NO");
continue;
}
else // tongyu
{
int CRT = 1;
for (int mod = 2; mod <= n / 2; ++mod) {
memset(cnt, 0, mod);
for (int i = 1;i <= n; ++i) cnt[a[i] % mod]++;
if (*min_element(cnt, cnt + mod) >= 2) CRT = 0;
}
if (CRT) puts("YES");
else puts("NO");
}
}
return 0;
}
先写到A~C的吧，后面的锅之后再补。
D. Koxia and Game
\(To be continued\)
E. Koxia and Tree
\(To be continued\)
F. Koxia and Sequence
\(To be continued\)
G. Koxia and Bracket
\(To be continued\)
H. Koxia, Mahiru and Winter Festival
\(To be continued\)
标签：std,1770,int,scanf,CF,long,解题,Koxia,include From： https://www.cnblogs.com/sunruize/p/17026544.html