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

多校A层冲刺NOIP2024模拟赛06

时间：2024-10-12 19:11:52浏览次数：9  
标签：06 int namespace 多校 long FILE using NOIP2024 define

rank 19，T1 100pts，T2 30pts，T3 45pts，T4 20pts

T1 小Z的手套（gloves）

二分答案，贪心匹配\(O(n\log n)\)的check即可。

时间复杂度\(O(n\log^2 n)\)

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#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)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = infile("gloves.in"),*OutFile = outfile("gloves.out");
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e5 + 10;
int n,m,a[N],b[N];
inline bool check(int mid){
    bitset<N> vis;vis.set();
    rep(i,1,n,1){
        int pos = upper_bound(b+1,b+1+m,a[i] - mid - 1) - b - 1;
        int p = vis._Find_next(pos);
        if(abs(b[p] - a[i]) > mid || p > m) return false;
        vis[p] = false;
    }
    return true;
}
inline void solve(){
    cin>>n>>m;
    rep(i,1,n,1) cin>>a[i];rep(i,1,m,1) cin>>b[i];
    sort(a+1,a+1+n);sort(b+1,b+1+m);
    if(n > m) swap(n,m),swap(a,b);
    int l = 0,r = 1e9,ans = 0;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(check(mid)) ans = mid,r = mid - 1;
        else l = mid + 1;
    }
    cout<<ans<<'\n';
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

小 Z 的字符串（string）

动态规划。

记\(f_{i,j,k,l}\)表示在前\(i\)个位置上，0放了\(j\)个，1放了\(k\)个，第\(i\)位上为\(l\in\{0,1,2\}\)的最小花费。

最后的答案为\(\frac{\min\limits_{i=0}^2 f_{n,ct_0,ct_1,i}}{2}\)

