当前位置：网站首页>2022杭电多校联赛第五场题解

2022杭电多校联赛第五场题解

2022-08-04 03:08:00 【Frank_Star】

签到题

1010题 Bragging Dice / “吹牛骰子”

题目大意
两个人玩明牌的 “吹牛骰子” 游戏，求先手和后手谁赢。
一个人投出的点数全部不同时，视为没有点数。

考察内容
博弈论

分析
双方都投出全部不同的点数时，全场都没有点数，先手必败，否则先手必胜。

#include<bits/stdc++.h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=2e5+10;
ll n,a[N],b[N];

int main(){
     
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
    
		cin>>n;
		for(int i=1;i<=n;i++){
    
			cin>>a[i];
		}
		for(int i=1;i<=n;i++){
    
			cin>>b[i];
		}
		
		int num[10]={
    0};
		int same=0; // 记录有点数的人 
		
		for(int i=1;i<=n;i++){
    
			num[a[i]]++;
			if(num[a[i]]>=2){
    
				same++;
				break; 
			}
		}
		
		memset(num,0,sizeof num);
		for(int i=1;i<=n;i++){
    
			num[b[i]]++;
			if(num[b[i]]>=2){
    
				same++;
				break; 
			}
		}
		 
		if(same>=1)cout<<"Win!"<<endl; // 至少有1个人有点数 
		else cout<<"Just a game of chance."<<endl;
	}
	return 0;
}
/* 1 5 1 2 3 4 5 1 2 3 4 4 */

基本题

1012题 Buy Figurines / 买手办

题目大意
若干个人排队买手办，每个人选择当前队伍人数最少的排队。
求最后一个人买完的时间。

考察内容
模拟，复杂度优化

分析
解法不唯一。

直接按照题意，模拟每个人排队即可。
有空队伍时，直接排进去。没有空队伍时，更新所有队伍当前的人数，然后排进人数最少的队伍。

#include<bits/stdc++.h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
int read(int &n){
    
	char ch=' '; int q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
} 
ll read(ll &n){
    
	char ch=' '; ll q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
}
const int N=2e5+10;
ll n,m;

struct node{
    
	ll start,last;
}a[N];

bool cmp(node x,node y){
    
	return x.start<y.start;
}

vector<ll> v[N]; 
int p[N]; 
 
ll t[N]; // 队伍最后的时间 
ll num[N]; // 队伍人数 

int main(){
     
	int t0; read(t0);
	while(t0--){
    
		read(n); read(m);
		for(int i=1;i<=n;i++){
    
			read(a[i].start);
			read(a[i].last);
		}
		sort(a+1,a+n+1,cmp); // 按照开始时间排序 
		
		memset(t,0,sizeof(t[0])*(n+1));
		memset(num,0,sizeof(num[0])*(m+1));
		memset(p,0,sizeof(p[0])*(m+1));
		for(int i=0;i<=m;i++)v[i].clear();
		
		for(int i=1;i<=n;i++){
     // 枚举每一个人 
			int F=0;
			for(int j=1;j<=m;j++){
     // 枚举每一个队伍 
				if(a[i].start>=t[j]){
     // 可以直接排进去 
					F=1;
					t[j]=a[i].start+a[i].last;
					v[j].push_back(t[j]);
					num[j]++; 
					break;
				}	
			} 
			if(F){
      
				continue;
			}
			
			// 找不到没有人的队伍时 
			for(int j=1;j<=m;j++){
     // 枚举每一个队伍，更新num[j] 
				int len=v[j].size();
				for(int k=p[j];k<len;k++){
    
					if(v[j][k]<=a[i].start){
    
						p[j]++;
						num[j]--;
					}
					else{
    
						break;
					}
				} 
			}
			
			ll minnum=1e18; // 找最少队伍的人数 
			for(int j=1;j<=m;j++){
    
				minnum=min(minnum,num[j]);
			}
			for(int j=1;j<=m;j++){
    
				if(num[j]==minnum){
     // 人数最少 
					t[j]+=a[i].last;
					v[j].push_back(t[j]);
					num[j]++; 
					break; 
				}	
			} 
		}
		
		ll ans=0;
		for(int i=1;i<=m;i++){
    
			ans=max(ans,t[i]);
		}
		
		cout<<ans<<endl;
	}
	return 0;
}

