【题解】牛客练习赛113题解
写在前面的话
这是第二次出练习赛，上一场出的练习赛是练习赛100，这场相比上场更加平衡了一些难度，看上去榜还是挺美的。
A 小红的基环树
知识点：图论，构造，贪心
难度：800
显然，最小直径是不会超过2的。我们可以先构造一棵菊花树（所有节点连在同一个节点上），然后连接两个叶子，这样就构造出了一个直径为2的基环树。
特殊的，当时，基环树的直径只有1。
参考代码（python）：
if input() == "3":
print(1)
else:
print(2)
B 小红的回文串
知识点：字符串，乘法原理
难度：800
回文串的性质即：对于每一个，
。因此我们可以对每个位置进行讨论：
如果两个位置都不是'?'，且两个字符不相等，则直接无解。
如果两个位置都不是'?'，且两个字符相等，则答案不变动。
如果两个位置有一个'?'，另一个为字母，则答案不变动。
如果两个位置都是'?'（或者恰好是字符串中间的那个'?'），则答案乘以26。
参考代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mod = 7 + 1e9;
string s;
int main() {
cin >> s;
int n = s.size();
LL ans = 1;
for (int i = 0, j = n - 1; i <= j; ++i, --j) {
if (s[i] == '?' || s[j] == '?') {
if (s[i] == '?' && s[j] == '?') {
ans = ans * 26 % mod;
}
} else {
if (s[i] != s[j]) {
ans = 0;
break;
}
}
}
cout << ans << endl;
return 0;
}
C 小红的数组操作（easy）
知识点：枚举
难度：1300
题意：我们注意到，在本难度中，每次元素只会加1。因此我们可以枚举“减”的次数，然后直接
计算出还需要几次“加1”操作。
参考代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[202020];
signed main(){
int n,p,x,q,y,i;
cin>>n>>p>>x>>q>>y;
int s=0;
for(i=0;i<n;i++)cin>>a[i],s+=a[i];
s%=n;
int mi=1e18;
for(i=0;i<n;i++){
mi=min(mi,((n-(s-i*y)%n+n)%n)%n*p+q*i);
}
cout<<mi;
}
D 小红的数组操作（hard）
知识点：枚举/最短路
难度：1700
方法1：枚举
我们仍然用easy难度中的枚举方法。不同的是，我们需要知道每次加，得到目标
的最小次数。有两种方案可以求：
① 解同余方程，可以直接使用exgcd来解决。
② 我们直接预处理出在模
意义下的值，这样即可O(1)调用了。
方法2：最短路
我们把模等于0到
的每个值作为一个节点，那么可以建一个带权图：
到
的权值为
，
到
的权值为
。然后跑最短路即可。
参考代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int,int>> edge[200005];
int dist[200005];
int vis[200005];
int n,p,x,q,y;
int a[200005];
void dijk(int x)
{
for(int i = 1;i<=n;++i)
dist[i] = 1e17;
dist[x] = 0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
q.push({0,x});
while(!q.empty())
{
int now = q.top().second;
int w = q.top().first;
q.pop();
if(vis[now])
continue;
vis[now] = 1;
for(auto v:edge[now])
{
if(vis[v.first])
continue;
if(w+v.second<dist[v.first])
{
dist[v.first] = w+v.second;
q.push({dist[v.first],v.first});
}
}
}
}
signed main()
{
cin>>n>>p>>x>>q>>y;
int sum = 0;
for(int i = 1;i<=n;++i)
{
cin>>a[i],sum+=a[i],sum%=n;
}
for(int i = 0;i<n;++i)
{
int xx = (i+x)%n;
edge[i+1].push_back({xx+1,p});
int yy = (((i-y)%n)+n)%n;
edge[i+1].push_back({yy+1,q});
}
dijk(sum+1);
if(dist[1]>=1e15)
cout<<-1<<'\n';
else
cout<<dist[1]<<'\n';
return 0;
}
E 小红走排列
知识点：构造
难度：1800
我们先找到最小步数的排列：，总步数为
。
然后怎么使得步数加1呢？直接将最后两位翻转即可。数组变成。
同理，我们希望使得步数加2的话，需要构造的排列为
……
当我们翻转完最后个数时，得到的排列为
。此排列的总步数为
同理，我们在上面这个排列的基础上再翻转后个数的前缀，可以得到最多的步数为
。对应的排列是
后面我们按这种方式，即可构造出任意想要的步数的排列。
参考代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 3 + 1e5;
int n;
LL k;
int ans[N];
int main() {
cin >> n >> k;
k -= n - 1;
vector<int> seq;
seq.push_back(1);
seq.push_back(n);
for (int l = 2, r = n - 1, flag = 1; l <= r && k;) {
if (flag) {
LL t = min<LL>(k, seq.back() - l);
l = seq.back() - t;
k -= t;
seq.push_back(l);
++l;
} else {
LL t = min<LL>(k, r - seq.back());
r = seq.back() + t;
k -= t;
seq.push_back(r);
--r;
}
flag = !flag;
}
seq.erase(seq.begin());
int t = n;
for (auto it = seq.rbegin(); it != seq.rend(); ++it) {
ans[*it] = t--;
}
t = 1;
for (int i = 1; i <= n; ++i) {
if (!ans[i]) {
ans[i] = t++;
}
}
for (int i = 1; i <= n; ++i) {
cout << ans[i] << ' ';
}
return 0;
}
F&&G 小红的好子序列(easy&&hard)
知识点：dp，组合数学，容斥
难度：easy 1800/ hard 2100
我们先考虑的做法。首先枚举“哪个数作为次数不小于一半的元素”，然后枚举“该元素的数量”和“剩余元素的数量”，即可计算出贡献。这样的综合复杂度为
。
然后我们考虑如何优化该代码。当我们需要枚举“剩余元素的数量”的时候，可以批量进行统计。具体的，若当前元素取了个，剩余的元素取
个时，带来的贡献为
，最终的总贡献为
，我们可以批量统计
的系数之和（类似前缀和的思路，计算
的前
项和）。
值得注意的是，类似{1,1,2,2}这样的数组我们在统计时计算了两次，因此需要利用容斥的思想减掉该部分的贡献。
参考代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mod = 7 + 1e9;
const int N = 3 + 1e5;
int n, a[N];
map<int, int> mp;
LL inv[N], fac[N], invFac[N];
LL c(int n, int m) {
if (m > n) {
return 0;
}
return fac[n] * invFac[m] % mod * invFac[n - m] % mod;
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
++mp[a[i]];
}
vector<int> b;
for (auto &i : mp) {
b.push_back(i.second);
}
sort(b.rbegin(), b.rend());
fac[0] = 1;
invFac[0] = 1;
inv[1] = 1;
fac[1] = 1;
invFac[1] = 1;
for (int i = 2; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod;
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
invFac[i] = invFac[i - 1] * inv[i] % mod;
}
LL ans = 0;
for (int i = 1; i <= b[0]; ++i) {
LL cnt = 0;
for (auto &j : b) {
if (j < i) {
break;
}
ans -= c(j, i) * cnt % mod;
cnt = (cnt + c(j, i)) % mod;
}
}
for (int i : b) {
LL cnt = 1;
for (int j = 1; j <= i; ++j) {
cnt = (cnt + c(n - i, j)) % mod;
ans += c(i, j) * cnt % mod;
}
}
ans = (ans % mod + mod) % mod;
cout << ans << endl;
return 0;
}
H 小红的括号串权值
知识点：树，字符串
难度：2400
我们讨论一个子串的权值，即求它内部所有括号对的“深度”之和。所谓括号对的深度，即其被嵌套的层数。例如，(()())最外层的那对括号深度为0，里面的两对括号深度为1。
那么怎么求所有子串的权值呢？我们先观察括号串的两种生成方式：
-
在一个合法括号串两侧加一对括号，例如，(()())。这种生成括号的方式，会使得内部每个括号对的权值加1，外部那个括号的权值为0。
-
将两个合法的括号串拼接，例如，(())()。这种生成括号串的方式，即将两个括号串的权值求和。
我们在计算所有子串权值时，将若干合法串并列，如果要取这一层的子串，一定是取若干个这一层连续的部分（每部分必须取完），这样才能保证合法。
因此我们可以建一棵树，对于每一对括号，它内部的括号即为它的儿子。这样意味着我们必须取“同一层若干个连续的并列子树”，这样才是一个合法解。每个节点存该对括号组成的那个子串的贡献。
那么我们统计权值可以这样统计：父亲的权值为所有儿子的权值之和加上子节点的数量（因为外面每加一层括号，会使得内部所有括号的权值加1）。那么最终每个节点贡献的权值为，其中
代表该节点同层左边的节点数，
代表该节点同层右边的节点数。
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int>g[302020];
int vis[303030];
int mod=1e9+7;
void add(int x,int y){
g[x].push_back(y);
g[y].push_back(x);
}
int sz[303030];
int dp[303030],res;
void dfs(int x,int pr){
vis[x]=1;
sz[x]=1;
for(auto i:g[x]){
if(i==pr)continue;
dfs(i,x);
sz[x]+=sz[i];
}
int cc=0;
for(auto i:g[x]){
if(i==pr)continue;
cc++;
dp[x]+=sz[i]+dp[i];
dp[x]%=mod;
}
int j=0;
for(auto i:g[x]){
if(i==pr)continue;
res+=1ll*dp[i]*(j+1)%mod*(cc-j)%mod;
res%=mod;
j++;
}
}
signed main(){
string s;
cin>>s;
int i;
s=')'+s;
stack<int>st;
st.push(0);
int cnt=0;
for(i=1;i<s.length();i++){
if(s[i]=='(')cnt++,st.push(i);
else {
cnt--;
if(cnt<0){
cnt=0;
st.pop();
st.push(i);
continue;
}
int temp=st.top();
st.pop();
add(temp,st.top());
}
}
res=0;
for(i=0;i<=s.length();i++){
if(!vis[i])dfs(i,-1);
}
cout<<res;
}
