首页 > 其他分享 >2024牛客暑期多校训练营4

2024牛客暑期多校训练营4

时间：2024-07-25 20:51:33浏览次数：14  
标签：tmp p2 CI p1 int 多校 2024 牛客 mod

Preface

最赤石的一集，上来先认为 D 是个煞笔贪心提交了该题的第一发代码并喜提 WA

后面下机后祁神把 L 扔给我告诉我就是个煞笔线段树板，结果我写完过不去样例发现题意假了

值得一提的是最后发现这两题是这场过的人最少的两题，直接开局给我干的道心破碎

之后 A 题写不来带权并查集样例没过就手贱交了两发，把罚时彻底搞炸了最后只能慢慢追题数

然而科技题 E 和煞笔题 B（感觉这题榜歪了，难度其实不大）都没写出来，这下等死就完了

好在后期和祁神一起把答辩题 K 很快地写出来还一发过了，苟住了排名导致没有太难看

LCT

带权并查集腐乳闪总出列

乍一看以为是个动态维护直径的经典东西，但由于空间限制而且它保证每次询问的点都是集合的根我们就可以搞一个别的

考虑用动态维护每个联通块的根到最远的叶子的距离，每次连边 \(a\to b\) 时只要用 \(b\) 的答案加上 \(a\) 到其联通块根的距离更新贡献即可

求一个点到其联通块的路径长度是带权并查集的经典问题，但路径压缩的时候很容易写错需要注意下

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5;
int t,n,a,b,c,fa[N],dep[N],dis[N],len[N];
inline int getfa(CI x)
{
    if (x==fa[x]) return x;
    int t=getfa(fa[x]);
    dep[x]=dep[fa[x]]+len[x];
    len[x]+=len[fa[x]];
    return fa[x]=t;
}
int main()
{
    for (scanf("%d",&t);t;--t)
    {
        RI i; for (scanf("%d",&n),i=1;i<=n;++i) fa[i]=i,dep[i]=dis[i]=len[i]=0;
        for (i=1;i<n;++i)
        {
            scanf("%d%d%d",&a,&b,&c);
            int anc=getfa(a);
            dis[anc]=max(dis[anc],dep[a]+1+dis[b]);
            fa[b]=a; len[b]=1;
            printf("%d%c",dis[c]," \n"[i==n-1]);
        }
    }
    return 0;
}

Pull the Box

神秘图论题，本来和祁神讨论出一个做法了但后面又被否了，后面发现好像就是对的

需要注意到路径的形式，即一定是人先走到某个与 \(1\) 相邻的位置拉动箱子；然后就一直拉着箱子不放手直到走到终点

分别考虑两段路的走法，前者只需要简单 BFS 一下即可；后者可以将人和箱子看作相邻的两个点，因此可以把原图中的边看成点来处理

当然直接暴力转化对偶图复杂度是 \(O(n^2)\) 的，但要注意到题解中讲的一个性质发现每个点会经过不超过两次，这题就有很好写的方法了

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=1e6+5,INF=1e9;
int t,n,m,st,x,y,pos[N<<1],vis[N],dis1[N],dis2[N<<1]; vector <pi> v[N];
int main()
{
    for (scanf("%d",&t);t;--t)
    {
        RI i; scanf("%d%d%d",&n,&m,&st);
        for (i=1;i<=n;++i) v[i].clear(),vis[i]=0,dis1[i]=INF;
        int idx=0; for (i=1;i<=m;++i)
        {
            scanf("%d%d",&x,&y);
            v[x].push_back(pi(y,idx)); pos[idx++]=y;
			v[y].push_back(pi(x,idx)); pos[idx++]=x;
        }
        for (i=0;i<idx;++i) dis2[i]=INF;
        dis1[st]=0; queue <int> q; q.push(st);
        while (!q.empty())
        {
            int now=q.front(); q.pop();
            for (auto [to,id]:v[now])
            if (to!=1&&dis1[to]>dis1[now]+1) dis1[to]=dis1[now]+1,q.push(to);
        }
        for (auto [x,id]:v[n]) dis2[id^1]=0,dis2[id]=1,q.push(id);
        while (!q.empty())
        {
        	int ne=q.front(),now=pos[ne]; q.pop();
        	if (++vis[now]>2) continue;
        	for (auto [to,id]:v[now])
        	{
        		if (id==(ne^1)) continue;
        		if (dis2[id]>dis2[ne]+1)
        		dis2[id]=dis2[ne]+1,q.push(id);
        	}
        }
        int ans=INF; for (auto [x,id]:v[1])
        ans=min(ans,dis1[x]+dis2[id^1]);
        if (v[n].size()<=1||ans>=INF) puts("Boring Game");
        else printf("Vegetable fallleaves\n%d\n",ans);
    }
    return 0;
}

