2021-11-28 09:00:00 至 2021-11-28 14:00:00
时长: 5小时

第一题：
A Greeting from ACM/ICPC Lab
题目描述
欢迎大家参加2021年山东大学程序设计竞赛新生挑战赛。

有一条公式说到：程序=算法+数据结构。由此可见，算法和数据结构是一个程序必不可少的灵魂。

那么有人会问了：我在哪里可以学到这些东西呢？一方面是在后续的课程中，会有这方面的课程。另一方面就是ACM/ICPC实验室了。

在说实验室之前，我们首先来说说ACM/ICPC比赛是什么。

国际大学生程序设计竞赛（英文全称：International Collegiate Programming Contest（简称ICPC））是由国际计算机协会（ACM）主办的，一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。经过近40年的发展，ACM国际大学生程序设计竞赛已经发展成为全球最具影响力的大学生程序设计竞赛。

在此之外还有CCPC，CCPC是中国大学生程序设计竞赛（China Collegiate Programming Contest， CCPC）是由教育部高等学校计算机类专业教学指导委员会主办的面向全国高校大学生的年度学科竞赛，旨在激发学生学习计算机领域专业知识与技能的兴趣，鼓励学生主动灵活地运用计算机知识和技能解决实际问题，有效提升算法设计、逻辑推理、数学建模、编程实现和计算机系统能力，培养团队合作意识、挑战精神和创新能力。CCPC大部分赛站中都有240支队伍参加比赛，其中排名前10%的可以获得金牌，排名10%到30%可以获得银牌，排名30%到60%可以获得铜牌，其余选手可以获得荣誉奖。

在XCPC（CCPC和ICPC的统称）比赛期间，每队由至多3名队员组成。每队使用1台电脑需要在5个小时内使用C/C++、Java和Python中的一种编写程序解决10到14个问题。程序完成之后提交评测机运行，运行的结果会判定为正确或错误两种并及时通知参赛队。

说完了比赛，我们来说说实验室。

ACM/ICPC实验室是一个大家一起学习算法，参加比赛，提升自己的地方。目前实验室的地址在科研楼121。实验室将会定期举办讲座，给大家介绍一些ACM/ICPC常见的数据结构与算法。实验室也会定期举办练习赛，以提高大家的编程与算法能力。

实验室取得过很多成就，比如在刚刚结束的CCPC广州站比赛中，山东大学队伍“樱花猪开喵喵车创大白熊”队就以及其优异的表现在区域赛中脱颖而出，在230支队伍中取得了第17名。

实验室的负责老师是鹿老师，他不仅以实际行动促进实验室的发展，同时也关心着实验室的每一位成员。他的课程同样生动有趣，譬如在之前开设的“众智科学与网络化产业”，就以活跃的课堂氛围和优秀的教学质量饱受好评。

实验室也有许多优秀的学长，他们会在你们学习算法的路上帮助你们指点迷津，帮助你们成为ACM/ICPC比赛的大牛。

但在这之前，写不完作业的cwc找到了你，给了你下面几个问题，希望你可以给他解答一下：

1.XCPC比赛一个队伍可以最多拥有（ ）人，可以使用（ ）台电脑？
A：3，3 B：3，1 C：4，1 D：4，4
2.下面哪些语言是XCPC比赛不可以使用的？
A：C++ B：python C：Java D：Matlab
3.队伍“樱花猪开喵喵车创大白熊”队在CCPC广州站获得的奖牌是？
A：金牌 B：银牌 C：铜牌 D：荣誉奖
4.实验室的地址是？
A：教学楼3区109 B：实验楼126 C：科研楼121 D：科研楼126
输入描述:
本题没有输入。
输出描述:
请输出四行，每行一个大写字母，代表每个选择题的答案。
备注:
注意是大写字母

第二题
百廿山大
题目描述
东临黄海，南望泰山。1901年，山东大学秉章程办学，开中国近代高等教育之先河。承齐鲁文脉，为天下储人才；融中西学术，为国家图富强。
2021年10月15日，山东大学迎来120周年华诞，很快，话题 #山东大学120周年校庆# 冲上微博热搜榜。

