2022杭电多校第五场题解

本文主要是介绍2022杭电多校第五场题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2022杭电多校第五场

在这里插入图片描述

Slipper（最短路）

题意
有一个以 $1$ 为根的有根树，每条边有一个边权 $w$ ，经过一条边消耗边权大小的能量。如果树上两点 $u$ ， $v$ 之间深度之差恰好为 $k$ ，则两点之间可以相互到达，从 $u$ 到 $v$ 或从 $v$ 到 $u$ 消耗能量 $p$ ，问从 $s$ 到 $t$ 消耗的最少能量。

分析
建图跑最短路。将每一个深度看作一个结点，并且拆为入点和出点。每个结点向当前深度的入点连一条边权为0的边，每个深度的出点向同层所有结点连一条边权为0的边。两个深度之间如果差值为 $k$ ，则从入点向出点连一条边权为 $p$ 的边。时间复杂度 $O (n l o g (n))$ 。

题解建图方法：

AC代码

typedef long long ll;
const int N=6e6+10;
const int M=2*N;
const ll inf=0x3f3f3f3f3f3f3f3f;
int head[N],e[M],ne[M],w[M],d[N],tot;
bool vis[N];
ll dis[N];
int n,s,t,k,p,mx;void add(int x,int y,int z)
{e[++tot]=y,ne[tot]=head[x],head[x]=tot,w[tot]=z;
}void dfs(int x) //dfs求深度 
{mx=max(d[x],mx);for(int i=head[x];i;i=ne[i]){int y=e[i];if(!d[y]){d[y]=d[x]+1;dfs(y);}}
}void dij()
{for(int i=0;i<=3*n;i++) vis[i]=0;for(int i=0;i<=3*n;i++) dis[i]=inf;dis[s]=0;priority_queue<pair<ll,int>> q;q.push({0,s});while(q.size()>0){int x=q.top().second;q.pop();if(vis[x]) continue;vis[x]=true;for(int i=head[x];i;i=ne[i]){int y=e[i];int z=w[i];if(dis[y]>dis[x]+z){dis[y]=dis[x]+z;q.push({-dis[y],y});}}}
}int main()
{int _;cin>>_;while(_--){cin>>n;for(int i=1;i<=3*n;i++) head[i]=0;tot=0;for(int i=1;i<n;i++){int x,y,z;cin>>x>>y>>z;add(x,y,z);add(y,x,z);}for(int i=1;i<=n;i++) d[i]=0;d[1]=1; mx=0;dfs(1);for(int i=1;i<=n;i++){add(i,n+d[i],0);add(n+mx+d[i],i,0);}cin>>k>>p;cin>>s>>t;for(int i=1;i<=mx;i++) //入点向出点连边{int x;x=i+k;if(x<=mx) add(n+i,n+mx+x,p);x=i-k;if(x>0) add(n+i,n+mx+x,p);}dij();cout<<dis[t]<<endl;}return 0;
}

Count Set（排列组合分治NTT）

题意
给定一个长度为 $n$ 的排列和一个非负整数 $k$ ，计算排列的子集 $T$ 的数量，要求 $∣ T ∣ = k$ 且 $\cap T|=0$ ，其中 $P(T)=\left\{y \mid y=p_{x}, x \in T\right\}$ 。

分析
将 $p_i$ 看做是 $i$ 到 $p_i$ 连的一条边，则排列 $p$ 可以分为若干个环。问题等价于从每个环中选取若干个环上不相临的点，点的总数为 $k$ 的方案数。从一个大小为 $m$ 的环中选取 $k$ 个不相邻的点的方案数是 $\left(\begin{array}{c} m-k \\ k \end{array}\right)+\left(\begin{array}{c} m-k-1 \\ k-1 \end{array}\right)$ 。分类讨论：环上的点从1~m编号，(1)选择1号点，问题转化为长度为 $m - 3$ 的链上不相临问题，方案数为 $C (m - k - 1, k - 1)$ ，（2）不选1号点，整个环从1号点处断开，问题转化为长度为 $m - 1$ 的链上不相临问题，方案数为 $C (m - k, k)$ 。需要注意的是，若环上只有一个点，认为这个点和自身相邻。推出这个式子后可以得到每个环的生成函数，使用分治NTT求指数为 $k$ 的多项式项的系数。

AC代码

#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define MUL(a, b) (ll(a) * (b) % P)
#define ADD(a, b) (((a) += (b)) >= P ? (a) -= P : 0)
typedef long long ll;
const int N=5e5+10;
const int mod=998244353;
const int P=mod;
int a[N],vis[N];
ll fac[N],inv[N];
int n,k,cnt;ll ksm(ll a,ll b)
{ll ans=1;for(;b;b>>=1){if(b&1) ans=ans*a%mod;a=a*a%mod;}return ans;
}using Poly = vector<int>;
vector<Poly> vec;
namespace NTT {const int g = 3;Poly Omega(int L) {int wn = ksm(g, P / L);Poly w(L); w[L >> 1] = 1;rep(i, L / 2 + 1, L - 1) w[i] = MUL(w[i - 1], wn);per(i, L / 2 - 1, 1) w[i] = w[i << 1];return w;}auto W = Omega(1 << 19);void DIF(int *a, int n) {for (int k = n >> 1; k; k >>= 1)for (int i = 0, y; i < n; i += k << 1)for (int j = 0; j < k; ++j)y = a[i + j + k], a[i + j + k] = MUL(a[i + j] - y + P, W[k + j]), ADD(a[i + j], y);}void IDIT(int *a, int n) {for (int k = 1; k < n; k <<= 1)for (int i = 0, x, y; i < n; i += k << 1)for (int j = 0; j < k; ++j)x = a[i + j], y = MUL(a[i + j + k], W[k + j]),a[i + j + k] = x - y < 0 ? x - y + P : x - y, ADD(a[i + j], y);int Inv = P - (P - 1) / n;rep(i, 0, n - 1) a[i] = MUL(a[i], Inv);reverse(a + 1, a + n);}
}namespace Polynomial {void DFT(Poly &a) { NTT::DIF(a.data(), a.size()); }void IDFT(Poly &a) { NTT::IDIT(a.data(), a.size()); }int norm(int n) { return 1 << (__lg(n - 1) + 1); }void norm(Poly &a) { if (!a.empty()) a.resize(norm(a.size()), 0); else a = {0}; }Poly &dot(Poly &a, Poly &b) { rep(i, 0, a.size() - 1) a[i] = MUL(a[i], b[i]); return a; }Poly operator*(Poly a, Poly b){int n = a.size() + b.size() - 1, L = norm(n);if (a.size() <= 100 || b.size() <= 100) {Poly c(n);rep(i, 0, a.size() - 1) rep(j, 0, b.size() - 1)c[i + j] = (c[i + j] + (ll) a[i] * b[j]) % P;return c;}a.resize(L), b.resize(L);DFT(a), DFT(b), dot(a, b), IDFT(a);return a.resize(n), a;}
};
using namespace Polynomial;void init(int n)
{fac[0]=inv[0]=1;for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;inv[n]=ksm(fac[n],mod-2);for(int i=n;i>=1;i--) inv[i-1]=inv[i]*i%mod;
}ll C(int a,int b)
{return fac[a]*inv[b]%mod*inv[a-b]%mod;
}Poly calc(int l,int r)
{int mid=(l+r)>>1;if(l==r) return vec[l];return calc(l,mid)*calc(mid+1,r);
}int main()
{int T;cin>>T;init(500000);while(T--){cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];if(k>n/2){cout<<0<<endl;continue;}for(int i=1;i<=n;i++) vis[i]=0;vec.clear();for(int i=1;i<=n;i++){if(!vis[i]){cnt=0;int x=i;while(!vis[x]){cnt++;vis[x]=1;x=a[x];}Poly poly(cnt/2+1);for(int i=0;i<=cnt/2;i++) poly[i]=(C(cnt-i,i)+C(cnt-i-1,i-1))%mod;vec.push_back(poly);}}Poly ans=calc(0,(int)vec.size()-1);if(ans.size()>k) cout<<ans[k]<<endl;else cout<<0<<endl;}return 0;
}

