“蔚来杯“2022牛客暑期多校训练营2补题记录(DGHJKL)

把题补了,感觉要自己梳理一下,就写一下题解,

后续会把其他自己能补的也补了.

"蔚来杯"2022牛客暑期多校训练营2_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ牛客ACM提高训练营是面向ICPC/CCPC/CSP/NOI比赛备战的选手，由金牌选手命题，提高训练高难度的编程比赛，ACM/NOI拔高训练营。https://ac.nowcoder.com/acm/contest/33187

目录

D.Link with Game Glitch(SPFA判断负环,小数转log存储)

G.Link with Monotonic Subsequence(构造,签到)

H.Take the Elevator(模拟,贪心)

J.Link with Arithmetic Progression(数学,线性回归方程)

K.Link with Bracket Sequence I(括号匹配,dp)

L.Link with Level Editor I

---

D.Link with Game Glitch(SPFA判断负环,小数转log存储)

思路:我们现在a个b物品转化为c个d物品,可以看成一个b物品可以转化为(c/a)个d物品,题目问c缩小几分之几可以保证不会无限的增长下去.首先明了,如果可以无限生成的话就肯定是形成了一个循环,而且这个循环是成倍增长的,也就是说这个环的增长倍数(c/a)是>1的,这样的话就会无限的增长.此时我们就可以把这个问题抽象成一个图论问题.:

我们按照题目给的生成关系建立单向边,边权就是每一组的(c/a).当然,如果连续处理多个这种小数相乘的话很容易丢精,那么就可以尝试把边建立为log,就w=log(c/a).这样的话边权就不是一个小时,而是一个带小数点的负数,不那么容易丢精.

然后我们对着这个图用spfa跑最长路(因为本来按照题意路径就在增长(c/a大于1的话)).然后用spfa判断负环.这里判断负环是根据spfa的性质,如果边权(也就是c/a)>1的话那么spfa的"缩点操作"就会无限伸长.那么这里就可以判断次数即可判断负环.而对于题目所说的要更改的w,(按照题意就是让每个边变为c/a*k,k为我们所求的倍数答案,范围是[0,1]).那么根据之前的log保证精度的写法,这个式子就变成了log(c/a)+log(k).这个k的取值对结果产生单调性,那么我们就可以采用二分k的大小,然后用SPFA判断负环进行check即可求出答案.

ps:这里向严格鸽学了个小数二分的方法,不用l<r.直接进行100次二分

for(int i=0;i<=100;i++)
    {
        double mid=(l+r)/2;
        if(check(mid))
            l=mid;
        else
            r=mid;
    }

一定可以保证精度了.

AC code:

#include<bits/stdc++.h>
using namespace std;
int tot=0,n;
struct node
{
    int to,ne;
    double val;
}edge[2010];
int h[1010];
void add(int x,int y,double val)
{
    edge[++tot].to=y;
    edge[tot].ne=h[x];
    edge[tot].val=val;
    h[x]=tot;
    return ;    
}
int vis[1010],cnt[1010];
double dis[1010];
int check(double mid)
{
    mid=log(mid);
    queue<int>qu;
    for(int i=1;i<=n;i++)
    {
        cnt[i]=vis[i]=0;
        dis[i]=0.0;
        qu.push(i);
    }
    while(qu.size())
    {
        int st=qu.front();
        qu.pop();
        vis[st]=0;
        for(int i=h[st];i!=-1;i=edge[i].ne)
        {
            double len=edge[i].val;
            int en=edge[i].to;
            if(dis[st]+mid+len>dis[en])
            {
                dis[en]=dis[st]+mid+len;
                cnt[en]=cnt[st]+1;
                if(cnt[en]>n)
                    return 0;
                if(vis[en]==0)
                {
                    vis[en]=1;
                    qu.push(en);
                }
            }
        }
    }
    return 1;
}
void solve()
{
    memset(h,-1,sizeof h);
    int m,u,v;
    double c1,c2;
    cin>>n>>m;
    while(m--)
    {
        cin>>c1>>u>>c2>>v;
        add(u,v,log(c2/c1));
    }              
    double l=0.0,r=1.0;
    for(int i=0;i<=100;i++)
    {
        double mid=(l+r)/2;
        if(check(mid))
            l=mid;
        else
            r=mid;
    }
    cout<<fixed<<setprecision(10)<<l<<endl;
    return ;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    solve();
    return 0;
}

