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

2024牛客暑期多校训练营9

时间:2024-08-13 19:17:00浏览次数:8  
标签:const int 多校 2024 牛客 return include RI define

Preface

久违的多校,又被徐神带飞力

这场总体可做题挺多的,前期出题也还算稳,但中间祁神写 H 睿智错误频发直接红温爆交了 7 发

但无所谓徐神会出手,上机把当时只过了两个队的 G 秒了,然后我爬上去把 B,C 写了然后对着 D 罚坐一整场

赛后经典看不懂出题人的一句话题解,坐等视频讲解吧(虽然看了也不一定看得懂)


Image Scaling

签到,将边长除以 \(\gcd\) 即可

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=505;
int n,m,W,H; char s[N][N];
int main()
{
    scanf("%d%d",&n,&m);
    for (RI i=1;i<=n;++i) scanf("%s",s[i]+1);
    for (RI i=1;i<=n;++i) for (RI j=1;j<=m;++j)
    if (s[i][j]=='x')
    {
        W=0; while (i+W<=n&&s[i+W][j]=='x') ++W;
        H=0; while (j+H<=m&&s[i][j+H]=='x') ++H;
        int g=__gcd(W,H); W/=g; H/=g;
        for (RI i=1;i<=W;++i,putchar('\n'))
        for (RI j=1;j<=H;++j) putchar('x');
        return 0;
    }
    return 0;
}

Break Sequence

2024牛客暑期多校训练营7的 D 思路几乎一模一样

朴素的想法就是令 \(f_i\) 表示以 \(i\) 为结尾的划分方案数,大力 \(O(n^2)\) 转移

但实际上由于每个数都要满足个数的限制,因此只看一种数,在固定右端点的情况下它合法的左端点一定是 \(O(m)\) 级别的若干区间

因此类似地用线段树维护贡献,和那题的区别就是维护信息的第二维不再是个数而是对应位置的 DP 方案数之和,还是在最大值等于数的总数时更新答案

当右端点变化时贡献的讨论比较繁琐,需要耐心且细致的讨论

