A
https://ac.nowcoder.com/acm/contest/64272/A
题意
游游定义一个数组为“稳定的”，当且仅当数组相邻的两个元素之差的绝对值不超过1。例如[2,3,2,2,1]是稳定的，而[1,3,2]则不是稳定的。
游游拿到了一个数组，她想求出该数组的最长的“稳定的”连续子数组的长度。
题解
首先，如果在某处不稳定了（即两相邻元素之差大于1），那么后面的稳定数组肯定不能用上这一段，它们被不稳定的一对元素隔开了
边输入边判断，设一个变量len，表示当前的最长稳定数组。如果满足数组相邻的两个元素之差的绝对值不超过1，就令len++，否则看len能不能更新ans，再令len=1
code
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N = 1e5 + 10;
int t, n;
int a[N];
int main() {
ios::sync_with_stdio(false);
cin >> n;
int len = 0, ans = 0;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(!len) len = 1;
else {
if(abs(a[i] - a[i - 1]) > 1) ans = max(ans, len), len = 1;
else len++;
}
}
ans = max(ans, len);
cout << ans << endl;
return 0;
}
B
https://ac.nowcoder.com/acm/contest/64272/B
题意
游游定义一个字符串是“好串”，当且仅当该字符串相邻的字符不相等。例如"arcaea"是好串，而"food"不是好串。
游游拿到了一个字符串，她可以将该字符串的各个字符顺序随意打乱。她想知道一共可以生产多少种不同的好串？
注意，输入的串长度不超过10.
题解
看到长度不超过10，由 \(10! = 3628800\)，我们可以枚举每个串，如果它是一个好串，ans += 1
code
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N = 500 + 10;
int t, n;
char s[12];
int a[12];
int f[12];
int main() {
scanf("%s", s + 1); n = strlen(s + 1);
f[0] = 1;
for(int i = 1; i <= n; i++) a[i] = i, f[i] = f[i - 1] * i;
int ans = 0; bool ff = 0;
do {
ff = 1;
for(int i = 1; i < n; i++) {
if(s[a[i]] == s[a[i + 1]]) {
ff = 0;
break;
}
}
if(ff == 1) ans++;
}while(next_permutation(a + 1, a + n + 1));
sort(s + 1, s + n + 1);
t = 0;
for(int i = 1; i <= n; i++) {
if(i == 1 || s[i] == s[i - 1]) t++;
else ans /= f[t], t = 1;
}
ans /= f[t];
printf("%d\n", ans);
return 0;
}
C
https://ac.nowcoder.com/acm/contest/64272/C
题意
游游准备开车出游，她的车非常特殊，油越多则最高速度越快，即最高速度和油量是成正比的。另外，行驶过程中油是不会消耗的。
车初速度 \(v_0\)，如果花 \(t\) 时间加油，那么车速变成 \(v_0 + x * t\)
问最快什么时候能到达距离为 \(y\) 的地方
题解
注意，题目虽然说油越多速度越快，但是加油过程中车是静止的
假设花 \(t\) 时间加油，那么最终所花的时间为 \(t + \frac{y}{t * x + v_0}\)，把它写成 \(t + \frac{v_0}{x} + \frac{\frac{y}{x}}{t + \frac{v_0}{x}} - \frac{v_0}{x}\)，
由均值不等式知，上式最小值为 \(2*sqrt(\frac{y}{x}) - \frac{v0}{x}\)，等号当且仅当 \(t + \frac{v_0}{x} == sqrt(\frac{y}{x})\) 时取得。
所以：如果 \(sqrt(\frac{y}{x}) - \frac{v_0}{x} \geq 0\) (即 \(t \geq 0\) 时)，ans = \(2*sqrt(\frac{y}{x}) - \frac{v0}{x}\)
否则 ans = \(y / v0\) （实际看来就是还不如不加油更快）
本题只得了75%的分数，就是因为忽视了均值不等式成立的条件！！！
code
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N = 500 + 10;
ll v0, x, y;
int main() {
cin >> v0 >> x >> y;
double ans = 0;
double tem = sqrt(1.0 * y / x) - 1.0 * v0 / x;
if(tem >= 0) ans = 2.0 * sqrt(1.0 * y / x) - 1.0 * v0 / x;
else ans = 1.0 * y / v0;
printf("%.10f\n", ans);
return 0;
}
D
https://ac.nowcoder.com/acm/contest/64272/D
题意
游游拿到了一个01串，该字符串仅由'0'和'1'两种字符组成，且第一个字符保证是'1'。
由于该字符串过长，游游用一个大小为n的数组表示该字符串：
第一个元素a_1 表示字符串开头有a_1 个'1'字符，第二个元素a_2 表示接着有a_2 个'0'字符，以此类推表示整个字符串。游游想知道，该01串共有多少个非空回文子串？由于答案可能过大，请对 \(10^9+7\) 取模。
思路
把答案分成两部分。
第一部分，一整串0或1。手推一下可知，\(a_i\) 对答案的贡献是 \(a_i * (a_i + 1) / 2\)。
第二部分，对于一整串0或1，若回文串包含除了它之外的部分，那么回文串的中心必然位于这个串的最中心，然后往外延伸。
假设采取一串1作为中心的串，它两边为0串，如果这两个0串不一样长，那么它们对答案的贡献是那个较短的串的长度；如果一样，那么就把串长都加给答案，然后再往外看两个串
code
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N = 1000 + 10, mod = 1e9 + 7;
int n, a[N];
ll ans = 0;
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
ans += 1ll * a[i] * (a[i] + 1) / 2;
/*
我改正的赛时wa掉的写法！！！忽略了（a[i] / 2）应该被括号括起来这件事，把乘2和2这个分子约掉了！！（比如a[i] == 3，本来要乘1*2，就会变成*3！！！）
ans += 2ll * (1 + a[i] / 2) * (a[i] / 2);
if(a[i] % 2) ans += a[i] / 2 + 1;
else ans -= a[i] / 2;
if(ans < 0) ans += mod;
*/
ans %= mod;
}
ans %= mod;
for(int i = 2; i < n; i++) {
int st = i - 1, en = i + 1;
while(st >= 1 && en <= n) {
ans += 1ll * min(a[st], a[en]);
ans %= mod;
if(a[st] != a[en]) break;
else st--, en++;
}
}
cout << ans << endl;
return 0;
}