【学习笔记】AGC018

AGC018

Tree and Hamilton Path

理论上界是${\sum }_{(u,v)}2\min (s_v,n-s_v)w_i$，这对于哈密顿回路是可以取到的（只需取原树重心，注意最后要回到根节点）。

比较容易想到枚举终点$v$（假设重心是$u$），然后只需断掉一条边。应该是正确的吧（确信

#include
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
int n,rt,f=0x3f3f3f3f,siz[100005];
ll L;
vector<pair<int,int>>g[100005];
void dfs(int u,int topf){
	siz[u]=1;int z=0;
	for(auto v:g[u]){
		if(v.fi!=topf){
			dfs(v.fi,u),siz[u]+=siz[v.fi],z=max(z,siz[v.fi]);
			L+=2ll*min(siz[v.fi],n-siz[v.fi])*v.se;
		}
	}if(max(z,n-siz[u])<f)f=max(z,n-siz[u]),rt=u;
}
void dfs2(int u,int topf){
	siz[u]=1;
	for(auto v:g[u]){
		if(v.fi!=topf){
			dfs2(v.fi,u),siz[u]+=siz[v.fi];
		}
	}
}
int main(){
	cin>>n;for(int i=1;i<n;i++){
		int u,v,w;cin>>u>>v>>w,g[u].pb(make_pair(v,w)),g[v].pb(make_pair(u,w));
	}
	dfs(1,0),dfs2(rt,0);int z=0x3f3f3f3f,son=0;
	for(auto v:g[rt])if(!son||siz[v.fi]>siz[son])son=v.fi;
	for(auto v:g[rt]){
		if(v.fi==son||siz[son]<=(n-1)/2)z=min(z,v.se);
	}cout<<L-z;
}
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

AGC014

Black and White Tree

应该可以看出就是求一个匹配。如果存在匹配（$n$是偶数）那么显然后手必胜，否则先手一直选比叶子浅的那个节点即可。

#include
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
int n,dp[100005];
vector<int>g[100005];
void dfs(int u,int topf){
	dp[u]=1;
	for(auto v:g[u]){
		if(v!=topf){
			dfs(v,u);
			if(dp[v]){
				if(!dp[u]){
					cout<<"First";
					exit(0);
				}dp[u]=0;
			}
		}
	}
}
int main(){
	cin>>n;if(n&1){
		cout<<"First";
		return 0;
	}
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		g[u].pb(v),g[v].pb(u);
	}dfs(1,0);cout<<"Second";
}
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

AGC028

Removing Blocks

答案是${\sum }_i{\sum }_j\frac{n!}{|i-j|+1}{a}_j$。固定$|i-j|$然后预处理$a_i$前缀和即可。

#include
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
const int mod=1e9+7;
int n;
ll res,fac[100005],a[100005],s[100005];
ll fpow(ll x,ll y){
	ll z(1);
	for(;y;y>>=1){
		if(y&1)z=z*x%mod;
		x=x*x%mod;
	}return z;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;for(int i=1;i<=n;i++)cin>>a[i],s[i]=(s[i-1]+a[i])%mod;fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
	for(int i=1;i<=n;i++){
		if(i!=1)res+=fac[n]*fpow(i,mod-2)%mod*(s[n]-s[i-1]+s[n-i+1])%mod;
		else res+=fac[n]*s[n]%mod; 
		res%=mod;
	}cout<<(res+mod)%mod;
}
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

Min Cost Cycle

长的很像结论题。

问题可以转化为，对于每条边$(u,v)$，选取$a_u,b_v$中的任意值加入答案，这样不必考虑它们的大小关系。

这可以形象表示为二分图的完美匹配，其中有$n$个点产生贡献，每条边恰好对应一个产生贡献的点。

我们观察到，如果不存在$a_i,b_i$同时产生贡献，那么这张图就会分裂成两条哈密顿回路而不合法。否则一定合法，证明将$i$作为回路起点遍历二分图，过程中不经过重复的点即可。

因此合法的答案为：

$1.1$ 只包含 { a i } , { b i } \{a_i\},\{b_i\} {ai​},{bi​}
$1.2$ 至少存在一个$i$，使得$a_i$,$b_i$都对答案产生贡献。

