Educational Codeforces Round 127（D~E）

不是张胖胖

已于 2022-04-24 20:18:33 修改

阅读量1.6k

点赞数 2

文章标签： c语言

于 2022-04-24 15:09:52 首次发布

本文链接：https://blog.csdn.net/zppbugmaker/article/details/124382591

版权

本文分别探讨了两个计算机科学领域的经典问题。第一个问题是关于数组插入优化的问题，通过动态规划策略找到最小的绝对差之和。第二个问题涉及完全二叉树的字符组合，利用动态规划和树的特性计算不同字符串的可能数量。文章深入浅出地解释了动态规划的应用，并提出了高效的解决方案。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

D. Insert a Progression

题意：
给你长度为 $n$ 的数组 $a$ 以及一个数字 $x$ ，要求你将 $1\sim x$ 的所有 $x$ 个数字随意插入数组 $a$ 中，要求插入完毕后新获得的数组 $a$ 的 $\sum _{i=1} ^{n+x-1}|a_i-a{i+1}|$ 值尽可能的小，输出这个值
思路：
在 $n$ 个数字中最大的数字为 $m a x$ ，最小的数字为 $m i n$
将 $\sim max$ 区间的数字插入数组，对答案可以不产生任何的影响
若 $m a x < x$ ，将 $x$ 插入后， $max\sim x$ 之间的数字也不再有任何影响
数字 $1$ 同理
于是问题可以转换为仅将数字 $1$ 和 $x$ 插入数组后对原数组答案的影响
将数字 $1$ 插入 $num_a$ 和 $num_b$ 间
新产生的贡献为： $min(num_a,num_b)-1)*2$
在这里插入图片描述
同理，数字 $x$ 插入的贡献为 $x-max(num_a,num_b))*2$
最后，注意特判插入数组首和尾的情况即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
int a[maxn];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n,x;
		scanf("%d%d",&n,&x);
		ll ans=0;
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=2;i<=n;i++) ans+=abs(a[i]-a[i-1]);
		int maxx=*max_element(a+1,a+1+n),minn=*min_element(a+1,a+1+n);
		ll add1=0,add2=0;
		add1=min(min(a[1],a[n])-1,2*(minn-1));
		if(x>maxx)
		add2=min(abs(max(a[1],a[n])-x),2*abs(maxx-x));
		printf("%lld\n",ans+add1+add2);
	}
}

E. Preorder

题意：
给你一颗完全二叉树，节点 $u$ 的左右儿子分别为 $u + 1$ ， $u + 2$ ，每个节点都有一个字符 $A$ 或 $B$
$f (i)$ 会范围一个字符串， $f (i) = s [i] + f (i * 2) + f (i * 2 + 1)$
同时，你还可以任意进行操作：交换一个节点上左右儿子上的字符
求 $f (1)$ 可以有多少种不同的字符串的可能
思路：
动态规划， $d p [i]$ 表示以点 $i$ 为根节点的子树的字符串数量
若点 $i$ 左右儿子子树相同， $d p [i] = d p [i * 2] * d p [i * 2 + 1]$
否则， $d p [i] = d p [i * 2] * d p [i * 2 + 1] * 2$
可以暴力判断子树的构造是否相同，总时间复杂度是 $O (n l o g (n))$

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=3e5+7;
int n;
char s[maxn];
ll mod=998244353;
bool cmp(int a,int b)
{
	if(s[a]!=s[b]) return false;
	if(2*a>n) return true;
	if(cmp(2*a,2*b) && cmp(2*a+1,2*b+1)) return true;
	if(cmp(2*a+1,2*b) && cmp(2*a,2*b+1)) return true;
	return false;
}
ll dfs(int u)
{
	if(2*u>n)
	{
		return 1;
	}
	else if(cmp(2*u,2*u+1))
	{
		return dfs(2*u)*dfs(2*u+1)%mod;
	}
	else 
	{
		return dfs(2*u)*dfs(2*u+1)*2%mod;
	}
}
int main()
{
	scanf("%d",&n);
	n=(1<<n)-1;
	scanf("%s",s+1);
	ll ans=dfs(1);
	printf("%lld\n",ans);
}