2022牛客寒假算法基础集训营1 ACDEFHIJL
很久没做题，赛时A了9道加起来WA了16发...剩下三道待补
A. 九小时九个人九扇门
链接：https://ac.nowcoder.com/acm/contest/23106/A
来源：牛客网
题目描述
在打越钢太郎的著名解谜游戏系列《极限脱出》的第一作《九小时九个人九扇门》中，有这样一个有趣的设定：游戏中，99位主人公被困在一座大型的豪华巨轮中，每个人手上都有一个奇怪的手表，手表上有一个数字，99个人的数字分别是1?91?9；在巨轮中，还有很多紧闭的数字门，每扇数字门上也有一个1?91?9的数字，要想打开数字门逃出生天，主角们必须要满足一个奇怪的条件：
kk个人能够打开门上数字为dd的一扇数字门，当且仅当这kk个人的腕表数字之和的数字根恰好为dd。
一个数字的数字根是指：将该数字各数位上的数字相加得到一个新的数，直到得到的数字小于1010为止，例如，149149的数字根为149=>1+4+9=14=>1+4=5149=>1+4+9=14=>1+4=5，故149149的数字根为5。我们约定，小于1010的数字，其数字根就为其本身。
例如，如果游戏中的一宫（手表数字为11）、四叶（手表数字为44）、八代（手表数字为88）三人组合在一起，就可以打开编号为44的数字门，这是因为1+4+8=131+4+8=13，而1313的数字根为44。
现在，你是游戏的主角，淳平，你知道船上包括自己在内的nn个人的手表数字，为了分析局势，你想要计算出可以打开1?91?9号门的人物组合有多少种，你可以完成这项任务吗？
输入描述:
输入的第一行包含一个整数n(1≤n≤105)n(1≤n≤105)，主人公的数量。下面一行nn个数，第ii个数字ai(1≤ai≤109)ai(1≤ai≤109)表示第ii位主人公的腕表数字。
输出描述:
你需要输出99个数字，第ii个数字表示有多少种不同的人物组合，可以打开编号为ii的数字门。答案可能很大，请你将答案对998244353998244353取模后输出。
示例1
输入
复制
9
1 2 3 4 5 6 7 8 9
输出
复制
56 56 58 56 56 58 56 56 59
注意到一个数的数字根和这个数模9的结果是一样的，同理两个数相加后的数字根等于这两个数的数字根在模9意义下相加。因此这就转换成了一个背包问题：
设dp[i, j]表示用前i个数能凑出数字根j的方案数。外层循环1到n遍历，内层循环0到8遍历即可。具体转移方程见代码。
#include
#include C. Baby's first attempt on CPU
链接：https://ac.nowcoder.com/acm/contest/23106/C
来源：牛客网
题目描述
在硬件小学期课程上，学生们要分组使用Verilog编写流水线CPU，并学会处理各种流水线CPU中常见的相关问题，包括数据相关、结构相关与控制（转移）相关，炸鸡块君也学到了许多。现在，他也要教你解决流水线CPU中数据相关下的先写后读相关问题。
在汇编语言程序中，程序是由多句汇编语句组成的，每句汇编语句会从寄存器中读一些数据（可能不读）和向寄存器中写一些数据（可能不写）。但由于CPU流水线式的架构，一条语句A写入寄存器的数据若想被语句B读到，则语句B和A之间至少要间隔三条语句，否则B将读到该寄存器中的老数据而不是A刚刚写入的数据，这被称为寄存器的先写后读相关问题。
例如，第一条语句写入了十号寄存器一个数据，若想写一个读取十号寄存器中数据的语句，则该语句最快也要等到第五句才可以（因为此时两条语句才恰好间隔三句）。
解决先写后读相关问题往往可以使用插入空操作（空操作也是一种汇编语句，该语句什么都不做，只起到占位的作用）的方法，即填充一些什么都不做的语句到原程序中。例如，现在第一条语句写入了八号寄存器、第二条语句读取了八号寄存器，因此存在对八号寄存器的先写后读相关问题，可以通过在之中插入三句空语句来解决该问题，即原程序在插入后变为：原第一条语句、空语句、空语句、空语句、原第二条语句。
现在，给出一个原有nn个语句的汇编程序，并给出程序中语句之间发生先写后读相关的情况，请你求出最少添加多少个空语句可以使得该程序完全不存在任何先写后读相关问题。
输入描述:
输入第一行包括一个整数n(3≤n≤100)n(3≤n≤100)，程序原有语句总数。
接下来有nn行，第ii行描述了第ii条程序语句，每行有三个数字。第ii行第jj个数字ai,j∈{0,1}ai,j∈{0,1}表示第ii句与第i?ji?j句间是否发生了先写后读相关，为11表示有发生先写后读相关（即第i?ji?j句写入了某一寄存器，而第ii句又要读取同一寄存器），为00表示没有。
输入保证对于i?j≤0i?j≤0的ai,jai,j有ai,j=0ai,j=0成立。
（你可以通过样例进一步理解输入的含义）
输出描述:
输出一个整数，表示为完全消除先写后读相关至少需加入多少条空语句。
示例1
输入
复制
4
0 0 0
1 0 0
0 1 0
0 0 0
输出
复制
3
范围很小，直接暴力模拟即可，用vector存储最终指令序列，nop的话就直接插0，每次判断是否需要新指令的时候就从vector末尾遍历看是否还需要插入新的nop以避免写后读。不知道过的人为啥比别的题少...
#include
#include D. 牛牛做数论
链接：https://ac.nowcoder.com/acm/contest/23106/D
来源：牛客网
题目描述
牛牛最近做了这么一道题：
"对于一给定的 n(1≤n≤109)n(1≤n≤109)，计算?(n)?(n), 之中 ?(x)?(x)是满足1≤y≤x1≤y≤x 且 gcd(x,y)=1gcd(x,y)=1的yy的个数。例如： ?(6)=2?(6)=2、?(5)=4?(5)=4."
牛牛一眼看出这就是欧拉函数，于是立刻用嘴巴解决了这道题。
牛牛意犹未尽，于是他又给你出了一道题。对于一个正整数 xx，牛牛定义H(x)H(x) :
H(x)=?(x)xH(x)=x?(x)
牛牛还规定，该函数的定义域为除了11的所有正整数。
于是，牛牛给出了一个整数nn，想要你回答两个关于H(x)H(x)的问题：
1、 回答一个 x0∈[2,n]x0∈[2,n]，使得 H(x0)H(x0) 取到 H(x)H(x) 在 [2,n][2,n]的最小值。若存在多个这样的x0x0，输出最小的一个。
2、 回答一个 x0∈[2,n]x0∈[2,n]，使得 H(x0)H(x0) 取到 H(x)H(x) 在 [2,n][2,n]的最大值。若存在多个这样的x0x0，输出最大的一个。
输入描述:
第一行为一个整数T(1≤T≤100)T(1≤T≤100)，表示测试组数。接下来的TT行，每行包括一个整数n(1≤n≤109)n(1≤n≤109)，牛牛给出的整数。
输出描述:
对于每个测试用例，输出两个空格分割的整数，依次为你对牛牛两个问题的答案。特别的，若n=1n=1，请输出?1?1表示H(1)H(1)没有定义。
示例1
输入
复制
3
2
5
1
输出
复制
2 2
2 5
-1
需要知道欧拉函数的性质：
\(φ(n)/n=(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)……(1-1/pn)\)
其中p1...pn是n的素因子。这样就可以知道，让答案最小的那个x0一定是要尽可能多的把靠前的素数选上（观察式子显然，这样可以使倒数最大，从而1-1/px最小）且这些素数的积不能超过n；让答案最大的那个x0一定是小于等于n的最大的素数（这样的话φ(x0)=1-1/x0，没有别的小于1的项了）。
#include
#include E. 炸鸡块君的高中回忆
链接：https://ac.nowcoder.com/acm/contest/23106/E
来源：牛客网
题目描述
炸鸡块君在高中时，学校规定进出校门必须要刷校园卡，否则禁止进入。
某一天，炸鸡块君和同学们一共nn个人去学校附近玩耍，但回学校时他们发现只有mm个人带了校园卡，于是他们想到了这样一个策略：先让mm个人带校园卡进入学校，再派一个人带着所有mm张校园卡出来，重复上述过程，直到所有人进入学校。
假设从外面进入学校和从校内出来到校外都需要花费一个单位的时间，求所有人都进入学校最少需要花费几个单位的时间。
输入描述:
输入第一行是一个整数T(1≤T≤105)T(1≤T≤105)，表示测试组数。每组测试包括两个整数n,m(1≤m≤n≤109)n,m(1≤m≤n≤109)，含义如题目所示。
输出描述:
输出一个整数，表示所有人进入学校需要花费最少几个单位时间。特别的，若无法让所有人进入学校，输出?1?1。
示例1
输入
复制
3
6 3
10 10
10 1
输出
复制
5
1
-1
思维签到。首先特判几种情况，然后注意到每次实际上是少了m - 1个人，但是要注意最后一轮可以有m个人直接走掉且不需要再回来，需要处理一下。
#include
#include F. 中位数切分
链接：https://ac.nowcoder.com/acm/contest/23106/F
来源：牛客网
题目描述
给定一个长为nn的数组aa和一个整数mm，你需要将其切成连续的若干段，使得每一段的中位数都大于等于mm，求最多可以划分成多少段。
我们定义，偶数个数的中位数为中间两个数中较小的那一个，奇数个数的中位数就是正中间的数。如[2,3,1,5][2,3,1,5]的中位数为22，[2,3,1,2][2,3,1,2]的中位数为22，[3,5,9,7,11][3,5,9,7,11]的中位数为77。
输入描述:
输入第一行是一个整数T(1≤T≤20)T(1≤T≤20)，测试组数。每个测试第一行是两个整数n,m(1≤n≤105,1≤m≤109)n,m(1≤n≤105,1≤m≤109)，含义如题目所示。
第二行输入nn个数，数组aa，满足1≤ai≤1091≤ai≤109。
由于本题输入量较大，建议使用scanf等高效输入方式。
输出描述:
每个测试用例，输出一个整数，表示最多可以划分成多少段，若无论如何划分都不能满足条件，输出?1?1。
示例1
输入
复制
4
5 4
10 3 2 3 2
5 3
5 2 3 3 2
2 5
4 5
5 2
10 3 2 3 2
输出
复制
-1
1
-1
5
首先容易判断无解的情况即超过m的数小于等于floor(n / 2)，因为此时不管怎么分总会有一段中大于等于m的数小于等于段长一半。其他情况一定有解，且解为大于等于m的数的个数减小于m的数的个数（这些数每个数添加到一个两类数相等的段，使得这些段的大于等于m的数的个数严格大于小于m的数的个数）。
#include
#include H. 牛牛看云
链接：https://ac.nowcoder.com/acm/contest/23106/H
来源：牛客网
题目描述
就像罗夏墨迹测试一样，同一片形状的云在不同人的眼中会看起来像各种各样不同的东西。
例如，现在天上飘过了一片长条状的云彩，hina说这片云长得像是薯条，moca说这片云长得像宾堡豆沙面包（5枚装），kasumi说这片云在闪闪发光，kokoro说这片云怎么看上去不开心呢，牛牛说这片云长得就像是：
Σi=1nΣj=in∣ai+aj?1000∣Σi=1nΣj=in∣ai+aj?1000∣
现在给出整数序列aa，请你帮牛牛求出这个式子的值。
输入描述:
第一行包括一个整数n(3≤n≤106)n(3≤n≤106)，整数序列的长度。第二行输入nn个以空格分隔的整数ai(0≤ai≤1000)ai(0≤ai≤1000)，表示序列aa。
输出描述:
输出一个整数，表示该式子的值。
示例1
输入
复制
4
500 501 500 499
输出
复制
8
正解貌似是1e3*1e3的n^2算法 ，比赛时写的1e6带log的树状数组。。。
首先遍历a数组，每到一个位置i则计算这个位置a[i]和之前各个位置a[j]的贡献，用树状数组维护1到1000 - a[i]的这些数的和，然后sum减去这个就是所有和a[i]加起来超过1000的那些a[j]的和，其中sum是到i的前缀和。分别计算完后更新答案即可。特别注意a[i]有可能为0，但是树状数组不太方便处理0的情况，因此单独维护一个变量zero表示1到i - 1的0的数量。细节见代码。
#include
#include I. B站与各唱各的
链接：https://ac.nowcoder.com/acm/contest/23106/I
来源：牛客网
题目描述
最近炸鸡块君在逛B站时发现了有趣的视频（ https://www.bilibili.com/video/BV1MR4y1H7NV ），这种视频被称作"各唱各的"挑战，基于此，炸鸡块君提出了一种有趣的"各唱各的"游戏，其具体规则如下：
有nn位UP主在翻唱一首共mm句的歌曲；
nn个UP主先各自独立的在不能与其他UP主交流的情况下录制一份唱歌的音频。对于这首歌中的每一句，每个UP主可以选择唱或不唱；
在所有UP主都录制完成后，将这nn份唱歌的音频合到一起。若在合成后的音频中，某一句歌词所有人都没唱或同时被所有人都唱了，则认为这句唱失败了，否则认为这句唱成功了。
现在，炸鸡块君想知道：假设这nn位UP主都足够聪明，每位UP主都精通编程且有一台计算速度无限快的超级计算机，但UP主之间不能交流，他们的目标是让成功唱出的句子数尽可能多，求期望唱成功的句子数量对109+7109+7取模的结果。
输入描述:
输入第一行是一个整数T(1≤T≤104)T(1≤T≤104)，测试用例的组数。每组测试用例包括两个整数n,m(1≤n,m≤109)n,m(1≤n,m≤109)，含义如题面所述。
输出描述:
对于每组样例输出一个整数，表示答案对109+7109+7取模的结果。若你的答案是一个形如pqqp的分数，则应输出p×q?1p×q?1对109+7109+7取模的结果，之中q?1q?1表示qq在模109+7109+7意义下的逆元。
示例1
输入
复制
1
1 100
输出
复制
0
这个题纯纯的无语。。比赛时过的人前中期一直很少导致以为这是复杂的概率期望，后来发现是签到难度。
容易知道每句歌词之间互不影响，而每一句歌词成功的概率是\(1-\frac{1}{2^n}\times 2=\frac{1-2^{n-1}}{2^{n-1}}\)，总的成功歌词的期望数再乘上m，快速幂求一下拟元即可。
#include
#include J. 小朋友做游戏
链接：https://ac.nowcoder.com/acm/contest/23106/J
来源：牛客网
题目描述
牛牛是一个幼儿园老师，他经常带小朋友们一起做游戏。
现在，牛牛的班里有AA个安静的小朋友和BB个闹腾的小朋友，牛牛想要从中选出恰好nn个人来做游戏。这个游戏需要小朋友们手拉手围成一个圆圈，但不妙的是，如果两个闹腾的小朋友在圆圈中紧挨着，他们就会打闹，导致游戏无法进行。
每个小朋友还有一个幸福度vv，若这位小朋友被选中参加游戏，则会使得班级的幸福度增加vv。
请你求出，在满足上述所有限制的情况下，恰当的安排围成圆圈的方法，能使得班级的幸福度最大为多少。
输入描述:
输入第一行是一个整数T(1≤T≤103)T(1≤T≤103)，测试数据组数。
每组测试数据，第一行是三个整数A,B,n(2≤A,B≤104,3≤n≤A+B)A,B,n(2≤A,B≤104,3≤n≤A+B)，含义如题目所示。
第二行是AA个数，第ii个数vai(1≤vai≤104)vai(1≤vai≤104)表示某位安静小朋友的幸福度。
第三行是BB个数，第ii个数vbi(1≤vbi≤104)vbi(1≤vbi≤104)表示某位闹腾小朋友的幸福度。
此外，保证所有测试数据的(A+B)(A+B)之和不会超过2?1052?105。
输出描述:
每组测试用例，输出一行一个整数，表示最大幸福度。若无论如何安排都不能进行游戏，输出?1?1。
示例1
输入
复制
3
3 6 7
1 3 4
5 4 3 4 3 5
4 6 7
1 3 4 1
5 4 3 4 3 5
7 7 7
1 2 3 4 5 6 7
9 8 7 6 5 4 3
输出
复制
-1
23
46
贪心，就是分奇偶先选一半或者一半+1的最大的那部分a（这样能保证把b间隔开），然后剩下的从两边贪心选最大的即可。
#include
#include L. 牛牛学走路
链接：https://ac.nowcoder.com/acm/contest/23106/L
来源：牛客网
题目描述
牛牛小朋友最近在学走路，由于牛牛的年龄尚小，只能在父母的指引下在二维坐标系里走路。
父母的指引是一个长为nn且只含有大写的UDLR四种字母的字符串，四种字母的含义为：
U表示牛牛的y坐标加一；D表示牛牛的y坐标减一；R表示牛牛的x坐标加一；L表示牛牛的x坐标减一。
现在，牛牛会完整的按照父母的指引从头到尾走一遍，求牛牛在走的全过程中距离初始位置的最远距离，二维坐标系中两点的距离定义为连接两点的线段长度。
输入描述:
输入第一行是一个整数T(1≤T≤100)T(1≤T≤100)，测试用例的组数。
每个测试用例的第一行是一个整数n(1≤n≤1000)n(1≤n≤1000)，父母的指引的长度；第二行是一个长为nn的字符串，保证只含有UDLR四种大写字母。
输出描述:
对于每个用例，输出一个小数表示答案，输出数字与答案的相对误差小于10?610?6以内都算正确。
示例1
输入
复制
3
4
LLLR
4
ULLD
5
LUDDL
输出
复制
3.000000000000
2.236067977500
2.236067977500
纯签到。
#include
#include