首页 > 其他分享 >CF1674C的题解

CF1674C的题解

时间:2023-08-25 21:14:46浏览次数:41  
标签:int 题解 long CF1674C pow 100 include

有意思的题目。

还是比较好想的。

先考虑 -1 的情况,可以想到,如果 \(t\) 的长度不为 \(1\),并且 \(t\) 里面还有 a 的话,那么这个新的 a 又能被下一个 \(t\) 替换,无限套娃。

剩下的,还是有两种情况:

  1. 如果 \(t\) 只有一个字符 a ,那么 \(s\) 无论怎么被替换都是一样的(全部都是 a ),所以,这种情况输出 1

  2. 如果不是第 1 种情况,那么最终的答案就为:

    \(\large C^0_n+C^1_n+C^2_n+C^3_n+...+C^n_n\)

    其实上面这个式子很好理解,只要从 \(s\) 里分别选出 \(0\) 个,\(1\) 个,\(2\) 个,......,\(n\) 个 a 出来被替换就是最后的方案数。

    根据组合数的定义,可以知道上面的式子就是 \(\large2^n\)。

    为了加快效率,可以使用 cmathpow 函数,也可以先预处理所有的 \(\large 2^i\) 的值。

code

#include<cstdio>
#include<cstring>

int q;
char s[100],t[100];
unsigned long long pow[100];

void init()
{
	pow[0]=1;
	for(int i=1;i<=50;i++) pow[i]=pow[i-1]*2;
}

int main()
{
	init();
	
	scanf("%d",&q);
	
	while(q--)
	{
		scanf(" %s %s",s+1,t+1);
		
		int le=strlen(s+1);
		int len=strlen(t+1);
		
		//-1
		if(len>1)
		{
			bool yes=0;
			for(int i=1;i<=len;i++)
				if(t[i]=='a')
				{
					yes=1;
					break;
				}
			if(yes)
			{
				printf("-1\n");
				continue;
			}
			else printf("%lld\n",pow[le]);
		}
		else
		{
			if(t[1]=='a') printf("1\n");
			else printf("%lld\n",pow[le]);
		}
	}
	
	return 0;
}

标签:int,题解,long,CF1674C,pow,100,include
From: https://www.cnblogs.com/osfly/p/17657941.html

相关文章

  • CF1674B的题解
    很简单的题可以先初始化一下,把所有单词放进一个map里,最后输入时用map映射即可。一个坑点,注意每一个单词的两个字母不相同。#include<cstdio>#include<map>#include<string>#include<iostream>usingnamespacestd;map<string,int>mp;voidinit(){ intindex=0;......
  • CF1311F的题解
    前置芝士:二维偏序。二维偏序的板子题。怎么看出是二维偏序的呢?考虑点对\((i,j)\),令\(x_i<x_j\)。若\(v_i>v_j\),则两点会越来越近,易知最短距离为\(0\),所以我们不需要考虑这种情况。所以问题转化成:\(x_i<x_j\)且\(v_i\lev_j\)的点对的距离和。很明显,二维偏序,套板子就......
  • CF1701B的题解
    简单构造题。很明显的,当\(d=2\)的时候代价最大。证明:\(\becausep_i\cdotd=p_{i+1}\)当\(d\)减小时,\(p_i\cdotd\)也在减小,\(p_{i+1}\)也在减小,那么\(p_{i+1}\)减小时,\(p_{i+1}\)可供选择的数就越多,代价也随即越大,那么\(d\)在取最小值时,代价最大,因为\(p\)是......
  • CF131D的题解
    注意到\(n\)实在是小到不行,我们可以直接采用比较暴力的做法。(嗯,可能算比较暴力吧很简单,找环,然后把环里的所有点全部压进dijkstra的优先队列就行了。找环最坏\(n\)遍跑满的dfs,最短路是\(O(n\logn)\)的,最坏时间复杂度为\(O(n^2)\),稳过。什么?怎么找环?都2202年了不会还......
  • CF605B的题解
    算是对Leap_Frog大佬的补充吧qwq。%%%Leap_Frog.我们来看一下大佬的这段话:考虑倒着思考Kruskal算法。按边权从小到大排序。每次插入一条边。如果是树边,那就新开节点。否则在当前节点内任意连边。这样构造,每次非树边插入都比当前两端小。所以必然正确。对于“如果是......
  • P3847的题解
    典型到不能再典型的区间dp了。观察四种操作,考虑到加一个数和删一个数的情况相同,所以无非就是:删一个数。改一个数。设\(dp[l][r]\)为让区间\(l\simr\)对称(变成回文串)的最少次数。可以很快地得出状态转移方程:情况\(1\):如果\(a_l=a_r\),则\(dp[l][r]=dp[l+1][r-......
  • CF1712A的题解
    挺简单的一道题。要想使\(\sum\limits^k_{i=1}p_i\)最小,很明显的,前\(k\)个数必须为\(1\simk\)。设\(c_i\)为\(i\)在\(p\)里出现的位置,则答案为\(\sum\limits^{k}_{i=1}[c_i>k]\)。#include<cstdio>intt;intn,k;inta[110],c[110];intans;intmain(){ sca......
  • 国标视频云服务EasyGBS国标视频平台视频快照无法显示的问题解决步骤
    国标视频云服务EasyGBS支持设备/平台通过国标GB28181协议注册接入,并能实现视频的实时监控直播、录像、检索与回看、语音对讲、云存储、告警、平台级联等功能。平台部署简单、可拓展性强,支持将接入的视频流进行全终端、全平台分发,分发的视频流包括RTSP、RTMP、FLV、HLS、WebRTC等......
  • [AGC030D] Inversion Sum 题解
    题意给定一个长度为\(n\)的排列\(a\)和\(m\)个形如\(\left(x,y\right)\)的操作,每次操作可以选择是否交换\(a_x,a_y\),求最终所有形成的排列的逆序对总数。(\(1\len,m\le3000\))。题解考虑转化题意,考虑求出最终总的期望逆序对数,即CF258D。转化答案\[\text{Ans}=......
  • Codeforces Round 894 (Div. 3) A-F题解
    A.GiftCarpet题意最近,特马和维卡庆祝了家庭日。他们的朋友Arina送给他们一块地毯,这块地毯可以用拉丁文小写字母的\(n\cdotm\)表来表示。维卡还没看过礼物,但特马知道她喜欢什么样的地毯。如果维卡能在地毯上读出自己的名字,她一定会喜欢的。她从左到右逐列阅读,并从当前列中......