恰巧就在今年，米咔的妹妹米啾也考上了山东大学，她对学校的百廿华诞从心里感到开心。看到微博上一条条对学校的祝福更是幸福感倍增。 
在这时，米啾在网站上看到了一篇英文的文章，这也是一篇对sdu祝福的文章，但是细心的她发现文章里有很多字符串 ‘sdu120’ 。热爱学校的她准备数一下这篇文章里面字符串 ‘sdu120’ 的数量，但是这篇文章实在是太长了，于是她把文章中的空格和标点符号都去掉后转交给你，想要让你帮忙编写一个程序数一下文章中字符串 ‘sdu120’ 的数量。 

输入描述:
第一行一个整数 n (1<=n<=1000)，表示这个字符串的长度。
第二行一个字符串 str 。
输出描述:
输出str中字符串 ‘sdu120’ 的数量。
示例1
输入
21
happybirthdaytosdu120
输出
1
备注:
数据保证str中只包含小写字母和数字。

第三题
题目描述
小Z喜欢数学，为了成为数学皇冠上的明珠，他开始研究数论。

这天小Z发现了这样一个函数f(x)f(x)f(x)，表示xxx的次大质因数，重复的质因数计算多次，比如f(6)=f(2×3)=2,f(8)=f(23)=2f(6)=f(2\times 3)=2,f(8)=f(2^3)=2f(6)=f(2×3)=2,f(8)=f(23)=2。特殊的，f(1)=0f(1)=0f(1)=0，对于任一质数p，f§=1f§=1f§=1。

小W看到后对小Z的发现感到惊奇，于是写下来这样一个式子，并希望小Z计算：

∑i=1n∑j=1nf(gcd(i,j))k\sum_{i=1}^n \sum_{j=1}^n f(gcd(i,j))^k∑i=1n∑j=1nf(gcd(i,j))k

其中gcd(i,j)gcd(i,j)gcd(i,j)表示i和j的最大公约数。

遗憾的是，小Z并不会计算这个式子，为了继续成为数学皇冠上的明珠，小Z向你求助，希望你能计算出这个式子的值。

由于答案可能很大，你只需要告诉小Z式子的值对2^32取模的结果。（可以理解为直接使用unsigned int类型进行计算）
输入描述:
共一行两个整数n和k。
输出描述:
一行一个整数，表示答案。
示例1
输入
3 1
输出
2
示例2
输入
340 25
输出
437389068
备注:
对于所有数据1\le n,k \le 2\times 10^91≤n,k≤2×109

第四题
合理分配
题目描述
实验室负责人 L 学长要毕业啦！
众所周知，ACM 实验室空间比较小，作为他的 好 学 弟 ，小 W 想尽可能多地占用 L 学长毕业后空出来的空间。
但是小 W 的队友小 Z 也希望分一部分，因此不同意他独占这部分空间，所以小 Z 选定了一个位置，允许小 W 先选一个连续的矩形部分，不能包含小 Z 选定的位置。
形式化的，L 学长的桌子是一个 a×ba\times ba×b 的矩形，行列的编号分别为 [0,a−1][0,a-1][0,a−1] 和 [0,b−1][0,b-1][0,b−1]，小 Z 选定了一个位置 (x,y)(x,y)(x,y)，小 W 想找到最大的子矩形，不能包含 (x,y)(x,y)(x,y) 这个点，现在请聪明的你告诉他，他能霸占的最大面积是多少。
输入描述:
一行，包含四个正整数，a,b,x,ya,b,x,ya,b,x,y
数据范围满足 1≤a,b≤1041\le a,b\le 10^41≤a,b≤104，0≤x<a0\le x<a0≤x<a，0≤y<b0\le y<b0≤y<b
输出描述:
输出一个正整数，表示最大面积

示例1
输入
8 8 0 0
输出
56

示例2
输入
2 3 1 0
输出
4

示例3
输入
10 10 4 8
输出
80

