2021-03-29 07:15 已编辑华南农业大学全栈开发

关注

牛客练习赛78 A~D题解

https://ac.nowcoder.com/acm/contest/11168#description

参考题解：https://blog.nowcoder.net/n/442c183ba9bc445ba641ed07e54f7164?f=comment

A: CCA的词典

题目描述

给定一个有 n 个单词的词典。

有 q 次询问，每次询问给定一个单词，询问有多少个单词可以通过交换相邻字母（也可以不交换）变成给定的单词。

样例

输入
4
aa
bb
ab
ba
2
aa
ba
输出
1
2

n，q <= 10^4，单词长度 <= 2，单词中的字母全为小写。

算法

(map)

由于单词最多只有两个，并且可以交换（也可以不计交换）两个字母

所以我们将所有单词都转化成字典序最小的形式

这样判断两个单词是否相同就与字母顺序无关了

然后用一个map记录所有单词（我这里用的是unordered_map）

时间复杂度 $O(N)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const int N = 10010;
char op[10];
int n;

void solve()
{
    map<string,int> H;
    scanf("%d",&n);
    for(int i = 0;i < n;i ++)
    {
        string s;
        scanf("%s",op);
        for(int i = 0;op[i];i ++)
            s += op[i];
        if(s.size() >= 2 && s[0] > s[1]) reverse(s.begin(),s.end()); 
        H[s] ++;
    }
    int q;
    scanf("%d",&q);
    while(q --)
    {
        string s;
        scanf("%s",op);
        for(int i = 0;op[i];i ++)
            s += op[i];
        if(s.size() == 2 && s[0] > s[1]) reverse(s.begin(),s.end()); 
        printf("%d\n",H[s]);
    }
}

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #else
    #endif // LOCAL
    int T = 1;
    // init(500);
    // scanf("%d",&T);
    while(T --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}

B: CCA的搬运

题目描述

在一个竖直的洞里有 n 个有重量的球，需要进行 m 次操作，每次操作需要将其中一个球拿出来然后放在最上面。

取出一个小球放在最上面需要消耗的体力为它上面的小球的重量之和。

现在给定每次操作需要取的小球的编号，要求出一种初始的放球方案使得消耗的总体力最少。

样例

n,m <= 2000,1 <= 每个小球的重量 <= 100 。

算法

(思维 + 贪心)

~~比赛的时候就想到了按照石子第一次出现的时间将石子从上到下排序接着模拟~~

~~但是比赛的时候脑抽了一下写了个O（N）的方法，还以为自己很对~~

首先在草稿纸上模拟会发现一个性质

贪心的按照石子第一次出现的时间将石子从上到下排序接着模拟似乎就能得到最优

简单证明一下：

设最优答案是ans，用上述贪心得到的答案是cnt

贪心得到的方法是一个合法方案所以,ans <= cnt
假设有 $[1,n]$ 不同的数

第x个数第一次操作的位置是i，

$[1,i - 1]$ 对y个不同的数进行了操作，

假设ans的排法中x在第j个位置， $j \in [1,y]$

设进行到第 $i - 1$ 个操作后的答案是: $S + S_x$ $(S_x是数字x对答案的贡献)$

如果将x放在第 $y + 1$ 个位置，其他y个数字的相对位置不变

由于y个数字的相对位置不变所以进行到第 $i - 1$ 个操作后

$S$ 不变，而由于x在其他y个数字的后面所以 $S_x = 0$

答案更优

按照这种方法不断转化，答案会更优所以

$ans <= cnt$

则 $ans = cnt$

时间复杂度 $O(N ^ 2)$

C++ 代码

比赛中我用的是另一个思路

一个序列：3 2 4 1 2 3 4 5

我们发现每个数字第一次出现的时候会将前面所有不同的数字累加到答案中

而第 $i$ 次出现 $(i > 1)$ 时会将上一次出现到当前位置之间的不同数字累加答案中

所以我们储存每一个数字出现的位置，然后计算每一个数字对答案的贡献

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const int N = 2010;
LL s[N];
int a[N],op[N];
// int last[N],l[N];
bool st[N],st2[N];
vector<int> last[N];
int n,m;

void solve()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d",&a[i]);
    }
    LL sum = 0,res = 0;
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d",&op[i]);
        last[op[i]].push_back(i);
    }
    for(int i = 1;i <= n;i ++)
    {
        if(last[i].size())
        {
            vector<int> stk;
            for(int j = 1,k = 0;j <= m && k < last[i].size();j ++)
            {
                if(j != last[i][k] && !st[op[j]]) //st表示是当前数字是否已经统计过了。只计算不同的数字的贡献
                {
                    sum += a[op[j]];
                    st[op[j]] = true;
                    stk.push_back(op[j]);
                }
                if(j == last[i][k])//last：当前数字下一个出现的位置
                {
                    res += sum;
                    sum = 0;
                    while(stk.size())
                    {
                        st[stk.back()] = false;//清空栈和st数组
                        stk.pop_back();
                    }
                    k ++;
                }
            }
        }
    }
    printf("%lld\n",res);
}

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #else
    #endif // LOCAL
    int T = 1;
    // init(500);
    // scanf("%d",&T);
    while(T --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}

模拟：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const int N = 2010;
LL s[N];
int a[N],op[N];
bool st[N];
int seq[N];
int n,m;