1003题 Slipper / 拖鞋

题目大意
给定一棵树和树上边权，每次可以走树上的边，也可以花费 $p$ 的代价向上或向下跳 $k$ 层。求点 $s$ 到点 $t$ 的最短路。

考察内容
树形dp，dfs，最短路

分析
赛时先写了一个dijkstra然后tle了，于是写了个树形dp。

每个点和每一层设一个状态，然后从终点开始dfs转移一下即可。

状态：
$f [i]$ 表示第 $i$ 个结点到终点的最短距离。
$f 2 [i]$ 表示第 $i$ 层中"最好"的点到终点的最短距离。

转移：
对于每个结点，枚举所有出边和向上向下跳的情况，更新答案。

这种方法不添加额外的边，转移时每个结点至多枚举一次，复杂度 $O (n)$

#pragma GCC optimize(3) // O3优化 
#include<bits/stdc++.h> 
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
int read(int &n){
    
	char ch=' '; int q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
} 
ll read(ll &n){
    
	char ch=' '; ll q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
}
const int N=1e6+5;
const int M=1e6+5; 

int head[N];
int ver[M],edge[M],nxt[M];
bool vis[N];

ll n,tot;
ll k,p,s,t;

ll u[N],v[N],w[N];
ll deep[N];
vector<ll> g[N];

ll f[N]; // f[i]表示第i个结点到终点的最短距离 
ll f2[N]; // f2[i]表示第i层中"最好"的点到终点的最短距离 
ll maxd=0;

void add(int x,int y,int z){
    
	ver[++tot]=y;
	edge[tot]=z; // 记录边权 
	nxt[tot]=head[x];
	head[x]=tot;
}

void dfs(int v,int fa,int d1){
     // 标记结点深度 
	deep[v]=d1;
	for(auto a1:g[v]){
    
		if(a1==fa)continue;
		
		dfs(a1,v,d1+1);
	}
}

void dfs2(int v){
    
	if(vis[v])return;
	
	vis[v]=1;
	int x=v;
	for(int i=head[x];i>0;i=nxt[i]){
     // 枚举出边 
		int y=ver[i];
		int z=edge[i]; // z保存边权 
		if(abs(deep[x]-deep[y])==k){
     // 可以跳 
			z=min((ll)z,p); // 更新z 
		}
		
		if(f[y]>f[x]+z){
     
			f[y]=f[x]+z; // 转移 
		}			
		if(deep[y]+k<=maxd){
    
			f[y]=min(f[y],f2[deep[y]+k]+p); // 转移 
			f2[deep[y]]=min(f2[deep[y]],f[y]);
		}
		if(deep[y]-k>=1){
    
			f[y]=min(f[y],f2[deep[y]-k]+p); // 转移 
			f2[deep[y]]=min(f2[deep[y]],f[y]);
		}
		
		dfs2(y); 
	}
}

struct node{
    
	ll deep,id;
}n1[N];

bool cmp(node nx,node ny){
    
	return nx.deep<ny.deep;
}

void init(ll n){
     // 初始化 
	memset(head,0,sizeof(head[0])*(n+1));
	memset(vis,0,sizeof(vis[0])*(n+1));
	memset(deep,0,sizeof(deep[0])*(n+1));
	
	memset(ver,0,sizeof ver);
	memset(edge,0,sizeof edge);
	memset(nxt,0,sizeof nxt);
	tot=0; 
	
	for(int i=0;i<=n;i++){
    
		g[i].clear();
	}
}

