[数据结构与算法]牛客非大白月赛45（全题解）

题集链接

OP

我最开始去洛谷找了半天牛客小白月赛

A 悬崖

思路

只需要特殊考虑第一次跳不到对面的情况，此时总距离为 x ；
其余情况共可跳 n 次，每次距离 x ；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    ll n,x;
    cin>>x>>n;
    if(n>x)cout<<x;
    else
    {
        cout<<n*x;
    }
    return 0;
}

B 数数

思路

即求
$$\sum _{i=1}^{n}2i?1$$
经等差数列求和，上式等于 n²；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    ll n;
    cin>>n;
    cout<<n*n;
    return 0;
}

C 山楂

模拟

思路

对于较低一级，显然优先通过 3 个一合成能合成更多的高一级物品，但是这种情况会对剩余的低级物品造成浪费（没有计算分数）；
我们可以将剩余的物品加入到前面一些数量为 3 的组中，使其变成数量为 4 的组，要注意可能存在组数小于剩余物品数的情况；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
int main()
{
    ll cnt,x=0;
    ll mrk=0;
    for(ll i=1;i<=8;i++)
    {
        cin>>cnt;
        x+=cnt;
        ll nxt=x/3;    //nxt为合成高级物品数
        mrk+=(nxt*3+min(nxt,x-nxt*3))*i;//min即处理上述情况
        x=nxt;
    }
    cout<<mrk;
    return 0;
}

D 切糕

思路

显然，两个合法串的拼接是合法串，合法串与非法串的拼接是非法串；
那么如果总串是非法串，则无论如何切割，都不能保证所有串都是合法串；
对于合法串：
我们可以找到若干个节点，使得如果在全部节点断开时，每一个子串都是最小的合法串（即不能再拆分成若干合法串的拼接），那么对于所有情况，每个节点都有“切”和“不切”两种情况，假设节点个数为 cnt ，那么结果即为 $2^{cnt}$ ；
我们找出节点的数量即可，显然以任意节点为右端点的前缀串都是合法串，依照此规律即可找出；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
ll qm(ll a,ll b)
{
    ll ans=1;
    for(;b;b>>=1)
    {
        if(b&1)ans=ans*a%M;
        a=a*a%M;
    }
    return ans;
}
int main()
{
    string g;
    cin>>g;
    int cnt=0,f=1,c=0;
    for(int i=0;f&&g[i];i++)
    {
        if(g[i]=='(')c++;
        else c--;
        if(c<0)f=0;
        else if(c==0)cnt++;
    }
    if(f&&!c)//f=1代表任何前缀均满足左括号数大于等于右括号数
    		 //c=0代表总串左右括号数相等
    {
        printf("%lld",qm(2,cnt-1));
        //这种情况下最后一个字符的右侧也是一个节点，但是对答案没有贡献
    }
    else
    {
        cout<<-1;
    }
    return 0;
}

E 筑巢

树状DP

思路

构造状态表示：
$dp[1][i]$ 代表巢穴包含 i 节点时，在以 i 为根的子树中幸福度最大值；
$dp[0][i]$ 代表巢穴不含 i 节点时，在以 i 为根的子树中幸福度最大值；
定义初态：
$dp[1][i]=po[i]$ ，即该点的幸福度；
$dp[0][i]=?\text{inf}$ ，即某足够小值；
确定状态转移方程：
$dp[1][i]+={\sum }_{j\in {\text{son}}_i}\max (0,dp[1][j]+di{s}_{i,j})$；
$dp[0][i]={\max }_{j\in {\text{son}}_i}(dp[0][i],\max (dp[1][j],dp[0][j]))$；
最终的结果即为 $\max (dp[0][1],dp[1][1])$ ；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
int n;
ll po[100005];
vector<pair<int,ll>>rod[100005];
ll dp[2][100005];
void dfs(int x,int f)
{
    dp[1][x]=po[x];
    dp[0][x]=(ll)-1e14-1;
    for(int i=0;i<rod[x].size();i++)
    {
        if(rod[x][i].first!=f)
        {
            dfs(rod[x][i].first,x);
            dp[1][x]+=max(0ll,rod[x][i].second+dp[1][rod[x][i].first]);
            dp[0][x]=max(dp[0][x],max(dp[1][rod[x][i].first],dp[0][rod[x][i].first]));
        }
    }
}
int main()
{
    cin>>n;
    int u,v;
    ll w;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&po[i]);
    }
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d%lld",&u,&v,&w);
        rod[u].push_back({v,w});
        rod[v].push_back({u,w});
    }
    dfs(1,1);
    cout<<max(dp[1][1],dp[0][1]);
    return 0;
}

