A . A. A.
题意: 你初始有 2 n 2n 2n 个数字,答案初始为 1 1 1。现在需要做 n n n 次操作,每次从这些数字中取出两个数字 x , y x,y x,y 并从原数字集合中删除,将答案乘以 x + y x+y x+y。现在需要找到一种方案使得答案最大,由于答案可能很大,需要将最大答案模 1 e 9 + 7 1e9+7 1e9+7输出。
题解: 对于一个 s u m = x + y sum=x+y sum=x+y,一定是 x x x越接近 y y y的时候, x × y x\times y x×y越大。因为 x × y = x × ( s u m − x ) = − x 2 + s u m ⋅ x x\times y=x\times (sum-x)=-x^2+sum\cdot x x×y=x×(sum−x)=−x2+sum⋅x,对称轴为 − b 2 a = s u m 2 -\frac{b}{2a}=\frac{sum}{2} −2ab=2sum。
所以对 2 n 2n 2n的序列排序后每次选择 a i + a 2 n − i , 0 ≤ i ≤ n − 1 a_i+a_{2n-i},0\leq i\leq n-1 ai+a2n−i,0≤i≤n−1,即可。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int n;
ll q[N];
void solve() {
scanf("%d", &n);
ll res = 1;
for(int i = 1; i <= n * 2; i++) {
scanf("%lld", &q[i]);
}
sort(q + 1, q + 1 + 2 * n);
for(int i = 1, j = 2 * n; i <= n; i++, j--) {
res = res * (q[i] + q[j]) % mod;
}
printf("%lld\n", res);
}
int main()
{
int T = 1;
//scanf("%d", &T);
while(T--) {
solve();
}
return 0;
}
B . B. B.
题意: 我们定义一个串 S S S 为 n a m o m o namomo namomo串,当且仅当:串长度为偶数,并且所有奇数下标位置字符都是辅音,所有偶数下标位置字符都是元音,这里下标从 1 1 1 开始,元音指 a e i o u aeiou aeiou这些字符,而辅音是除了元音以外的所有小写字符。串长大于等于 6 6 6,并且从第三个字符开始是一个循环节为 2 2 2的串。
题解: 从索引 f i r fir fir开始,如果从 f i r fir fir开始长度为 6 6 6的串是 n a m o m o namomo namomo串,那么就继续枚举看是否存在每两个字符都相同的 n a m o m o namomo namomo串。如 " n a m o m o m o " "namomomo" "namomomo",
有从索引 1 1 1开始的 " n a m o m o " "namomo" "namomo", " n a m o m o m o " "namomomo" "namomomo",以及从索引 3 3 3开始的 " m o m o m o " "momomo" "momomo"。
所以从 1 1 1开始后,我们继续枚举到 8 8 8,然后计算一次以 1 1 1开始的合法串个数,从 3 3 3开始的合法串个数。
举个例子: n a m o m o m o m o q a q a namomomomoqaqa namomomomoqaqa这个串
我们从 n a na na开始找到第一个长度为 6 6 6的,如果可以继续往后找,那么每往后加两个字符,就会多一些串,如我们此时串尾的索引为 6 6 6,那么可以继续往后延两个字符 m o mo mo,所以增加了 n a m o m o m o namomomo namomomo和 m o m o m o momomo momomo,再继续往后加两个就是增加了新的 n a m o m o m o m o namomomomo namomomomo和 m o m o m o m o momomomo momomomo(串头索引从 3 3 3开始),和 m o m o m o momomo momomo(串头索引从 5 5 5开始)。至于每次循环结束后,由于 w h i l e while while到的串尾可以作为下一个合法串的串头,如这里的串尾 m o mo mo(索引从 9 9 9开始),可以作为 m o q a q a moqaqa moqaqa的串头,所以每次 i = j − 2 i=j-2 i=j−2,又因为 f o r for for尾会有个 i i i++,所以再减去 1 1 1即 i = j − 2 − 1 i=j-2-1 i=j−2−1
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
const int mod = 1e9 + 7;
int n;
char s[N];
char str[] = "aeiou";
bool check_even(char ch) {
for(int i = 0; i < 5; i++)
if(ch == str[i]) {
return true;
}
return false;
}
bool check_odd(char ch) {
for(int i = 0; i < 5; i++)
if(ch == str[i]) {
return false;
}
return true;
}
int check_pre(int fir) {
int flag = 1;
flag = (flag && check_odd(s[fir]) && check_odd(s[fir + 2]));
flag = (flag && check_even(s[fir + 1]) && check_even(s[fir + 3]));
flag = (flag && s[fir + 2] == s[fir + 4] && s[fir + 3] == s[fir + 5]);
return flag;
}
void solve() {
scanf("%s", s + 1);
int len = strlen(s + 1);
ll res = 0;
if(len >= 6) {
for(int i = 1; i + 5 <= len; i++) {
if(check_pre(i)) {
res++;
int j = i + 6, k = i + 7;
while(k <= len && s[j] == s[i + 4] && s[k] == s[i + 5]) j += 2, k += 2;
int slen = k - 2 - i + 1;
if(slen >= 8) {
ll cnt = (slen - 6) / 2;
res += cnt; //以i开头的长度超过6的
res += cnt; //以i + 2, i + 4...开头的长度为6的
cnt--;
res += (cnt + 1) * cnt / 2;//以索引i+2,i+4...开头的长度大于6的
}
i = j - 2 - 1;
}
}
}
printf("%lld\n", res);
}
int main()
{
int T = 1;
//scanf("%d", &T);
while(T--) {
solve();
}
return 0;
}