哈喽

Hello!昨天是六一儿童节，可在雅安接连发生了6.1、4.3级地震。我在成都，虽然我没感觉到，但我们学校都通知我们应急疏散。

额——似乎扯远了。上次我发了ACC-C++组初赛的真题，上周就比了决赛，满分600分，我只得了370分，我走的时候最高只有590分，听说到最后的时候最后一道题全成都参加比赛的400多个人没有一个人做出来。

好了，进入正题。

真题

题目一——圈地盘

描述

小函和朋友在游乐园玩耍，发现了一个非常有意思的项目。

项目的玩法是这样的，每人手中有一根长度一样的绳子，用这根绳子可以绕成一个矩形，这个矩形就是自己的“地盘”。聪明的你肯定知道，围成正方形时候的”地盘“最大。

给定绳子长度n，求出其围成正方形的面积是多少。

输入

一个正整数n表示绳子的长度（10<=n<=10000，保证n是4的倍数）

输出

一行，一个数字，表示用给定长度的绳子围成的正方形的面积

输入样例 1

12

输出样例 1

9

思路点拨

这道题考验的是基础的输入输出。
#include <iostream>
using namespace std;
int main(int argc, char **argv)
{int n;cin >> n;cout << (n / 4) * (n / 4) << endl;return 0;
}

题目二——门票

描述

现如今的疫情反复无常，严重影响了大众的收入和消费。现某游乐园决定对门票做一次折扣活动。

每个账号限购20张门票。一张门票的售价为15元，现在全部半价出售，并在半价基础之上再次进行折扣活动。

折扣活动规则如下：若购买数量不超过5张打9折；超过5张打85折。

小函准备通过小程序购买n张门票，问：小函购买门票一共花费多少钱？

输入

输入一个正整数n，即小函需要购买的门票数量n,1≤n≤20。

输出

一行，小函总共花费的钱。

保留2位小数输出

输入样例 1

5

输出样例 1

33.75

输入样例 2

10

输出样例 2

63.75

提示

样例1说明：

小函购买的门票数量是5，需要的总花费=7.5*5*0.9=33.75

样例2说明：

小函购买的门票数量是10，需要的总花费=7.5*10*0.85=63.75

思路点拨

这道题考察的是if 判断语句的使用。根据题意，应分为门票数少于五张和大于等于五张两种情况。
#include <iostream>
using namespace std;
int main(int argc, char **argv)
{int n;float m;cin >> n;if (n <= 5){m = n * 7.5 * 0.9;}else{m = n * 7.5 * 0.85;}printf("%.2f", m);return 0;
}

题目三——免单挑战

描述

小函和好朋友去游乐园游玩，他们非常钟爱过山车项目，但是过山车项目的价格很贵。

正好今天是免单活动日，只要能够快速准确的回答出[n, m]范围内5的倍数的累乘之积即可获得免单。

（[n,m]表示n~m之间，包括n与m）

输入

两个正整数n、m(1<=n<m<=50)，保证其中一定有5的倍数。

输出

一行，表示[n, m]范围内5的倍数的数字之积

输入样例 1

10 20

输出样例 1

3000

思路点拨

这道题考察的是for 循环语句，是阶乘的变体，只用在阶乘的基础上进行一个判断。
#include <iostream>
using namespace std;
int main(int argc, char **argv)
{int n, m;long long ans = 1;cin >> n >> m;for (int i = n; i <= m; i++){if (i % 5 == 0)ans *= i;}cout << ans << endl;return 0;
}

题目四——逃脱

描述

小函和好朋友正在游乐园体验“大逃亡”游戏，游戏场地是临时搭建的“玲珑塔”。在塔中心的位置放置着任务卡。其描述如下：想要从塔中顺利逃出，要根据以下描述解出生门密码。

密码是一个正整数，并且这个正整数最多只有2、3、5、7四种质因子，不会再有其他质因子（1一种质因子也没有，也符合要求）。例如630符合要求，而22不符合。

根据屏幕上随机显示的数字n，计算出第n个符合要求的密码。如n=30，应输出49。

规定符合密码要求的数字不超出长整型数的范围。

输入

一个正整数n，含义如题目描述，n ≤ 10000。

输出

一个符合密码要求的正整数。

输入样例 1

1

输出样例 1

1

输入样例 2

30

输出样例 2

49

提示

数据范围

70% 的数据满足 n≤100。

100% 的数据满足 n≤10000。

思路点拨

