2023.11.11 模拟赛复盘
前记
通过四个半小时的努力，得到了 41pts / 400pts 的高分。
当时心态很爆炸，经过不断的反思，发现自己比赛意识太差，暴力打不出，正解想出来 tmd 不会写，这就是最大的问题。
所以以后要多打比赛还得多复盘。
比赛链接
T1 种树
简化题意：
给定 \(n\) 个正整数 \(p_1, p_2,\dots,p_n\) 和 \(w\)，请你将每个 \(p_i\) 扩大 \(d_i~(d_i\ge1)\) 倍并且 \((\prod\limits_{i=1}^{n}d_i)=w\)。设 \(g_i\) 表示 \(p_i\) 的正因数个数，求出最大化的 \(\prod\limits_{i=1}^{n}g_i\)，并对 \(998244353\) 取模。
对于任意正整数 \(p\) ，都可以表示成：\(p=\prod\limits_{i=1}^{m}a_i^{k_i}\)（\(k_i\ge1\) 且 \(a_i\) 为互不相同的质数）。
由因数定理，不难想到 \(g_i =\prod\limits_{i=1}^{m}k_i+1\)（每个 \(a\) 的次数有 \(k+1\) 种取法）。
那么对于这个题，我们可以得到贪心策略如下：
-
如果对于质数 \(k\)，序列 \(p\) 中每一个数都有一个因子为 \(k\)（我们称此情况为条件 A），那么就将 \(w / k\)，并且将序列中含有 \(k\) 的指数最小的那个数乘上 \(k\)
-
如果不是条件 A，对于答案直接翻倍即可。
Code:
#include <bits/stdc++.h>
#define rint register int
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e4 + 5;
const int mod = 998244353;
int n, w;
int a[N];
int ans = 1;
priority_queue<int, vector<int>, greater<int> > q;
void calc(int x, int s)
{
int cnt;
for (rint i = 1; i <= n; i++)
{
cnt = 0;
while (a[i] % x == 0)
{
cnt++;
a[i] /= x;
}
q.push(cnt + 1);
}
while (s > 0)
{
int x = q.top();
q.pop();
q.push(x + 1);
s--;
}
for (rint i = 1; i <= n; i++)
{
ans = ans * q.top() % mod;
q.pop();
}
}
signed main()
{
cin >> n >> w;
for (rint i = 1; i <= n; i++)
{
cin >> a[i];
}
for (rint i = 2; i * i <= w; i++)
{
if (w % i == 0)
{
int cnt = 0;
while (w % i == 0)
{
cnt++;
w /= i;
}
calc(i, cnt);
}
}
if (w > 1) calc(w, 1);
for (rint i = 1; i <= n; i++)
{
/*
这一步没有必要判断 j 一定是质数
举个例子, 如果 2 不行, 那么 2 的倍数一定也不行
*/
for (rint j = 2; j * j <= a[i]; j++)
{
int cnt = 0;
while (a[i] % j == 0)
{
a[i] /= j;
cnt++;
}
ans = ans * (cnt + 1) % mod;
}
if (a[i] > 1)
{
//cout << a[i] << " ";
ans = ans * 2 % mod;
}
}
cout << ans << endl;
return 0;
}
T2 汪了个汪
简化题意：构造一个边长为 \(n\) 的数字三角形，满足相邻两个数组成的无序数对只出现一次，并且每行开头数字不同，每行数字不同，只包含 \(1\) 到 \(n\) 的数字。
这个题有很多种构造方案，在这里记录最简单的一种。
一般来说这种傻逼构造题对于 \(n\) 为偶数情况来说比较好入手，我们先来打个表搓一下：
1 1 1
2 1 2 4 2 4
3 1 4 3 1 5
4 3 2 1 4 6 2 5
5 3 6 1 4
6 5 4 3 2 1
通过瞪眼法，不难发现，这个三角形是沿着斜边高对称的对吧。我们现在砍掉一半：
1 1 1
2 2 4 2 4
3 1 3 1 5
4 4 6 2
5 3
6
接着瞪眼法，我们大概猜一下，对于偶数情况如何构造：
-
1.第一列，一定是 \(1,2,3,....n\)
-
2.对于 \(n\) 所构造的数字三角形，它一定可以由 \(n - 2\) 所构造的数字三角形推过来
-
3.除了最右边一列，下面添加的两个数都是这个数上方两个数加 \(2\)
考虑奇数如何构造。
先看 \(n = 5\)：
1
2 4
3 1 5
4 5 2 3
5 3 4 1 2
我们再猜一个结论：
- 1.第一列，一定是 \(1,2,3,....n\)
- 2.沿着斜边高对称，但是，这个对称是指，\(1\) 换成 \(2\)，\(2\) 换成 \(1\)，其余同理
然后就和偶数一样了，因为我们对于 \(n=5\)，只需要找出
1
2 4
3 1
4
就可以确定它了。
该结论正确性我们就坚信它是对的就可以了。
#include <bits/stdc++.h>
#define rint register int
#define int long long
#define endl '\n'
using namespace std;
const int N = 5e3 + 5;
int n;
int a[N][N];
signed main()
{
cin >> n;
for (rint i = 1; i <= n / 2; i++)
{
for (rint j = 1; j <= i; j++)
{
int k = i & 1;
if (j < i)
{
a[i * 2 - j][j] = a[i * 2 - j - 2][j] + 2;
a[i * 2 - j + 1][j] = a[i * 2 - j - 1][j] + 2;
}
else
{
a[i * 2 - j][j] = i * 2 - k;
a[i * 2 - j + 1][j] = k + 1;
}
}
}
if (n & 1)
{
for (rint i = 1; i <= n / 2 + 1; i++)
{
a[n + 1 - i][i] = n;
}
for (rint i = 1; i <= n; i++)
{
for (rint j = 1; j <= min(i, n - i); j++)
{
a[n + 1 - j][n + 1 - i] = a[i][j] & 1 ? a[i][j] + 1 : a[i][j] - 1;
}
}
}
else
{
for (rint i = 1; i <= n; i++)
{
for (rint j = 1; j <= min(i, n + 1 - i); j++)
{
a[n + 1 - j][n + 1 - i] = a[i][j];
}
}
}
for (rint i = 1; i <= n; i++)
{
for (rint j = 1; j <= i; j++)
{
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}