#include
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
int n,a[200005],b[200005],vis[200005];
ll res,s1,s2;
vector<pair<int,int>>v;
int main(){
	cin>>n;for(int i=1;i<=n;i++)cin>>a[i]>>b[i],v.pb(make_pair(a[i],i)),v.pb(make_pair(b[i],i+n)),s1+=a[i],s2+=b[i];
	sort(v.begin(),v.end());
	for(int i=0;i<n;i++)res+=v[i].fi,vis[v[i].se]=1;
	for(int i=1;i<=n;i++){
		if(vis[i]&&vis[i+n]){
			cout<<min({res,s1,s2});
			return 0;
		}
	}
	ll res2=0x3f3f3f3f3f3f3f3f;
	for(int i=1;i<=n;i++){
		if(vis[i]){
			if(i!=v[n-1].se)res2=min(res2,res+b[i]-v[n-1].fi);
			else res2=min(res2,res+b[i]-v[n-2].fi);
		}
		else {
			if(i+n!=v[n-1].se)res2=min(res2,res+a[i]-v[n-1].fi);
			else res2=min(res2,res+a[i]-v[n-2].fi);
		}
	}
	cout<<min({res2,s1,s2});
}
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

Chords

不太会做。

AGC013

Ants on a Circle

如果不考虑掉头，那么蚂蚁位置组成的集合是可以确定的。并且顺时针方向蚂蚁的相对位置不会改变。

假设圆足够大，而所有蚂蚁都集中在下部，那么$1$的位置就是最终坐标最小的位置。

假设某一时刻一个蚂蚁穿过了$L$（相当于坐标减成了$0$），那么变成了 { n , 1 , 2 , . . . , n − 1 } \{n,1,2,...,n-1\} {n,1,2,...,n−1}，因此只需计算环上被顺时针逆时针穿过的次数即可。

比较抽象

#include
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
int n;
ll L,T;
ll res;
vector<int>v;
int main(){
	cin>>n>>L>>T;
	for(int i=0;i<n;i++){
		ll X,w;cin>>X>>w;
		if(w==1){
			v.pb((X+T)%L);
			res+=(X+T)/L;
		}
		else{
			v.pb(((X-T)%L+L)%L);
			res-=(L-X+T-1)/L;
		}
	}
	sort(v.begin(),v.end());
	res=(res%n+n)%n;
	for(int i=res;i<n;i++)cout<<v[i]<<"\n";
	for(int i=0;i<res;i++)cout<<v[i]<<"\n";
}
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

AGC016

Games on DAG

很明显是状压的题目。

设$d{p}_{i,S}$表示当前$SG$值考虑到$i$，点集为$S$的方案数。如果一个点不在$S$中，那么隐含它的$SG$值比$i$大，因此对于$j\notin S$，记有$nu{m}_j$条边指向$SG$为$i$的点，那么$d{p}_{i,S}\leftarrow d{p}_{i,S}\times {\prod }_{j\notin S}(2^{nu{m}_j}-1)$。

最后统计$SG(1)\ne SG(2)$的方案数即可。复杂度$O(n^3{3}^n)$。

#include
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
const int mod=1e9+7;
int n,m,dp[1<<15],a[15][15];
struct node{
	int u,v;
}e[1005];
void add(int &x,int y){
	if((x+=y)>=mod)x-=mod;
}
ll fpow(ll x,ll y){
	ll z(1);
	for(;y;y>>=1){
		if(y&1)z=z*x%mod;
		x=x*x%mod;
	}return z;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v,u--,v--,a[u][v]=1;
	}dp[0]=1;int res=0;
	for(int i=0;i<n;i++){
		for(int s=(1<<n)-1;s>=0;s--){
			if(dp[s]){
				for(int s2=(1<<n)-1-s;s2;s2=(s2-1)&((1<<n)-1-s)){
					if((s2&1)&&(s2&2))continue;
					ll v=dp[s];for(int j=0;j<n;j++){
						if(!(s>>j&1)&&!(s2>>j&1)){
							int num=0,num2=0;
							for(int k=0;k<n;k++){
								if(a[j][k]&&(s2>>k&1))num++;
								if(a[k][j]&&(s2>>k&1))num2++;
							}v=v*(fpow(2,num)-1)%mod*fpow(2,num2)%mod;
						}
					}add(dp[s+s2],v); 
				}dp[s]=0;
			}
		}
		add(res,dp[(1<<n)-1]);
	}cout<<(res+mod)%mod;
}
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

AGC017

Game on Tree

博弈论题目。

记$SG(u)$表示以$u$为根的子树对应的$SG$函数值。如果$u$是叶子那么$SG(u)=0$。

我们不妨将$u$的博弈问题视为所有子节点的问题的组合，也就是说，我们将与$u$相连的边以及$v$的子树视为整体，$SG(u)$就等于其异或和。