至于为什么除以二，因为一个去一个回，都算过了一遍。

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#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)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = infile("string.in"),*OutFile = outfile("string.out");
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 410;
int f[N/2][N/2][N/2][3],t[3][N],n,ct[3];
char s[N];
inline void solve(){
    cin>>(s+1);n = strlen(s+1);
    rep(i,1,n,1) t[s[i]-'0'][++ct[s[i]-'0']] = i;
    if(max({ct[0],ct[1],ct[2]}) > (n+1)/2) cout<<"-1\n",exit(0);
    memset(f,0x3f,sizeof f);
    f[0][0][0][0] = f[0][0][0][1] = f[0][0][0][2] = 0;
    rep(i,0,ct[0],1) rep(j,0,ct[1],1) rep(k,0,ct[2],1){
        int p = i + j + k;
        if(i) f[i][j][k][0] = min(f[i-1][j][k][1],f[i-1][j][k][2]) + abs(p - t[0][i]);
        if(j) f[i][j][k][1] = min(f[i][j-1][k][0],f[i][j-1][k][2]) + abs(p - t[1][j]);
        if(k) f[i][j][k][2] = min(f[i][j][k-1][0],f[i][j][k-1][1]) + abs(p - t[2][k]);
    }
    cout<<min({f[ct[0]][ct[1]][ct[2]][0],f[ct[0]][ct[1]][ct[2]][1],f[ct[0]][ct[1]][ct[2]][2]})/2;
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

一个真实的故事（truth）

[COCI2015-2016#3] NEKAMELEONI

线段树+双指针。记录一下每个值在每一段最左侧的位置和最右侧的位置，然后pushup的时候将左右儿子的归并起来，跑遍\(O(k)\)的双指针即可。

时间复杂度\(O(nk\log n +qk\log n)\)

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#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)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
namespace IO{
    char buf[1<<23],*p1,*p2;
    #define gc() (p1==p2&&(p2=(p1=buf)+fread_unlocked(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
    #define pc putchar_unlocked
    template<class T>
    inline void read(T &x){
        x = 0;
        char s = gc();
        for(;s < '0' || s > '9';s = gc());
        for(;'0' <= s && s <= '9';s = gc()) x = (x<<1)+(x<<3)+(s^48);
    }
    template<class T,class... Args>
    inline void read(T &x,Args&... argc){read(x);read(argc...);}
    template<class T>
    inline void write(T x){
        static int sta[20],top = 0;
        do{sta[++top] = x%10,x /= 10;}while(x);
        do{pc(sta[top--]+'0');}while(top);
    }
    inline void write(char x){pc(x);}
    template<class T,class... Args>
    inline void write(T x,Args... argc){write(x);write(argc...);}
}using namespace IO;
const int N = 1e5+ 10,inf = 0x3f3f3f3f;
int n,m,a[N],K;
struct Segment_Tree{
    struct segment_tree{
        int l,r,ans;
        bitset<51> h;
        int pl[51],pr[51];
        #define pl(k) tree[k].pl
        #define pr(k) tree[k].pr
        #define l(k) tree[k].l
        #define r(k) tree[k].r
        #define h(k) tree[k].h
        #define ans(k) tree[k].ans
    }tree[N<<2];
    inline void pushup(int k){
        int ls = k<<1,rs = k<<1|1;
        h(k) = h(ls)|h(rs);
        rep(i,1,K,1) 
            pl(k)[i] = min({pl(ls)[i],pl(rs)[i]}),
            pr(k)[i] = max({pr(rs)[i],pr(ls)[i]});
        if(h(k).count() != K) return ans(k) = inf,void();
        vector<int> pos;pos.emplace_back(0);

        rep(i,1,K,1){
            if(1 <= pr(ls)[i] && pr(ls)[i] <= n) pos.emplace_back(pr(ls)[i]);
            if(1 <= pl(rs)[i] && pl(rs)[i] <= n) pos.emplace_back(pl(rs)[i]);
        }
        sort(pos.begin(),pos.end());
        int ln = pos.size() - 1;
        int ct[51] = {0},res = 0;
        ans(k) = inf;
        for(int l = 1,r = 1;l <= ln; ++l){
            while(res < K && r <= ln){
                if(!ct[a[pos[r]]]) res++;
                ct[a[pos[r]]]++;
                r++;
            }
            if(res == K) ans(k) = min(ans(k),pos[r-1]-pos[l]+1);
            ct[a[pos[l]]]--;
            if(!ct[a[pos[l]]]) res--;
        }
        ans(k) = min({ans(k),ans(ls),ans(rs)});
    }
    void build(int k,int l,int r){
        l(k) = l,r(k) = r;
        rep(i,1,K,1) pl(k)[i] = inf,pr(k)[i] = -inf;
        if(l == r){
            h(k).set(a[l]),pl(k)[a[l]] = pr(k)[a[l]] = l,
            ans(k) = h(k).count()==K?1:inf;
            return void();
        }
        int mid = (l + r) >> 1;
        build(k<<1,l,mid);build(k<<1|1,mid+1,r);
        pushup(k);
    }
    void update(int k,int pos,int val){
        if(l(k) == r(k)){
            h(k).reset(a[pos]);
            pl(k)[a[pos]] = inf;
            pr(k)[a[pos]] = -inf;
            pl(k)[val] = pr(k)[val] = pos;
            h(k).set(val);a[pos] = val;
            ans(k) = h(k).count()==K?1:inf;
            return;
        }
        int mid = (l(k) + r(k)) >> 1;
        if(pos <= mid) update(k<<1,pos,val);
        else update(k<<1|1,pos,val);
        pushup(k);
    }
}T;
inline void solve(){
    read(n,K,m);
    rep(i,1,n,1) read(a[i]);
    T.build(1,1,n);
    while(m--){
        int op;read(op);
        if(op ^ 1){
            if(T.ans(1) == inf) puts("-1");
            else write(T.ans(1),'\n');}
        else{
            int pos,val;read(pos,val);T.update(1,pos,val);
        }
    }
}
signed main(){
    solve();
}

异或区间（xor）

不会

标签：06,int,namespace,多校,long,FILE,using,NOIP2024,define
From： https://www.cnblogs.com/hzoi-Cu/p/18461278

相关文章

  • ABB机器人备件3HAC035065-003
    ABB机器人备件3HAC035065-003是一款重要的伺服电机备件，对于确保ABB机器人的正常运行至关重要。以下是对该备件的详细解析：一、备件信息型号：3HAC035065-003类型：伺服电机备件适用品牌：ABB应用：主要用于ABB机器人的关节驱动，是机器人运动控制的关键部件。二、备件特点与优势高性能......
  • 2006-2023年上市公司社会责任报告、ESG报告文本（TXT）
    2006-2023年上市公司社会责任报告、ESG报告文本（TXT）1、时间：2006-2023年2、范围：A股上市公司3、样本量：14279份4、说明：上市公司社会责任报告是企业对外公布的一份关于其社会责任实践和成果的详细文件，涵盖环境保护、社会贡献和公司治理等方面的表现。通常包含公司在减少环境影响......
  • 《GESP2级2306》 解析
    一、单选题（每题2分，共30分）1.高级语言编写的程序需要经过以下（D）操作，可以生成在计算机上运行的可执行代码。A.编辑B.保存C.调试D.编译在高级语言编程过程中，要生成在计算机上运行的可执行代码，需要经过一系列的操作。针对给出的选项，我们可以逐一分析：A.编辑-这是......
  • 《GESP3级2306 单选题判断题》 解析
    描述一、单选题（每题2分，共30分）1.高级语言编写的程序需要经过以下（D）操作，可以生成在计算机上运行的可执行代码。A.编辑B.保存C.调试D.编译这是一道关于程序开发流程的问题。我们来逐一分析各个选项，并确定哪个操作是生成可执行代码的关键步骤。‌编辑（A选项）‌：编辑......
  • 10.11日noip多校联考总结
    10.11日noip多校联考总结T1看到感觉像是一个很玄学的题目，在考场上推了大概一个多小时，又写了大概半个小时，终于调出来了。谨记：三分取mid需要进行浮点数运算。对于每一行和每一列定义两个数组来记录要加多少，因为我们只需要知道其中任意一个数就可以推出所有的数，那么考虑枚举x0，来......
  • 多校A层冲刺NOIP2024模拟赛05
    A.好数（number）很容易想到\(n^3\)枚举两个，看第三个是否出现，扩展一下，枚举一个，看剩下需要的和是否出现过，提前处理出两两的和和最早能合出这个数的位置，复杂的\(O(n^2)\)点击查看代码#include<bits/stdc++.h>constintmaxn=5000+10;usingnamespacestd;intn,a[maxn],cnt,......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛05
    Rank烂。A.好数（number）签，唐，没签上。考虑之前几次类似的题方法都是选\(k-1\)的方案存起来以使总复杂度除以一个\(n\)，故考虑记共\(n^2\)个两两组合之和，枚举当前点\(i\)前面的点，找是否有值为它们的差的组合，复杂度\(\mathcal{O(n^2)}\)，用map记再挂个\(\logn\)。赛......
  • 多校A层冲刺NOIP2024模拟赛05
    T1、好数（number）签到题把选三个数相加拆为选择一个数，然后看前面有没有能用两个数组合出答案。$O(n^2)$。码(#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<int,int>pii;#definemkmake_pair#de......
  • [45] (多校联训) A层冲刺NOIP2024模拟赛05
    这是什么午休，大黄突然走进来大黄：闪电特效！其他人：？大黄：5k!其他人：？？？大黄：【闪电特效】【闪电特效】男人中的男人【闪电特效】【闪电特效】雄性中的雄性【闪电特效】【闪电特效】巅峰！【闪电特效】【闪电特效】A.好数简单变形一下\[f_i+f_j+f_k=c\]\[f_j+f_k=c-f_i\]然......
  • 多校A层冲刺NOIP2024模拟赛05
    咋是计数专场啊，讨厌计数！就会一个签到题，恼了。rank21,T1100pts,T20pts,T320pts,T40ptsdp设计状态不行。T3典型的背包没看出来，T2简单dp不会设计状态。有一些套路还是要学好数（number）签到题。假设一个数\(a_i\)是好数，那么一定有\(a_i=a_x+a_y+a_z(x\ley\lez)\)用一个b......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99