牛客寒假算法基础集训(白给)营4题解

发展生产力不是没有用处的,也不是说说写写而已的,而是它确实能给我带来收益。虽然这场有点小小的遗憾吧,字符串那题没能debug出来,最小生成树裸题没发现导致本来能A掉的题根本就没做,不过总体来说,我觉得海星。

(我上场中的杯子啥时候发过来啊……)


A Applese的取石子游戏

原题:https://ac.nowcoder.com/acm/contest/330/A

又是取石子,糟糕,这是博弈论。

这题最快的人用了46秒,显然这并不是难题,随后有一千多人A掉了这题。我为什么记得这么清楚?因为那个时候我还没有A掉这题,我交了三次都WA了。原本的思路是去模拟取的过程,简单的策略是哪边大取哪边,后来发现不对。因为存在不是必胜的可能。既然俩人都是绝顶聪明,做出的决定显然要最大化自己的利益才可以。

这样想,这题就开始麻烦了。我当时感觉,这题一定有什么显然的结论我没有推出来。既然是博弈,我们考虑一下策略问题,到底要选择什么样的策略才能保证我可以赢下这个游戏?

不难想,Applese先动,由经验规律“先攻压制”,个人推测Applese可能存在必胜策略,于是直接输出Applese,拿下此题。那这个题正常的考虑方式应该是什么呢?

牛客正解作者“你以为你CF过了四题”这样说:

实际上,由于题面中的两个限制条件,可以得出先手有必胜策略:即选择所有的奇数项或者偶数项。

如果奇数项的和较大,先手就取第一个,这样每一次轮到后手都只能取到偶数项。反之亦然同理。
因此,作为本场比赛的签到题之一,直接输出Applese即可通过。

所以这题就不贴标程啦,只需要输出Applese就好。

E Applese涂颜色

原题:https://ac.nowcoder.com/acm/contest/330/E

感谢Java为我带来的生产力。让我免受C++大整数模板的痛苦。

这个题,说是方阵,实际上可以看成很多很多的纸条,每张纸条有很多横着一排的方格,要求是左右相邻的两格不可以涂成相同的颜色,只能涂黑和白。稍微模拟一下发现,无论纸条多长,都是只有两种情况。都是黑白相间。为啥这里能简化成纸条?因为行与行之间的涂色是独立的,这里方便我们计数。依据乘法原理,每张纸条的方案数相乘就是总答案。一张纸条有两个方案,一共n张纸条(想一想,为什么),所以最终的答案就是2n % 1e9+7。

不幸的是,n最大有10100000,这令我们无法接受,只能使用高精度计算。

然而,在C++语言里,没有给定的高精度计算模板,自己实现也是相当的费劲而且易错,这里就完全可以掏出之前学的Java了。

使用Java的BigInteger类存储数字,并且Java对大整数类还附带了很多常用的数学函数,这里我们需要的pow函数便在这里面。

东西都封装好了,直接实现就可以。以字符串模式读入,m我们可以不要,使用字符串分割留下来有用的n,转换成大整数类,然后对2和1e9+7都造一个大整数实例(大整数的pow函数传参也必须是大整数),计算得到结果,完全OK。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;
import java.math.*;
public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.nextLine();
String[] a = s.split(" ");
String nn = a[0];
BigInteger n = new BigInteger(nn);
BigInteger p = new BigInteger("2");
BigInteger mo = new BigInteger("1000000007");
BigInteger ans = p.modPow(n,mo);
System.out.println(ans);
in.close();
}
}

I Applese的回文串

原题:https://ac.nowcoder.com/acm/contest/330/I

题意很简单,是我想多了,没能当场AC,本题赛后已补。

给你一个字符串,这个字符串可能是回文串,但是多一个字符,问你如果再补上一个字符(可以是任意字符,任意位置),可不可以搞成回文串。

读完题第一反应:搜!

然后看到字符串大小1e5。。。发出了系统栈的声音:救救孩子,我要炸

