首页 > 其他分享 >多校A层冲刺NOIP2024模拟赛09

多校A层冲刺NOIP2024模拟赛09

时间：2024-10-20 10:21:16浏览次数：6  
标签：int rep 09 多校 long num using NOIP2024 define

又双叒叕垫底啦

rank 4，T1 50，T2 100，T3 39，T4 35。

accoder 上同分，rank 20

排列最小生成树 (pmst)

打的\(O(n^2 \log n^2)\)暴力

发现总是存在⼀颗⽣成树，使得⽣成树⾥的所有边的边权都⼩于\(n\)。
考虑 Kruskal 的过程，我们只需要留下那些边权⼩于\(n\)的边。

然后用桶排序即可。

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#define Infile(x) freopen(#x".in","r",stdin)
#define Outfile(x) freopen(#x".out","w",stdout)
#define Ansfile(x) freopen(#x".ans","w",stdout)
#define Errfile(x) freopen(#x".err","w",stderr)
#ifdef LOCAL
    FILE *InFile = Infile(in),*OutFile = Outfile(out);
    // FILE *ErrFile = Errfile(err);
#else
    FILE *InFile = Infile(pmst),*OutFile = Outfile(pmst);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 5e4 + 10;
#define pii pair<int,int>
#define mk make_pair
int n,len,fa[N];
vector<pii> ct[N];
inline int get_fa(int x){while(x != fa[x]) x = fa[x] = fa[fa[x]];return x;}
int cx[N],cy[N];
inline void solve(){
    cin>>n;
    rep(i,1,n,1){int x;cin>>x;cx[i] = x;cy[x] = i;}
    len = sqrt(n);
    rep(i,1,n,1){
        rep(j,i+1,min(i+len,n),1){
            int val;
            val = abs(cx[i]-cx[j])*(j-i);
            if(val <= n) ct[val].emplace_back(mk(i,j));
            val = abs(cy[i]-cy[j])*(j-i);
            if(val <= n) ct[val].emplace_back(mk(cy[i],cy[j]));
        }
    } 
    int tot = 0;
    rep(i,1,n,1) fa[i] = i;
    ll ans = 0;
    rep(i,1,n,1) for(auto j:ct[i]){
        int x = j.first,y = j.second;
        x = get_fa(x),y = get_fa(y);
        if(x == y) continue;
        fa[x] = y,ans += i,tot++;
        if(tot == n-1) break;
    }
    cout<<ans<<'\n';
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}

卡牌游戏 (cardgame)

签。

发现循环节是\(lcm\)，然后找规律即可。大体的规律就是\(\forall i\in [1,\gcd(n,m)]\)所有的\(\frac{k_1}{i}=0,\frac{k_2}{i}=0 (1\le k_1\le n,1\le k_2\le m)\)都会组一次队。

然后对于每一个\(i\)处理，离散化后开个权值树状数组维护即可。时间复杂度\(O(n\log n)\)。

注意不能用memset清空

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#define Infile(x) freopen(#x".in","r",stdin)
#define Outfile(x) freopen(#x".out","w",stdout)
#define Ansfile(x) freopen(#x".ans","w",stdout)
#define Errfile(x) freopen(#x".err","w",stderr)
#ifdef LOCAL
    FILE *InFile = Infile(in),*OutFile = Outfile(out);
    // FILE *ErrFile = Errfile(err);
#else
    FILE *InFile = Infile(cardgame),*OutFile = Outfile(cardgame);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#define int long long