这道题我是用的暴力枚举，即一个一个去试，试到正确的密码时把它存储下来，最后再输出存储的这个值。
#include <iostream>
using namespace std;
int main(int argc, char **argv)
{int n, temp, ans, index = 0;cin >> n;for (int i = 1; index < n; i++){temp = i;while (temp % 2 == 0){temp /= 2;}while (temp % 3 == 0){temp /= 3;}while (temp % 5 == 0){temp /= 5;}while (temp % 7 == 0){temp /= 7;}if (temp == 1){ans = i;index++;}}cout << ans << endl;return 0;
}
但这种方法可能会超时。在返校后，老师又给我们讲了另一种解法，但涉及了一个概念——丑数。

这其实就是一道丑数的变体。这道题不用像百度一样用队列。我们把题中的“丑数”称为“丑数2”（这个名字有点low），只用根据两个丑数2相乘的积一定是丑数2来完成（但其实我也没听懂）。

这道题的代码我不知道我放哪儿去了，有兴趣的可以试着做一下，反正我们后面还要再讲一遍这道题。

题目五——一夫当关

描述

小函和朋友们进行分组对抗，两方根据给定的地图路线一攻一守。其中进攻的一方从地图的出发点开始，目标是沿着某条路线能够达到守方的终点。起点到终点之间有 n-2 个路口，分别标上号，起点为 1 号，终点为 n 号，路口分别为 2…n-1 号，从起点到终点有很多条路径可以到达。

小函现为守方，他想能守在某个非起点终点的路口，使得攻方的人无论选择哪条路线都不能到达终点，即形成“一夫当关，万夫莫开”之势。

你能帮助小函找出他可以在哪些路口“一夫当关”吗？

输入

第一行两个用空格隔开的整数 n（3≤n≤2000）和 e（1≤e≤8000）。分别表示起点、终点、路口的总数，以及地图的路线总数。

接下来从第 2 到第 e+1 行，每行两个用空格隔开的整数 p 和 q，表示路口 p 和 q 之间有路径直达。

输入数据保证所求路口一定存在，并且每个路口都和起点、终点能够连通。

输出

第一行一个整数 m，表示所求路口的数目。

第二行按从小到大的顺序依次输出每个所求路口的编号，每两个数之间用一个空格隔开。

注意：不包括起点和终点。

输入样例 1

6 6

1 2

2 4

2 3

3 5

4 5

5 6

输出样例 1

2

2 5

提示

样例解释

按照样例可得如下的地图，1为起点，6为终点，其中小函守在2、5两个路口可以形成“一夫当关”之势。

数据范围

30% 的数据满足 3≤n≤50,1≤e≤50。

60% 的数据满足 3≤n≤500,1≤e≤2000。

100% 的数据满足 3≤n≤2000,1≤e≤8000。

这道题我没做出来，但好像可以用DFS完成。

题目六——游乐场

描述

小函在游乐园玩耍，游乐园有很多游乐项目。第 i 个项目从 ti 时刻准时开放，总共时长为 si，如果参与了第 i 个项目，则当前积分变为 ci（是积分的数值，不是积分的增长值）。

有 N 种游乐园观光车，每种观光车数量不限，每种观光车的运行时长为 ai，乘坐观光车需要你的积分达到 qi（>=qi）才可以。在每个时刻你可以选择玩游乐项目、休息、乘坐观光车，如果选择玩项目则必须花费 si 时间完整体验，如果选择乘坐观光车必须花费完整的 ai 时间（即必须全程玩该项目或乘该趟车不能中途上下）。同一时刻只能体验一次项目或者乘坐一次观光车。而且游乐园有规定，在 T 时刻后必须出园（部分游乐项目可以在 T 时刻后结束）。求在时限内最多可以乘坐几次观光车。在刚开始时，你的积分为1，时刻为1。

输入

第一行三个整数 T，M，N，T表示总时间，有 M 个项目，有 N 类观光车。

接下来 M 行每行三个整数 ti，si，ci。

接下来 N 行每行两个整数 ai，qi。

输出

共一行，一个整数，表示时限内最多可以乘坐几次观光车。

输入样例 1

10 1 2

3 2 5

4 1

1 3

输出样例 1

6

提示

样例解释

在时刻3之前休息。

在时刻3开始参与游乐项目1号，用时2结束，此时为时刻5，此时积分值为5。

在时刻5开始选择观光车2号，每次乘车用时1，则在结束时刻10之间可以乘车6次。

数据范围

20%的数据满足 M,N<=4, T<=15。

50%的数据满足 M<=100,N<=1000，T<=1000。

100%的数据满足 M<=1000，N<=100000，T<=100000，1<=ci<=100，1<=ai、ti<=T。

这道题是动态规划，也没做出来。