总复杂度 \(O(nm\log n)\)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=200005,INF=1e9,mod=998244353;
int n,m,cnt,vis[N],a[N],b[N],f[N]; vector <int> pos[N];
inline int sum(CI x,CI y)
{
    return x+y>=mod?x+y-mod:x+y;
}
inline pi operator + (const pi& A,const pi& B)
{
    if (A.fi>B.fi) return A;
    if (A.fi<B.fi) return B;
    return {A.fi,sum(A.se,B.se)};
}
class Segment_Tree
{
    private:
        pi O[N<<2]; int tag[N<<2];
        inline void pushup(CI now)
        {
            O[now]=O[now<<1]+O[now<<1|1];
        }
        inline void apply(CI now,CI mv)
        {
            O[now].fi+=mv; tag[now]+=mv;
        }
        inline void pushdown(CI now)
        {
            if (tag[now]) apply(now<<1,tag[now]),apply(now<<1|1,tag[now]),tag[now]=0;
        }
    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 modify(CI beg,CI end,CI mv,TN)
        {
            if (beg<=l&&r<=end) return apply(now,mv); int mid=l+r>>1; pushdown(now);
            if (beg<=mid) modify(beg,end,mv,LS); if (end>mid) modify(beg,end,mv,RS);
            pushup(now);
        }
        inline void update(CI pos,CI mv,TN)
        {
            if (l==r) return (void)(O[now].se=mv); int mid=l+r>>1; pushdown(now);
            if (pos<=mid) update(pos,mv,LS); else update(pos,mv,RS); pushup(now);
        }
        inline pi query(CI beg,CI end,TN)
        {
            if (beg<=l&&r<=end) return O[now]; int mid=l+r>>1; pushdown(now);
            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()
{
    scanf("%d%d",&n,&m);
    for (RI i=1;i<=n;++i) scanf("%d",&a[i]);
    for (RI i=1;i<=m;++i) scanf("%d",&b[i]);
    sort(b+1,b+m+1); f[0]=1;
    for (RI i=1;i<=n;++i) if (!vis[a[i]]) ++cnt,vis[a[i]]=1;
    for (RI i=1;i<=n;++i)
    {
        auto work=[&](vector <int>& pos,CI mv)
        {
            if (m==0) return;
            int sz=pos.size(),L,R;
            for (RI j=2;j<=m;++j)
            {
                R=b[j-1]+1; L=b[j];
                if (R>sz) R=-INF; else R=pos[sz-R];
                if (L>sz) L=1; else L=pos[sz-L]+1;
                if (L<=R) SEG.modify(L,R,mv);
            }
            L=b[1]; R=i;
            if (L>sz) L=1; else L=pos[sz-L]+1;
            if (L<=R) SEG.modify(L,R,mv);
            L=1; R=b[m]+1;
            if (R>sz) R=-INF; else R=pos[sz-R];
            if (L<=R) SEG.modify(L,R,mv);
        };
        SEG.update(i,f[i-1]);
        SEG.modify(i,i,cnt);
        work(pos[a[i]],-1);
        pos[a[i]].push_back(i);
        work(pos[a[i]],1);
        pi tmp=SEG.query(1,i);
        //printf("i = %d; cnt = %d; val = %d\n",i,tmp.fi,tmp.se);
        if (tmp.fi==cnt) f[i]=tmp.se; else f[i]=0;
    }
    return printf("%d",f[n]),0;
}

Change Matrix

很典的约数容斥题,比赛的时候貌似写丑了写了 \(O(n\log^2 n)\) 的东西上去但还是一发过了

考虑快速计算编号为 \(k\) 的行的贡献,不难发现这一行的所有数初始时都是 \(k\) 的约数,有:

\[R(k)\times \sum_{g|k} g\times f(g) \]

其中 \(f(g)\) 表示 \([1,n]\) 中与 \(k\) 的 \(\gcd\) 值为 \(g\) 的数的个数,这个很容易用约数容斥算出;\(R(k)\) 为第 \(k\) 行乘上的数

但现在的问题是随着某些列被乘上一些数后,就不能简单地用个数来刻画贡献了

不过我们可以修改 \(f(g)\) 的定义,将列的乘法贡献也包含在内,只要在修改列的时候将其约数对应的 \(f(\star)\) 一并修改即可

单次复杂度为 \(d^2(x)\),其中 \(d(x)\) 为 \(x\) 的约数个数,在数据随机的情况下可以看作 \(O(n\log^2 n)\)

#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,mod=1e9+7;
int n,q,R[N],C[N],FR[N],FC[N],ans; vector <int> frac[N];
inline void inc(int& x,CI y)
{
    if ((x+=y)>=mod) x-=mod;
}
inline void dec(int& x,CI y)
{
    if ((x-=y)<0) x+=mod;
}
inline void init(CI n)
{
    for (RI i=1;i<=n;++i) for (RI j=i;j<=n;j+=i) frac[j].push_back(i);
}
inline int calcR(CI k)
{
    int ret=0; vector <int> tmp(frac[k].size(),0);
    for (RI i=frac[k].size()-1;i>=0;--i)
    {
        int d=frac[k][i]; tmp[i]=FC[d];
        for (RI j=i+1;j<frac[k].size();++j)
        if (frac[k][j]%d==0) dec(tmp[i],tmp[j]);
        inc(ret,1LL*d*tmp[i]%mod);
    }
    return 1LL*ret*R[k]%mod;
}
inline int calcC(CI k)
{
    int ret=0; vector <int> tmp(frac[k].size(),0);
    for (RI i=frac[k].size()-1;i>=0;--i)
    {
        int d=frac[k][i]; tmp[i]=FR[d];
        for (RI j=i+1;j<frac[k].size();++j)
        if (frac[k][j]%d==0) dec(tmp[i],tmp[j]);
        inc(ret,1LL*d*tmp[i]%mod);
    }
    return 1LL*ret*C[k]%mod;
}
int main()
{
    scanf("%d%d",&n,&q); init(n);
    for (RI i=1;i<=n;++i) R[i]=C[i]=1,FR[i]=FC[i]=n/i;
    for (RI i=1;i<=n;++i) inc(ans,calcR(i));
    for (RI i=1;i<=q;++i)
    {
        char opt[5]; int x,y;
        scanf("%s%d%d",opt,&x,&y);
        if (opt[0]=='R')
        {
            dec(ans,calcR(x));
            for (auto d:frac[x]) dec(FR[d],R[x]);
            R[x]=1LL*R[x]*y%mod;
            for (auto d:frac[x]) inc(FR[d],R[x]);
            inc(ans,calcR(x));
        } else
        {
            dec(ans,calcC(x));
            for (auto d:frac[x]) dec(FC[d],C[x]);
            C[x]=1LL*C[x]*y%mod;
            for (auto d:frac[x]) inc(FC[d],C[x]);
            inc(ans,calcC(x));
        }
        printf("%d\n",ans);
    }
    return 0;
}

Luner XOR

看起来是个可做题,比赛的时候徐神和祁神在讨论一个 sosdp 的做法,但没有 Rush 出来

赛后看题解就只有一句话,式子中间也没有转化啥的直接歇逼,只能等讲题视频出来去试着听一手了


Sticky Pistons

徐神伟大,无需多言

据徐神说好像就是个经典的贪心,但我题目都没看就不作评论了

#include <bits/stdc++.h>

int a[1005] = {-100};

std::vector<int> push(int n, int k) {
    int p = n + 1, q = p - 1;
    std::vector<int> res;
    std::vector<std::pair<int, int>> op;
    while(p > 0) {
        while(p - q <= k && a[p] - p == a[q] - q) q--;
        if(q == p - 1) { p = q; continue; }
        res.push_back(q + 1);
        op.push_back({q + 2, p});
        if(p - q > k && a[p] - p == a[q] - q) break;
        p = q;
    }
    for(auto [l, r]: op) {
        // std::cout << "[" << l << ", " << r << "]\n";
        for(int i = l; i <= r; ++i) a[i]++;
    }
//     if(res.size()) {
//         std::cout << "debug: ";
//         for(int i = 1; i <= n + 1; ++i) std::cout << a[i] << char(i == n + 1 ? 10 : 32);
//     }
    return res;
}

void printv(std::vector<std::vector<int>> ops) {
    std::cout << ops.size() << char(10);
    for(auto op: ops) {
        std::sort(op.begin(), op.end());
        std::cout << op.size();
        for(auto op: op) std::cout << ' ' << op;
        std::cout << char(10);
    }
}

void work() {
    int n, k;
    std::cin >> n >> k;
    std::vector<std::vector<int>> ans1, ans2;
    for(int i = 1; i <= n + 1; ++i) a[i] = i;
    for(;;) {
        auto v = push(n, k);
        if(v.empty()) break;
        ans1.push_back(v);
    }
    for(int i = 1; i <= n + 1; ++i) a[i] = i;
    for(;;) {
        auto v = push(n, 1);
        if(v.empty()) break;
        ans2.push_back(v);
    }
    printv(ans1);
    std::reverse(ans2.begin(), ans2.end());
    printv(ans2);
}

int main() {
    std::ios::sync_with_stdio(false);
    int t; std::cin >> t; while(t--) work();
    return 0;
}

Two Convex Polygons

简单手玩发现答案就是 \(A\) 的周长加上以 \(B\) 的直径为半径的圆的周长

求凸包直径可以经典旋转卡壳,然后这题就做完了

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

using LD = long double;
constexpr LD PI = acos(-1.0L);

struct Pt{
    int x, y;
    int len2()const{return x*x+y*y;}
    LD len()const{return sqrtl(x*x+y*y);}
    int crs(const Pt &b)const{return x*b.y-y*b.x;}
    Pt operator-(const Pt &b)const{return Pt{x-b.x, y-b.y};}
};
int cross(const Pt &p, const Pt &a, const Pt &b){return abs((a-p).crs(b-p));}

void solve(){
    int n; cin >> n; vector<Pt> A(n);
    for (int i=0; i<n; ++i){
        int x, y; cin >> x >> y;
        A[i] = Pt{x, y};
    }
    int m; cin >> m; vector<Pt> B(m*2+1);
    for (int i=0; i<m; ++i){
        int x, y; cin >> x >> y;
        B[m+i] = B[i] = Pt{x, y};
    }
    B[2*m] = B[0];

    int R2 = 0;
    for (int i=0, j=0; i<m; ++i){
        R2 = max({R2, (B[j]-B[i]).len2(), (B[j]-B[i+1]).len2()});
        while (j<2*m && cross(B[i], B[i+1], B[j]) <= cross(B[i], B[i+1], B[j+1])){
            ++j;
            R2 = max({R2, (B[j]-B[i]).len2(), (B[j]-B[i+1]).len2()});
        }
    }

    LD ans=0.0L;
    for (int i=0; i<n; ++i){
        ans += (A[(i+1)%n]-A[i]).len();
    }
    ans += 2*PI*sqrtl(R2);
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cout << setiosflags(ios::fixed) << setprecision(15);
    int t; cin >> t; while (t--) solve();
    return 0;
}

Interesting Numbers

不难发现把 \(L,R\) 分成两部分后两边的取值都只有 \(10^{30}\) 范围,在 __int128 可表示的范围内

很容易根据前半部分的取值是否卡住边界来推出后半部分的取值范围,计算数量的话只要开根号即可

但为了避免精度误差建议手动二分开根,不然可能会爆精度

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
typedef __int128 i128;
const int N=65;
int n; i128 pw[35]; char L[N],R[N];
inline void write(i128 x)
{
    if (x>9) write(x/10); putchar(x%10+'0');
}
inline i128 calc(i128 L,i128 R)
{
    if (L>R) return 0;
    i128 l=0,r=pw[15],retl=-1;
    while (l<=r)
    {
        i128 mid=l+(r-l)/2;
        if (mid*mid>=L) retl=mid,r=mid-1;
        else l=mid+1;
    }
    if (retl==-1) return 0;
    l=0; r=pw[15]; i128 retr=-1;
    while (l<=r)
    {
        i128 mid=l+(r-l)/2;
        if (mid*mid<=R) retr=mid,l=mid+1;
        else r=mid-1;
    }
    if (retr==-1) return 0;
    if (retl>retr) return 0;
    return retr-retl+1;
}
int main()
{
    scanf("%d%s%s",&n,L+1,R+1);
    pw[0]=1; for (RI i=1;i<=30;++i) pw[i]=pw[i-1]*10;
    i128 L1=0,L2=0,R1=0,R2=0;
    for (RI i=1;i<=n/2;++i) L1=L1*10+L[i]-'0';
    for (RI i=n/2+1;i<=n;++i) L2=L2*10+L[i]-'0';
    for (RI i=1;i<=n/2;++i) R1=R1*10+R[i]-'0';
    for (RI i=n/2+1;i<=n;++i) R2=R2*10+R[i]-'0';
    i128 ans=calc(L1+1,R1-1)*calc(0,pw[n/2]-1);
    if (L1!=R1)
    {
        ans+=calc(L1,L1)*calc(L2,pw[n/2]-1);
        ans+=calc(R1,R1)*calc(0,R2);
    } else ans+=calc(L1,R1)*calc(L2,R2);
    return write(ans),0;
}

Kill The Monsters

注意到如果对一个怪用了多种操作,则优先进行操作二一定最优

特判掉 \(k=1\) 的情况后,考虑枚举进行的操作二的次数,不难发现每次操作一定是对当前最大的数执行

用堆动态维护全局最大值,由于操作二的次数不超过 \(O(n\log a_i)\),因此总复杂度 \(O(n\log a_i\log n)\) 可以通过

#include<cstdio>
#include<iostream>
#include<queue>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,k,a[N];
signed main()
{
    scanf("%lld%lld",&n,&k); int mx=0;
    for (RI i=1;i<=n;++i) scanf("%lld",&a[i]),mx=max(mx,a[i]);
    if (k==1) return printf("%lld\n",mx),0;
    priority_queue <int> hp; int ans=mx;
    for (RI i=1;i<=n;++i) hp.push(a[i]);
    for (int c=1;;++c)
    {
        int tmp=hp.top(); hp.pop();
        if (tmp==0) break;
        tmp/=k; hp.push(tmp);
        ans=min(ans,hp.top()+c);
    }
    return printf("%lld",ans),0;
}

Postscript

今天这场结束后好像只有周四周五两场多校了(周日的 HDU 要去打 Astar 所以不打),这么看来暑假也是一转眼要结束了

标签:const,int,多校,2024,牛客,return,include,RI,define
From: https://www.cnblogs.com/cjjsb/p/18357557

相关文章

  • DRM:清华提出无偏差的新类发现与定位新方法 | CVPR 2024
    论文分析了现有的新类别发现和定位(NCDL)方法并确定了核心问题:目标检测器往往偏向已知的目标,忽略未知的目标。为了解决这个问题,论文提出了去偏差区域挖掘(DRM)方法,以互补的方式结合类无关RPN和类感知RPN进行目标定位,利用未标记数据的半监督对比学习来改进表征网络,以及采用简单高效的m......
  • 2024亚太杯数学建模b题基于机器学习回归的洪水预测模型研究
    本届亚太杯中文赛项已经结束,本文分享我的解决思路。摘 要洪水的频率和严重程度与人口增长趋势相近。迅猛的人口增长,扩大耕地,围湖造田,乱砍滥伐等人为破坏不断地改变着地表状态,改变了汇流条件,加剧了洪灾程度。2023年,全球洪水造成了数十亿美元的经济损失。因此构建与研究洪水......
  • 20240813:组合计数选做
    P3214[HNOI2011]卡农题意:\(m\)个集合,\(n\)种元素,求集合间互不相同且每种元素出现偶数次的方案数。题目等价于从\(1\sim2^n-1\)里选出\(m\)个不同的数,使他们异或和为\(0\)。不妨对每个数标号,由于互不相同,最后除以\(m!\)即可。设\(f_i\)表示前\(i\)个数异或......
  • 2024年导游考试题库及答案
    1、下列有关接待宗教旅游团(者)的说法中,正确的有________。A、非穆斯林到穆斯林家中做客时,一般不主动与妇女或少女握手B、穆斯林客人禁食鳗鱼C、对基督徒可称呼弟兄、姐妹D、对佛教徒不可以道“辛苦”E、送穆斯林中国火腿答案:ABC2、导游员小张在带团过程中强迫旅游者进购......
  • 搬砖人2024年的智能工作伙伴 —— 4款思维导图软件种草集!
    幕布思维导图这玩意儿特别厉害,成了很多学生学习的好帮手,在学习中经常觉得信息太多太乱,不好理清楚。这时候用幕布思维导图,我们可以把那些复杂的知识点整理得有条有理。每个主题、每个小点都清清楚楚,学习的时候一眼就能看出重点。这种一看就明白的学习法,不仅让我们学得更快,还能让......
  • 破防了!加班狗常用的TOP4 PDF编辑器2024年集锦
    我们天天都得跟一堆文件打交道,尤其是PDF文件。PDF的好处是,不管在哪个设备上打开,内容和格式都保持原样,而且不容易被改。不过,有时候这也让人挺头疼的,因为想改点什么就麻烦了。幸好,技术一直在进步,现在市面上有很多好用的PDF编辑器,它们就像魔法棒,让编辑文档变得轻松又快速。今天,我......
  • 2024年这3款翻译工具,真的能帮你摆脱‘词不达意’的尴尬
    在现在这个全球化越来越普遍的时代,会翻译东西对我们来说越来越重要,无论是学习、工作还是日常生活中。不过,对很多刚开始学翻译的人来说,这事儿可能看起来挺难的。别急,到了2024年,有几款好用的翻译工具,就算是翻译新手也能很快上手。今天,咱们就来说说这些工具如何帮我们更好地理解和......
  • 盘点2024年让互联网人打Call的录屏大师,你种草了吗?
    嘿,朋友们,你们有没有为录个教程、直播回放或者游戏精彩瞬间而烦恼过?市面上录屏软件一大堆,但真正能让你录得开心、录出新高度的软件可不好找!今天我这个录屏大师就来给你们介绍2024年三款超棒的录屏神器,让你的录屏过程变得既有趣又轻松!一:Foxit专业录屏武器即时通道___ https:/......
  • 算法的学习笔记——二进制中 1 的个数(牛客JZ15)
    ......
  • 2024最新最全【AIGC】学习零基础入门到精通,看完这一篇就够了!
    AIGC(AI-GeneratedContent)即人工智能生成内容,是指利用人工智能技术来创造各种形式的内容,包括文字、图像、视频、音频和游戏等。与专业生成内容(PGC)和用户生成内容(UGC)相对应,AIGC代表着内容生产方式的演进,其生产速度以指数级增长。为什么要学习AIGC?根据猎聘大数据研究院发布......