---

G.Link with Monotonic Subsequence(构造,签到)

思路:把数组分块,每一块内保证递增,然后每一开之间保证递减即可.当两者分块接近于的时候对于结果的贡献就会更小.比如(1-9),我们分成三块1,2,3   4,5,6    7,8,9,然后把这三块倒序排列:

7,8,9,4,5,6,1,2,3.此时答案最小.

AC code:

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int l,r;
};
vector<node>ve;
void solve()
{
    ve.clear();
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int k=n/i+(n%i!=0);
        if(i<k)
            continue;
        for(int j=1;j<=n;j+=k)
            ve.push_back({j,min(n,j+k-1)});
        for(int j=ve.size()-1;j>=0;j--)
        {
            for(int k=ve[j].l;k<=ve[j].r;k++)
            {
                cout<<k<<" ";
            }
        }
        cout<<endl;
        break;
    }
    return ;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)
       solve();
 
    return 0;
}

H.Take the Elevator(模拟,贪心)

思路:n个人,一个电梯,电梯最多容纳m个人,楼高k.

我们可以把每个人上楼下楼的操作分成两类,然后都看成下楼的操作.然后进行模拟,从最高处向下走.当遇到一个区间的上端点,(把那个上下楼操作看成一个区间)就说明此时需要上来一个人.下端点就看成电梯上要下一个人.我们就记上人为+1,下人为-1.每个点就会存在一个值,再把这些值按照序号进行排序.从最高处往下遍历.当同一个点有上下人多个操作时,先下人在上人.

当到某个点时,电梯上的人超过了上限,那么就需要在这个高度的点在开一个电梯.那么我们把对于上升下降处理的两种情况.因为我们每次坐电梯都有上升下降两种操作,那么每次我们之前储存的上升下降的电梯楼层进行两两匹配,然后每次取能到的最高点,计算要经过的层数即可.

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
    int id,val;
};
bool cmp(node a,node b)
{
    if(a.id!=b.id)
        return a.id>b.id;
    else
        return a.val<b.val;
}
vector<node>up,down;
vector<int>ans_up,ans_down;
void solve()
{
    int x,y,n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>x>>y;
        if(x<y)
        {
            up.push_back({x,-1});
            up.push_back({y,1});
        }
        else if(x>y)
        {
            down.push_back({x,1});
            down.push_back({y,-1});
        }
    }
    sort(up.begin(),up.end(),cmp);
    sort(down.begin(),down.end(),cmp);

    int cnt=0;
    for(int i=0;i<up.size();i++)
    {
        cnt+=up[i].val;
        if(cnt>ans_up.size()*m)
            ans_up.push_back(up[i].id);
    }
    cnt=0;
    for(int i=0;i<down.size();i++)
    {
        cnt+=down[i].val;
        if(cnt>ans_down.size()*m)
            ans_down.push_back(down[i].id);
    }

    int maxx=max(ans_up.size(),ans_down.size());
    while(ans_up.size()<maxx)
        ans_up.push_back(0);
    while(ans_down.size()<maxx)
        ans_down.push_back(0);
    int ans=0;
    for(int i=0;i<maxx;i++)
    {
        ans+=2*(max(ans_up[i],ans_down[i])-1);
    }
    cout<<ans<<endl;
    return ;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    solve();
    return 0;
}

J.Link with Arithmetic Progression(数学,线性回归方程)

