20240108 A 组模拟赛 题解
前言
fun fact：这场比赛有至少三个人在 T1 对拍超过一万组的情况下仍挂了分，其中两个甚至从 100pts 挂到 0pts（不瞒你说，这两个人是我和 KK）。
此外，XD 作为唯一一个赛时想出 T3 做法，且和另外一位重庆老哥并列第一 95pts 的人，在赛后大量批话。具体请移步2024 批话合集。
唉，140->31。
T1
简单树形 DP。
设 $dp_i$ 表示从 $i$ 开始，涂完 $i$ 子树需要的最小时间。显然构造方案可以把所有儿子倒序排列后，每次涂前 $w_u$ 个，转移是简单的。
考虑如何换根，难点在于删掉将要换到的那个位置。容易发现每次删一个数会使后面全部往前平移一个。那么排序后倒序考虑删每个点，如果这个点恰好是某一块的开头才有可能使贡献改变，这个可以 multiset 维护。
复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=5e5+5,inf=0x3f3f3f3f;
int n,w[N],dp[N],pd[N];
vector<pii> vec[N];
vector<int> e[N];
void dfs(int x,int fa){
dp[x]=0;
for(auto i:e[x]){
if(i==fa) continue;
dfs(i,x);
vec[x].push_back(mkp(dp[i],i));
}
sort(vec[x].begin(),vec[x].end(),greater<pii>());
int sz=vec[x].size()-1;
forup(i,0,sz){
if(!(i%w[x])){
dp[x]=max(dp[x],vec[x][i].fi+i/w[x]+1);
}
}
}
void dfs2(int x,int fa){
multiset<int> ss;
sort(vec[x].begin(),vec[x].end(),greater<pii>());
int sz=vec[x].size()-1;
forup(i,0,sz){
if(!(i%w[x])){
ss.insert(vec[x][i].fi+i/w[x]+1);
}
}
ss.insert(0); // 这里是防止 RE
pd[x]=*prev(ss.end());
fordown(i,sz,0){
if(!(i%w[x])){
ss.erase(ss.find(vec[x][i].fi+i/w[x]+1));
if(i<sz) ss.insert(vec[x][i+1].fi+i/w[x]+1);
}
if(vec[x][i].se==fa||vec[x][i].se==x) continue;
vec[vec[x][i].se].push_back(mkp(*prev(ss.end()),x));
dfs2(vec[x][i].se,x);
}
}
signed main(){
n=read();
forup(i,1,n){
w[i]=read();
}
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,0);
dfs2(1,0);
forup(i,1,n){
printf("%d\n",pd[i]);
}
}
T2
感觉很智慧啊。
首先如果 $m=1$ 就是个裸的 Nim 游戏。但是 Nim 游戏是把每一堆分开的，而这个问题每一维都和其他维相关（因为有黑洞），考虑把四维放在一起的做法。
以下简称先手必胜为“必胜”，后手为“必败”。
首先按有向图博弈的思路，容易得到一个 $O(n^5)$ DP，具体来说，如果一个点下一步能走到的所有点都是必胜那么这个点必败，否则（指有至少一个点必败）这个点必胜。
注意到只需要考虑四个方向在下一个黑洞之前有没有必败点，又由于 DP 是从小到大枚举的，所以可以对每一维开一个三维的数组 $V_{a,b,c}$ 表示其余三维分别是 $a,b,c$，这一维到上一个黑洞前有没有必败点，每次遇到黑洞把对应四个点清零即可。
但是这个很难再压了，考虑继续优化。
注意到对最后一维记录的这个东西非常多余，因为你会连续地枚举这一维。容易发现，在每个黑洞之后找到第一个必败点，后面的都是必胜的（因为这一维对应的 $V$ 都是 $1$ 了）。而容易发现这个可以用 bitset 来维护。
具体来说，$V$ 只维护前三维，然后每次把对应的三个 bitset 并起来取反。这样每次只需要一个 _Find_next 就能找到第一个必败点，然后一直到下一个黑洞都是必胜的。具体求答案可以用总的减去必败的和黑洞。
注意每次更新三个 $V$，另外黑洞可以用指针维护。
时间复杂度 $O(\frac{n^4}{w}+m\log m)$，空间复杂度 $O(n^3+m)$，前面这个 $n^3$ 是 bitset 类型的所以不会炸。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=205,inf=0x3f3f3f3f;
int n,m,cnt;
struct Node{
int a,b,c,d;
bool operator <(const Node &r)const{
if(a!=r.a) return a<r.a;
if(b!=r.b) return b<r.b;
if(c!=r.c) return c<r.c;
return d<r.d;
}
}sv[100005];
bitset<N> b1[N][N],b2[N][N],b3[N][N],bs;
signed main(){
n=read();m=read();
forup(i,1,m){
int a=read(),b=read(),c=read(),d=read();
sv[i]=Node{a,b,c,d};
}
sort(sv+1,sv+m+1);
int ll=1;
forup(a,1,n){
forup(b,1,n){
forup(c,1,n){
bs=~(b1[b][c]|b2[a][c]|b3[a][b]);
int j=bs._Find_next(0);
#define ava (ll<=m&&sv[ll].a==a&&sv[ll].b==b&&sv[ll].c==c)
if(j<(ava?sv[ll].d:n+1)){
b1[b][c].set(j,1);
b2[a][c].set(j,1);
b3[a][b].set(j,1);
++cnt;
}
while(ava){
int i=sv[ll].d;
++ll;
b1[b][c].set(i,0);
b2[a][c].set(i,0);
b3[a][b].set(i,0);
int j=bs._Find_next(i);
if(j<(ava?sv[ll].d:n+1)){
b1[b][c].set(j,1);
b2[a][c].set(j,1);
b3[a][b].set(j,1);
++cnt;
}
}
}
}
}
printf("%d\n",n*n*n*n-m-cnt);
}
T3
怪题。
容易想到质因数完全相同的集合可以随意互换。
感觉这句话有歧义啊，若一个数的质因数分解为 $x=\prod p_i^{k_i}$，设 $f(x)=\prod p_i$，那么对于任意一对 $i,j$ 使得 $f(i)=f(j)$，$i,j$ 显然可以互相交换（因为任意一个数若和 $i$ 互质当且仅当和 $j$ 互质），设这样的集合为 $S$。
但是容易发现限制比这个更弱，比如在 $n=5$ 时 $1,3,5$ 是可以随意交换的，但显然这三者的 $f$ 不相同。
注意到若两个质数 $p_1,p_2$，满足 $\left\lfloor\frac{n}{p_1}\right\rfloor=\left\lfloor\frac{n}{p_2}\right\rfloor$，那么将这两个数的倍数集合完全互换也是合法的（对于交，容易发现完全不管它是没关系的）。因为我们只关注互质关系，所以具体包含哪个质因子其实就不重要了。
注意到若 $p_1\ne p_2$，又有 $\left\lfloor\frac{n}{p_1}\right\rfloor=\left\lfloor\frac{n}{p_2}\right\rfloor$，可以推出 $p_1,p_2>\sqrt{n}$，那么每个数只有一个这样的质因子。
这样就可以直接维护了。最终答案就是每个 $S$ 内没被用过的点数的阶乘之积乘上 $p_1\to p_2$ 的映射关系数量即可。
用欧拉筛复杂度可以做到 $O(n)$，注意特判 $1$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
char buf[1<<21],*p1,*p2;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=3e7+5,mod=1e9+7;
int n,a[N];
int vv[N],mx[N],mul[N];
vector<int> pri;
int vis1[N],vis2[N];
int cnt1[N],cnt2[N];
int fact[N];
void init(){
mx[1]=1;mul[1]=1;
++cnt1[1];++cnt2[1];
forup(i,2,n){
if(!vv[i]){
mx[i]=i;mul[i]=1;
pri.push_back(i);
++cnt2[n/i];
}
++cnt1[mul[i]*mx[i]];
for(auto j:pri){
if(i*j>n) break;
vv[i*j]=1;
if(i%j==0){
mx[i*j]=mx[i];
mul[i*j]=mul[i];
break;
}else{
mx[i*j]=mx[i];
mul[i*j]=mul[i]*j;
}
}
}
fact[0]=1;
forup(i,1,n){
fact[i]=1ll*fact[i-1]*i%mod;
}
}
bool chk(int a,int b){
int pa=(a==1?1:n/mx[a]),pb=(b==1?1:n/mx[b]);
if(mul[a]!=mul[b]||pa!=pb) return false;
if(vis1[mx[a]]){
if(vis1[mx[a]]!=mx[b]){
return false;
}
}else if(vis2[mx[b]]){
return false;
}
return true;
}
signed main(){
n=read();
init();
forup(i,1,n){
a[i]=read();
if(a[i]){
if(!chk(i,a[i])){
puts("0");
return 0;
}
int pp=i==1?1:n/mx[i];
if(!vis1[mx[i]]){
vis2[mx[a[i]]]=1;
vis1[mx[i]]=mx[a[i]];
--cnt2[pp];
}
--cnt1[mx[a[i]]*mul[a[i]]];
}
}
int ans=1;
forup(i,1,n){
ans=1ll*ans*fact[cnt1[i]]%mod;
ans=1ll*ans*fact[cnt2[i]]%mod;
}
printf("%d\n",ans);
}