第五题
自此开始签到
题目描述
2021年的山东大学新生赛格外的隆重，不仅规模大，而且还招募了大量志愿者来给选手发放气球。热心的小祎报名成为了志愿者，现在由他负责你所在的机房气球的分发。根据学校要求，每个同学每过一道题都要发放一个气球。由于参赛人数太多，一个一个的发放对于小祎来说太累了。所以他打算等到比赛结束再发放气球。他发放时会沿着一列或一行从头走到尾。现在他想要知道每行与每列需要多少气球。
为了便于统计，小祎将机房看为一个二维平面， 每个机位的坐标都为正整数。具体的说，有nnn行mmm列电脑。整场比赛共有QQQ次过题，第iii过题的同学所在的机位坐标为(xi,yi)(x_i,y_i)(xi,yi)。最后请你输出每行每列各需要多少个气球。
输入描述:
第一行输出三个正整数n,m,Qn,m,Qn,m,Q表示机房共有nnn行mmm列电脑,整场比赛有QQQ次过题。
接下来QQQ行，每行两个正整数(x,y),(1≤x≤n,1≤y≤m)(x,y),(1\le x \le n,1\le y\le m)(x,y),(1≤x≤n,1≤y≤m)，表示第xxx行第yyy列的机位的同学通过了一道题。
输出描述:
输出共两行，
第一行nnn个整数，第iii个整数表示第iii行需要的气球数量。
第二行mmm个整数，第iii个整数表示第iii列需要的气球数量。
示例1
输入
2 2 4
1 1
1 1
1 2
2 1
输出
3 1
3 1
备注:
1≤n,m,Q≤1051\le n,m,Q\le 10^51≤n,m,Q≤105
1≤x≤n,1≤y≤m1\le x \le n,1\le y \le m1≤x≤n,1≤y≤m

第六题
寻回数列
题目描述
小祎期中考试遇到了一道数学题，原题如下
给出一个长度为n的非负数列a，记数列中第i个数字为aia_iai。请你求出任意一个x满足：xa1=∑i=2nxaix^{{a_1}=\sum\limits_{i=2}}nx^{a_i}xa1=i=2∑nxai
这对于小祎来说实在是太简单了，他很快就写出了x的值。
考试结束之后，小祎与同学交流起来这道题，可是他们都记不起原题中的数列a是什么样子的，不过他还记得答案X的值。
现在请你凭借你过人的智慧，构造出任意一个符合条件的数列a，使其满足上式。
你的输出需要保证0≤ai≤n0\le a_i\le n0≤ai≤n

输入描述:
输入共一行两个用空格隔开的正整数n,x。含义见【题目描述】
输出描述:
输出共一行n个用空格隔开的正整数,第i个数字表示aia_iai。
当你输出多于n个数字时，只有前n个数字有效。
如果有多种答案，你只需要输出任意一种
输入保证有解。
示例1
输入
12 6
输出
2 0 0 0 0 0 0 1 1 1 1 1
说明
62=60+60+60+60+60+60+61+61+61+61+61=366²⁼⁶0+6⁰⁺⁶0+6⁰⁺⁶0+6⁰⁺⁶1+6¹⁺⁶1+6¹⁺⁶1=3662=60+60+60+60+60+60+61+61+61+61+61=36
备注:
2≤x<n≤1062 \le x < n \le 10^62≤x<n≤106

第七题
士兵过河
题目描述
在一条河的中间有一个长为L的独木桥，有N个士兵在这个桥上。这些士兵希望通过独木桥到河的一边，但这条桥太窄了，导致两个士兵不能并排行进，也不能交错而过。
他们想到了一个方法：每个人都以每单位时间移动一个单位距离的速度不断向前进，当迎面碰到另一个人时，两个人都将立即掉头并继续前进。现在，士兵想知道自己是否到河岸，如果能他们还希望知道自己到河岸所花的时间。为了方便，我们按初始时位置从东到西的顺序对士兵从 1开始编号。
输入描述:
输入的第一行包含两个正整数 N，L保证 N<=1e5，l<=1e9且N<L 。
输入的第二行包含N个正整数，第 i 个数 pi 表示第 i 个士兵到东侧河岸的距离，保证 pi 随 i 增大严格递增，且 0<pi<L。
输入的第三行包含 N个整数，第 i 个数di 若为 1 则表示第 i个士兵一开始朝向西侧，为 0 则表示朝向东侧。
输出描述:
输出仅一行，包含 N 个数，第 i个数表示第 i 个士兵到达河岸所花时间，四舍五入保留到整数。若第 i 只士兵无法爬下绳子，则输出的第 i个数为 -1。
示例1
输入
3 6
1 3 5
1 1 0
输出
5 5 3
说明
在第一秒，二号士兵和三号士兵在位置4相遇，接着二者转向，两秒后，三号士兵到岸边，在第二秒，一号士兵和二号士兵在位置三相遇，二者转向，接着，三秒后，一号士兵和二号士兵同时到达岸边。

