A 游游的最长稳定数组
游游定义一个数组为“稳定的”，当且仅当数组相邻的两个元素之差的绝对值不超过1。例如$[2,3,2,2,1]$是稳定的，而$[1,3,2]$则不是稳定的。
游游拿到了一个数组，她想求出该数组的最长的“稳定的”连续子数组的长度，你能帮帮她吗？
思路
模拟题，遍历数组内容，记录两两之间的绝对值存入新数组，在新数组里寻找最长子数组
代码
1
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n,a[N];
void solve()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
int res = 0;
for(int i = 1; i <= n; i++)
{
int length = 1;
for(int j = i + 1; j <= n; j++)
{
if(abs(a[j] - a[j - 1]) <= 1) length++;
else
{
i = j - 1;
break;
}
}
res = max(length,res);
}
cout << res << '\n';
}
int main() {
solve();
return 0;
}
|
B 游游的字符重排
游游定义一个字符串是“好串”，当且仅当该字符串相邻的字符不相等。例如”arcaea”是好串，而”food”不是好串。
游游拿到了一个字符串，她可以将该字符串的各个字符顺序随意打乱。她想知道一共可以生产多少种不同的好串？
思路
全排列，直接将字符串视为一串ASCII的数字数组然后求这个数组的全排列就行。因为数据范围足够小（字符数小于等于10），所以可以直接暴力枚举
补充：next_permutation
和prev_permutation相对，作为获取全排列时可以使用的非常方便俩函数
next_permutation在使用的时候会自动获取传入的“上一个序列”，所以如果想要获取全排列，next_permutation要和sort连用，并且sort的规则为升序排序
基本用法：
1
2
3
4
5
6
7
8
9
| int n=5;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
do{
for(int i=0;i<n;i++)
cout<<a[i]<<' ';
cout<<endl;
}while(next_permutation(a,a+n,cmp));
|
同样的，struct和vector也可以使用这个函数，但是比较函数要自定义，并且在全排列之前也要升序
代码
1
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 20;
int a[N];
string s;
void solve()
{
cin >> s;
int n = s.size();
for(int i = 0; i < s.size(); i++) a[i] = s[i] - 'a';
sort(a,a + n);
int result = 0;
do
{
bool flag = true;
for(int i = 1; i < n; i++)
{
if(a[i] == a[i - 1])
{
flag = false;
break;
}
}
if(flag) result++;
}while(next_permutation(a,a + n));
cout << result << endl;
}
int main() {
solve();
return 0;
}
|
C 游游开车出游
游游准备开车出游，她的车非常特殊，油越多则最高速度越快，即最高速度和油量是成正比的。另外，行驶过程中油是不会消耗的。
已知游游的车初始的最高速度为$v_0$，当游游花费了$t$时间加油时，车的最高速度会变成$v_0+t∗x$。
游游开车的总里程为$y$，假设游游始终以最高速度行驶（即忽略加速时间），游游想知道，自己最少花费多少时间可以完成出游？
思路
纯数学题？纯数学题？纯数学题？
对公式进行求导，然后得到导数的极值点，再代回原式
梦回高中
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include <bits/stdc++.h>
using namespace std;
void solve()
{
long double v0,x,y;
cin >> v0 >> x >> y;
if(v0 > sqrt(x*y)) printf("%.12llf",y/v0);
else printf("%.12llf",2*sqrt(y/x) - v0/x);
}
int main() {
solve();
return 0;
}
|