总的来说，这场比赛的题还是比较水的，至少难度什么的甚至没法和热身赛相比。然而这场比赛中不乏需要注意的细节问题，比如unsigned long long出现了好几次什么的。。。在这上面栽了一把。C、H题的分析仍存在问题（还是我菜）。。。暂时不列出。
A. a*b problem
A. a*b problem
时间：1000ms 空间：256mb
【题目描述】给你两个非负整数a和b，你需要输出a*b的值。
【程序输入说明】
第一行输入一个数字T(T<=10)，表示数据组数。
接下来T行，每行两个非负整数a和b。(0<=a,b<2^32)【程序输出说明】
你需要输出T行，每行表示a*b的结果。
【输入样例】
3
4 3
11 2
1 100【输出样例】
12
22
100【提示】
无
分析
看起来这题是道水题，1min写完提交。。。于是您就WA了一发。
仔细看题面：a, b的最大值可以到\(2^{32}\)！这意味着a * b的上限是\(2^{64}\)，这个数远远超出了int甚至long long的上限(int的上限是\(2^{31}-1\)，long long的上限是\(2^{63}-1\))，从而只能用unsigned long long存。用unsigned long long修正后AC。
注意：这道题比较适合用C++做，因为涉及到unsigned long long类型输入输出的问题，用C++的输入输出流会比较方便，另外就是根据已知情况来看用C语言做这道题即使没有任何问题也可能玄学WA。。。
代码
#include <iostream>
using namespace std;
int main() {
ios :: sync_with_stdio(false);
int T = 0;
cin >> T;
while(T--){
unsigned long long a, b;
cin >> a >> b;
cout << a * b << endl;
}
return 0;
}
B. 白学北楼
B. 白学北楼
时间：1000ms 空间：256mb在安微大学有一个教学楼，叫白学北楼，它的侧面图如下：
白学北楼由5栋楼宇拼接构成，每栋楼宇都是5层楼，每层楼有一些教室，教室的编号由一个大写字母和三个阿拉伯数字构成，第一个大写字母是A、B、C、D中一个，表示该教室在哪栋楼，第一个阿拉伯数字表示该教室所在的楼层，第二个和第三个阿拉伯数字表示该教室在该楼层的方位。如A202表示A栋2楼的一间教室，D511表示D栋5楼的一间教室。
比较特殊的是白学北楼有两个B栋，其中数字编号为奇数的教室在B单栋，数字编号为偶数的教室在B双栋，如B207，B511，B101在B单，B100，B502，B312在B双。
有五条走廊连接着这些建筑(如图中红色所示)：在一楼有四个走廊分别串起了五栋建筑，特殊的是，在B单和B双三楼的中间也有一条走廊，这意味着如果从B311教室走到B308教室，就不需要下楼下到B单一楼，再走到B双一楼再上楼了，可以直>接顺着走廊走过去。
Chelly是一个不喜欢上下楼梯的阿宅，所以如果从一个教室走到另一个教室，他>会选择上下楼梯次数最少的路径。如从B401走到B300，他会选择先下一层楼梯，再走B单B双中间的走廊走过去，于是最少的上下楼梯次数就是1次。如从A505走到D311，那别无他法，Chelly只能下到A的一楼，穿过四条走廊，再从D的一楼走楼梯上到三楼，总共需要上下楼梯6次。
今天Chelly要在白学北楼上n节课，按顺序给出Chelly的课的所在教室，你需要回答Chelly总共最少需要上下多少次楼梯？
注意：因为Chelly是一个被宇宙射线射中的人，所以他如果上一节课在B单且下一节课在B双，或者上一节课在B双且下一节课在B单，他一定会走三楼之间的走廊去打水喝。即如果从上一节课教室B100走到下一节课教室B201，他会先上到B双的三楼走走廊过去B单三楼，再下一层楼。所以一共走的次数是3次。但如果上一节课教室是D101，下一节课教室是A101，那么他就不会去打水，直接走一楼走廊走过去，上下楼梯的次数是0.
【程序输入说明】
第一行输入一个数字T(T<=10)，表示数据组数。
每组数据第一行一个数字n(1<=n<=1000)表示Chelly课的数目。
接下来n行每行一个字符串表示教室编号。（保证教室编号合法）。【程序输出说明】
你需要输出T行，每行表示最少需要走楼梯的数目。
【输入样例】
1 4 D222 B201 B442 A111
【输出样例】
7
【提示】
D222 ——> B201 走两次楼梯
B201 ——> B442 走两次楼梯
B442 ——> A111 走三次楼梯
总共需要走7次楼梯
分析
没什么好说的，直接翻译题意便可。
代码
#include <cstdio>
#include <cstring>
#include <cstdlib>
// 将数字字符转化为对应的数字
#define NUM(x) ((x) - '0')
// 求某位数模2的余数（用来比较是奇数还是偶数）
#define OE(x) ((x) % 2)
using namespace std;
const int MAXN = 1010;
char building[MAXN][10];
int main() {
int T = 0;
scanf("%d", &T);
while(T--){
int n = 0;
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%s", building[i]);
int time = 0;
for(int i = 0; i < n - 1; i++){
if(building[i][0] != building[i + 1][0]){
time += NUM(building[i][1] - 1) + NUM(building[i + 1][1] - 1);
} else {
if(building[i][0] != 'B'){
time += abs(NUM(building[i][1]) - NUM(building[i + 1][1]));
} else {
// 如果两间教室都在B单或都在B双
if(OE(NUM(building[i][3])) == OE(NUM(building[i + 1][3]))){
time += abs(NUM(building[i][1]) - NUM(building[i + 1][1]));
} else {
time += abs(NUM(building[i][1]) - 3) +
abs(NUM(building[i + 1][1]) - 3);
}
}
}
}
printf("%d\n", time);
}
return 0;
}
D. 瓶子数列
D. 瓶子数列
时间：1000ms 空间：256mb【题目描述】
瓶子数列是这样的数列:
若a[1..n]满足存在一个i使得a1>=a[2]>=a[3]>=……>=a[i]<=a[i+1]<=a[i+2]<=……<=a[n]
那么就称这个数列a[1..n]是一个瓶子数列。如数列{6,4,3,1,1,1,10,11}就是一个瓶子数列，{1,4,3,2,1,1,3}就不是一个瓶子数列。
现在Alice和Bob在玩一个游戏，Alice偷偷生成一个长度为n的数列a[1..n]，起初Bob对Alice生成的数列一无所知。然后Bob每次可以询问Alice某个位置上的a的值，很明显，Bob询问的次数越多，获得的信息也就越多，当Bob的询问足够多的时候，聪明的Bob就能正确判断出Alice生成的数列a[1..n]是否是瓶子数列了。
现在给出n和Alice生成的数列a[1..n]，你需要回答在最坏的情况下，聪明的Bob需要询问多少次才能判断出a[1..n]是否是瓶子数列。
Bob是很聪明的，如果他获得的信息足以让他判断出是否是瓶子数列，那么他就能准确地判断出来，并且他不会重复询问之前已经询问过的位置。【程序输入说明】
第一行输入一个数字T(T<=10)，表示数据组数。
接下来T组数据，每组数据第一行一个整数n(1<=n<=1000)
第二行n个整数表示Alice生成的数列。(0<=ai<=1000000000)【程序输出说明】
对于每组数据，输出一行，表示Bob最多需要询问的次数。
【输入样例】
2
4
1 1 1 1
7
2 4 1 1 8 1 1【输出样例】
4
6【提示】
对于第一组数据，Bob在把所有位置的数知晓之前，无法判断出是否为瓶子序列。
对于第二组数据，Bob询问6次，在7个位置里选6个位置询问，方案数是C(7,6)=7，即一共有7种询问方法，这7种询问方法都能让Bob可以判定是否是瓶子序列；若询问次数小于6，那么容易发现一定存在一种询问方式使得Bob无法判断，所以在最坏情况下，Bob需要询问6次。
分析
本题是一道动态规划入门题，然而第一次见时确实要花一番功夫思考。下面给出本题详解。
为什么Bob大多数情况下不需要遍历整个数组
很多人刚看到这道题的时候，肯定都会想：Bob难道不需要每一次都把数组里的所有数询问一遍吗？！如果不这么做，要是漏下数怎么办？
且慢，Bob毕竟潜心研究密码学30年，每天都在与Alice洪水般的加密消息作斗争，他岂会让您在知乎上水一篇“我比Bob聪明”系列？Bob拿着 (对您而言) 不完整的信息，就敢断定给定的是不是一个瓶子数列，一定有他的道理。
我们先来看“瓶子数列”指什么：显然瓶子数列指先减后增的单峰数列。如果一个数列不是瓶子数列，就一定有一个峰顶。只要Bob能确认数列中的某个元素是峰顶，立即就能断定这个数列不是瓶子数列。而确定峰顶显然并不需要遍历整个数列。
以题目中的样例二为例：如果Bob直接询问了第五个元素8，那么他只要接着再询问第1个元素即可：第1个元素是2，现在有8 > 2，不符合瓶子数列的定义。于是此时Bob只询问了两次就能判断给定的数列不是瓶子数列。
然而令Bob无可奈何的情况还是有的，请见下文。
Bob什么时候需要询问的次数最多
Bob询问每个数列的位置毕竟是随机选择的，他不能依据已知的信息推断出其他的元素按什么规律分布，从而就不能猜测他下一次询问的元素值的大概范围。因此，如果Bob的运气非常不好，他可能会面临这样一种情况：仍以样例二中数列为例，如果Bob事先声明要询问5次，然后他先后询问了位于7，6，4，3，2号上的元素，即4，1，1，1，1，他已知的元素此时构成一个瓶子数列；然而，除非在询问过程中就找到一个峰顶，否则根据已知的子序列构成瓶子数列来推断原数列就是瓶子数列是不可能的！换句话说，Bob现在确实漏数了。他必须要再访问一个元素，才能为他提供足够的信息：剩下的元素2和8都能让他各确认一个峰顶。
因此，我们可以推断出：
- 如果给定数列是瓶子数列，那么Bob不得不遍历数列的每一个元素。
- 如果给定数列不是瓶子数列，那么Bob最多需要遍历{数列中最长的构成瓶子数列的子数列的长度 + 1}个元素。
怎样帮Bob找到这个子数列
上述推断为我们构造出了状态转移方程的雏形。但是在试图列方程时会面临一个问题：瓶子数列不仅有前半部分，还有第i个元素之后的后半部分，而只列计算前半部分的方程必将忽略后半部分，反之亦然。所以这时我们需要正向和反向各遍历一次。这样列出本题所需的方程就很简单了。
设\(m_{r}(i)\)和\(m_{l}(i)\)分别是以第i个元素为结尾的构成瓶子数列的正向和反向最长子数列的长度，给定数列总长设为n，其第i个元素记作a(i)。显然可以分别列出状态转移方程：
正向情况：
\(m_{r}(1)=1\)
\(m_{r}(i)=max(m_{r}(i),m_{r}(j) + 1) || j=1,2,\cdots,n-1\)且\(a(j)\geq a(i)\)
反向情况：
\(m_{l}(n)=1\)
\(m_{l}(i)=max(m_{l}(i),m_{l}(j) + 1) || j=n,n-1,\cdots,2\)且 \(a(j)\geq a(i)\)
设Bob最多需要询问time次，则有
\(time=m_{r}(i)+m_{l}(i)-1\)
此时找出了Bob最坏情况下将会发现的整个最长子数列的长度。依照上文，如果该长度与给定数列长度相等，则直接输出time，否则输出time + 1。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1010;
int a[MAXN], mr[MAXN], ml[MAXN];
int main() {
int T = 0;
scanf("%d", &T);
while(T--){
int n = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
memset(mr, 0, sizeof(mr));
memset(ml, 0, sizeof(ml));
mr[1] = 1;
for(int i = 2; i <= n; i++){
mr[i] = 1;
for(int j = 1; j < i; j++)
if(a[j] >= a[i])
mr[i] = max(mr[i], mr[j] + 1);
}
ml[n] = 1;
for(int i = n - 1; i >= 1; i--){
ml[i] = 1;
for(int j = n; j > i; j--)
if(a[j] >= a[i])
ml[i] = max(ml[i], ml[j] + 1);
}
int time = 0;
for(int i = 1; i <= n; i++)
time = max(time, mr[i] + ml[i] - 1);
printf("%d\n", time == n ? time : time + 1);
}
return 0;
}
E. 分组
E. 分组
时间：1000ms 空间：256mb【题目描述】
翔老师开了一门抽象代数课程，有n名同学选了这门课。现在翔老师要给这n名同学分组，两人一组，三人一组，四人一组，五人一组，六人一组等等都可以。一个组是good group的当且仅当该组人数>=3人。现在翔老师想知道他要把n名同学分成若干组，最多能有多少个good group。
【程序输入说明】
第一行输入一个数字T(T<=10)，表示数据组数。
接下来T组数据，每组数据一行一个整数n(1<=n<=1000)对于每组数据，输出一行，表示最多能分出多少个good group。
【输入样例】
1
8【输出样例】
2 【提示】
翔老师可以把四个人分成一组，另外四个人分成一组，这样一共有2个good group。
分析
要获取最多的good group，只需要将n名同学尽量分成3人小组便可，即最后good group的数目为n / 3。
(不要受提示的误导)
代码
#include <iostream>
using namespace std;
int main() {
int T = 0;
cin >> T;
while(T--){
int num = 0;
cin >> num;
cout << num / 3 << endl;
}
return 0;
}
F. Operation II
F. Operation II
时间：1000ms 空间：256mb【题目描述】
现在有4个整数n,k,A,B。对于一个数字x，我们可以有以下两种操作：
1、x=x-1
2、x=x/k，要求x是k的倍数
其中第一种操作花费A元，第二种操作花费B元。
现在我们需要把数字n通过若干次的操作变成1，最少需要花多少元呢？【程序输入说明】
第一行输入一个数字T(T<=10)，表示数据组数。
接下来T组数据，每组数据四个整数n,k,A,B(1<=n,k,A,B<=1000000000)【程序输出说明】
对于每组数据，输出一行，表示最少需要花多少元。
【输入样例】
2
9 2 3 1
19 3 4 2
5 5 2 20【输出样例】
6
12
8【提示】
对于第一组数据n=9
首先进行第一种操作：n=n-1=8
再进行第二种操作：n=n/k=4
再进行第二种操作：n=n/k=2
再进行第二种操作：n=n/k=1
花费是3*1+1*3=6
分析
这个题数据量比较大，传统的O(N)均会TLE，应从逐渐除k入手，考虑使用以下的O(logN)算法。
代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1000;
int rem[MAXN];
long long n = 0, k = 0, A = 0, B = 0;
int main() {
ios :: sync_with_stdio(false);
int T = 0;
cin >> T;
while(T--){
cin >> n >> k >> A >> B;
memset(rem, 0, sizeof(rem));
if(k == 1)
cout << (n - 1) * A << endl;
else {
int len = 0;
long long money = 0;
while(n > 0){
rem[len++] = n % k;
n /= k;
}
money += len * B;
for(int i = 0; i <= len; i++)
money += rem[i] * A;
for(int i = len; i >= 1; i--){
long long tmp = money;
tmp -= B;
tmp -= rem[i] * A;
tmp += k * rem[i] * A;
if(tmp < money){
money = tmp;
rem[i - 1] += k * rem[i];
} else
break;
}
cout << money - A << endl;
}
}
return 0;
}
G. 演唱会
G. 演唱会
时间：1000ms 空间：256mb【题目描述】
Chelly要开演唱会了，大家争先恐后地想组成应援团。一共有n个人报名参加，要从中选出6个人作为应援团，选择的这6个人要满足以下规则：一个名字首字母是C的人、一个名字首字母是H的人，一个名字首字母是E的人、两个名字首字母是L的人，一个名字首字母是Y的人(组成“CHELLY”的形状)。那么一共有多少种组团方法呢？
每个人的名字都是不含空格的字符串，其中首字母是大写的。【程序输入说明】
第一行输入一个数字T(T<=10)，表示数据组数。
接下来T组数据，每组数据第一行输入一个n(1<=n<=1000)表示人数。
以下n行每行一个字符串表示每个人的名字。（每个人名字长度不超过20）【程序输出说明】
对于每组数据，输出一行，表示有多少种组团方法。
【输入样例】
1
8
Christina
Utaha
Harada
Emt
Lilly
Loli
Yuuyi
Hasaki【输出样例】
2 【提示】
两种组团方法：
{Christina,Harada,Emt,Lilly,Loli,Yuuyi}
{Christina,Hasaki,Emt,Lilly,Loli,Yuuyi}
分析
该题乍看像是一道单独统计字母个数的水题，而且人数上限1000看起来并不大。但本题的关注点在于：最后输出的结果是相乘而不是相减！
我们假设这样一种情况：在给出的1000个人中，名字为五个首字母之一的人分别各占100人。这样的话结果就是(100 ^ 5) * 99 * (1 / 2)，接近10^12的数量级，超出了int的存储范围！因此long long类型又出现了。将最后输出结果的类型改为long long本题才能AC。
代码
#include <iostream>
#include <cstring>
using namespace std;
char name[30];
int main() {
ios :: sync_with_stdio(false);
int T = 0;
cin >> T;
while(T--){
int n = 0;
cin >> n;
unsigned long long c = 0, h = 0, e = 0, l = 0, y = 0;
for(int i = 0; i < n; i++){
cin >> name;
switch(name[0]){
case 'C': c++; break;
case 'H': h++; break;
case 'E': e++; break;
case 'L': l++; break;
case 'Y': y++; break;
}
}
cout << c * h * e * (l * (l - 1) / 2) * y << endl;
}
return 0;
}