比赛传送门
作者： fn

---

签到题

1010题 Bragging Dice / “吹牛骰子”

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

考察内容
博弈论

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

#include
#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

*/ 
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

基本题

1012题 Buy Figurines / 买手办

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

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

分析
解法不唯一。

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

#include
#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;
}
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

---

1003题 Slipper / 拖鞋

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

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

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

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

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

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

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

#pragma GCC optimize(3) // O3优化 
#include 
#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

*/ 
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181

---

进阶题

1007题 Count Set / 数集合

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

求选择的方案数。

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

分析

#include
#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();
}
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172

---