Bragging Dice（思维）

题意
YahAHa和Peanut在玩骰子游戏，游戏规则如下：
两个玩家各有 $n$ 个筛子，并且都放在各自的杯子中。两位玩家轮流进行，YahAHa先手。在第一轮YahAHa可以宣布“两个杯子中有 $x$ 个筛子的点数是 $y$ 点”。接下来Peanut有两种选择：

挑战YahAHa，此时游戏结束。两位玩家打开各自的杯子，如果恰好有 $\geq 1)$ 个 $\leq y \leq 6)$ 点的筛子，YahAHa胜，否则Peanut胜。
继续宣布“两个杯子中有 $x_1$ 个筛子的点数是 $y_1$ ”，要求 $x_1>x$ ， $\leq y_1 \leq 6$ 或者 $x_1=x$ ， $\geq y$ 。

为了使游戏更有趣，这里有一些特殊规则：

如果没有人宣布“有 $x$ 个1点的筛子”，那么1点可认为是任意点数
如果一个杯子中所有筛子点数相同，就认为杯子中还有一个同点数的筛子
如果一个杯子中筛子的点数各不相同，则认为各个点数的筛子个数为0

如果同时满足多条特殊规则，优先考虑第三条规则。
两个玩家都知道两个杯子中每个筛子的点数。
问在最优策略下YahAHa是否能够获胜。

