脚本宝典收集整理的这篇文章主要介绍了CF EDU 110 D - Playoff Tournament，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

D - playoff Tournament

树形dp

1. 将字符串颠倒，并把每个结点的左右儿子交换，即可变成二叉树的形式（本题中让左右儿子交换）
2. 首先 dp 算出当前字符串每个结点的答案
3. 注意到修改一个结点时只会影响到他上方一条链上的结点，数目为 (LOGn) 级别，因此每次修改复杂度为 (logn)

#include <iostream>
#include <cstring>
#include <algorIThm>
#include <vector>
#include <cmath>
#define rs (u << 1)
#define ls (u << 1 | 1)
using namespace std;
tyPEdef long long ll;
const int N = 1e6 + 10;
const ll INF = 1e18;
string s;
int f[N];
int k, n;
int dp(int u)
{
    //注意递归出口不要越界字符串数组
	if (u > n)
		return 1;
	if (f[u] >= 0)
		return f[u];
	if (s[u] == '0')
		return f[u] = dp(ls);
	if (s[u] == '1')
		return f[u] = dp(rs);
	return f[u] = dp(ls) + dp(rs);
}

void modify(int u, char c)
{
	if (u <= 0)
		return;
	s[u] = c;
	if (c == '0')
		f[u] = dp(ls);
	else if (c == '1')
		f[u] = dp(rs);
	else
		f[u] = dp(ls) + dp(rs);
	modify(u >> 1, s[u >> 1]);
}
int main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	memset(f, -1, sizeof f);
	cin >> k >> s;
	n = s.size();
	reverse(s.begin(), s.end());
	s = " " + s;
	dp(1);
	int q;
	cin >> q;
	while(q--)
	{
		int p;
		char c;
		cin >> p >> c;
		modify(n + 1 - p, c);
		cout << f[1] << endl;
	}
	return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的CF EDU 110 D - Playoff Tournament全部内容，希望文章能够帮你解决CF EDU 110 D - Playoff Tournament所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。