Sort4

考虑原排列所构成的置换环，对于长度恰为 \(3,4\) 的环可以一次排好；否则对于长度 \(len>4\) 的环可以每次排好其中三个元素，规约成 \(len-3\) 的问题

而长度恰为 \(2\) 的环就比较特殊，可以每次挑两个一起复原，因此这部分特殊处理即可

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

const int N = 1e6+5;
int t, n, A[N];
bool vis[N];

int dfs(int x, int d){
    if (vis[x]) return d;
    else{
        vis[x]=true;
        return dfs(A[x], d+1);
    }
}
signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> t;
    while (t--){
        cin >> n;
        for (int i=1; i<=n; ++i) cin >> A[i], vis[i]=false;
        int sz2=0, ans=0;
        for (int i=1; i<=n; ++i) if (!vis[i]){
            int res = dfs(i, 0);
            // printf("t=%d i=%d res=%d\n", t, i, res);
            ans += res/3;
            if (res%3==2) ++sz2;
        }
        ans += (sz2+1)/2;
        cout << ans << '\n';
    }
    return 0;
}

Plants vs. Zombies (Sunflower Edition)

开场以为是个煞笔贪心冲上去很快地似了，还好后面马上发现自己 trivial 了马上扔了这题没有重蹈校赛的覆辙

String God's String

多项式科技题，徐神一眼秒了这题字符串的处理部分，然后发现对于这题转化后的 0/1 背包部分做不了一点，直接坐牢到结束

由于我根本不会啥多项式科技这题就扔给徐神补了，徐神也是决定重写一遍多项式全家桶的板子以备不时之需

Good Tree

神秘乱搞构造题，当时随便写了个东西后抱着交一发试试的心态冲了一发，没想到直接就过了

考虑先构造一条有 \(d\) 个点的链，显然最大化差值的两个点选在两个端点处最优，差值初始时为 \(0\)

不难发现此时可以通过在每个点下面挂点使得差值每次增加 \(d-1,d-3,d-5,\dots\)

因此很直观地会想到 \(d\) 取 \(\sqrt x\) 左右大致是最优的，但可能需要左右微调一下

然后我就写了一个以 \(\sqrt x\) 为中心左右各取 \(5\) 个数作为链的长度的东西，然后交上去就过了

这个构造的正确性证明可以参考官方题解，这种写法就省去了繁琐的讨论部分

#include<cstdio>
#include<iostream>
#include<cmath>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int INF=1e18;
int t,n;
inline int calc(CI x)
{
    int cnt=x,tmp=n;
    while (tmp>0)
    {
        int y; if (tmp>=x-1) y=x-1;
        else
        {
            y=tmp;
            if (y%2!=(x-1)%2) --y;
        }
        if (y==0) return INF;
        cnt+=tmp/y; tmp-=tmp/y*y;
    }
    return cnt;
}
signed main()
{
    for (scanf("%lld",&t);t;--t)
    {
        scanf("%lld",&n); int ans=INF;
        int l=max(2LL,(int)sqrt(n)-5),r=(int)sqrt(n)+5;
        for (RI i=l;i<=r;++i) ans=min(ans,calc(i));
        printf("%lld\n",ans);
    }
    return 0;
}

Horse Drinks Water

