2024.9.12 CF1783 VP
A：先将 \(a\) 降序排序，此时只有位置 \(2\) 有可能不满足条件。找到最小的 \(i\ge 2\) 使得 \(a_1\neq a_i\)（不存在则无解），然后交换 \(a_2,a_i\)，即为一个解。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define psbk push_back
#define fst first
#define scd second
#define umap unordered_map
#define pqueue priority_queue
#define vc vector
#define endl '\n'
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
constexpr int inf = 0x3f3f3f3f;
int n, a[55];
bool cmp(int x, int y)
{
return x > y;
}
void solve()
{
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
sort(a + 1, a + n + 1, cmp);
for(int i=2;;i++)
{
if(i > n)
{
cout << "NO" << endl;
return;
}
if(a[i] != a[1])
{
swap(a[2], a[i]);
break;
}
}
cout << "YES" << endl;
for(int i=1;i<=n;i++)
{
cout << a[i] << ' ';
}
cout << endl;
}
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt;
cin >> tt;
while(tt--)
{
solve();
}
return 0;
}
B：一开始看错题了，看成了最大化相邻格差的绝对值之和，吃了两发罚时。
差的绝对值只有 \(1\sim n^2-1\) 这 \(n^2-1\) 个值。给出一种构造（以 \(n=6\) 为例）：
\[\begin{matrix}
1 & 36 & 2 & 35 & 3 & 34\\
31 & 6 & 32 & 5 & 33 & 4\\
7 & 30 & 8 & 29 & 9 & 28\\
\vdots & \vdots & \vdots & \vdots & \vdots &\vdots
\end{matrix}\]
其中 \(36-1，36-2，35-2，35-3，34-3，34-4，33-4，33-5，\cdots\) 构成 \(n^2-1\sim 1\) 的序列，其 \(beauty\) 达到最大。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define psbk push_back
#define fst first
#define scd second
#define umap unordered_map
#define pqueue priority_queue
#define vc vector
#define endl '\n'
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
constexpr int inf = 0x3f3f3f3f;
int n, a[55][55];
void solve()
{
cin >> n;
int cur1 = 1, cur2 = n * n;
for(int i=1;i<=n;i++)
{
if(i % 2)
{
for(int j=1;j<=n;j++)
{
if((i + j) % 2 == 0)
{
a[i][j] = cur1++;
}
else
{
a[i][j] = cur2--;
}
}
}
else
{
for(int j=n;j;j--)
{
if((i + j) % 2 == 0)
{
a[i][j] = cur1++;
}
else
{
a[i][j] = cur2--;
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout << a[i][j] << ' ';
}
cout << endl;
}
}
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt;
cin >> tt;
while(tt--)
{
solve();
}
return 0;
}
C：这题场上写了很久，吃了 \(4\) 发罚时，下次注意先想清楚细节再写代码。
大体上是先选准备时长短的。先选出前 \(k\) 短的，使得任何一个都不能再选。若此时未选 \(k+1\) 号选手，且将已选选手中准备时间最长的替换为 \(k+1\) 号选手后总时间 \(\le m\)，则你的胜场数还是 \(k\)，而 \(k+1\) 号选手的胜场数从 \(k+1\) 变成了 \(k\)，其他选手与你的排名相对位置不变，所以你的排名会 \(-1\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define psbk push_back
#define fst first
#define scd second
#define umap unordered_map
#define pqueue priority_queue
#define vc vector
#define endl '\n'
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
constexpr int inf = 0x3f3f3f3f;
int n, m, pa[500005];
struct Node {
int x, id;
} a[500005];
bool cmp(Node x, Node y)
{
return x.x == y.x ? x.id > y.id : x.x < y.x;
}
void solve()
{
cin >> n >> m;
for(int i=1;i<=n;i++)
{
cin >> a[i].x;
a[i].id = i;
}
sort(a + 1, a + n + 1, cmp);
for(int i=1;i<=n;i++)
{
pa[a[i].id] = i;
}
int sum = 0;
for(int i=1;i<=n;i++)
{
if(sum + a[i].x > m)
{
int ans = 1;
for(int j=1;j<=n;j++)
{
ans += (i - 1 < (j >= i) + a[j].id - 1);
}
int ID = pa[i];
if(ID >= i && sum - a[i - 1].x + a[ID].x <= m)
{
ans--;
}
cout << ans << endl;
return;
}
sum += a[i].x;
}
cout << 1 << endl;
}
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt;
cin >> tt;
while(tt--)
{
solve();
}
return 0;
}
D：这题看了两分钟就想到思路了，但是由于 C 花费太长时间没写完。感觉比 C 简单。
看到 \(300\) 的数据范围容易想到三次方 dp。设 \(dp_{i,j}\) 表示操作完位置 \(i\) 后，位置 \(i+1\) 的值为 \(j\) 的序列数。
初值：
\[dp_{1,i}=\begin{cases}
1&\text{if}\ i=a_2\\
0&\text{if}\ i\neq a_2
\end{cases}\]
转移：刷表法。对每个 \(dp_{i,j}\)，依次执行 \(dp_{i+1,a_{i+2}+j}\gets dp_{i+1,a_{i+2}+j}+dp_{i,j}\)，\(dp_{i+1,a_{i+2}-j}\gets dp_{i+1,a_{i+2}-j}+dp_{i,j}\)（\(j=0\) 则只转移一次）。
答案：\(Ans = \sum_{i}dp_{n-1,i}\)。
注意：
-
记得取模
-
数组下标不能为负，要将第二维下标都加上一个数。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define psbk push_back
#define fst first
#define scd second
#define umap unordered_map
#define pqueue priority_queue
#define vc vector
#define endl '\n'
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
constexpr int inf = 0x3f3f3f3f, mo = 998244353;
int n, a[305], dp[305][180010];
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
dp[1][a[2] + 90000] = 1;
dp[2][a[3] + a[2] + 90000] = 1;
if(a[2])
{
dp[2][a[3] - a[2] + 90000] = 1;
}
for(int i=2;i<n-1;i++)
{
for(int j=-90000;j<=90000;j++)
{
if(!j)
{
(dp[i + 1][a[i + 2] + 90000] += dp[i][90000]) %= mo;
}
else
{
if(a[i + 2] + j <= 90000)
{
(dp[i + 1][a[i + 2] + j + 90000] += dp[i][j + 90000]) %= mo;
}
if(a[i + 2] - j <= 90000)
{
(dp[i + 1][a[i + 2] - j + 90000] += dp[i][j + 90000]) %= mo;
}
}
}
}
int ans = 0;
for(int i=0;i<=180000;i++)
{
(ans += dp[n - 1][i]) %= mo;
}
cout << ans << endl;
return 0;
}