const int N = 1e5 + 10;
int n,m,a[N],b[N],ans1,ans2,ans3;
#define eb emplace_back
struct BIT{
    int tree[N<<1],mx;
    inline int lowbit(int x){return (x&(-x));}
    inline void upd(int pos,int val){rep(i,pos,mx,lowbit(i)) tree[i] += val;}
    inline int qry(int pos){int res = 0;drep(i,pos,1,lowbit(i)) res += tree[i];return res;}
}T;
inline void get_ans(int &ans1,int &ans2,int &ans3){
    int gcd = __gcd(n,m);
    rep(i,1,gcd,1){
        int res = 0;
        rep(j,i,n,gcd) T.upd(a[j],1),res++;
        rep(j,i,m,gcd){
            ans2 += T.qry(b[j]-1);
            ans3 += T.qry(b[j]) - T.qry(b[j]-1);
            ans1 += res - T.qry(b[j]);
        }
        rep(j,i,n,gcd) T.upd(a[j],-1);
    }
    ans1 *= gcd;ans2 *= gcd;ans3 *= gcd;
}
inline void solve(){
    cin>>n>>m;
    rep(i,1,n,1) cin>>a[i];
    rep(i,1,m,1) cin>>b[i];
    vector<int> num;
    rep(i,1,n,1) num.eb(a[i]);rep(i,1,m,1) num.eb(b[i]);
    sort(num.begin(),num.end());
    num.erase(unique(num.begin(),num.end()),num.end());
    T.mx = num.size();
    rep(i,1,n,1) a[i] = lower_bound(num.begin(),num.end(),a[i]) - num.begin() + 1;
    rep(i,1,m,1) b[i] = lower_bound(num.begin(),num.end(),b[i]) - num.begin() + 1;
    if(n > m) swap(n,m),swap(a,b),get_ans(ans2,ans1,ans3);
    else get_ans(ans1,ans2,ans3);
    cout<<ans1<<'\n'<<ans2<<'\n'<<ans3<<'\n';
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}

比特跳跃 (jump)

诡异建图题，没调出来，打的暴力与特殊性质。

当\(S=1\)时，发现只有\(n=(2^k)-1\)时，到第\(n\)个点的最短路才有权值。

当\(S=2\)时，发现只需要考虑改变一位即可。

当\(s=3\)时，发现\(x|y\ge max(x,y)\)，所以如果跳跃到\(i\)的如果不是从\(j(j|i=i)\)过来的，那么一定不如从1跳过来。然后只需要考虑改变一位即可，用上拓展域跑一遍即可。

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#define Infile(x) freopen(#x".in","r",stdin)
#define Outfile(x) freopen(#x".out","w",stdout)
#define Ansfile(x) freopen(#x".ans","w",stdout)
#define Errfile(x) freopen(#x".err","w",stderr)
#ifdef LOCAL
    FILE *InFile = Infile(in),*OutFile = Outfile(out);
    // FILE *ErrFile = Errfile(err);
#else
    FILE *InFile = Infile(jump),*OutFile = Outfile(jump);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 2e6 + 10;
struct Edge{
    struct EDGE{int to,next;ll w;}edge[N<<1];
    int head[N],cnt;
    inline void Add(int u,int v,ll w){
        // cerr<<u<<' '<<v<<' '<<w<<'\n';
        edge[++cnt] = {v,head[u],w};head[u] = cnt;
        edge[++cnt] = {u,head[v],w};head[v] = cnt;
    }
    inline void add(int u,int v,ll w){
        edge[++cnt] = {v,head[u],w};head[u] = cnt;
    }
    #define repe(i,x,y,e) for(int i = e.head[x],y = e.edge[i].to; i;i = e.edge[i].next)
}g;
ll dist[N];
bitset<N> vis;
int n,m,s,k;
#define pii pair<ll,int>
#define mk make_pair
inline void dijkstra(int s){
    priority_queue<pii,vector<pii>,greater<pii> > q;
    memset(dist,0x3f,sizeof dist);
    dist[s] = 0;q.push(mk(dist[s],s));
    // cout<<'\n';
    while(q.size()){
        int x = q.top().second;q.pop();
        // cerr<<x<<'\n';
        if(vis[x]) continue;
        vis[x] = true;
        for(int i = g.head[x]; i;i = g.edge[i].next){
            int y = g.edge[i].to;
            if(dist[y] > dist[x] + g.edge[i].w){
                dist[y] = dist[x] + g.edge[i].w;
                q.push(mk(dist[y],y));
            }
        }
    }
}
int sta[N],id[N];
inline void solve(){
    cin>>n>>m>>s>>k;
    int lg = log2(n);
    rep(i,1,m,1){
        int u,v,w;cin>>u>>v>>w;
        g.Add(u,v,w);
    }
    if(s == 1){
        g.Add(1,n+1,0);
        rep(i,2,n,1) rep(j,0,lg,1)
            if(!(i&(1<<j))) g.Add(i,n+1,0);
    }
    if(s == 2){
        rep(i,0,n,1) rep(j,0,lg,1){
            if((i^(1<<j))&&(i^(1<<j)) <= n)
                g.Add(i,i^(1<<j),1ll*k*(1<<j));
        }
    }
    if(s == 3){
        rep(i,1,n,1) sta[i] = i+1;
        int tt = n;
        sort(sta+1,sta+1+n,[](int x,int y){return __builtin_popcount(x) < __builtin_popcount(y);});
        rep(i,1,n,1) g.Add(1,i,1ll*k*(i|1));
        rep(i,1,n,1){
            int s = sta[i];
            id[s] = ++tt;
            g.add(s,id[s],0);g.add(id[s],s,1ll*s*k);
            rep(j,0,lg,1) if(s&(1<<j)) g.add(id[s^(1<<j)],id[s],0);
        }
    }
    dijkstra(1);
    rep(i,2,n,1) cout<<dist[i]<<' ';
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}