F 交换

模拟，字典树

思路

我们首先可以发现，给定序列按照某指令集子串顺行转换为升序序列 即意味着 升序序列按指令集某子串逆行可转换为给定串；
其次我们也可以发现，如果给定串的排序后序列是1~10序列的前缀，则意味着该1~10序列按照排序的过程逆向执行得到的串的前缀也是给定串；
然后看到 $n?2\text{e}3$ ，我们便可以意识到某固定串经过所有指令集子串处理的结果是可以枚举获得的；
既然我们的目标是将给定串升序排序，依照以上三点结论，我们可以直接将串1 2 3 4 5 6 7 8 9 10逆向执行指令集的每一个子串，并把得到的结果和需要的操作数记录在字典树中，方便以后匹配；
对于每一个执行结果的每一个前缀，我们已经发现后面的内容是同质的（即前缀相同时，后缀内容不影响前缀的生成），我们便可以对于每一个前缀只存储最少的操作数；

代码

经测试，以下代码中 short 均改为 int 亦可AC ；
为了方便操作，我将 1~10 串变为了 0~9 的 string，本质是相同的；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
pair<short,short>pr[2003];
struct 
{
    int son[10]={0};
    short mx=5000;
}dict[12000007];
int idx=0;
void mt(string g,short x)//加入字典树
{
    //cout<<x<<' '<<g<<endl;
    int now=0;
    for(int i=0;i<10;i++)
    {
        if(!dict[now].son[g[i]-'0'])
        {
            dict[now].son[g[i]-'0']=++idx;
            now=idx;
        }
        else
        {
            now=dict[now].son[g[i]-'0'];
        }
        dict[now].mx=min(dict[now].mx,x);//更新前缀的最小操作数
    }
}
short ck(string g,int k)//查找匹配的前缀
{
    int now=0;
    for(int i=0;i<k;i++)
    {
        if(!dict[now].son[g[i]-'0'])
        {
            return 5000;
        }
        else
        {
            now=dict[now].son[g[i]-'0'];
        }
    }
    return dict[now].mx;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&pr[i].first,&pr[i].second);
    }
    for(int i=1;i<=n;i++)
    {
        string tmp1="0123456789";
        //string tmp2="9876543210";
        if(i==1)mt(tmp1,0);//,mt(tmp2,0);
        for(int j=i;j>=1;j--)
        {
            swap(tmp1[pr[j].first-1],tmp1[pr[j].second-1]);
            //swap(tmp2[pr[j].first-1],tmp2[pr[j].second-1]);
            mt(tmp1,i-j+1);
            //mt(tmp2,i-j+1);
        }
    }
    int k,tp;
    while(m--)
    {
        string g1="0000000000";
        //string g2="0000000000";
        scanf("%d",&k);
        for(int i=0;i<k;i++)
        {
            scanf("%d",&tp);
            tp--;
            g1[i]=tp+'0';
            //g2[i]=9-tp+'0';
        }
        tp=ck(g1,k);
        //cout<<g1<<' '<<g2<<endl;
        //tp=min(ck(g1,k),ck(g2,k));
        printf("%d\n",(tp==5000)?-1:tp);
    }
    return 0;
}

以上代码中，被注释掉的有关 tmp2 和 g2 的部分是关于逆序排序的，如果字典树内存加倍的话，也可以正常处理逆序排序结果；
被题目描述坑了QAQ；

ED

\