第八题
hyc追求女神
题目描述
hyc有一个钦慕已久的女神，可惜女神总是对hyc爱答不理。hyc想到一个可以和女神搭话的办法。由于女神是纸片人，女神只能在一个数轴上移动，并且女神每次出门，会准备N个不相同的正整数，每次女神会选择其中一个数k，并从位置x跳跃到位置x+k，每个数只能选择一次。女神会从位置0开始一直移动直到选完N个数。hyc会准备N-1个玫瑰，放在女神会经过的路径上的一些位置(hyc武德充沛，不会把玫瑰放在女神经过路径的起点和终点)。如果女神会跳到这个位置（不是从空中经过），就会捡到hyc的玫瑰，然而女神不想捡到hyc的玫瑰，于是，她想请你帮忙解决这个问题。
输入描述:
第一行输入一个数N，2<=N<=100000
第二行输入N个正整数，第i个表示女神准备的数 Xi，保证每个数小于等于100000且各不相同
第三行输入N-1个正整数，第i个表示hyc放玫瑰的位置ai，对于
s=∑i=1Nxis=\sum_{i=1}^{N}{x_{i}}s=∑i=1Nxi
有0<ai<s
输出描述:
若女神有一种选择数的方式，可以不捡到hyc的玫瑰，输出“YES”，否则输出“NO”
示例1
输入
3
1 2 3
1 2
输出
YES
说明
女神可以选择[3 1 2]这种方式

第九题
通关
题目描述
一个01序列，体力为0，从起点出发，遇0-1，遇1+1，保证最后可以到达终点，但是在过程中，可能会出现体力值为负的情况，为了避免这种情况，可以先选择一点，从该点出发到达终点，并保存当时的体力，然后重新从起点出发，走到所选择的点的前一点，请给出所选起点（若有多种答案，输出一种即可）
输入描述:
第一行输入n，表示序列长度为n
第二行输入连续的n个数
1<n<1e5
输出描述:
输出一个数字
示例1
输入
5
0 0 1 1 1
输出
3

第十题
gcd

题目描述
两个长度为n（n<=1e5）数组a,b,
对于每个i,输出gcd(a[1]*b[i],a[2]*b[i],…,a[n]*b[i]);
输入描述:
第一行输入n
第二行输入连续的n个数字，为a数组
第三行输入连续的n个数字，为b数组
（n<=1e5,1<=ai,bi<=1e9）
输出描述:
输出n行，每行一个数字
示例1
输入
3
6 10 12
3 10 5
输出
6
20
10
备注:
gcd是最大公因子，指两个或多个整数共有约数中最大的一个。eg:gcd(21,36)=3

gcd的java求法：

static int gcd(int x,int y){
if(y==0)return x;
return gcd(y,x%y);
}

第十一题
Yzh的旅行计划
题目描述
T国度是一个奇怪的国家，现在Yzh踏上了这个国家。

Yzh发现这个国度一共存在n个城市，存在n-1条道路连接n个城市，使得T国形成一棵树形结构。T国的1号城市为树的根节点。
Yzh发现，T国的是一个风景优美的国家，T国居民也是喜欢旅行的居民，基于热爱旅行的传统，T国的旅行者协会为每个城市进行了评价，并计算出每个城市的风景得分wiw_iwi。这里我们认为如果两个城市的风景得分相同，那么这两个城市的风景是一模一样的。

Yzh还发现除了城市有风景得分，这些充满智慧的居民有固定的旅行计划：

