Namomo Test Round 2 部分题解

$A.$ 题意： 你初始有 $2n$ 个数字，答案初始为 $1$。现在需要做 $n$ 次操作，每次从这些数字中取出两个数字 $x,y$ 并从原数字集合中删除，将答案乘以 $x+y$。现在需要找到一种方案使得答案最大，由于答案可能很大，需要将最大答案模 $1e9+7$输出。 题解： 对于一个$sum=x+y$，一定是$x$越接近$y$的时候，$x\times y$越大。因为$x\times y=x\times (sum-x)=-x^2+sum\cdot x$，对称轴为$-\frac{b}{2a}=\frac{sum}{2}$。 所以对$2n$的序列排序后每次选择$a_i+a_{2n-i},0\le i\le 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.$ 题意： 我们定义一个串 $S$ 为$namomo$串，当且仅当：串长度为偶数，并且所有奇数下标位置字符都是辅音，所有偶数下标位置字符都是元音，这里下标从 $1$ 开始，元音指$aeiou$这些字符，而辅音是除了元音以外的所有小写字符。串长大于等于$6$，并且从第三个字符开始是一个循环节为$2$的串。 题解： 从索引$fir$开始，如果从$fir$开始长度为$6$的串是$namomo$串，那么就继续枚举看是否存在每两个字符都相同的$namomo$串。如$"namomomo"$， 有从索引$1$开始的$"namomo"$，$"namomomo"$，以及从索引$3$开始的$"momomo"$。 所以从$1$开始后，我们继续枚举到$8$，然后计算一次以$1$开始的合法串个数，从$3$开始的合法串个数。 举个例子：$namomomomoqaqa$这个串 我们从$na$开始找到第一个长度为$6$的，如果可以继续往后找，那么每往后加两个字符，就会多一些串，如我们此时串尾的索引为$6$，那么可以继续往后延两个字符$mo$，所以增加了$namomomo$和$momomo$，再继续往后加两个就是增加了新的$namomomomo$和$momomomo$(串头索引从$3$开始)，和$momomo$(串头索引从$5$开始)。至于每次循环结束后，由于$while$到的串尾可以作为下一个合法串的串头，如这里的串尾$mo$(索引从$9$开始)，可以作为$moqaqa$的串头，所以每次$i=j-2$，又因为$for$尾会有个$i$++，所以再减去$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; }