进一步分析，如果我们不看与$u$相连的那条边，那么其对应的就是$SG(v)$。考虑这条边的意义是，随时可以把整棵子树删掉，因此随时可以转化为$SG(v^{\prime })\to 0$，所以每个状态的$SG$值都要加$1$，故而$SG(u)={\oplus }_{v\in son(u)}(SG(v)+1)$。

#include
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
int n,dp[100005];
vector<int>g[100005];
void dfs(int u,int topf){
	for(auto v:g[u]){
		if(v!=topf)dfs(v,u),dp[u]^=dp[v]+1;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;for(int i=1;i<n;i++){
		int u,v;cin>>u>>v,g[u].pb(v),g[v].pb(u);
	}dfs(1,0);
	if(dp[1])cout<<"Alice";
	else cout<<"Bob";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

AGC009

Uninity

直接建点分树好像是最优的。

题目可以等价于，对每个点标一个 $\text{lebal}$ 记作$f_i$，满足对于任意标号相同的点 $u$,$v$，其路径上存在一个点$w$，满足$f_w>f_u$ 。要求$\max f_i$的最小值。

道理很简单，因为点分树可以看成一个类似$BFS$树的结构。

然后回到原树上。任选一点作$DFS$，确定$f(u)$的步骤为，首先确定子树的$f$值，然后对于无遮挡的标号$k$，如果两颗子树有，那么$f(u)\ge k$，如果一颗子树有，那么$f(u)\ne k$。

可以感性认识到其贪心得到的点分树是合法的，并且保证了$f(u)$最小。

#include
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
int n,ban[100005],lab[100005],res;
vector<int>g[100005];
void dfs(int u,int topf){
	int s=0;
	for(auto v:g[u]){
		if(v!=topf){
			dfs(v,u);
			s|=ban[u]&ban[v];
			ban[u]|=ban[v];
		}
	}int k=0;while((1<<k)<=s||ban[u]>>k&1){
		if(ban[u]>>k&1)ban[u]-=1<<k;
		k++;
	}lab[u]=k,ban[u]|=1<<k;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;for(int i=1;i<n;i++){
		int u,v;cin>>u>>v,g[u].pb(v),g[v].pb(u);
	}dfs(1,0);
	for(int i=1;i<=n;i++)res=max(res,lab[i]);
	cout<<res;
}
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

AGC024

Sequence Growing Hard

我爱计数题。

事实上限制可以转述为，设当前删的数的连续块是$x$，连续块后继是$y$，那么$x>y$。

如果给定$A_n$求 { A 0 , A 1 , . . . , A n − 1 } \{A_0,A_1,...,A_{n-1}\} {A0​,A1​,...,An−1​}的方案数，那么等价于删数的方案数，把每个连续段抽象为$(val,x)$，那么能将第$i$段的最右边的数删去的条件是$va{l}_i>va{l}_{i+1}$。

设$d{p}_{i,j}$表示第$i$个序列，只用了$[1,j]$的整数，每次删一个数，满足$va{l}_i>va{l}_{i+1}$的方案数。类似于笛卡尔树的思想，我们枚举第一个$1$的位置$k$，以及第$l$个被删除，那么左边相当于$d{p}_{k-1,j-1}$（不能出现$1$），右边相当于$d{p}_{i-k,j}$，并且只有当右边全部删完后才能删$k$，所以乘上组合数$\left(\genfrac{}{}{0ex}{}{l-1}{i-k}\right)$。

所以$d{p}_{i,j}={\sum }_{k=1}^i{\sum }_{l=1}^{i}d{p}_{k-1,j-1}\times d{p}_{i-k,j}\times \left(\genfrac{}{}{0ex}{}{l-1}{i-k}\right)$。预处理组合数，复杂度$O(n^3)$。

$\text{remark}$ 这个状态和转移确实比较抽象，反正我肯定想不出来。 感性理解一下吧。

#include
#define fi first
#define se second
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
int n,K,mod,c[305][305];
ll dp[305][305];
void init(int n){
	for(int i=0;i<=n;i++)c[i][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
		}
	}
}
int main(){
	cin>>n>>K>>mod,init(300);
	for(int i=0;i<=K;i++)dp[0][i]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=K;j++){
			dp[i][j]=dp[i][j-1];
			for(int k=1;k<=i;k++){
				dp[i][j]=(dp[i][j]+dp[k-1][j-1]*dp[i-k][j]%mod*c[i][i-k+1]%mod)%mod;
			}
		}
	}cout<<dp[n][K];
}
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