void solve()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d",&a[i]);
    }
    int tot = 0;
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d",&op[i]);
        if(!st[op[i]])
        {
            st[op[i]] = true;
            seq[++ tot] = op[i];
        }
    }
    LL res = 0;
    for(int i = 1;i <= m;i ++)
    {
        LL sum = 0;
        for(int j = 1;j <= tot;j ++)
        {
            if(seq[j] == op[i])
            {
                for(int k = j - 1;k >= 1;k --)
                    seq[k + 1] = seq[k];
                seq[1] = op[i];
                break;
            }
            sum += a[seq[j]];
        }
        res += sum;
    }

    printf("%lld\n",res);
}

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #else
    #endif // LOCAL
    int T = 1;
    // init(500);
    // scanf("%d",&T);
    while(T --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}

C:CCA的子树

题目描述

给定一棵 n 个点的带点权的有根树，根节点为 1 。

要选出两个节点，满足任意一个不是另一个的祖先节点，最大化以两个节点为根的子树的点权和。

如果选不出两棵合法的子树，则输出“Error”。

样例

输入
5
10 -5 5 6 7
1 2
1 3
2 4
2 5
输出
13

n <= 2×10^5，点权的绝对值 <= 10^9

算法

(贪心)

很直接的想法统计一个节点的任意两个子节点就能满足这两个节点不是互为祖先节点

最大化两个节点为根的子树的点权和，就dfs维护每一个节点的子树中的最大点权和

一边dfs一边更新答案

时间复杂度 $O(N)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const int N = 200010;
const LL INF = 1e16;
int h[N],ne[N * 2],e[N * 2],idx;
int w[N];
LL sz[N];
LL ans = -INF;
int n;

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

LL dfs(int u,int father)
{
    LL d1 = -INF,d2 = -INF;
    sz[u] = w[u];
    for(int i = h[u];~i;i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        LL d = dfs(j,u);
        if(d >= d1) d2 = d1,d1 = d;
        else if(d > d2) d2 = d;
        sz[u] += sz[j];
    }
    if(d1 != -INF && d2 != -INF) ans = max(ans,d1 + d2);
    return max(d1,sz[u]);
}

void solve()
{
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    for(int i = 1;i <= n;i ++) scanf("%d",&w[i]);
    for(int i = 0;i < n - 1;i ++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    dfs(1,-1);
    if(ans == -INF)
    {
        puts("Error");
        return;
    }
    printf("%lld\n",ans);
}

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #else
    #endif // LOCAL
    int T = 1;
    // init(500);
    // scanf("%d",&T);
    while(T --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}

D: CCA的小球

题目描述

给定 n 个小球，每个小球有颜色，要将它们摆成一行。

两个方案不同，当且仅当存在某个位置，两种方案摆在这个位置的小球颜色不同。
一个方案合法，当且仅当不存在任意两个位置相邻的小球颜色相同，求合法方案数对 10^9+7 取模后的值。

样例

n <= 10^6，0 < 颜色编号 < 2^31，每种颜色出现次数 <= 2

算法

(容斥原理)

有n个小球，不同的摆放方案就是 $n! / 2 ^{cnt}$ $,cnt是出现多次的颜色个数$

那么答案就是总的方案数 - 至少出现一次两个颜色相同的小球放在相邻位置的方案 + 至少出现两次两个颜色相同的小球放在相邻位置的方案 - ...

由于每种颜色出现的次数最多是2，所以我们可以用捆绑法

例如求至少出现一次两个颜色相同的小球放在相邻的位置的方案

从cnt个重复出现的颜色中选一个，将这种颜色的两个小球捆绑成一个

然后用这n-1个球求方案

$C_{cnt}^{1} * (n - 1)! / 2 ^ {cnt - 1}$

以此类推：

如求至少出现 $i$ 次两个颜色相同的小球放在相邻的位置的方案

$C_{cnt}^{i} * (n - i)! / 2 ^ {cnt - i}$

最终答案就是 $ans = \sum_{i = 0}^{cnt}(-1)^{i}C_{cnt}^{i} * (n - i)! / 2 ^ {cnt - i}$

时间复杂度 $O(N)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const int N = 1000010,mod = 1e9 + 7;
int n;
LL fac[N],inv[N],bi[N];
LL col[N];
int nums[N],cnt;

LL qmi(LL a,int k)
{
    LL res = 1;
    a %= mod;
    while(k)
    {
        if(k & 1) res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}

void init(int n)
{
    bi[0] = inv[0] = fac[0] = 1;
    for(int i = 1;i <= n;i ++) fac[i] = (fac[i - 1] * i) % mod;
    inv[n] = qmi(fac[n],mod - 2);
    for(int i = n;i;i --) inv[i - 1] = inv[i] * i % mod;
    for(int i = 1;i <= n;i ++) bi[i] = bi[i - 1] * 2 % mod;
}

void solve()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%lld",&col[i]);
    }
    sort(col + 1,col + 1 + n);
    int tows = 0;
    for(int i = 1;i <= n;i ++)
        if(i != 1 && col[i] == col[i - 1])
            tows ++;
    LL res = 0;
    for(int i = 0,sign = 1;i <= tows;i ++)
    {
        res = (res + sign * fac[tows] * inv[i] % mod * inv[tows - i] % mod * fac[n - i] % mod * qmi(bi[tows - i],mod - 2) % mod) % mod;
        sign = -sign;
    }
    printf("%lld\n",(res % mod + mod) % mod);
}

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #else
    #endif // LOCAL
    int T = 1;
    init(N - 1);
    // scanf("%d",&T);
    while(T --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}