1. 居民会选择一棵子树进行旅行，他会在这个子树的城市中选择部分城市旅行。
2. 每个居民都有自己的期望风景值xxx，他只会在城市风景得分大于自己期望值的城市旅行。
3. 在旅行结束后，居民会对每一个风景得分yyy，统计其被居民访问的次数。如果风景得分y一共出现奇数次，那么他会感到快乐，并且对于这个风景得分的快乐值为 x⊗yx \otimes yx⊗y。否则，不会有快乐值。
   现在T国的居民想要询问自己的一次旅行的快乐值之和。Yzh将这个问题抛给了你。
   具体的，每次询问会有给出（u，x）表示期望值为x的居民在u子树旅行，请求你计算他的快乐值之和。
   输入描述:
   第一行两个整数n，Q，分别表示T国的城市个数和询问次数。
   第二行n个整数wiw_iwi，表示第i个城市的风景得分。
   第二行到第n行，描述这棵树的形态，每行两个整数，描述一条边u,v。
   接下来q行，每行两个整数u,x，描述一次询问。
   n,Q≤105,1≤x,wi≤n,Q≤105n,Q≤10^5,1≤x,w_i≤n,Q \leq 10^5n,Q≤105,1≤x,wi≤n,Q≤105
   输出描述:
   对于每次询问，输出一个整数表示答案。
   示例1
   输入
   6 5
   2 3 4 2 3 3
   1 2
   2 3
   2 4
   2 5
   1 6
   1 1
   1 4
   2 1
   2 3
   6 1
   输出
   7
   0
   8
   7
   2
   说明
   树的形态如下图所示：
   1、询问(1,1)：子树1中风景得分大于1且出现奇数次的为{3,4}{3,4}{3,4}，答案为(3⊗1)+(4⊗1)=7(3 \otimes 1) + (4 \otimes 1 )= 7(3⊗1)+(4⊗1)=7
   2、询问(1,4)：子树1中风景得分大于4且出现奇数次的为{4}{4}{4}，答案为4⊗4=04\otimes 4 = 04⊗4=0
   3、询问(2,1)：子树2中风景得分大于1且出现奇数次的为{2,4}{2,4}{2,4}，答案为(2⊗1)+(4⊗1)=8(2\otimes 1) +( 4\otimes1) = 8(2⊗1)+(4⊗1)=8
   4、询问(2,3)：子树2中风景得分大于3且出现奇数次的为{4}{4}{4}，答案为4⊗3=74 \otimes 3 = 74⊗3=7
   5、询问(6,1)：子树6中风景得分大于1且出现奇数次的为{3}{3}{3}，答案为3⊗1=23\otimes 1 = 23⊗1=2

第十二题
网站屏蔽
题目描述
最近一段时间，qzy总是在浏览一个奇奇怪怪的网站，每天茶饭不思，这让他的朋友们十分担心，于是他们决定屏蔽这个网站。
众所周知，想要屏蔽一个网站，就必须要知道这个网站的地址。通过一些手段，qzy的朋友们成功找到了他的浏览记录。由于qzy过度沉迷这个网站，因此这个网站在浏览记录中出现的次数是严格大于一半的。现在，他们交给了你一个十分艰巨的任务——从浏览记录中找到这个网址。
输入描述:
第一行包含一个数字N（1≤N≤1.5e5），表示浏览记录的项目数。
接下来N行，每行代表一条浏览记录，这是一个由小写字母和数字构成的字符串。数据保证每个字符串的长度不超过101。
输出描述:
一个字符串s，表示找到的目标网址。
示例1
输入
10
baidu
baidu
oeis
bilibili
oeis
oeis
oeis
oeis
oeis
github
输出
oeis

第十三题
ICPC沈阳I.Linear Fractional Transformation
题目描述
第46届ICPC国际大学生程序设计竞赛亚洲区域赛沈阳站在2021年11月21日如期举行，小Z和小W参加了这场比赛。

他们在比赛中遇到了这样一道题：

存在一个函数f(x)=ax+bcx+df(x)=\frac{ax+b}{cx+d}f(x)=cx+dax+b,现给定x0x_0x0，求f(x0)f(x_0)f(x0)。

小Z和小W使用了复数高斯消元、方程两两相减消二次项等复杂算法，最后得到一个可以输出nan的优秀程序，成功地没有通过这道题。

现在你知道了f(x)f(x)f(x)的表达式和x0x_0x0，请帮助小Z和小W计算f(x0)f(x_0)f(x0)的值。

输入描述:
一行五个整数依次为a,b,c,d,x0a,b,c,d,x_0a,b,c,d,x0。
输出描述:
一行一个数表示f(x0)f(x_0)f(x0)的值，四舍五入保留两位小数。
示例1
输入
1 2 3 4 5
输出
0.37
示例2
输入
25 340 50 437 1010
输出
0.50
备注:
1≤a,b,c,d,x0≤1041\le a,b,c,d,x_0\le 10^41≤a,b,c,d,x0≤104，且a,b,c,d,x0a,b,c,d,x_0a,b,c,d,x0均为整数。

如果您是Java选手，可以使用System.out.printf("%.2f",ans)将double类型的ans保留两位小数输出。