区间 (interval)

打的\(O(n^2+q)\)的。滚去学DS的，等学到再打。

标签：int,rep,09,多校,long,num,using,NOIP2024,define
From： https://www.cnblogs.com/hzoi-Cu/p/18486983

相关文章

  • 209号资源-源程序：（SIC）黑翼风筝算法：一种受自然启发的元启发式算法，用于解决基准函数和工
    ......
  • springboot叙州区图书馆管理系统设计与实现---附源码60921
    摘 要图书馆作为知识传播和学术研究的重要场所，扮演着非常关键的角色。随着信息技术的快速发展和图书馆管理的日益复杂化，传统的手工管理方式已经无法满足现代图书馆的需求。因此，采用计算机技术和信息系统来辅助图书馆管理成为一种必要的选择。本系统的前端界面涉及的技......
  • 多校A层冲刺NOIP2024模拟赛09
    GG多校A层冲刺NOIP2024模拟赛09T1排列最小生成树(pmst)需要思考一会。你得发现一个性质：所有要的边的权值都得小于n，因为每个点都可以找到至少一条边权小于n的边，所以最后生成树里的边的边权一定小于n。那么$\vertp_i-p_j\vert\times\verti-j\vert$中较......
  • 09视图
    视图......
  • [51] (多校联训) A层冲刺NOIP2024模拟赛09
    关于生成式AI怎么才能让这个b学会断句我目前的方案是，把逗号和句号单独作为一个特殊词汇看待，也统计到词频里，该断句的时候就断表扬这次的题解，写的很清楚A.排列最小生成树总存在一颗生成树使得树上最大边权值小于\(n\)考虑直接连接序列里的所有\((i,i+1)\)，因为\(|a_......
  • P1091 [NOIP2004 提高组] 合唱队形
    分析题目知道求一个最长上升子序列和一个最长下降子序列的长度均为同一个起点的最长的长度。于是求点击查看代码#include<iostream>#include<stack>#include<cmath>#include<algorithm>#include<set>#include<vector>#include<climits>#include<string.h>#incl......
  • Golang笔记_day09
    Go面试题（二）1、怎么做代码优化减少内存分配        内存分配是任何程序的基本操作之一，也是一个明显的性能瓶颈。在Golang中，减少内存分配是一种有效的代码优化方式。为了减少内存分配，我们可以使用以下技巧：复用变量：在循环或迭代过程中，尽量避免重新分配变量。通过在循......
  • 2024.10.18 2309版
    起于《海奥华预言》的思考◆地球管理结构和参考持续更新中...... 英文地址：https://github.com/zhuyongzhe/Earth/tags中文地址：https://www.cnblogs.com/zhuyongzhe85作者：朱永哲 ---------------------------------------------------------------------------------......
  • P10992 Solution
    DescriptionLinkSolution好题。本题主要有两个问题：哈希函数的设计和子串的枚举。作为哈希题的套路，首先可以想到二分答案长度，再做check。考虑如何设计哈希函数来check。令二分出的长度为\(len\)。设计出的哈希函数需要满足两个条件：两个串对应的字符集相同，对应字符集的下......
  • [49 & 50] (多校联训) A层冲刺NOIP2024模拟赛08 | CSP-S 模拟 12
    一小孩在奶茶店玩封盖机被绞断四根手指记者：你现在感觉怎么样小孩：......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99