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;
}
T3 挑战 NPC IV
大概就是说对于一个序列进行全排列,每一个排列都有一个对应的价值,求第 \(k\) 小的价值。
由于此题过于复杂,我只打了个 4pts 暴力就滚蛋了,所以在此复制 TernaryTree 的题解。
再进行复制之前,梳理一下本题思路。
对于 \(n>28\) 的情况,由于最小值的个数一定极大,也就是说,对于此题的第 \(k\) 小的答案,就是最小价值。
对于 \(n<28\),进行 dp 求解。
先来明确一点定义。定义一个排列为 $p$,其每个元素的优美度构成的序列为 $q$,定义 $q$ 中数字 $i$ 出现的次数为 $cnt_i$。
首先考虑一个 $q$ 序列可以被还原成几个 $p$ 序列。$q$ 中每个相同的数字都可以被替换为 $p$ 中未被选择过的优美度为其自身的数,所以方案数是
$$\prod cnt_i!$$
接下来解决 $cnt_i$ 的计算问题。若 $1+\operatorname{lowbit}(p_i)=q_i$,则有 $p_i=2^{q_i-1}\cdot (2k+1)$,其中 $k$ 为非负整数。通过解不等式,得到 $cnt_i=\left\lfloor\dfrac{n+2^{i-1}}{2^i}\right\rfloor$。
上面那个阶乘的柿子引导我们去思考,对于一个非常大的 $n$ 结果会如何。那么就是,当我们按总优美度最小的方案填入 $q$ 中,这个 $q$ 所对应的 $p$ 个数就足够多以至于远远大于我们的 $k$ 了。通过计算/打表可以得出,当 $n\gt 28$ 时,最小值的个数已经超过了 $10^{18}$。于是对于这种情况,我们只需要构造出其最小值即可。
进行一个套路式贡献的拆。一个数的优美度被计算到答案里,当且仅当选择的区间包含它;而包含它的区间是 $i\cdot (n-i+1)$ 个。这是一个单峰函数,越往中心的 $i$ 其值越大。而为了让答案最小,我们显然要把 $q$ 值最大的放在两边,把最小的放在中间。通过枚举 $\log V\to 1$ 的 $q$ 值,维护前面放了几个,计算出这一次选择的 $q$ 值放在哪两段区间(因为显然是一左一右,放在两边),推一小段柿子即可得到这个值的贡献。在代码中,这一部分实现了函数 solve
和 calc
。
接下来考虑如何解决 $n\le 28$ 的部分。这个时候只会有 $5$ 种 $q$ 值,即 $1\sim 5$。我们考虑一个 dp:令 $f_{i,j_1,j_2,j_3,j_4,j_5,z}$ 表示前 $i$ 个位置,填了 $j_1$ 个 $1$,$j_2$ 个 $2$,以此类推;并且所有位置上的数乘上其贡献(即 $i(n-i+1)$)的和是 $z$ 的 $q$ 个数。注意到 $j1$ 是没用的,因为 $j_1=i-j_2-j_3-j_4-j_5$;其次 $i$ 可以通过滚动数组滚掉。又 $28$ 以内 $cnt_2\le 7$,$cnt_3\le 4$,$cnt_4\le 2$,$cnt_5\le 1$,并且计算/打表出 $z$ 最大就 $6\times 10^3$,我们把 dp 数组压缩到了 $8\times5\times3\times2\times(6\times 10^3)$ 的大小。此处的转移是简单的。
最后计算答案时,从 $0\sim 6\times 10^3$ 枚举 $z$,查看 $f_{cnt_2,cnt_3,cnt_4,cnt_5,z}$ 乘上一个 $q$ 对应的方案数是否 $\le k$,若成立输出 $z$,否则将减去对应的个数即可。
#include <bits/stdc++.h>
#define rint register int
#define int long long
#define endl '\n'
#define ll __int128
using namespace std;
const int N = 7e3 + 5;
const int M = 6e3;
const int mod = 998244353;
const int inv2 = 499122177;
const int inv6 = 166374059;
int T, n, k;
int f[8][5][3][2][N];
int g[8][5][3][2][N];
int solve(int l, int r, int n)
{
int s1 = (n + 1) % mod * ((l % mod + r % mod) % mod) % mod * ((r % mod - l % mod + mod + 1) % mod) % mod * inv2 % mod;
l--;
int s2 = r % mod * ((r + 1) % mod) % mod * ((r * 2 % mod + 1) % mod) % mod * inv6 % mod;
int s3 = l % mod * ((l + 1) % mod) % mod * ((l * 2 % mod + 1) % mod) % mod * inv6 % mod;
return ((s1 - s2 + mod) % mod + s3) % mod;
}
int calc(int n)
{
int l = 0, r = n + 1, c = 0;
for (rint i = 62; i >= 1; i--)
{
int s = (n / (1ll << (i - 1)) + 1) / 2;
if (!s) continue;
if (l == n - r + 1)
{
(c += (solve(l + 1, l + s / 2, n) + solve(r - s + s / 2, r - 1, n)) % mod * i % mod) %= mod;
l += s / 2;
r -= s - s / 2;
}
else
{
(c += (solve(l + 1, l + s - s / 2, n) + solve(r - s / 2, r - 1, n)) % mod * i % mod) %= mod;
l += s - s / 2;
r -= s / 2;
}
}
return c;
}
void dp()
{
int c1 = (n / 1 + 1) / 2;
int c2 = (n / 2 + 1) / 2;
int c3 = (n / 4 + 1) / 2;
int c4 = (n / 8 + 1) / 2;
int c5 = (n / 16 + 1) / 2;
memset(f, 0, sizeof f);
f[0][0][0][0][0] = 1;
for (int i = 1; i <= n; i++)
{
memset(g, 0, sizeof g);
for (rint j = 0; j <= min(c2, i); j++)
{
for (rint k = 0; k <= min(c3, i - j); k++)
for (rint p = 0; p <= min(c4, i - j - k); p++)
for (rint l = 0; l <= min(c5, i - j - k - p); l++)
for (rint z = 0; z <= M; z++)
{
if (z >= 1 * i * (n - i + 1))
g[j][k][p][l][z] += f[j][k][p][l][z - 1 * i * (n - i + 1)],
g[j][k][p][l][z] %= mod;
if (z >= 2 * i * (n - i + 1))
g[j][k][p][l][z] += f[j - 1][k][p][l][z - 2 * i * (n - i + 1)],
g[j][k][p][l][z] %= mod;
if (z >= 3 * i * (n - i + 1))
g[j][k][p][l][z] += f[j][k - 1][p][l][z - 3 * i * (n - i + 1)],
g[j][k][p][l][z] %= mod;
if (z >= 4 * i * (n - i + 1))
g[j][k][p][l][z] += f[j][k][p - 1][l][z - 4 * i * (n - i + 1)],
g[j][k][p][l][z] %= mod;
if (z >= 5 * i * (n - i + 1))
g[j][k][p][l][z] += f[j][k][p][l - 1][z - 5 * i * (n - i + 1)],
g[j][k][p][l][z] %= mod;
}
}
memcpy(f, g, sizeof g);
}
int mul = 1;
for (rint i = 1; i <= c1; i++) mul = mul * i;
for (rint i = 1; i <= c2; i++) mul = mul * i;
for (rint i = 1; i <= c3; i++) mul = mul * i;
for (rint i = 1; i <= c4; i++) mul = mul * i;
for (rint i = 1; i <= c5; i++) mul = mul * i;
for (rint z = 0; z <= M; z++)
{
ll v = (ll)f[c2][c3][c4][c5][z] * mul;
if (k <= v)
{
cout << z << endl;
break;
}
else
{
k -= v;
}
}
}
signed main()
{
cin >> T;
while (T--)
{
cin >> n >> k;
if (n > 28)
{
cout << calc(n) << endl;
}
else
{
dp();
}
}
return 0;
}
T4 四暗刻单骑
当时我们智慧的教练告诉我 T4 简单,这个大怨种就去写了,最后荣获 0pts 的高分!
在这里引入 樱雪喵 大佬的题解
先考虑 \(O(nm)\) 做法:
交替摸牌,所以每张牌被谁摸到是固定的。
因为游戏过程中每个人手里的两张牌都不会相同(不然就结束了),他们一定不会打出和对手手里一样那张牌。所以最后和牌的方式一定是一个人从牌堆中摸到了和自己一样的牌。
再考虑两个人手牌一样的情况,他们任何一人都不能丢掉这张牌,不然对面就赢了。因此这种情况的结局是能够直接判定的:判断下一张相同的牌被谁摸到即可,如果没有就是平局。
那么,一个人想和牌,他的策略一定是从某个时刻开始一直拿着某张牌,直到摸到下张一样的。
考虑某个人一直拿着第 $i$ 张牌会产生什么效果:
- 如果下一张同色的牌被自己摸到,设它的位置是 $x$。那么拿着这张牌的结果是在 $x$ 时刻胜利。
- 如果下一张同色的牌被对手摸到,对手必然不能把这张牌丢掉。因此双方手牌相同,结局已经确定。
- 再下一张被自己摸到,但因为从 $x$ 时刻开始对面就没有翻盘的机会了,我们记它的结果是在 $x$ 时刻直接胜利。
- 被对手摸到,记它的结果是在 $x$ 时刻失败。
- 否则是在 $x$ 时刻达成平局。
那么我们可以在序列上模拟这个过程,如果牌的效果是胜利就选择胜利更早的;失败就选择失败得更晚的,因为可能后面能摸到胜利的牌而翻盘。如果当前已经到达了某个人手里的牌的胜利或失败时刻,则判定答案。
然而直接这样搞并不正确,可怜的樱雪喵写假了一天也没想明白哪里不对。
考虑这样的一组数据:牌堆依次为 $3,1,4,3,4$,初始手牌为 $1,2$。
Alice 在第一轮是否把牌换成 $3$ 都是平局,她更希望等到后面胜利。而 Bob 如果寄希望于后面胜利,不选择把 $2$ 换成 $1$,他最后只能失败。而如果他的目标是平局,他会摸走牌堆中的 $1$,并成功平局。
这启发我们思考一个问题:存在一些情况,如果一个人目标是取得胜利,他就输了;但如果他的目标仅仅是保住平局,却能成功阻止对面赢。这是不能直接贪心判断的。
考虑用如下做法改变他们的目标:先钦定平局算 Alice 赢,这等价于 Alice 的目标是保住平局。如果此时 Bob 仍然能赢,才算作 Bob 必胜。反之同理。
如果正反都不满足条件,则说明存在一种方式使本来要输的人保住平局,答案为平局。
预估得分 48pts,实际得分 52pts
#include <bits/stdc++.h>
#define rint register int
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5 + 5;
int id, n, m, k;
int a[N];
int flag;
vector<int> pos[N];
int find(int x, int l, int r)
//二分找位置
{
auto k = upper_bound(pos[x].begin(), pos[x].end(), l);
if (k == pos[x].end() || (*k) > r)
{
return -1;
}
return *k;
}
int get(int x, int l, int r, int p = 0)
//x 是当前牌的颜色, l,r 是询问的区间(l 是这张牌的位置), g 是用来特判初始手牌的
//这个函数的整体作用是求“一直拿着这张牌的结果”
//正数则表示是在第几轮赢,负数表示在第绝对值轮输
{
int k = find(x, l + p, r);
if (k == -1)
{
return (l & 1) == flag ? n + 1:- n - 1;
}
if ((k & 1) == (l & 1))
{
return k;
}
int K = find(x, k, r);
if (K == -1)
{
return (l & 1) == flag ? k : -k;
}
else if((K & 1) == (l & 1))
{
return k;
}
return -k;
}
int solve(int x, int y, int l, int r)
//solve 按照摸牌顺序模拟他们决策的过程
{
if (x == y)
{
int nxt = find(x, l - 1, r);
if (nxt == -1)
{
return flag ? 1 : -1;
}
else if ((nxt & 1) == (l & 1))
{
return 1;
}
else return -1;
}
int wx = get(x, l - 2, r, 1);
int wy = get(y, l - 1, r);
for (rint i = l; i <= r; i++)
{
if (wx == i)
{
return 1;
}
if (wy == i)
{
return -1;
}
if (-wx == i)
{
return -1;
}
if (-wy == i)
{
return 1;
}
if (x == y)
{
int nxt = find(x, i - 1, r);
if (nxt == -1)
{
return flag ? 1 : -1;
}
else if((nxt & 1) == (l & 1))
{
return 1;
}
else return -1;
}
if ((i & 1) == (l & 1))
{
int nxt = get(a[i], i, r);
if (nxt > 0 && (nxt < wx || wx < 0))
{
wx = nxt;
x = a[i];
}
else if (nxt < 0 && wx < 0 && nxt < wx)
{
wx = nxt;
x = a[i];
}
}
else
{
int nxt = get(a[i], i, r);
if (nxt > 0 && (nxt < wy || wy < 0))
{
wy = nxt;
y = a[i];
}
else if (nxt < 0 && wy < 0&& nxt < wy)
{
wy = nxt;
y = a[i];
}
}
}
return flag ? 1 : -1;
}
signed main()
{
cin >> n >> m >> k;
for (rint i = 1; i <= n; i++)
{
cin >> a[i];
pos[a[i]].push_back(i);
}
while (m--)
{
id++;
int x, y, l, r;
cin >> x >> y >> l >> r;
flag = 1;
int res1 = solve(x, y, l, r);
flag = 0;
int res0 = solve(x, y, l, r);
if (res1 == -1)
{
puts("B");
}
else if(res0 == 1)
{
puts("A");
}
else
{
puts("D");
}
}
return 0;
}
考虑优化,可以使用线段树。
假设每张牌的结局是已经确定的,依旧不容易快速地维护答案,因为输了要尽可能晚输,赢了又要尽可能早赢。
我们继续观察性质。
注意到,到达某张手牌判定答案的时刻时,被判定的一定是赢的那张牌。换句话说,一个人必然不会一直拿着一张输的牌,直到因为这张牌而输掉。
考虑证明这个结论。假设 Alice 现在手里拿着一张输的牌,并且下一轮就要输了;这时候她又摸到了另一张要输的牌。因为这两张牌不同,它们输的位置也一定不同。那么新摸的这张牌一定输得比原来那张要晚。每当出现这种情况 Alice 就换牌,即可保证始终不因为输的牌而输掉。
当然这里要特判拿着初始手牌在第一轮就输掉的情况,因为此时他们没有选择权。
因此我们只需判断一段区间内最早赢的牌被谁摸到了。
考虑离线询问,从左向右扫描 $r$。对于在 $i$ 位置的牌,它的贡献只与它下一张相同的牌、下下张相同的牌是否在区间内有关。因此一张牌的贡献只会改变 $3$ 次,可以每次修改暴力求新值。
那么对于每个询问,最早赢的牌即为区间内最小值所在的位置,判断这张牌位置的奇偶性即可。
我们需要一个数据结构支持单点修改,区间查询最小值和最小值的位置。这里使用线段树维护。
复杂度 \(O((n+m)\log n)\)
代码不会写,不写了。
标签:11,nxt,return,int,rint,2023.11,define,模拟,mod From: https://www.cnblogs.com/spaceswalker/p/17837327.html