T1
题目描述
给你一个长度为$n$的序列，在他的子序列中让你找一个山谷序列，山谷序列定义为：
1. 序列的长度为偶数。
2. 假设子序列的长度为$2n$。则前$n$个数是严格递减的，后$n$个数是严格递增的，并且第一段的最后一个
元素和第二段的第一个元素相同，也是这段序列中的最小值。
现在想让你找所有子序列中满足山谷序列规则的最长的长度为多少？
输入描述
第一行输入一个整数$T$，代表有$T$组测试数据。
对于每一组测试数据，一行输入1个整数$n$，代表有序列的长度为$n$。
接下来$n$个数，代表序列的每一个元素值$a[i]$。
$1 \leq T \leq 100$
$1 \leq n \leq 1000$
$1 \leq a[i] \leq 10 ^ 4$
输出描述
对于每一组数据，输出一行，代表最长的满足要求的山谷序列长度。
示例1
样例输入
3
9
5 4 3 2 1 2 3 4 5
5
1 2 3 4 5
14
87 70 17 12 14 86 61 51 12 90 69 89 4 65
样例输出
8
0
6
说明
用例1：
用长谷序列为：5 4 3 2 2 3 4 5
用例2：
没有两个相等的元素，所以答案为0
用例3：
其中一个最长山谷序列为：87 70 12 12 69 89
算法
(最长上升子序列) $O(T \times n ^ 2)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int T, n;
int a[N], f[N], g[N];
int main() {
cin >> T;
while (T -- ) {
unordered_map<int, vector<int>> S;
cin >> n;
for (int i = 1; i <= n; i ++ ) {
cin >> a[i];
if (S.count(a[i])) S[a[i]].push_back(i);
else S[a[i]] = {i};
}
memset(f, 0, sizeof f);
memset(g, 0, sizeof g);
for (int i = 1; i <= n; i ++ ) {
f[i] = 1;
for(int j = 0; j < i; j ++ )
if (i > 1 && a[i] < a[j])
f[i] = max(f[i], f[j] + 1);
}
for (int i = n; i >= 1; i -- ) {
g[i] = 1;
for(int j = i + 1; j <= n; j ++ )
if (i < n && a[i] < a[j])
g[i] = max(g[i], g[j] + 1);
}
int ret = 0;
for (auto item: S){
if (item.second.size() > 1) {
auto &t = item.second;
for (int i = 0; i < t.size(); i ++ )
for (int j = i + 1; j < t.size(); j ++ )
ret = max(ret, min(f[t[i]], g[t[j]]) * 2);
}
}
cout << ret << endl;
}
return 0;
}
T2
题目描述
给出$a_n, \dots, a_1, a_0$，求方程$a_nx^n + a_{n - 1}x^{n - 1} + \dots + a_1x + a_0 = 0$的所有实数解。
保证$a_i$不全等于0。
输入描述
第一行输入一个整数$n$（$1 \leq n \leq 5$）
第二行输入$n+1$个整数表示$a_n, \dots, a_1, a_0$（$0 \leq |ai| \leq 10$）
输出描述
从小到大输出所有解，重根只打印一次，所有数字保留两位小数。
若无解输出“NO”
示例1
样例输入
2
1 2 1
样例输出
-1.00
示例2
样例输入
3
1 4 2 5
样例输出
-3.82
示例3
样例输入
2
2 0 1
样例输出
NO
算法
() $O()$
骗分，24%
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int n;
double a[6];
int main() {
cin >> n;
for (int i = n; i >= 0; i -- ) cin >> a[i];
if (n == 1) {
if (a[1] == 0) puts("No");
else {
double x = - a[0] / a[1];
printf("%.2lf", x);
}
} else if (n == 2) {
double delta = a[1] * a[1] - 4 * a[0] * a[2];
if (delta < 0) puts("No");
else if (delta == 0) {
double x = -a[1] / (2 * a[2]);
printf("%.2lf", x);
} else {
double x1 = (-a[1] - sqrt(delta)) / (2 * a[2]);
double x2 = (-a[1] + sqrt(delta)) / (2 * a[2]);
printf("%.2lf %.2lf", x1, x2);
}
} else if (n == 3) {
puts("No");
} else if (n == 4) {
puts("No");
} else puts("No");
return 0;
}
T3
题目描述
有一根初始长度$L$的巧克力棒，如果长度不小于$d$，则随机地人中等概率选择一个位置将巧克力棒掰断成
左右两份，然后扔掉左边的部分，留下右边的部分，然后看右边部分长度是否超过$d$，以此决定是否继
续掰断分成两份，依次类推。请你输出掰断次数的期望。
输入描述
输入两个正整数$L，d，1 \leq d \leq L \leq 200$
输出描述
保留四位小数输出答案。
示例1
样例输入
1 1
样例输出
0.0000
示例2
样例输入
2 1
样例输出
1.6931
算法
(数学) $O(1)$
- 设$f(L)$表示长度为$L$的巧克力棒的掰断次数的期望
- 显然有$f(L) = 0, L < d$
- 设$x$表示到右端点的距离，当$x < d$时，期望为0，不用考虑；当$d \leq x \leq L$时，期望为$f(L) = \frac{1}{L}\int_d^L f(x) dx + 1$
$$f(L)^{\prime} = -\frac{1}{L ^ 2} \int_d^L f(x) dx + \frac{f(L)}{L} = \frac{1}{L}$$
$$\implies f(L) = \ln{L} + C, f(d) = 1$$
$$\implies C = 1 - \ln{d}$$
$$\implies f(L)= \begin{cases} 0, & \text {L < d} \\\\ \ln{\frac{L}{d}} + 1, & \text{$L \geq d$} \end{cases}$$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
double L, d;
int main()
{
cin >> L >> d;
if (L <= d) puts("0.0000");
else {
double ret = log(L / d) + 1;
printf("%.4lf", ret);
}
return 0;
}
T4
题目描述
有一个圆环上面有6个点，每一个点都有一个数字，对于两个圆环来说，若6个数字完全一致（顺序可以随
机，只要数相同即可），则说明这两个圆环是一样的，现在有$n$个圆环，想问你这里面有没有一样的两
个圆环，若有输出YES，否则输出NO。
输入描述
第一行输入一个整数$T$，代表有$T$组测试数据。
对于每一组测试数据，第一行输入一个整数$n$，代表有$n$个圆环。
接下来$n$行，每一行6个整数代表每一个圆环的6个点的值。
$1 \leq T \leq 100$
$1 \leq n \leq 10 ^ 5$
圆环的每一个值的大小都小于$10^5$，且每一个文件内的$n$的总和不超过$10^6$
输出描述
对于每组测试数据：若有两个一样的输出YFS，否则输出NO。
示例1
样例输入
2
2
1 2 3 4 5 6
2 3 4 5 6 1
3
1 2 3 4 5 6
8 5 4 1 2 3
2 3 4 5 6 7
样例输出
YES
NO
算法
() $O()$
Python 代码
import sys
def main():
n = int(input())
for i in range(n):
a = int(input())
l = []
for j in range(a):
line = sys.stdin.readline().strip()
s = ''.join(str(x) for x in sorted(list(map(int, line.split()))))
l.append(s)
if len(set(l)) == len(l):
print("NO")
else:
print("YES")
if __name__ == "__main__":
main()
T5
题目描述
小$Q$的饭店承接了某公司的配餐服务，小$Q$需要给这家公司配送$T$次餐食。配送的路途可以抽象为$n$个点，$m$条单向路径的有向图，每条路径有长度，其中饭店在1号点，公司在$n$号点。小$Q$需要往返饭店和公司$T$次，每次小$Q$需要从1号点出发到$n$号点，再从$n$号点回到1号点，小$Q$想知道他配送完所有餐食需要走过的路程最少长度是多少。
输入描述
第一输入三个数$n, m, T$，代表有$n$个点，$m$条单向路径，$T$表示配送次数。
接下来$m$行，每一行输出三个数$x, y, d$，$d$代表从$x$到$y$的距离是$d$。
$1 \leq n \leq 2000$
$1 \leq m \leq 10 ^ 5$
$1 \leq T \leq 100$
$1 \leq x, y \leq n$
$1 \leq d \leq 100$
输出描述
对于每一次查询，输出一个答案代表往返最短路径和。保证能完成配送。
示例1
样例输入
5 5 3
1 2 1
2 3 1
3 5 1
5 1 1
4 5 1
样例输出
12
算法
() $O()$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 2010, M = 1e5 + 10;
typedef pair<int, int> PII;
int T, n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dijkstra(int pos_s, int pos_e) {
memset(dist, 0x3f, sizeof dist);
memset(st, false, sizeof st);
dist[pos_s] = 0;
priority_queue<PII, vector<PII>, greater<PII>> q;
q.push({0, pos_s});
while (q.size()) {
auto t = q.top(); q.pop();
int dis = t.x, v = t.y;
if (st[v]) continue;
st[v] = true;
for (int i = h[v]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j] > dis + w[i]) {
dist[j] = dis + w[i];
q.push({dist[j], j});
}
}
}
return dist[pos_e];
}
int main() {
cin >> n >> m >> T;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++ ) {
int a, b, c; cin >> a >> b >> c;
add(a, b, c);
}
int s2e = dijkstra(1, n), e2s = dijkstra(n, 1);
int ret = (s2e + e2s) * T;
cout << ret;
return 0;
}
请教一下T3里那个 $f(L)=\frac{1}{L} f(x)dx + 1$里为啥要乘$\frac{1}{L}$和为啥要$+1$呢？QAQ
$f$是一个递归求期望的过程，当前已经掰了一次了，所以要加1，然后枚举并求出掰之后剩下的长度的期望，而合法的剩下的长度就是上面写的那一种情况，每次掰的概率是相等的，假设当前长度是$L$，那概率就是$\frac{1}{L}$，直到最后不能掰为止。
原来如此！！谢谢巨巨 QAQ
请问Acwing上建图方式都是用add函数方式建图，但这个含义是什么意思呀，在哪可以看到这个指导说明
这里
谢谢
请问T3数学期望怎么求出来的？？
已更新
谢谢
T5题的dist[1]的初始化为啥为1啊？还有这题用朴素版的dijskstra是不是也行？
写错了，已更正。朴素版的比堆优化版的多一个数量级，数据出的不极限的话应该也行