直接高中考点.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
int read() 
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
int arr[100005];
void solve()
{
    int n;
    double ans=0,xy=0.0,x2=0.0;
    n=read();
    double avgx=0.0,avgy=0.0;
    for(int i=1;i<=n;i++)
    {
        arr[i]=read();
        avgx=avgx+i;
        avgy=avgy+arr[i];
    }
    avgx/=n;
    avgy/=n;
    for(int i=1;i<=n;i++)
    {
        double ax=i-avgx,ay=arr[i]-avgy;
        xy=xy+ax*ay;
        x2=x2+ax*ax;
    }
    double k=xy/x2;
    double b=avgy-k*avgx;
    for(int i=1;i<=n;i++)
    {
        ans+=(i*k+b-arr[i])*(i*k+b-arr[i]);
    }
    printf("%.8lf\n",ans);
    return ;
}
signed main()
{
    int t;
    t=read();
    while(t--)
        solve();
    return 0;
}

K.Link with Bracket Sequence I(括号匹配,dp)

思路:f(i,j,k)的含义是原串长度为j,和子串相匹配的长度为i,此时原串左括号比右括号多k的方案的总数.

详细思路在注释里:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N =5e5+10,mod=1e9+7;
int f[210][210][210];
/*
三维状态,第三维表示此时左括号比右括号多k个
状态转移方程是:
当当前的字符串遍历到s[j]=='('时
f[i][j][k]由下面两个状态转移过来
(1)f[i-1][j-1][k-1] 和原串匹配成功,j比原来+1,当前原串此处为'(',但是原串之前要比
此时的原串少一个'(',所以原来k的要小1
(2)f[i-1][j][k+1]   和原串匹配失败,j不变,原串此时是')',同理,之前比现在多一个'(',
所以k要大1
同理
当当前的字符串遍历到s[j]==')'时
f[i][j][k]由下面两个状态转移过来
(1)f[i-1][j][k-1] 和原串匹配失败,j不变,但是此时原串是'(',但是上一层比原串少一个'('
,所以原来k的要小1
(2)f[i-1][j-1][k+1]   和原串匹配失败,原串此时是')',上一层比这一层多一个')',
所以k要大1
当当前的字符串遍历到s[j]==')'时
*/
void solve()
{
    string s;
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=m+1;i++)
        for(int j=0;j<=m+1;j++)
            for(int k=0;k<=m+1;k++)
                f[i][j][k]=0;
    cin>>s;
    s=" "+s;
    f[0][0][0]=1;
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<=n;j++)
        {
            for(int k=0;k<=i;k++)
            {
//注意边界处理!
                if(j==0)
                {   
                    if(k)
                        f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1])%mod;
                    f[i][j][k]=(f[i][j][k]+f[i-1][j][k+1])%mod;
                }
                else
                {   
                    if(s[j]=='(')
                    {    
                        if(k)
                            f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k-1]+f[i-1][j][k+1])%mod;
                        else
                            f[i][j][k]=(f[i][j][k]+f[i-1][j][k+1])%mod;
                    }
                    else
                    {
                        if(k)
                            f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]+f[i-1][j-1][k+1])%mod;
                        else
                            f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k+1])%mod;                    
                    }
                    
                }
            }
        }
    }
    cout<<f[m][n][0]<<endl;
    return ;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

L.Link with Level Editor I

思路:用dp写,详细思路见代码(有点抽象):

#include <bits/stdc++.h>
using namespace std;
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<int> f(m + 1), p(m + 1);
    //p为上一层的情况,也就是上一层到达下标的位置的最近世界编号
    //f用于转移上一层的情况,(且保证只走一步或者不走,所以还要把f的值赋给p)
    int ans =  0x3f3f3f3f;
    for (int i = 1; i <= n; i++) {
        p[1] = i;
        //如果在第i个世界从1出发
        int k;
        cin >> k;
        for (int j = 1; j <= k; j++) {
            int x, y;
            cin >> x >> y;
            f[y] = max(f[y], p[x]);
//保持不动或者走一步
            if (f[m])ans = min(ans, i - f[m] + 1);     
//f保存的就是从某个世界的1号节点能到达当前节点,存的就是这个出发世界的编号
//所以当f的值存在时,就直接相减求出
        }
        p=f;
        //到达下一层,f作为从p更新而来的下一层,到达下一层循环时就作为了新的上一层
    }
    if (ans >= 0x3f3f3f3f)
        cout << -1 << endl;
    else
        cout << ans << endl;

    return (0 ^ 0);
}