论如何 AK WFYZ公益班测试-20240330

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-30 15:39:56

晚了半个点参赛，因为此前 vp 了上一场 CF Div.4（AK）

C 没测第二个样例，刚好题目翻译有问题（事实不应该去重，但翻译成了去重），怒挂 50。
D 题我看最后一个点 $n=2000$，就以为 $n \le 2000$，事实上 $n \le 2\cdot 10^5$，挂 40。 F 题写的正解，然而要求的值看错了，导致没调出来，哎。

A - CF598A

套公式直接算。

B - CF598B

同一个长度为 $len$ 的区间执行 $k$ 次和执行 $k \mod len$ 次效果是一样的，可以以此在每次操作中快速计算出每个字符新的位置。
注意到操作次数很少，模拟就可以。

C - CF598D

bfs 就行了，注意本题洛谷翻译是错的，应该按照题目警示贴来。

D - P2846

线段树维护，每个节点记录本区间答案，以及一个 lazytag 代表本区间灯状态是否反转。

E - CF461B

设状态 $dp_{u,1/0}$，代表 $u$ 为根的子树，$u$ 所在的连通块有一个/没有黑色节点，且其他连通块合法的方案数。

先考虑 $x_u$ 为 $1$ 的情况，此时对于每个子节点，如果其所在连通块有一个黑色节点，则不能保留其和 $u$ 的连边，如果没有黑色节点，则其必须和 $u$ 连边；简单地说，如果和 $u$ 连边，那么自己连通块必须有一个黑色节点，反之必须没有。
此时显然 $dp_{u,0} = 0,dp_{u,1} =\prod\limits_{v \in son_u} (dp_{v,0}+dp_{v,1})$
如果 $x_u$ 为 $0$ 呢？
考虑 $u$ 连通块中存在一个黑色节点的情况，此时必须有恰好一个连通块中存在一个 $1$ 的子节点和自己连边，其余连通块存在一个黑色节点的子节点都必须和 $u$ 断边，另外所有连通块不存在黑色节点的子节点都必须和 $u$ 连边，得出结论： $dp_{u,1}=\sum\limits_{s_1 \in son_u} (dp_{s_1,1}\cdot \prod\limits_{s_2 \neq s_1}(dp_{s_1,0}+dp_{s_2,0}))$
接下来考虑 $u$ 连通块中没有黑色节点的情况，此时子结点中，如果一个子节点连通块中没有黑色，那么必须保留和 $u$ 的边，否则必须删除和 $u$ 的边，显然有结论：
$dp_{u,0} =\prod\limits_{v \in son_u} (dp_{v,0}+dp_{v,1})$

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(itn i=a;i>=b;i--)
typedef long long ll;
const ll mod=1e9+7;
int t;
const int maxn=1e5+5;
int n;
int p[maxn];
int x[maxn];
vector<int> g[maxn];
ll dp[maxn][2];
ll qpow(ll a,ll b){
	ll ret=1;
	while(b){
		if(b&1)ret=ret*a%mod;
		a=a*a%mod;
		b>>=1; 
	}
	return ret;
}
ll inv(ll a){
	return qpow(a,mod-2);
}
void dfs(int u,int _fa){
	ll sum=1;
	for(int v:g[u]){
		if(v!=_fa){
			dfs(v,u);
			sum*=(dp[v][0]+dp[v][1]);
			sum%=mod;
		}
	}
	if(x[u]==1){
		dp[u][1]=sum;
	}else{
		for(int v:g[u]){
			if(v!=_fa){
				dp[u][1]+=dp[v][1]*(sum*inv(dp[v][0]+dp[v][1])%mod)%mod;
				dp[u][1]%=mod;
			}
		}
		dp[u][0]=sum;
	}
}
void solve(){
	scanf("%d",&n);
	FOR(i,0,n-2){
		int pi;
		scanf("%d",&pi);
		g[pi].emplace_back(i+1);
		g[i+1].emplace_back(pi);
	\/\/	printf("%d --> %d\n",pi,i+1);
	} 
	FOR(i,0,n-1){
		scanf("%d",&x[i]);
	}
	dfs(0,-1);
	printf("%lld\n",(dp[0][1]%mod+mod)%mod);
}
int main(){
	t=1;
	while(t--){
		solve();
	}
	return 0;
}

F - CF598E

$dp_{x,y,k}$ 代表初始有一个长为 $x$，宽为 $y$ 的巧克力，搞出大小为 $k$ 的巧克力的最小代价。

转移十分的暴力，枚举分割点，将其分割成两个小巧克力，并枚举第一个小巧克力和第二个小巧克力各贡献多少大小的巧克力（用来凑成大小为 $k$ 的巧克力）
然后没啥好说的，自认为本蒟蒻的代码还是比较好懂的。

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
int T;
const int maxn=55;
ll dp[maxn][maxn][maxn];
\/\/ chang,kuan 的巧克力搞出 k
ll dfs(int chang,int kuan,int k){
    if(k==0)return 0;
    if((chang==1&&kuan==1)&&(k!=1))return 1e18;
    if(dp[chang][kuan][k]<dp[0][0][0])return dp[chang][kuan][k];
    if(k>chang*kuan){return 1e18;}
    if(k==chang*kuan){return 0;}
    FOR(lef,0,k){
        FOR(i,1,chang-1){
            ckmn(dp[chang][kuan][k],dfs(i,kuan,lef)+dfs(chang-i,kuan,k-lef)+kuan*kuan);
        }
        FOR(i,1,kuan-1){
            ckmn(dp[chang][kuan][k],dfs(chang,i,lef)+dfs(chang,kuan-i,k-lef)+chang*chang);
        }
    }
 \/\/   printf("dp[%d][%d][%d] = %lld\n",chang,kuan,k,dp[chang][kuan][k]);
    return dp[chang][kuan][k];
}
void solve(){
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    printf("%lld\n",dfs(n,m,k));
}
int main()
{
    memset(dp,0x7f,sizeof dp);
    dp[1][1][1]=0;
	scanf("%d",&T);
	while(T--){
		solve();
	}
	return 0;
}

vector 的博客

博客