Educational Codeforces Round 127（D~E）_C

文章目录

D. Insert a Progression
E. Preorder

D. Insert a Progression

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

同理，数字 x x x插入的贡献为 ( x − m a x ( n u m a , n u m b ) ) ∗ 2 (x-max(num_a,num_b))*2 (x−max(numa,numb))∗2
最后，注意特判插入数组首和尾的情况即可

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

#include
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);
}