分析
如果两个杯子中的点数都各不相同，那么所有点数的个数都为0，而规则要求 $\geq 1$ ，在YahAHa宣布之后，Peanut选择结束游戏，Peanut必胜。除了这种情况，YahAHa可以宣布个数不为0的最大点数的个数，YahAHa必胜。

AC代码

const int N=2e5+10;
int a[N],b[N];int main()
{int _;cin>>_;while(_--){int n;cin>>n;set<int> s,t;for(int i=1;i<=n;i++) cin>>a[i],t.insert(a[i]);for(int i=1;i<=n;i++) cin>>b[i],s.insert(b[i]);if(s.size()==n&&t.size()==n) cout<<"Just a game of chance."<<endl;else cout<<"Win!"<<endl;}return 0;
}

Buy Figurines（优先队列线段树二分）

题意
有 $n$ 个人打算去买雕像，有 $m$ 个窗口，每个窗口可以看作是一个队列。第 $i$ 个人的到达时间是 $a_i$ 且花费 $s_i$ 的时间购买雕像。每个人到达的时候优先选择人数少的队列，如果多个队列人数最少，则优先选择编号小的队列。如果同一时间点有人离开有人到达，来的人会在要离开的人离开后做出选择。输出最后一个离开的人离开的时间。

分析
用优先队列维护每个队列的结束时间，用线段树维护每个队列的人数。在第 $i$ 个人到达时，更新结束时间 $\leq a_i$ 的队列，每个人最多入队一次，出队一次。更新队列的结束时间和人数后，通过线段树二分查找人数最少且编号最小的队列。时间复杂度 $O (n l o g (n))$ 。

题解的做法也是类似的，不同的是用set维护。

AC代码

typedef long long ll;
const int N=2e5+10;
int tr[N<<2];
int cnt[N]; //每个队列的人数 
ll tim[N]; //每个队列的结束时间 
struct node {ll x,s;bool operator<(const node &a) {return x<a.x;}
}p[N];void build(int p,int l,int r)
{if(l==r){tr[p]=0;return ;}int mid=(l+r)>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);tr[p]=min(tr[p<<1],tr[p<<1|1]);
}void change(int p,int l,int r,int x)
{if(l==r){tr[p]=cnt[l];return ;}int mid=(l+r)>>1;if(x<=mid) change(p<<1,l,mid,x);else change(p<<1|1,mid+1,r,x);tr[p]=min(tr[p<<1],tr[p<<1|1]);
}int query(int p,int l,int r,int x,int y,int mn) //线段树二分
{if(l==r) return l;int mid=(l+r)>>1;if(tr[p<<1]==mn) return query(p<<1,l,mid,x,y,mn);else return query(p<<1|1,mid+1,r,x,y,mn);
}int main()
{int _;cin>>_;while(_--){int n,m;cin>>n>>m;for(int i=1;i<=m;i++) cnt[i]=0,tim[i]=0;build(1,1,m);priority_queue<pair<ll,int>> q;for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].s;sort(p+1,p+n+1); //按到达时间排序 for(int i=1;i<=n;i++){ll x=p[i].x,s=p[i].s;while(q.size()>0){ll z=-q.top().first;int y=q.top().second;if(z<=x){cnt[y]--;change(1,1,m,y);q.pop();}else break;}int mn=tr[1]; //队列最少人数 int t=query(1,1,m,1,m,mn); //选择第t个队列 cnt[t]++;change(1,1,m,t);tim[t]=max(tim[t],x)+s;q.push({-tim[t],t});}ll ans=0;for(int i=1;i<=m;i++) ans=max(ans,tim[i]);cout<<ans<<endl;}return 0;
}