神崎兰子

2023-07-11 20:42 已编辑偶像大师灰姑娘女孩后端

关注

【题解】牛客练习赛113题解

写在前面的话

这是第二次出练习赛，上一场出的练习赛是练习赛100，这场相比上场更加平衡了一些难度，看上去榜还是挺美的。

A 小红的基环树

知识点：图论，构造，贪心

难度：800

显然，最小直径是不会超过2的。我们可以先构造一棵菊花树（所有节点连在同一个节点上），然后连接两个叶子，这样就构造出了一个直径为2的基环树。

特殊的，当 $n=3$ 时，基环树的直径只有1。

参考代码（python）：


if input() == "3":
    print(1)
else:
    print(2)

B 小红的回文串

知识点：字符串，乘法原理

难度：800

回文串的性质即：对于每一个 $i$ ， $s_i=s_{n-i-1}$ 。因此我们可以对每个位置进行讨论：

如果两个位置都不是'?'，且两个字符不相等，则直接无解。

如果两个位置都不是'?'，且两个字符相等，则答案不变动。

如果两个位置有一个'?'，另一个为字母，则答案不变动。

如果两个位置都是'?'（或者恰好是字符串中间的那个'?'），则答案乘以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。因此我们可以枚举“减 $y$ ”的次数，然后直接 $O(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难度中的枚举方法。不同的是，我们需要知道每次加 $x$ ，得到目标 $k$ 的最小次数。有两种方案可以求：

① 解同余方程 $ax \equiv b(mod n)$ ，可以直接使用exgcd来解决。

② 我们直接预处理出 $kx$ 在模 $n$ 意义下的值，这样即可O(1)调用了。

方法2：最短路

我们把模 $n$ 等于0到 $n-1$ 的每个值作为一个节点，那么可以建一个带权图： $i$ 到 $i x$ 的权值为 $p$ ， $i$ 到 $i-y$ 的权值为 $q$ 。然后跑最短路即可。

参考代码：

#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,3,...,n$ ，总步数为 $n-1$ 。

然后怎么使得步数加1呢？直接将最后两位翻转即可。数组变成 $1,2,3,...,n-2,n,n-1$ 。

同理，我们希望使得步数加2的话，需要构造的排列为 $1,2,3,...,n-3,n,n-1,n-2$

……

当我们翻转完最后 $n-1$ 个数时，得到的排列为 $1,n,n-1,...,2$ 。此排列的总步数为 $(n-1) (n-2)$

同理，我们在上面这个排列的基础上再翻转后 $n-1$ 个数的前缀，可以得到最多的步数为 $(n-1) (n-2) (n-3)$ 。对应的排列是 $1,n,2,3,4,...,n-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

我们先考虑 $O(n^2)$ 的做法。首先枚举“哪个数作为次数不小于一半的元素”，然后枚举“该元素的数量”和“剩余元素的数量”，即可计算出贡献。这样的综合复杂度为 $O(n^2)$ 。

然后我们考虑如何优化该代码。当我们需要枚举“剩余元素的数量”的时候，可以批量进行统计。具体的，若当前元素取了 $j$ 个，剩余的元素取 $k$ 个时，带来的贡献为 $C_i^j*C_{n-i}^k$ ，最终的总贡献为 $\sum_{j=1}^i \sum_{k=0}^{j} C_i^j*C_{n-i}^k$ ，我们可以批量统计 $C_i^j$ 的系数之和（类似前缀和的思路，计算 $\sum_{k=0}^i C_{n-i}^k$ 的前 $j$ 项和）。

值得注意的是，类似{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）。那么最终每个节点贡献的权值为 $(l 1)*(r 1)$ ，其中 $l$ 代表该节点同层左边的节点数， $r$ 代表该节点同层右边的节点数。

#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;
}