首页 > 其他分享 >[63] (多校联训) A层冲刺NOIP2024模拟赛19

[63] (多校联训) A层冲刺NOIP2024模拟赛19

时间:2024-11-07 21:31:53浏览次数:1  
标签:联训 string int res pos 多校 while 63 ans

lhx 对 \((\ln n)^{\ln n}\) 求导求出一个形如 \(\frac{1}{n\ln n\ln\ln n}\) 的东西

A.图书管理

说一种很好玩的 \(n^2\log n\) 做法(因为动态中位数我只会这个)

对顶堆:

就是你开一个大根堆和一个小根堆,然后把它们怼在一起,钦定比中位数大的放小根堆,小的放大根堆,这样中间就是中位数

关于怎么才能知道基准是哪个数,其实你没必要知道基准是哪个数,因为你这是两个堆顶在一块了,你完全可以根据堆的特性来做,现在你只需要维护两个堆大小的平衡,这样就能保证找到中位数,加入插入某个数之后不平衡了,那么直接弹出较大的堆的堆顶,插入另一个堆(这样你还能保证两个堆的值域不交,除非堆顶相等,证明考虑直接想这个对顶堆的性质)

因此这玩意实现了动态插入,平衡,寻找中位数,可以用优先队列实现堆,复杂度均挂 \(\log\),\(2s\) 的话是稳过的,如果值域很大的话,这个做法是相当优秀的那一种

对顶堆写法
#include<bits/stdc++.h>
using namespace std;
template<typename T>
class single_mid_t{
    private:
        priority_queue<T,vector<T>,less<T>>p1;
        priority_queue<T,vector<T>,greater<T>>p2;
        inline void fixed(){
            while((int)p1.size()-(int)p2.size()>1){
                p2.push(p1.top());
                p1.pop();
            }
            while((int)p1.size()-(int)p2.size()<1){
                p1.push(p2.top());
                p2.pop();
            }
        }
    public:
        inline void insert(T x){
            p1.push(x);
            fixed();
        }
        inline T askmid(){
            return p1.top();
        }
};
int n;
long long ans;
int a[10001];
single_mid_t<int>s[10001];
int main(){
    scanf(n);
    for(int i=1;i<=n;++i){
        scanf(a[i]);
    }
    for(int i=1;i<=n;++i){
        ans+=1ll*i*i*a[i];
        s[i].insert(a[i]);
        for(int j=i+1;j+1<=n;j+=2){
            s[i].insert(a[j]);s[i].insert(a[j+1]);
            ans+=1ll*i*(j+1)*s[i].askmid();
        }
    }
    cout<<ans;
}

然后说 \(n^2\) 的正解

因为这个题是排列,你可以枚举中位数

钦定一个数 \(a_i\) 是中位数,考虑位每个地方赋值,令 \(a_j\lt a_i\) 处的 \(j\) 的值与 \(a_j\gt a_i\) 处的 \(j\) 的值相等,问题转化为求包含 \(i\) 的区间 \([l,r]\) 数量,满足区间和为 \(0\)

还是一样的,如果你钦定每处值的绝对值是 \(1\) 的话,这个值还是不会超过 \([-n,n]\),因此仍然考虑开桶,内层也可以 \(O(n)\) 做出来

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int dx=10000;
int n,ans;
int a[20001],cnt[20001];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
        cin>>a[i];
    }
	for(int i=1;i<=n;i++){
	    int tot=0;
        for(int j=i;j<=n;++j){
            tot+=(a[j]>a[i])-(a[j]<a[i]);
            cnt[tot+dx]+=j;
        }
        tot=0;
	    for(int j=i;j>=1;--j){
            tot-=(a[j]>a[i])-(a[j]<a[i]);
            ans+=j*cnt[tot+dx]*a[i];
        }
        tot=0;
	    for(int j=i;j<=n;++j){
            tot+=(a[j]>a[i])-(a[j]<a[i]);
            cnt[tot+dx]&=0;
        }
	}
	cout<<ans;
}

B.两棵树

连通块数=剩余的点数−剩余的边数

贡献被拆成四个部分:点×点−边×点−点×边+边×边

  1. 点×点:选择 \(x\in T,u\in U\),当 \(x\neq u\) 均保留概率 \(\frac{1}{4}\),当 \(x=u\) 概率为 \(0\),所以期望为 \(\frac{n(n-1)}{4}\)

  2. 边×点:选择 \((x,t)\in T,u\in U\),当 \(x\neq u,y\neq u\) 均保留概率 \(\frac{1}{8}\),其余情况概率为 \(0\),所以期望为 \(\frac{(n-1)(n-2)}{8}\)

  3. 边×边:选择 \((x,y)\in T,(u,v)\in U\),当 \(x,y,u,v\) 互不相同时,概率为 \(frac{1}{16}\),其余情况概率为 \(0\),可以枚举所有 \((x,y)\),计算符合条件的边 \((u,v)\) 数量:\(n-1-\deg_Ux-\deg_Uy\),如果 \(U\) 存在 \((u,v)=(x,y)\) 则加一