但是仔细一想,没那个必要。就只有一个字符有变动,那么我找一下原来打算要变成回文串的位置到底有哪个不一样,不就好了吗。

这么想没错,但是一想你就上当了。这样的写法很危险,一旦边界判不合适就会像我一样————

噔 噔 咚(心肺停止)

原来的设想很简单:

假设现在红位置和绿位置不匹配,那么只需要检查一下子串1和子串2是不是回文串就可以。

但是,由于边界细节问题很难把控(指for循环的起止点和极限数据的处理),你无法保证一次就写对。后来实践证明这个方法写起来都是各种各样的bug,导致无法AC。后来我又测了一下,我修改bug最多的程序也只能过90%的点。

正解为我们提供了一个思路,同时也暴露了这题的很严重的思维误导嫌疑。正解是试图删除不匹配的红或绿,然后抽出了一个独立的函数去判断是不是回文。

妙啊,真的是妙。我是真的无言以对啊。正解告诉我们,在这个题里面,添加字符和删除字符是等价的。于是你就很自然的被思维误导进去了。

正解的解法很简单,设定一个判断回文串的函数,如果它是回文串就返回-1,如果不是则返回第一个出现不匹配字符的左位置。我们首先预判一下原串是不是回文串,如果原串是回文串直接答案是Yes(因为直接在中间塞一个任意字符就可以,仍然是回文串)对于原串不是回文串的情况,设立一个字符串副本fuDuJi,没错,复读机,复读s的内容。然后这两个串一个删掉头位置不匹配,一个删掉尾位置不匹配,然后把处理后的字符串扔进判断函数,处理就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <string>
#define debug cout << "OK" << endl;
using namespace std;
string s;

int checkHW(string s) {
int l = s.length();
for (int i = 0; i < l; i++) {
if (s[i] != s[l - 1 - i])
return i;
}
return -1;
}

bool fail = true;

int main() {
cin >> s;
int misMatch = checkHW(s);
if (misMatch == -1)
fail = false;
else {
string fuDuJi = s;
int l = s.length();
fuDuJi.erase(l - misMatch - 1, 1);
s.erase(misMatch, 1);
if (checkHW(s) == -1 || checkHW(fuDuJi) == -1)
fail = false;
}
if (fail)
cout << "No";
else
cout << "Yes";
system("pause");
return 0;
}

J Applese的减肥计划

原题:https://ac.nowcoder.com/acm/contest/330/J

不要被这个所谓的误差限制给吓住了,只要公式对,正常输出就行。

我在做这个题的时候大脑突然短路,忘记了两个东西:

1.余弦定理是啥

2.cos 120°等于多少(推算的时候)

这题说是签到题,实际上如果高中学那点物理知识忘了的话还真的无法签到23333

考察二力合成,满足平行四边形法则,然后把其中一个力移动到对边去就组成了一个矢量三角形,两个力知道,只需要知道夹角就能根据余弦定理求合成力了。平行四边形的一对角角度是a,另一对显然角度都是180°-a,然后以此套公式就可以。

注意,cmath里面的cos函数(其实三角函数都算上)它的参数是!弧!度!但是给你的a是!角!度!所以一定要加上角度转换弧度!都是高考过来的人,公式你应该知道。

注意,你可以使用camath里面自带的PI值,写上M_PI就好。但是精度比较差,不过做这个题够用了。总不能为了一个题还要现场去推高精度的pi吧。。。

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
double f1,f2,f3,a;
int main() {
cin >> f1 >> f2 >> a;
f3 = pow(f1, 2) + pow(f2, 2)-cos((180 - a) * M_PI / 180) * 2 * f1 * f2;
printf("%lf", sqrt(f3));
return 0;
}

-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------


本文标题:牛客寒假算法基础集训(白给)营4题解

文章作者:Shawn Zhou

发布时间:2019年01月29日 - 19:01

最后更新:2019年01月29日 - 22:01

原始链接:http://shawnzhou.xyz/2019/01/29/19-01-29-01/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。
0%