• 2022杭电多校第五场题解

    2022杭电多校第五场

    在这里插入图片描述

    Slipper（最短路）

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93

    Count Set（排列组合 分治NTT）

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

    分析
    将 p i p_i pi​看做是 i i i到 p i p_i pi​连的一条边，则排列 p p p可以分为若干个环。问题等价于从每个环中选取若干个环上不相临的点，点的总数为 k k k的方案数。从一个大小为 m m m的环中选取 k k k个不相邻的点的方案数是 ( m − k k ) + ( m − k − 1 k − 1 ) \left(

    m−kk" role="presentation" style="position: relative;">m−kk
    \right)+\left(
    m−k−1k−1" role="presentation" style="position: relative;">m−k−1k−1
    \right) (m−kk​)+(m−k−1k−1​)。分类讨论：环上的点从1~m编号，(1)选择1号点，问题转化为长度为 m − 3 m-3 m−3的链上不相临问题，方案数为 C ( m − k − 1 , k − 1 ) C(m-k-1,k-1) C(m−k−1,k−1)，（2）不选1号点，整个环从1号点处断开，问题转化为长度为 m − 1 m-1 m−1的链上不相临问题，方案数为 C ( m − k , k ) C(m-k,k) C(m−k,k)。需要注意的是，若环上只有一个点，认为这个点和自身相邻。推出这个式子后可以得到每个环的生成函数，使用分治NTT求指数为 k k 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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134

    Bragging Dice（思维）

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

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

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

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

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

    分析
    如果两个杯子中的点数都各不相同，那么所有点数的个数都为0，而规则要求 x ≥ 1 x \geq 1 x≥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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

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

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

    分析
    用优先队列维护每个队列的结束时间，用线段树维护每个队列的人数。在第 i i i个人到达时，更新结束时间 ≤ a i \leq a_i ≤ai​的队列，每个人最多入队一次，出队一次。更新队列的结束时间和人数后，通过线段树二分查找人数最少且编号最小的队列。时间复杂度 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
  • 相关阅读:
    BUUCTF Reverse/[GXYCTF2019]simple CPP
    leetcode 20. 有效的括号
    Redis基础详解
    ABAP学习笔记之——第五章：内表
    干货丨产品的可行性分析要从哪几个方面入手？
    Zigbee—网络层地址分配机制
    『NLP学习笔记』TextCNN文本分类原理及Pytorch实现
    微信小程序开发04 性能优化：借助微信开发者工具提升小程序性能
    领域驱动设计代码模型
    《现代命令行工具指南》8. 备忘清单：让常用命令能够信手拈来 - navi
  • 原文地址：https://blog.csdn.net/weixin_46155777/article/details/126538837