T20200607
题一：答题比赛
【问题描述】
\(YYH\)报名参加了一个特殊的电视问答节目。这个节目共有\(n\)个问题，每回答正确\(1\)题，\(YYH\)就会获得\(1\)分，而每当\(YYH\)连续答对k题，那么他的现有得分乘以\(2\)，注意答对第\(k\)题后，是先加\(1\)分到总分中，再把总分乘以\(2\)，此时连续答对题目计数器会清零。现在\(YYH\)成功对了\(m\)题，他想知道他的最小得分。因为这个数字可能很大，你只需要输出这个数对\(1,000,000,009\)取模的结果即可。
【输入格式】
仅一行，三个数\(n,m,k\)如题目描述。
【输出】
仅一行，一个数，\(YYH\)的最小得分。
【输入输出样例1】
| exam.in | exam.out |
|---|---|
| 5 3 2 | 3 |
【输入输出样例2】
| exam.in | exam.out |
|---|---|
| 5 4 2 | 6 |
【样例解释】
样例\(1\)答对第\(1,3,5\)题可以获得最低分\(3\)分；
样例\(2\)只答错第\(4\)题，可以获得最低分\(6\)分。
【数据范围】
对于\(30%\)的数据，\(n,m,k<=10\)
对于\(60%\)的数据，\(n,m,k<=1000\)
对于\(100%\)的数据，\(1<=k<=n<=10^9，0<=m<=n\)
贪心一下应该就可以了
题二：人类基因组
【问题描述】
\(L\)教授最近正在研究一个关于人类基因的项目，基因可以被看作一个长度为\(n\)的序列 \(A_1,A_2,\dots,An\): 。对于这个基因序列循环移动\(k\)位之后，就可以得到一个新的基因序列为：\(A_k,\dots,A_1,A_2,…,A_k\) 。当一个基因序列满足对于任意的前\(i(1<=i<=n)\)项和都满足不小于 \(0\)，我们就称这个基因序列为优质基因序列。
由于\(L\)教授最近工作比较繁忙，所以找到了正在实验室闲逛的你，你的任务就是帮\(L\)教授统计出所有优质基因序列的个数。
【输入格式】
第一行一个整数\(n\)，表示基因序列的长度。 第二行\(n\)个整数，依次为\(A_1,A_2,......,A_n\)的值。
【输出格式】
输出仅一个整数，表示优质基因序列的个数。
【输入输出样例1】
| genes.in | genes.out |
|---|---|
| 3 2 2 3 |
3 |
【样例1说明】
\(3\)个元素的序列：\(2\;2\;3\)，循环移动情况如下： 循环移动0位得到序列：\(2\;2\;3\)，前\(i\)项和分别为：\(2\;4\;7\)，符合条件； 循环移动1位得到序列：\(2 \;3 \;2\)，前\(i\)项和分别为：\(2\;5\;7\)；符合条件； 循环移动2位得到序列：\(3 \;2 \;2\)，前\(i\)项和分别为：\(3 \;5 \;7\)；符合条件；
【输入输出样例2】
| genes.in | genes.out |
|---|---|
| 5 3 -1 2 -3 4 |
2 |
【数据范围】
对于\(30%\)的数据，满足$1<=N<=5,000 $ 对于\(50%\)的数据，满足$1<=N<=10,000 $ 对于\(100%\)的数据，满足$1<=N<=1,000,000，-1,000<=Ai<=1,000 $
拼成\(2N\)的链，单调队列维护一下即可
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
using namespace std;
const int Maxn = 1e6 + 10;
int N, Sum, Cut, Ans, H, T(1);
int Arr[Maxn << 1], Q[Maxn << 1];
inline int Read()
{
int X(0), T(1), O(getchar());
while (O < '0' || O > '9')
{
if (O == '-') T = -1;
O = getchar();
}
for (; O >= '0' && O <= '9'; O = getchar()) X = (X << 1) + (X << 3) + (O ^ 48);
return X * T;
}
int main()
{
freopen ("genes.in", "r", stdin);
freopen ("genes.out", "w", stdout);
N = Read();
for (int i = 1; i <= N; ++i) Arr[i] = Arr[i + N] = Read();
for (int i = 1; i <= N * 2; ++i) Arr[i] += Arr[i - 1];
for (int i = 1; i <= N - 1; ++i)
{
while (H <= T && Arr[Q[H]] >= Arr[i]) H++;
while (H <= T && Arr[Q[T]] >= Arr[i]) --T;
Q[++T] = i;
}
for (int i = N; i < N * 2; ++i)
{
while (H <= T && i - Q[H] >= N) H++;
while (H <= T && Arr[Q[T]] >= Arr[i]) --T;
Q[++T] = i;
if (Arr[Q[H]] >= Arr[i - N + 1]) ++Ans;
}
printf ("%d\n", Ans);
}
题三：最短路径
【问题描述】
平面内给出 \(n\)个点，记横坐标最小的点为 \(A\)，最大的点为 \(B\)，现在\(Zxd\)想要知道在每个点经过一次（\(A\)点两次）的情况下从\(A\)走到\(B\)，再回到\(A\)的最短路径。但他是个强迫症患者，他有许多奇奇怪怪的要求与限制条件：
从 \(A\) 走到 \(B\) 时，只能由横坐标小的点走到大的点。
由 \(B\) 回到 \(A\) 时，只能由横坐标大的点走到小的点。
有两个特殊点 \(b1\) 和 \(b2\)， \(b1\) 在 \(0\) 到 \(n-1\) 的路上，\(b2\) 在 \(n-1\) 到 \(0\) 的路上。
请你帮他解决这个问题助他治疗吧！
【输入格式】
第一行三个整数 \(n,b1,b2,( 0 < b1，b2 < n-1 且 b1 \neq b2)\)。n 表示点数，从 \(0\) 到 \(n-1\) 编号，\(b1\) 和 \(b2\) 为两个特殊点的编号。
以下 \(n\) 行，每行两个整数 \(x,y\) 表示该点的坐标\((0 <= x，y <= 2000)\)，从 \(0\) 号点顺序给出。\(Doctor Gao\)为了方便他的治疗，已经将给出的点按 \(x\) 增序排好了。
【输出格式】
仅一行，输出最短路径长度（精确到小数点后面 \(2\) 位）。
| 【样例输入】 | 【样例输出】 |
|---|---|
| 5 1 3 1 3 3 4 4 1 7 5 8 3 |
18.18 |
【样例解释】
最短路径：\(0->1->4->3->2->0\)
【数据范围】
\(20%\)的数据\(n<=20\)
\(60%\)的数据\(n<=300\)
\(100%\)的数据\(n<=1000\)
对于所有数据\(x,y,b1,b2\)如题目描述。
对于这种问题，发现他的数据很小，考虑Dp：
就是\(Dp\left[i\right]\left[j\right]\)表示来经过\(i\), 回去经过\(j\)
所以有:
2
3
4
k = max(i, j) + 1;
Dp[i][k] = max(Dp[i][k], Dp[i][j] + Dis(j, k));
Dp[k][j] = max(Dp[k][j], Dp[i][j] + Dis(i, k));所以就可以愉快的切掉了
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
using namespace std;
const int Maxn = 1e3 + 10;
const double INF = 1e9 + 10;
int N, B1, B2;
double Ans, F[Maxn][Maxn];
int X[Maxn], Y[Maxn], Pre[Maxn];
bool Vis[Maxn];
inline double Get(int A, int B)
{
return sqrt((X[A] - X[B]) * (X[A] - X[B]) + (Y[A] - Y[B]) * (Y[A] - Y[B]));
}
inline double UpDate(double &X, double Upt) { if (Upt < X) X = Upt; }
int main()
{
freopen ("paths.in", "r", stdin);
freopen ("paths.out", "w", stdout);
scanf ("%d %d %d", &N, &B1, &B2);
for (int i = 0; i < N; ++i) scanf ("%d %d", X + i, Y + i);
for (int i = 0; i <= N; ++i)
for (int j = 0; j <= N; ++j)
F[i][j] = INF;
F[0][0] = 0;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
{
if (i == N - 1 && j == N - 1) break;
int K = max(i, j);
if (K == N - 1)
{
if (i != N - 1 && K != B2) UpDate(F[K][j], F[i][j] + Get(i, K));
if (j != N - 1 && K != B1) UpDate(F[i][K], F[i][j] + Get(j, K));
}
else
{
++K;
if (K != B2) UpDate(F[K][j], F[i][j] + Get(i, K));
if (K != B1) UpDate(F[i][K], F[i][j] + Get(j, K));
}
}
printf ("%.2lf\n", F[N - 1][N - 1]);
// system("pause");
}