int main(){
     // 树形dp 
	int t0; read(t0);
	while(t0--){
    
		read(n);
		for(int i=1;i<=n-1;i++){
    
			read(u[i]);
			read(v[i]);
			read(w[i]);
		}
		read(k); read(p); // 可以花费p跳过深度差距为k的结点 
		read(s); read(t);
		
		init(n); // 初始化 
		
		for(int i=1;i<=n-1;i++){
    			
			add(u[i],v[i],w[i]);
			add(v[i],u[i],w[i]);
			
			g[u[i]].push_back(v[i]);
			g[v[i]].push_back(u[i]);
		}
		dfs(1,0,1); // 从根结点开始，标记每个结点的深度 
		
		for(int i=0;i<=n;i++){
    
			f[i]=f2[i]=1e18;
		}
		f[t]=0; // 终点到自己距离0 
		
		maxd=deep[1]; // 保存最大深度 
		for(int i=2;i<=n;i++){
    
			maxd=max(maxd,deep[i]); 
		}
		f2[deep[t]]=0; 
	
		// 转移和终点直接连接的点 
		int x=t;
		for(int i=head[x];i>0;i=nxt[i]){
    
			int y=ver[i];
			int z=edge[i]; // z保存边权 
			
			if(f[y]>f[x]+z){
    
				f[y]=f[x]+z;
				f2[deep[y]]=min(f2[deep[y]],f[y]);
			}
		}
		
		for(int i=max(k,t+1);i<=maxd;i++){
    
			f2[i]=min(f2[i],f2[i-k]+p); // 更新f2[] 
		}
		for(int i=t-1;i>=1;i--){
    
			f2[i]=min(f2[i],f2[i+k]+p); // 更新f2[] 
		}
	
		dfs2(t); // 转移 
		
		cout<<f[s]<<endl; // 答案为起点到终点的最短距离 
	}
	return 0;
}
/* 1 11 1 2 10 2 3 10 1 4 10 4 5 10 1 6 10 6 7 10 1 8 10 8 9 10 1 10 10 10 11 10 1 2 3 11 */

进阶题

1007题 Count Set / 数集合

题目大意
从一个 $1$ 到 $n$ 的排列中选 $k$ 个数字，要求每个选出的数字和所有选中的下标都不同。

求选择的方案数。

考察内容
生成函数，NTT，数学知识，Pólya定理

分析

1007分析

#include<bits/stdc++.h>
#define fr(i,l) for(S i=0;i<l;i++)
#define S int
#define U unsigned
#define UL U long long
#define LL long long
constexpr U mod=998244353u;
constexpr U g=3u;
constexpr U gi=332748118u;
using std::max;
using std::min;
using std::swap;
U pow(U a,U b)
{
    
    U ans=1;
    while(b)
    {
    
        if(b&1)ans=(UL)ans*a%mod;
        a=(UL)a*a%mod;
        b>>=1;
    }
    return ans;
}
U mo(U x){
    return x>=mod?x-mod:x;}
U& mul(U&a,U b){
    return a=(UL)a*b%mod;}
void mov(U*a,const U*b,S len){
    memmove(a,b,len*sizeof(U));}

namespace Poly
{
    
    constexpr S ml=1<<19,mn=80;
    U mem[(ml+16)*mn],*stk[mn],top=mn,f[(ml+16)*2],wr[ml+16],wi[ml+16],ninv[ml+16];
    U*m(){
    return stk[--top];}void m(U*p){
    stk[top++]=p;}
    S up(S x){
    S l=1;while(l<x)l<<=1;return l;}
    void init()
    {
    
        fr(i,mn)stk[i]=mem+i*(ml+16);
        U*fp;
        for(S len=1;fp=f+len,len<=ml;len<<=1)
            fr(i,len)fp[i]=(fp[i>>1]>>1)|(i&1?len>>1:0);
        for(S len=1;len<ml;len<<=1)
        {
    
            U Wr=pow(g,(mod-1)/(len<<1));
            U Wi=pow(gi,(mod-1)/(len<<1));
            U tr=1,ti=1;
            fr(i,len)
            {
    
                wr[len+i]=tr;mul(tr,Wr);
                wi[len+i]=ti;mul(ti,Wi);
            }
        }
    }
#define lst(n,a,x) poly&n(a){
      x return*this;}
struct poly{
    
