Acw第 101 场周赛 总结太菜了,只能做简单题,复杂点的只能过样例 😭 ,加油吧4972. 解方程给定一个一元二次方程$$ ax^2 + bx + c = 0 $$保证给定方程有解，且恰好有两个不同的实数根。请你对该方程进行求解。一元二次方程求根公式为：$$ x = \frac{-b \pm \sqrt{b^2-4ac}}{2a} $$输入格式共一行，包含三个整数 a,b,c。输出格式共两行，第一行输出较大的根，第二行输出较小的根。结果保留六位小数。数据范围所有测试点满足 −1000≤a,b,c≤1000，保证给定方程有解，且恰好有两个不同的实数根。输入样例：1 30 200输出样例：-10.000000 -20.000000题解:这个比较简单,一次Ac#include <iostream> #include <cmath> #include <iomanip> using namespace std; int main() { int a, b, c; cin >> a >> b >> c; double triangle = sqrt(pow(b, 2) - (4 * a * c)); double res1 = (-b + triangle) / (2 * a); double res2 = (-b - triangle) / (2 * a); if (res1 > res2) cout << fixed << setprecision(6) << res1 << endl << res2 << endl; else cout << fixed << setprecision(6) << res2 << endl << res1 << endl; return 0; }4973. 栈给定一个栈，初始时栈为空。你需要依次进行 n 个操作。每个操作给定一个由小写字母构成的非空字符串，随后进行判断：如果栈中已经包含该字符串，则将该字符串上升至栈顶，栈中其它元素的相对顺序保持不变。如果栈中还未包含该字符串，则将该字符串直接插入到栈的顶部。所有操作完成后，请你按照从栈顶到栈底的顺序，依次输出栈内所有元素。输入格式第一行包含整数 n。接下来 n 行，每行包含一个由小写字母构成的非空字符串。输出格式按照从栈顶到栈底的顺序，依次输出栈内所有元素。每个元素占一行。数据范围前 55 个测试点满足 1 ≤ n ≤ 10。所有测试点满足 1 ≤ n ≤ 2×10^5，每个给定字符串的长度范围 [1,10]。输入样例1：4 apple pear banana pear输出样例1：pear banana apple输入样例2：8 pen book eraser desk desk eraser book pen输出样例2：pen book eraser desk题解:自己题目让用stack来操作,但是需求不太好实现,就换成了vector题目中的输出样例可以过,当数据量大的时候就会Time Limit Exceeded#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<string> arr; string temp; for (int i = 0; i < n; ++i) { cin >> temp; vector<string>::iterator it = find(arr.begin(), arr.end(), temp); if (it != arr.end()) { arr.erase(it); arr.push_back(temp); } else { arr.push_back(temp); } } for (vector<string>::reverse_iterator it = arr.rbegin(); it != arr.rend(); it++) { cout << *it << endl; } return 0; }正解-逆向推导#include <iostream> #include <cstring> #include <algorithm> #include <unordered_set> using namespace std; const int N = 200010, M = 11; int n; char str[N][M]; int main() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%s", str[i]); unordered_set<string> hash; for (int i = n - 1; i >= 0; i -- ) if (!hash.count(str[i])) { puts(str[i]); hash.insert(str[i]); } return 0; }正解-正向做#include <iostream> #include <cstring> #include <algorithm> #include <unordered_map> using namespace std; const int N = 200010, M = 11; int n; int l[N], r[N], idx; char str[N][M]; unordered_map<string, int> pos; int insert(int k, int x) { l[x] = k, r[x] = r[k]; l[r[x]] = x, r[k] = x; } void remove(int k) { l[r[k]] = l[k]; r[l[k]] = r[k]; } int main() { l[0] = r[0] = 1; l[1] = r[1] = 0; idx = 2; scanf("%d", &n); for (int i = 0; i < n; i ++ ) { char* s = str[idx]; scanf("%s", s); if (pos.count(s)) { int k = pos[s]; remove(k); insert(0, k); } else { pos[s] = idx; insert(0, idx); idx ++ ; } } for (int i = r[0]; i != 1; i = r[i]) puts(str[i]); return 0; }4974. 最长连续子序列给定一个长度为 n 的整数序列 a1,a2,…,an。给定序列满足，任意两个相邻元素之差的绝对值不超过 1，即对于每个 1 ≤ i <= n，保证 | ai+1 − ai | ≤ 1。请你找到给定序列的一个尽可能长的连续子序列，要求该连续子序列应满足其中的最大元素与最小元素之差不超过 1。输出满足条件的最长连续子序列的长度。输入格式第一行包含整数 n。第二行包含 n 个整数 a1,a2,…,an。输出格式一个整数，表示满足条件的最长连续子序列的长度。数据范围前 6 个测试点满足 2 ≤ n ≤ 20。所有测试点满足 2 ≤ n ≤ 10^5,1 ≤ ai ≤ 10^5。输入样例1：5 1 2 3 3 2输出样例1：4输入样例2：11 5 4 5 5 6 7 8 8 8 7 6输出样例2：5题解:自己#include <iostream> #include <algorithm> #include <cstdio> #include <cmath> using namespace std; const int N = 1e5 + 10; int n; int arr[N]; int main(int argc,char** argv){ int n; scanf("%d",&n); for(int i = 0; i < n; i++){ scanf("%d", &arr[i]); } int answer = 0; for(int i = 0; i < n; i++){ int startValue = arr[i]; int maxValue = startValue; int minValue = startValue; for(int start = i + 1;start < n; start++){ maxValue = arr[start] > maxValue ? arr[start] : maxValue; minValue = arr[start] < minValue ? arr[start] : minValue; int absValue = abs(maxValue - minValue); if(absValue <= 1){ answer = start - i + 1 > answer ? start - i + 1 : answer; }else{ break; } } } printf("%d",answer); }正解提取性质: 合法的序列中只会存在两个不同的元素,一个为x另一个就会为y，y=x+1 or y = x-1#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 100010; int n; int w[N], cnt[N]; int main() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &w[i]); int res = 0; for (int i = 0, j = 0, s = 0; i < n; i ++ ) { if (!cnt[w[i]]) s ++ ; cnt[w[i]] ++ ; while (s > 2) { cnt[w[j]] -- ; if (!cnt[w[j]]) s -- ; j ++ ; } res = max(res, i - j + 1); } printf("%d\n", res); return 0; }引用1.第 101 场周赛 竞赛 - AcWing弹幕里遇到一个很自信的同学 | AcWing第101场周赛：https://www.bilibili.com/video/BV1to4y1w71n/