总结
太菜了,只能做简单题,复杂点的只能过样例 😭 ,加油吧
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;
}引用
- 弹幕里遇到一个很自信的同学 | AcWing第101场周赛：https://www.bilibili.com/video/BV1to4y1w71n/
评论 (0)