    U*mem,*a;
    S len;
    poly(S len):len(len){
    a=mem=m();cls(0,len);}
    poly():poly(1){
    }
    poly(U x):poly(){
    a[0]=x;}
    poly(U*l,S len):len(len){
    a=mem=m();mov(a,l,len);}
    poly(const poly&b):poly(b.a,b.len){
    }
    ~poly(){
    if(mem)m(mem);}
    lst(operator=,const poly&b,if(mem)rsz(b.len);mov(a,b.a,b.len);)
    U& operator[](S idx){
    return a[idx];}
    poly& cls(S l,S len){
    memset(a+l,0,len*4);return *this;}
    lst(rsz,S nlen,if(nlen>len)cls(len,nlen-len);len=nlen;)
    template<U*wp=wr>
    lst(NTT,S len=-1,static UL a[ml+16];
        if(~len)rsz(len);else len=this->len;
        fr(i,len)a[i]=this->a[f[len+i]];
        for(S i=1;i<len;i<<=1)
        {
    
            U*w=wp+i;
            for(S j=0;j<len;j+=i<<1)
            fr(k,i)
            {
    
                UL x=a[j+k];
                UL y=a[i+j+k]*w[k]%mod;
                a[j+k]=x+y;
                a[i+j+k]=x-y+mod;
            }
        }
        fr(i,len)this->a[i]=a[i]%mod;
    )
    lst(NTTi,S len=-1,NTT<wi>(len);*this*=pow(this->len,mod-2);)
    poly operator+(const poly&b){
    return poly(*this)+=b;}
    poly operator-(const poly&b){
    return poly(*this)-=b;}
    poly operator*(const poly&b){
    return poly(*this)*=b;}
    poly operator*(U x){
    return poly(*this)*=x;}
    lst(operator+=,const poly&b,rsz(max(len,b.len));fr(i,b.len)a[i]=mo(a[i]+b.a[i]);)
    lst(operator-=,const poly&b,rsz(max(len,b.len));fr(i,b.len)a[i]=mo(a[i]-b.a[i]+mod);)
    lst(operator*=,poly b,S l=up(len+b.len-1);NTT(l).vmul(b.NTT(l)).NTTi();)
    lst(operator*=,U x,fr(i,len)mul(a[i],x);)
    lst(vmul,const poly&b,fr(i,len)mul(a[i],b.a[i]);)
    lst(print,,fr(i,len)printf("%u ",a[i]);puts("");)
};
};
using Poly::poly;

U fact[500001];
U ifact[500001];

U C(int n,int m){
    
    if(m<0||m>n)return 0;
    return (UL)fact[n]*ifact[m]%mod*ifact[n-m]%mod;
}
int p[500000];
int vis[500000];
int sz[500000],num;

poly calc(int l,int r){
    
    if(l==r){
    
        poly t(sz[l]/2+1);
        t[0]=1;
        for(S i=1;i<t.len;i++)
            t[i]=mo(C(sz[l]-i-1,i-1)+C(sz[l]-i,i));
        return t;
    }
    else{
    
        int mid=l+r>>1;
        poly a=calc(l,mid);
        poly b=calc(mid+1,r);
        int len=a.len+b.len-1;
        return (a*=b).rsz(len);
    }
}


void sol(){
    
    int n,k;
    scanf("%d%d",&n,&k);
    fr(i,n)scanf("%d",p+i),p[i]--;
    memset(vis,0,4*n);
    num=0;
    fr(i,n){
    
        if(!vis[i]){
    
            vis[i]=1;
            sz[num]=1;
            int t=p[i];
            while(!vis[t]){
    
                vis[t]=1;
                sz[num]++;
                t=p[t];
            }
            if(sz[num]>1)num++;
        }
    }
    poly a=calc(0,num-1);
    
    if(k>=a.len){
    
    	printf("0\n");
    }
    else{
    
    	printf("%u\n",a[k]);
    }
}

int main(){
    
    Poly::init();
    
	// 预处理阶乘 
    fact[0]=1;
    for(S i=1;i<=500000;i++)
        fact[i]=(UL)fact[i-1]*i%mod; 
        
    ifact[500000]=pow(fact[500000],mod-2);
    for(S i=500000;i;i--)
        ifact[i-1]=(UL)ifact[i]*i%mod;
        
    int T;
    scanf("%d",&T);
    while(T--)sol();
}