2020 4月月赛题解

cocktail 2020-04-09 11:53:10 2020-04-09 14:51:45

第一题

观察题,虽然输入输出格式中没有说任何东西,但是只要认真读题就可以发现是要输出hello world

第二题

简单签到题。注意前提是A+B和B+A属于一种组合

c=a+b,不妨假设a是较小的加数,b是较大的加数的情况下,c是一定的,那么只要确定a就可以同时确定与之对应的b(b=c-a)

那么考虑得到a的枚举范围是1~c/2,所以答案就应该是c/2

第一第二两题主要练习文件读入输出的使用,还不会的同学赶紧到图灵姬的示例里学习哦(题目下面有示例代码的) https://turingjudge.com/problem/1001/

第三题

考察绝对值函数的使用,使用方法为abs(x),返回 x 的绝对值,这个函数包含在<math.h>的头文件中。

考虑模拟题中所述内容

   //考虑使用类似斐波那契数列的方式模拟
    int a; //前一个数
		int b; //新数
		手动输入第一个数a
		for(int i=2~n){
				1.输入新数b
		    2.sum+=本次的绝对差值
		    3.a=b为下一次循环做准备,将本次输入的新数作为下一次循环中的“前一个数”
		}

第四题

也是按题意模拟,但是细节比较多。

最暴力的方法可以按字符串的每一位一直if下去,比如第一个位置只能是"H"或者"h",第二位只能是"E“或者”e“,以此类推。

第五题

首先考虑暴力模拟,看一眼数据范围,n=109,T=100,直接劝退

其次看到最少次数可能是DP?再看一眼数据范围,n=109,T=100,哪怕是预处理出所有的情况也需要O(n),超时

显而易见本题是一个正难则反的题目

将题意变为从 n 到 1,每次除二或者减一,求最少的次数变为 1。

显然除以二是可以更快的从n变成1(最快log),所以能除二时(即偶数时)尽量除二,否则就减一。

因为奇数时只要减一必然可以变成偶数,下一次一定可以除以二,所以复杂度O(T logn)

核心程序

  while(n != 1){
	  	if(n % 2 == 0)
		    	n /= 2;
		  else
			   n--;
		  ans++;
 }	

第六题

注意回文串的定义:正着读和反着读一样。

也就是说除了自己本身字母形成的长度为1的回文串外,必须要遇到一个和自己相同的字母才能形成回文串。

比如一个a,只能和其他的a对应,才能形成回文串。如:aba abba aaa aa等。对于每个a,都可以和其他任意一个a对应形成一个回文串。

如果要求构造回文子串最多的串,那么直接排序原字符串即可。

假设有k个a,子串包含1个a的情况有k种,子串包含2个a的情况有k-1种,子串包含3个a有k-2种.....显然的等差数列求和

而统计回文子串的数量也就很清晰了,直接统计a-z出现的次数即可,然后对每个字符的次数分别算对应的回文串数量就行了。

估算一下最终ans的答案最大可能性,1000002/2≈5*109,超出int上限,注意开 long long

  cin >> str;
	for(int i = 0; i < str.size(); i++)
		cnt[str[i] - 'a']++;
	for(int i = 0; i < 26; i++)
		ans += cnt[i] * (cnt[i] + 1) / 2;

恭喜

AMAZE UI
Hello world!