奇怪的是似乎和我推出来不是很一样,为啥我推完之后剩一个 \(\frac{(n-1)^2}{2}\)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=998244353;
inline int constexpr power(int a,int t=p-2){
    int ans=1,base=a;
    while(t){
        if(t&1){
            ans=ans*base%p;
        }
        base=base*base%p;
        t>>=1;
    }
    return ans;
}
int n,ans;
vector<int>t[200001],u[200001];
int fa[200001];
void dfs(int now,int last){
    fa[now]=last;
    for(int i:u[now]){
        if(i!=last){
            dfs(i,now);
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n-1;++i){
        int x,y;cin>>x>>y;
        t[x].push_back(y);
        t[y].push_back(x);
    }
    for(int i=1;i<=n-1;++i){
        int x,y;cin>>x>>y;
        u[x].push_back(y);
        u[y].push_back(x);
    }
    ans=(n-1)%p*power(2)%p;
    dfs(1,0);
    int res=0;
    for(int i=1;i<=n;++i){
        for(int j:t[i]){
            if(j>i){
                res=(res+n-1)%p;
                res=((res-(int)u[i].size()-(int)u[j].size())%p+p)%p;
                if(fa[i]==j or fa[j]==i) res=(res+1)%p;
            }
        }
    }
    ans=(ans+res*power(16)%p)%p;
    cout<<ans;
}

C.函数

好题

首先可以做有无解的判定

零点存在定理,找到所有数中 \(x_i\operatorname{xor}a-b\) 的最大值和最小值,如果这两个值同号则一定不存在解,异或值最大最小可以 01-trie 解决

然后继续零点存在定理,我们可以找到最大和最小的两个位置,现在这两个位置一定不同号,那么可以确定的是中间总存在一个位置合法(两个异号中间总有大于一个异号的连接点)

因此我们只需要维持这种端点异号的关系,每次二分中间点的值,每次用这个点替换同号的端点,最终一定会找到一个断点是合法的

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct trie{
    signed to[1000001*32][2];
    signed id[1000001*32];
    signed cnt=0;
    inline const string to_string(int x){
        string ans;
        while(x){
            ans.push_back(x%2+'0');
            x/=2;
        }
        while(ans.size()!=31ull) ans.push_back('0');
        reverse(ans.begin(),ans.end());
        return ans;
    }
    inline void insert(int x,int _id){
        int pos=0;
        string y=to_string(x);
        for(char i:y){
            if(!to[pos][i-'0']){
                to[pos][i-'0']=++cnt;
            }
            pos=to[pos][i-'0'];
        }
        id[pos]=_id;
    }
    inline pair<int,int> askmax(int x){
        int pos=0,ans=0;
        string y=to_string(x);
        for(char i:y){
            ans*=2;
            if(to[pos][1-(i-'0')]){
                pos=to[pos][1-(i-'0')];
                ans++;
            }
            else{
                pos=to[pos][i-'0'];
            }
        }
        return {id[pos],ans};
    }
    inline pair<int,int> askmin(int x){
        int pos=0,ans=0;
        string y=to_string(x);
        for(char i:y){
            ans*=2;
            if(to[pos][i-'0']){
                pos=to[pos][i-'0'];
            }
            else{
                pos=to[pos][1-(i-'0')];
                ans++;
            }
        }
        return {id[pos],ans};
    }
};
trie t;
int n,q;
int x[1000001];
inline bool check(int i,int a,int b){
    return ((x[i]^a)-b)*((x[i+1]^a)-b)<=0;
}
inline int f(int x,int a,int b){
    return (x^a)-b;
}
void bl(){
    for(int i=1;i<=n;++i){
        cin>>x[i];
    }
    while(q--){
        int a,b;
        cin>>a>>b;
        bool flag=false;
        for(int i=1;i<n;++i){
            if(f(x[i],a,b)*f(x[i+1],a,b)<=0){
                cout<<i<<" ";
                flag=true;
                break;
            }
        }
        if(!flag) cout<<-1;
        cout<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>q;
    for(int i=1;i<=n;++i){
        cin>>x[i];
        t.insert(x[i],i);
    }
    while(q--){
        int a,b;
        cin>>a>>b;
        auto tmpa=t.askmax(a),tmpb=t.askmin(a);
        if(n==1 or f(x[tmpa.first],a,b)*f(x[tmpb.first],a,b)>0){
            cout<<-1<<'\n';
        }
        else{
            if(tmpa.first>tmpb.first) swap(tmpa,tmpb);
            int l=tmpa.first,r=tmpb.first;
            while(l!=r-1){
                int mid=(l+r)/2;
                if(f(x[mid],a,b)<=0){
                    if(tmpa.second-b<=0){
                        l=mid;
                    }
                    else{
                        r=mid;
                    }
                }
                else{
                    if(tmpa.second-b>0){
                        l=mid;
                    }
                    else{
                        r=mid;
                    }
                }
            }
            cout<<l<<'\n';
        }
    }
}

这是什么

标签:联训,string,int,res,pos,多校,while,63,ans
From: https://www.cnblogs.com/HaneDaCafe/p/18533865

相关文章

  • 多校 A 层冲刺 NOIP2024 模拟赛 19
    题解还是得写,不能偷懒啊~多校A层冲刺NOIP2024模拟赛19图书管理签到题考虑最困难的部分是确定中位数,不妨钦定中位数,然后计算其贡献,然后考虑只枚举一个边界,另一个边界可以放桶里。时间复杂度\(O(n^2)\)。两棵树概率期望考虑拆贡献,有等式\[连通块个数=点数-边数\]证明考虑......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛19
    RankbydCSP之后就没场切过题......
  • 多校A层冲刺NOIP2024模拟赛19
    讲个笑话:(讨论时间)huge:(叹气)这讨论啊,就是改不了,这换了铃声了,也没……众人:现在是讨论时间啊。huge:(停顿)那刚才大课间那会哇啦哇啦的……图书管理简要题意给定一个长度为\(n(n\le10^4)\)的排列,求\(\sum\limits_{l=1}^n\sum\limits_{r=l}^n[r-l为偶数]l\timesr\timesf_{l,r}\)......
  • 多校A层冲刺NOIP2024模拟赛19
    多校A层冲刺NOIP2024模拟赛19\(T1\)A.图书管理(book)\(90pts/90pts\)部分分\(90pts\):平衡树/线段树、主席树上二分/对顶堆暴力维护中位数,同luoguP3871[TJOI2010]中位数|luoguP1168中位数,时间复杂度为\(O(n^{2}\logn)\),需要适当卡常。点击查看代码in......
  • Xshell 8 Build 0063绿色特别版发布:功能强大且永久免费使用
    软件介绍Xshell是一款功能强大的Linux远程连接工具,被誉为SSH终端管理器和SSH远程连接主机客户端的最佳选择。它不仅支持多选项卡管理多个主机,还提供了对多种远程协议的支持,如Telnet、Rlogin、SSH/SSHPKCS#11、SFTP和Serial等。此外,Xshell还具备Unicode编码支持、动态端口转发、自......
  • 基于PLC的嵌入式软PLC开发及IEC6631-3标准eCLR内核运行环境研究【附数据】
    ......
  • 多校A层冲刺NOIP2024模拟赛18
    多校A层冲刺NOIP2024模拟赛18T1选彩笔(rgb)签到题,但是没签上。。。没想到三维前缀和,直接上了个bitset。就是直接二分答案,然后枚举这三维每维的区间的起点,前缀和查数量是否大于等于$K$即可,也可以把二分答案改为第一维的双指针,少一个$log$。T2兵蚁排序(sort)比T1还签......
  • CSP2024 前集训:多校A层冲刺NOIP2024模拟赛18
    前言不知道咋回事儿?脑子里一直放歌。然后T3空间给了256,开了256.23死了。T1选彩笔显然可以二分答案,所以现在有了\(O(nv^3\logv)\)的做法,去重后可以拿到\(80pts\),发现直接三维前缀和就可以做到\(O(v^3\logv)\)。点击查看代码#include<bits/stdc++.h>#definell......
  • STM32H563核心板调试笔记(一)
    前言这是组里师兄负责的项目,以FPGA为数据采集核心,但还需要执行一些流程性的指令,因此还需要一个CPU。我们不用Zynq是因为它里面的CPU性能比较强,功耗比较高(其实我们没有人很懂Zynq,可以说这是我们选型的假设,现在选都选好了,你就承认吧)。而MCU部分组里也就我比较懂,于是我经过一番比较......
  • CF963-Div2-E. Xor-Grid Problem
    CF963-Div2-E.Xor-GridProblem题意给定一个\(n\timesm\)的矩阵\(a\),有两种操作:选择一行,把每个数变成所在列所有数的异或之和。选择一列,把每个数变成所在行所有数的异或之和。求进行任意次操作后整个矩阵最小的美丽值。思路第一个发现:同一数异或两次相当于没有异......