应该是个签，我题目都没看

#include <bits/stdc++.h>

using ll = long long;

long double L2(ll x1, ll y1, ll x2, ll y2) {
    return sqrtl((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main() {
    std::ios::sync_with_stdio(false);
    int t; std::cin >> t; while(t--) {
        int64_t x1, y1, x2, y2;
        std::cin >> x1 >> y1 >> x2 >> y2;
        std::cout << std::fixed << std::setprecision(15)
            << std::min(
                L2(-x1, y1, x2, y2),
                L2(x1, -y1, x2, y2)
            ) << char(10);
    }
    return 0;
}

Yet Another Origami Problem

徐神开场秒的，当时我还在和 L 题的错误题意 version 搏斗，因此连这题题意都不知道

from math import gcd

T = int(input())

for t in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    min_a = min(a)
    if min_a == max(a):
        print(0)
        continue
    g = 0
    for i in range(1, n):
        g = gcd(g, a[i] - min_a)
    
    print(g)

Friends

拿个 two pointers 随便搞一搞就过了

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> fd(n + 1);
    for(int i = 1, u, v; i <= m; ++i) {
        std::cin >> u >> v;
        fd[v].push_back(u);
    }
    int l = 0;
    int ans = 0;
    for(int i = 1; i <= n; ++i) {
        auto &fs = fd[i];
        fs.push_back(i);
        std::sort(fs.begin(), fs.end());
        int cc = 0;
        for(int j = 0; j < fs.size() - 1; ++j) if(fs[j] < fs[j + 1] - 1) cc = j + 1;
        ans += i - (l = std::max(l, fs[cc])) + 1;
        // std::cout << l << ", " << i << char(10);
    }
    std::cout << ans << char(10);
    return 0;
}

Zero

徐神太有实力了，直接用随机过程的方法淦过去了，我一点听不懂做法

大致思路就是求出以每个点为右端点时，连续的 \(1\) 的数量的期望，然后一波神秘拆贡献计算即可

 #include <bits/stdc++.h>

using llsi = long long signed int;

constexpr llsi mod = 998244353;

constexpr llsi ksm(llsi a, llsi b) {
    llsi res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

constexpr llsi inv2 = ksm(2, mod - 2);

llsi C[32][32], p[100001], e[100001][32], B[32][32];

int main() {
    std::ios::sync_with_stdio(false);
    int n, K; std::cin >> n >> K;
    for(int i = 0; i <= 31; ++i) C[i][0] = 1;
    for(int i = 1; i <= 31; ++i) for(int j = 1; j <= i; ++j)
        C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    
    std::string s; std::cin >> s;
    
    for(int i = 1; i <= n; ++i) {
        switch(s[i - 1]) {
            case '0': p[i] = 0; break;
            case '1': p[i] = 1; break;
            case '?': p[i] = inv2; break;
        }
    }
    
    for(int i = 0; i <= n; ++i) e[i][0] = 1;
    for(int i = 1; i <= n; ++i) for(int k = 1; k <= K + 1; ++k) {
        for(int j = 0; j <= k; ++j) {
            e[i][k] += C[k][j] * e[i - 1][j] % mod;
        }
        e[i][k] = e[i][k] % mod * p[i] % mod;
    }
    
//     for(int i = 1; i <= n; ++i) std::cout << e[i][K] << char(i == n ? 10 : 32);
    B[0][1] = 1;
    for(int k = 1; k <= K + 1; ++k) {
        for(int j = 1; j <= k + 1; ++j) B[k][j] = C[k + 1][j];
        for(int j = 0; j <= k - 1; ++j) {
            for(int l = 0; l <= j + 1; ++l)
                B[k][l] += mod - B[j][l] * C[k + 1][j] % mod;
        }
        for(int j = 0; j <= k + 1; ++j) B[k][j] = B[k][j] % mod * ksm(k + 1, mod - 2) % mod;
    }
//     for(int i = 1; i <= K + 1; ++i)
//         for(int j = 0; j <= i + 1; ++j)
//             std::cout << B[i][j] << char(j == i + 1 ? 10 : 32);
    llsi ans = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= K + 1; ++j)
            ans += e[i][j] * B[K][j] % mod;
    }
    std::cout << ans % mod << char(10);
    return 0;
}

Calculate the Expression

究极赤石题，做法一眼就出但写起来就是纯纯的享受

这种单点修改区间查询一眼线段树维护，难点在于如何设计区间存储的状态

在和祁神一波讨论后发现大致可以分为以下三种类型存储区间：

  • 含有至少一个 +：这种区间可以规约为形如 \(a\times b+c\times d\) 的形式，其中 \(a,d\)​ 都是可能继续扩展的数
  • 含有至少一个 *：这种区间可以规约为形如 \(a\times b\times c\) 的形式，其中 \(a,c\) 都是可能继续扩展的数
  • 否则该区间只有单纯的数字，需要特殊处理

合并时需要根据左右两个区间的类型分 \(3\times 3=9\)​ 种类型讨论，总复杂度 \(O(n\log n)\)

建议这题写之前在纸上手玩清楚再上机就不太容易写错，我赛时写这题的时候也是把祁神摇过来当 Debugger 全程理清思路才能一发入魂

#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=500005,mod=998244353;
int q,n,pw[N]; char s[N];
inline int S(CI x,CI y)
{
    return x+y>=mod?x+y-mod:x+y;
}
inline void inc(int& x,CI y)
{
    if ((x+=y)>=mod) x-=mod;
}
struct ifo
{
    int l,r,a,b,c,d,p1,p2,res,add,mul;
    inline ifo(CI L=0,CI R=0,CI A=0,CI B=0,CI C=0,CI D=0,CI P1=0,CI P2=0,CI Res=0,CI Add=0,CI Mul=0)
    {
        l=L; r=R; a=A; b=B; c=C; d=D; p1=P1; p2=P2; res=Res; add=Add; mul=Mul;
    }
    inline int type(void) const
    {
        if (add) return 1;
        if (mul) return 2;
        return 3;
    }
    inline int val(void) const
    {
        int tp=type();
        if (tp==1) return S(res,(1LL*a*b+1LL*c*d)%mod);
        if (tp==2) return S(res,1LL*a*b%mod*c%mod);
        return S(res,a);
    }
    inline void init(const char& ch)
    {
        if (ch=='+') add=1,b=c=1,p1=p2=l; else
        if (ch=='*') mul=1,b=1,p1=p2=l; else a=ch-'0';
    }
};
inline ifo operator + (const ifo& A,const ifo& B)
{
    ifo C; int tpa=A.type(),tpb=B.type();
    C.l=A.l; C.r=B.r;
    C.res=S(A.res,B.res);
    C.add=A.add|B.add; C.mul=A.mul|B.mul;
    if (tpa==1&&tpb==1)
    {
        int tmp=S(1LL*A.d*pw[B.p1-B.l]%mod,B.a);
        tmp=1LL*tmp*A.c%mod*B.b%mod;
        inc(C.res,tmp);
        C.a=A.a; C.b=A.b; C.c=B.c; C.d=B.d;
        C.p1=A.p1; C.p2=B.p2;
    } else
    if (tpa==1&&tpb==2)
    {
        int tmp=S(1LL*A.d*pw[B.p1-B.l]%mod,B.a);
        tmp=1LL*tmp*A.c%mod*B.b%mod;
        C.a=A.a; C.b=A.b; C.c=tmp; C.d=B.c;
        C.p1=A.p1; C.p2=B.p2;
    } else
    if (tpa==1&&tpb==3)
    {
        int tmp=S(1LL*A.d*pw[B.r-B.l+1]%mod,B.a);
        C.a=A.a; C.b=A.b; C.c=A.c; C.d=tmp;
        C.p1=A.p1; C.p2=A.p2;
    } else
    if (tpa==2&&tpb==1)
    {
        int tmp=S(1LL*A.c*pw[B.p1-B.l]%mod,B.a);
        tmp=1LL*tmp*A.b%mod*B.b%mod;
        C.a=A.a; C.b=tmp; C.c=B.c; C.d=B.d;
        C.p1=A.p1; C.p2=B.p2;
    } else
    if (tpa==2&&tpb==2)
    {
        int tmp=S(1LL*A.c*pw[B.p1-B.l]%mod,B.a);
        tmp=1LL*tmp*A.b%mod*B.b%mod;
        C.a=A.a; C.b=tmp; C.c=B.c;
        C.p1=A.p1; C.p2=B.p2;
    } else
    if (tpa==2&&tpb==3)
    {
        int tmp=S(1LL*A.c*pw[B.r-B.l+1]%mod,B.a);
        C.a=A.a; C.b=A.b; C.c=tmp;
        C.p1=A.p1; C.p2=A.p2;
    } else
    if (tpa==3&&tpb==1)
    {
        int tmp=S(1LL*A.a*pw[B.p1-B.l]%mod,B.a);
        C.a=tmp; C.b=B.b; C.c=B.c; C.d=B.d;
        C.p1=B.p1; C.p2=B.p2;
    } else
    if (tpa==3&&tpb==2)
    {
        int tmp=S(1LL*A.a*pw[B.p1-B.l]%mod,B.a);
        C.a=tmp; C.b=B.b; C.c=B.c;
        C.p1=B.p1; C.p2=B.p2;
    } else
    if (tpa==3&&tpb==3)
    {
        C.a=S(1LL*A.a*pw[B.r-B.l+1]%mod,B.a);
    }
    return C;
}
class Segment_Tree
{
    private:
        ifo O[N<<2];
    public:
        #define TN CI now=1,CI l=1,CI r=n
        #define LS now<<1,l,mid
        #define RS now<<1|1,mid+1,r
        inline void build(TN)
        {
            if (l==r)
            {
                O[now]=ifo(); O[now].l=O[now].r=l;
                return O[now].init(s[l]);
            }
            int mid=l+r>>1; build(LS); build(RS);
            O[now]=O[now<<1]+O[now<<1|1];
        }
        inline void update(CI pos,const char& ch,TN)
        {
            if (l==r)
            {
                O[now]=ifo(); O[now].l=O[now].r=l;
                return O[now].init(ch);
            }
            int mid=l+r>>1;
            if (pos<=mid) update(pos,ch,LS); else update(pos,ch,RS);
            O[now]=O[now<<1]+O[now<<1|1];
        }
        inline ifo query(CI beg,CI end,TN)
        {
            if (beg<=l&&r<=end) return O[now]; int mid=l+r>>1;
            if (end<=mid) return query(beg,end,LS);
            if (beg>mid) return query(beg,end,RS);
            return query(beg,end,LS)+query(beg,end,RS);
        }
        #undef TN
        #undef LS
        #undef RS
}SEG;
int main()
{
    RI i; scanf("%d%s",&q,s+1); n=strlen(s+1);
    for (pw[0]=i=1;i<=n;++i) pw[i]=10LL*pw[i-1]%mod;
    for (SEG.build();q;--q)
    {
        int opt; scanf("%d",&opt);
        if (opt==1)
        {
            int l,r; scanf("%d%d",&l,&r);
            printf("%d\n",SEG.query(l,r).val());
        } else
        {
            int x; char ch[5]; scanf("%d%s",&x,ch);
            SEG.update(x,ch[0]);
        }
    }
    return 0;
}

Deceleration

赛时把 第 \(x\) 秒减速 看成 第 \(x\) 个位置减速 了，然后冲了个线段树连样例都过不去，直接把罚时搞炸了

不想补题了直接白兰吧

Postscript

今天这场算是难得的后期发力了，能不能以后每场都出点像 K 这样的赤石题给我做啊，就好这一口赤石

标签：tmp,p2,CI,p1,int,多校,2024,牛客,mod
From： https://www.cnblogs.com/cjjsb/p/18324117

相关文章

  • 2024暑假集训测试11
    前言比赛链接。这次好多外校的参加\(60\)多个人，反正至少没怎么挂分。确切的说赛时我只能冲T1、T2，T3可撤销或可持久化并查集都不会，赛后现学的，T4更抽象，可惜T2打假了。T3最后五分钟才开始看，没想直接打暴力了。但是T3数据太水了，加了捆绑还是水，赛后安排了重测。T1Pe......
  • 河南萌新联赛2024第（二）场：南阳理工学院
    A-国际旅行Ⅰ因为保证联通，所以直接排序就好了#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingvi=vector<int>;i32main(){ intn,m,q; cin>>n>>m>>q; via(n); for(int&i:a)cin>>i; sort(a......
  • 【专题】2024年云计算白皮书报告合集PDF分享（附原数据表）
    原文链接：https://tecdat.cn/?p=371122023年全球云计算市场显著增长，预计将持续繁荣至2027年突破万亿美元，中国市场同样保持强劲势头，预计也将大幅跃升。国内云计算经过十余年发展，虽取得显著进展，但在资源布局、服务质量和技术融合等方面仍需深化提升。阅读原文，获取专题报告合集全文，解......
  • 平邑2024高算（补题）
    Day1risk题目描述解法考虑最后的集结，不妨考虑找出所有集结过程中可能经过的边，不难发现是一棵树，所以答案就是最小生成树。代码点击查看代码structnode{ intu,v,w;}e[3000001];intn,m;intfa[3000001];intfind(intx){ returnx==fa[x]?fa[x]:fa[x]=find(......
  • 多校数据结构
    多校数据结构省选选手不再需要学习新数据结构，主要需要学习数据结构题目的常见套路，训练代码能力，提升思维能力。因此，此次授课主要提供各种类型的数据结构题目，点拨解题思路，为选手在比赛中处理各类数据结构问题提供参考。[CF1039D]YouAreGivenaTree题目描述有一棵\(n\)个......
  • 2024 暑假友谊赛-热身2
    TreeDestruction-洛谷|计算机科学教育新生态(luogu.com.cn)思路:树的直径。定理：在一棵树上，从任意节点y开始进行一次DFS，到达的距离其最远的节点z必为直径的一端。第一次dfs1(),从任意一个点,到达的最远的点必然是直径两端的其中一个。再从找到的端点开始dfs1(),......
  • NOIP2024/7/25模拟赛
    T4题意：答案对\(2^{16}\)取模。分析：根节点\(1\)选到\(1\)的概率为\(\frac{1}{n}\)，然后随便把剩下的\(n-1\)分配给它的所有子树，记\(1\)的其中一个儿子为\(y\)，那么\(y\)选到它所被分配到的数中最小值的概率为\(\frac{1}{siz_{y}}\)，然后\(y\)再继续分配给它的子......
  • 河南萌新联赛2024第（二）场：南阳理工学院
    1.D-A*BBBB原题链接：https://ac.nowcoder.com/acm/contest/87255/D根据乘法的原理，且b的每一位都相同，最终答案则是错位相加得出的结果，于是我们将a翻转，从个位开始计算，如果当前位置小于a.size就往前累加，但如果大于或等于b.size就从头开始一个一个的减（这个过程可以通过纸上手写乘法计......
  • 2024.7.25（Git、gitlab以及分支管理）
    分布式版本控制系统一、Git概述Git是一种分布式版本控制系统,用于跟踪和管理代码的变更。它是由LinusTorvalds创建的,最初被设计用于Linux内核的开发。Git允许开发人员跟踪和管理代码的版本,并且可以在不同的开发人员之间进行协作。Github用的就是Git系统来管理它们的网......
  • Metasploit Pro 4.22.2-2024071901 (Linux, Windows) - 专业渗透测试框架
    MetasploitPro4.22.2-2024071901(Linux,Windows)-专业渗透测试框架Rapid7Penetrationtesting,releaseJul19,2024请访问原文链接：https://sysin.org/blog/metasploit-pro-4/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.org世界上最广泛使用的渗透测试框架......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99