RandolphJ

分类

比赛(2) 题解(48)

/ 注册

全部文章（共55篇）

【牛客小白月赛22】NC202476 交换游戏

一共12个孔，只有2^12=4096种情况，但是查询次数很多，我们可以考虑用二进制1和0表示‘o’和‘-’两种状态，进行状态压缩，用一个二进制数代表一种情况。然后再在记忆化搜索的过程中把已知情况的答案记录下来，方便下次直接用。搜索的时候就找 '-oo' 和 'oo-'，注意到它们有共同点：中间是1...

2020-02-26

4 1083

【牛客小白月赛22】NC202485 收集纸片

一不小心拿了运行时间最快qwq（2ms）（截止此时）要求从一个初始位置开始，经过所有的纸片，最终再回到初始坐标，求走过的最短距离。方法1：暴力枚举或dfs（2ms）我们可以用求1~n的全排列，计算所有可能的走法，由于纸片数不超过10，所以走法最多只有10!种。全排列求法见《算法竞赛进阶指南》...

2020-02-25

3 904

【牛客小白月赛22】NC202474 操作序列

这是一道挺不错的STL模拟题，做法也很多，可以借此巩固一下对STL的知识运用由于数列长度无限，所以我们需要离散化，可以用一个容器（如map，set，建议先了解一下它们的用法及基本的指针用法）存储不为0的数及它的下标增加操作：给下标为 tt 的数加 cc 。特别注意，如果在下标 [t-30,t+...

2020-02-24

4 1346

【牛客小白月赛22】题解

【牛客小白月赛22】题解链接题目知识点题目难度 A 操作序列 STL，map，set，模拟普及/提高- B 树上子链树形dp，树的直径普及+/提高 C 交换游戏记忆化搜索，状态压缩普及/提高- D 收集纸片全排列，dfs，状压dp，TSP问题普及/提高- ...

牛客小白月赛22

2020-02-23

1 678

【牛客小白月赛22】NC202488 累乘数字

先输出n，再输出d个00即可 #include<cstdio> using namespace std; int a,b; int main(){ while(~scanf("%d%d",&a,&b)){ printf("%d",a); f...

2020-02-22

1 773

【牛客小白月赛22】NC202486 方块涂色

原来n×m的方格，涂去r行还剩(n-r)×m个，再把c列涂去，答案为(n-r)×(m-c) #include<cstdio> using namespace std; int main(){ long long n,m,r,c; while(~scanf("%lld %l...

2020-02-22

0 937

【牛客小白月赛22】NC202475 树上子链

求树上最长链（或者说树的直径、树上距离最远的两点距离，树中所有最短路径距离的最大值qwq）的模板题，网上讲解很多，注意点权有负数即可参考资料1(by ROCKYONE) 参考资料2(by forever_dreams) 1.树形DP（可以有效处理负边权）2.两次dfs或bfs（无法处理负边权） ...

2020-02-22

7 1193

【牛客小白月赛22】NC202511 计算A+B

比赛时这道签到题写炸了。。写了1个多小时还没写对，还想着有没有什么空格、除‘+’之外的其他符号。。开始写高精度怎么也写不对，后来又试试__int128（赛后才发现2^128只有38位左右，还是不够）以上都是废话qwq我还是太菜了赛后稍微改一改就过了，好气哦qwq。。只需注意4个坑：字符串中+在...

2020-02-22

4 1136

【牛客小白月赛21】NC201612 I love you

《爱》（罗伊·克里夫特创作诗歌）参看小白月赛3的B题，只不过这里的字符串变长了一些,注意iloveyou作为子序列出现不一定是连续的。用f[i]表示iloveyou匹配了前i个的字符的子序列数，当遇到第i个字符，则之前匹配了前i-1个的字符的子序列都可以变为匹配了前i个的字符的子序列，即f[i]...

2020-01-31

13 1258

【牛客小白月赛21】NC201610 Game

因为质因数是无法再被分解的,所以最后集合中的数全为n的质因数，先考虑把n质因数分解。不难发现，每次分解为哪2个数并不重要，只不过是把集合中的数字个数加1，那么质因数个数的奇偶很可能决定了谁最后无法操作。假设 n 有 p 个质因数，那么这场游戏将进行 p-1 次操作（每次操作后集合中的数字个数+1...

2020-01-31

2 867