Teza Round 1 (Codeforces Round 1015, Div. 1 + Div. 2)¶
2025-04-05
打得不是很好的一把，做出C题的人一大半都做出了D，我没写出来。这个D确实挺简单的。
比赛链接: https://codeforces.com/contest/2084
A¶
直接猜就行， \(n\) 为偶数时一定不行，为奇数时可以。
void ChatGptDeepSeek()
{
int n;
cin >> n;
if (n & 1)
{
// n 1 2
cout << n << " ";
for (int i = 1; i <= n - 1; i++)
cout << i << " ";
cout << '\n';
}
else
cout << "-1\n";
}
B¶
\(gcd([a_{i+1},a_{i+2},...,a_n]\le min([a_{i+1},a_{i+2},...,a_n])\) , 所以整个数组的最小值只能放在前半部分。
我们可以取所有的最小值的倍数的 \(gcd\) ，若不等于最小值，则不可能存在合法的方案。
void ChatGptDeepSeek()
{
int n;
cin >> n;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a.begin() + 1, a.end());
ll g = 0;
for (int i = 2; i <= n; i++)
if (a[i] % a[1] == 0)
g = __gcd(g, a[i]);
if (g == a[1])
cout << "Yes\n";
else
cout << "No\n";
}
C¶
发现如果有 $a_i=x $ , \(b_i=y\) ，则必须存在 \(a_j=y\) ， \(b_j=x\) ，我们把这样对称的点放到对称的位置即可。
只有 \(n\) 为奇数时，必须出现一个 \(a_i=b_i\) 的位置。
void ChatGptDeepSeek()
{
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
cin >> b[i];
}
/*
必然是有 x y
就會有 y x 不然就不行
若n為奇數 則肯定會有一個位置兩邊是相同的 這個一定要放在中間
*/
vector<int> p1(n + 1), p2(n + 1);
for (int i = 1; i <= n; i++)
{
p1[a[i]] = i;
p2[b[i]] = i;
}
{
int cnt = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] == b[i])
cnt++;
if (p1[b[i]] != p2[a[i]])
{
cout << "-1\n";
return;
}
}
if ((n & 1) && cnt > 1)
{
cout << "-1\n";
return;
}
if ((n % 2 == 0) && cnt)
{
cout << "-1\n";
return;
}
}
vector<pair<int, int>> ans;
if (n & 1)
{
for (int i = 1; i <= n; i++)
{
if (a[i] == b[i])
{
if (i != (n + 1) / 2)
{
ans.push_back({i, (n + 1) / 2});
swap(a[i], a[(n + 1) / 2]);
swap(b[i], b[(n + 1) / 2]);
p1[a[i]] = i;
p2[b[i]] = i;
break;
}
}
}
}
for (int i = 1; i <= n / 2; i++)
{
int j = n - i + 1;
if (b[j] != a[i])
{
int k = p1[b[i]];
// swap(k,j)
swap(a[j], a[k]);
swap(b[j], b[k]);
ans.push_back({k, j});
p1[a[k]] = k;
p2[b[k]] = k;
}
// for (int j = 1; j <= n; j++)
// cerr << a[j] << " \n"[j == n];
// for (int j = 1; j <= n; j++)
// cerr << b[j] << " \n"[j == n];
}
// {
// vector c = a;
// reverse(c.begin() + 1, c.end());
// assert(c == b);
// }
cout << ans.size() << '\n';
for (auto [l, r] : ans)
cout << l << " " << r << '\n';
}
D¶
我们如果能将数组分成 \(m+1\) 段，且每一段的长度大于等于 \(k\) ，那么答案就会是每一段的长度。否则答案不可能大于 \(n-mk<k\) ，可以构造成每段都是 \([0,k-1]\) ，这样可以保证答案取到 \(n-mk\) 。