Codeforces Round 872 (Div. 2) 题解
A. LuoTianyi and the Palindrome String
略
B. LuoTianyi and the Table
略
C. LuoTianyi and the Show
略
D1. LuoTianyi and the Floating Islands (Easy Version)
题意
在树上随机撒\(k(k \leq 3)\)个关键点,规定一个点是好的当且仅当这个点到所有关键点的距离之和是所有的点之中最小的,问期望的好点个数。
题解
这个\(k = 3\)实际上是比较优启发性的,分类讨论一下。
k = 1
发现好的点只有那个关键点,故为\(1\)
k = 2
好的点只会是关键点之间的路径上的点,问题等价于算出树上两两点对之间的路径和。
场上写了一个十分蠢且不好扩展的丢人写法,放出来给大家看看
void Dfs(int x)
{
vis[x] = 1 ;
ans += f[x]*(f[x]+1)%MOD*inv(2)%MOD+MOD-1,ans %= MOD ;
for(auto v:e[x]) if(!vis[v]) f[v] = f[x]+1,Dfs(v) ;
}
void S(int x,int fa)
{
int tot = 0,al = 0 ; vis[x] = ss[x] = 1 ; g[x] = f[x] ; int ed = 0 ;
for(auto v:e[x]) if(!vis[v])
{
++tot ; S(v,x) ; ed = v ;
ss[x] += ss[v],g[x] += g[v],g[x] %= MOD,al += g[v]-ss[v]*f[x]%MOD+MOD,al %= MOD ;
}
if(tot < 2) return ; tot = 0 ; int rp = ss[x]-1 ;
for(auto v:e[x]) if(v != fa)
{
if(v == ed) continue ;
al -= g[v]-ss[v]*f[x]%MOD,al += MOD,al %= MOD ; rp -= ss[v]; // print(rp) ;
ans += rp*(g[v]-ss[v]*f[x]+ss[v]%MOD+MOD)%MOD,ans %= MOD ;
ans += ss[v]*al%MOD,ans %= MOD ;
} //enter ;
}
大概就是先算完竖着的路径和,然后再算横着的路径和。
接下来给出一种好写且易扩展的思路。
考虑每一条边会被计算多少次,答案很显然是\((n-sz_x)(sz-x)\)，子树外和子树内有关键点时这条边就会被用上,两两配对的次数就是这条边会用上的次数。
k = 3
画一下图,会发现实际上就只有两种形态,一条链和┴形状。
链的形状显然只能是中间的那一个关键点，┴形状答案也只能是中间的那一个点,所以答案为\(1\)。
D2. LuoTianyi and the Floating Islands (Hard Version)
题意
同上,\((k \leq 2\times10^5)\)
题解
这时候分一条一条的路径就不好做了,还是从考虑边入手。
假设某一种情况我们先从一个好的点\(x\),走向和它相邻的点\(y\),对于距离的改变为\(k-sz(y)-sz(y)\),\(sz_y\)是\(y\)子树内的关键点个数。
显然只有当\(k=2\times sz(y)\)时,对于\(x,y\)的假设才都合理。
对于\(k\)为奇数的时候显然不成立,不会有任何的边会计算,答案为\(1\)。
对于\(k\)为偶数的情况,我们希望这条边两端的关键点的数量相等。
我们显然可以使用组合数来求解,一条边会被经过的方案数为\(\binom{n-si_y}{k/2}\binom{si_y}{k/2}\),\(si_y\)是\(y\)子树大小
code
#include <bits/stdc++.h>
#define int long long
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc('\n')
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
bool s_gnd ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
x = 0 ;rg int f(0) ; rg char c(gc()) ;
while(!isdigit(c)) f |= (c=='-'),c = gc() ;
while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
x = (f?-x:x) ;
read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
if(x < 0) pc('-'),x = -x ;
do stk[++tp] = x%10,x /= 10 ; while(x) ;
while(tp) pc(stk[tp--]^48) ; space ;
print(p...) ;
}
const int N = 1e5+5 ;
const int MOD = 1e9+7 ;
int n,k,ans ;
int fac[N],inv[N],vis[N],sz[N] ;
vector<int>e[N] ;
bool S_GND ;
inline int C(int x,int y)
{
if(x < y) return 0 ;
return fac[x]*inv[y]%MOD*inv[x-y]%MOD ;
}
void Solve(int x)
{
vis[x] = sz[x] = 1 ;
for(auto v:e[x]) if(!vis[v])
Solve(v),sz[x] += sz[v] ;
ans += C(n-sz[x],k/2)*C(sz[x],k/2)%MOD,ans %= MOD ;
}
inline int Pow(int x,int p)
{
int res = 1 ; while(p)
{
if(p&1) res = res*x%MOD ;
x = x*x%MOD,p >>= 1 ;
} return res ;
}
signed main()
{
//cerr<<(double)(&s_gnd-&S_GND)/1024.0/1024.0 ;
// freopen(".in","r",stdin) ;
// freopen(".out","w",stdout) ;
read(n,k) ;
if(k&1) return puts("1"),0 ;
fac[0] = inv[0] = inv[1] = 1 ;
FOR(i,1,n,1) fac[i] = fac[i-1]*i%MOD ;
FOR(i,2,n,1) inv[i] = (MOD-MOD/i)*inv[MOD%i]%MOD ;
FOR(i,2,n,1) inv[i] = inv[i-1]*inv[i]%MOD ;
FOR(i,2,n,1)
{
int u,v ; read(u,v) ;
e[u].pb(v),e[v].pb(u) ;
}
Solve(1),ans *= Pow(C(n,k),MOD-2),ans %= MOD ;
print((ans+1)%MOD) ;
return 0 ;
}
E. LuoTianyi and XOR-Tree
题意
给定一棵树,每个点有点权,每次可以修改一个点的点权,求最少修改多少次能使每个叶子节点到根节点的异或和为\(0\)。
题解
这是一个很有意思的。
一个基础的想法,设\(f_x\)表示\(x\)的子树都变成一个数的最小代价。
转移大概就是长这个样子的\(f_x = \sum_{v \in son_x}f_v\)
但是这样是不是少了什么?我们还需要一个将所有儿子都变成同一个数的代价。
只有这一维显然是不够的,那便多加一维,\(f_{x,y}\)表示\(x\)的子树都变成一个数\(y\)的最小代价。
转移\(f_{x,y} = \sum_{v \in son_x}\min_{u=0} (f_{v,u}+(u!=y))\)
但是这样显然状态太多了,是不是有些状态是多余的没有用?
我们是可以直接修改点权,所以对于\(v\)的子树内的点的值在全部相同的情况下,我们可以通过修改\(v\)的点权将他们变为任意值,这就会导致出现大量的无用状态。
怎么优化呢?我们希望原先就出现在叶子中的异或值尽量多,手动修改的尽量少。
所以我们记一个集合\(g_x\)表示\(x\)的子树变成同一个值且次数最少,这个值的可能取值。
我们在转移的时候就枚举儿子\(g_v\)集合中的数,考虑将所有儿子集合全部变成儿子集合中的哪一个。
很明显变成众数是最优的,因为不同于它的数字数字最小,并且如果子树集合中的某一个非众数\(k\)在之后会用上,使用众数也不劣,因为我们可以修改\(x\)的权值花费\(1\)的代价将其修改为任意数。
若有多个众数,则需要加入\(g_x\)了,因为在之后的转移中不知道哪一个众数会用上,可能会在之后的转移之中省掉\(1\)的贡献,所以需要将他们都存下来。
维护每个儿子集合的时候可以使用dsu on tree,启发式合并,每次将小集合插入大集合即可,均摊下来插入次数是\(nlogn\)次的。
坑点:最后要判断根节点可以变的集合中有没有\(0\),没有则要多花一次。
code
参考了hl666大佬的简洁写法Orz。
#include <bits/stdc++.h>
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc('\n')
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
bool s_gnd ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
x = 0 ;rg int f(0) ; rg char c(gc()) ;
while(!isdigit(c)) f |= (c=='-'),c = gc() ;
while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
x = (f?-x:x) ;
read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
if(x < 0) pc('-'),x = -x ;
do stk[++tp] = x%10,x /= 10 ; while(x) ;
while(tp) pc(stk[tp--]^48) ; space ;
print(p...) ;
}
const int N = 2e5+5 ;
int n,ans ;
int a[N],vis[N] ;
vector<int>e[N] ;
map<int,int>mp[N] ;
void Solve(int x)
{
vis[x] = 1 ; int mx = 0 ;
if(e[x].size() == 1 && x != 1) ++ans,mp[x][a[x]]++ ;
for(auto v:e[x]) if(!vis[v])
{
a[v] ^= a[x],Solve(v) ;
if(mp[v].size() > mp[x].size()) swap(mp[x],mp[v]) ;
for(auto [q,p]:mp[v]) mx = max(mx,mp[x][q]+=p) ;
}
if(mx > 1)
{
ans -= mx-1 ;
for(auto it = mp[x].begin() ; it != mp[x].end() ;)
if(mx != it->second) it = mp[x].erase(it) ;
else it->second = 1,++it ;
}
}
bool S_GND ;
signed main()
{
//cerr<<(double)(&s_gnd-&S_GND)/1024.0/1024.0 ;
// freopen(".in","r",stdin) ;
// freopen(".out","w",stdout) ;
read(n) ;
FOR(i,1,n,1) read(a[i]) ;
FOR(i,2,n,1)
{
int u,v ; read(u,v) ;
e[u].pb(v),e[v].pb(u) ;
}
Solve(1),ans -= mp[1].count(0)>0 ;
print(ans) ;
return 0 ;
}