首页 > 其他分享 >CSP 模拟 33

CSP 模拟 33

时间:2024-09-26 19:34:10浏览次数:10  
标签:ch 33 ++ id int && push CSP 模拟

A 商品

对于一个数对 \((x,y)[x<y]\),无论怎样选择区间,这个数对的贡献都是 \(y-x\),那么考虑对于所有数对,把 \(x\) 和 \(y\) 分别放到一起,排好序。如果当前区间确定,在两个数组二分一下,前缀和就能处理出答案。
显然区间越大越好,所以只考虑区间左端点,考虑只对于点对 \((x,y)\) 来说,\(l\le x\) 相同,\(r\ge y\) 相同,所以可以取到 \(x\) 和 \(y-d\) 两个左端点。一次检查每个端点计算答案即可。
赛时端点没有考虑右边的贡献,并且一开始想数据结构,后来发现优先队列更好,然后就没思考性质,80pts,但是确实是对的。
直接大力分讨 \(x\),\(y\) 与区间的关系,拿优先队列存储,然后根据单调性一个一个扔,巨麻烦。

#include<bits/stdc++.h>
#define int long long
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=4e5+10;
int n,d,a[N],temp[N],ans=0,ans2,ans3,ans4,ans5,size,num,Ne[N];
int l=0,r=0,L,R;
bool vis[N];
struct NODE{
    int x,y,id;
    bool operator<(const NODE &a)const{return x>a.x;}
};
struct WU{
    int x,y,id;
    bool operator<(const WU&a)const{return y>a.y;}
};
std::priority_queue<NODE> q1,q2,q3;
std::priority_queue<WU> qf,q4,q5;
signed main(){
    freopen("goods.in","r",stdin);freopen("goods.out","w",stdout);
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    n=read(),d=read();
    for(int i=1;i<=n;++i)temp[i]=a[i]=read();
    std::sort(temp+1,temp+n+1);
    l=r=temp[1];L=R=1;
    int top=0;
    for(int i=1;i<n;++i){
        int x=a[i],y=a[i+1];if(x>y)std::swap(x,y);
        Ne[++top]=x,Ne[++top]=y-d;
        q1.push({x,y,i});
    }
    std::sort(Ne+1,Ne+top+1);
    while(L<=top){
        l=Ne[L];
        l=std::max(l,0ll);r=l+d;
        while(!q1.empty()){
            auto it=q1.top();q1.pop();
            int x=it.x,y=it.y,id=it.id;
            if(x>=r&&y>=r){
                q1.push({x,y,id});break;
            }
            if(x>=l&&x<=r&&y>=r){
                q2.push({x,y,id});ans2+=x;size++;
                qf.push({x,y,id});
                vis[id]=1;
                continue;
            }
            if(x>=l&&x<=r&&y>=l&&y<=r){
                q3.push({x,y,id});ans3+=y-x;
                continue;
            }
            if(x<=l&&y>=r){
                q4.push({x,y,id});ans4++;
                continue;
            }
            if(x<=l&&y>=l){
                q5.push({x,y,id});ans5+=y;
                continue;
            }
        }
        while(!q2.empty()){
            auto it=q2.top();q2.pop();
            int x=it.x,y=it.y,id=it.id;
            if(!vis[id])continue;
            ans2-=x;size--;vis[id]=0;
            if(x>=l&&x<=r&&y>=r){
                q2.push({x,y,id});ans2+=x;size++;
                vis[id]=1;
                break;
            }
            if(x>=l&&x<=r&&y>=l&&y<=r){
                q3.push({x,y,id});ans3+=y-x;
                continue;
            }
            if(x<=l&&y>=r){
                q4.push({x,y,id});ans4++;
                continue;
            }
            if(x<=l&&y>=l&&y<=r){
                q5.push({x,y,id});ans5+=y;
                continue;
            }
        }
        while(!qf.empty()){
            auto it=qf.top();qf.pop();
            int x=it.x,y=it.y,id=it.id;
            if(!vis[id])continue;
            ans2-=x;size--;vis[id]=0;
            if(x>=l&&x<=r&&y>=r){
                qf.push({x,y,id});ans2+=x;size++;
                vis[id]=1;
                break;
            }
            if(x>=l&&x<=r&&y>=l&&y<=r){
                q3.push({x,y,id});ans3+=y-x;
                continue;
            }
        }
        while(!q3.empty()){
            auto it=q3.top();q3.pop();
            int x=it.x,y=it.y,id=it.id;ans3-=y-x;
            if(x>=l&&x<=r&&y>=l&&y<=r){
                q3.push({x,y,id});ans3+=y-x;
                break;
            }
            if(x<=l&&y>=r){
                q4.push({x,y,id});ans4++;
                continue;
            }
            if(x<=l&&y>=l&&y<=r){
                q5.push({x,y,id});ans5+=y;
                continue;
            }
        }
        while(!q4.empty()){
            auto it=q4.top();q4.pop();
            int x=it.x,y=it.y,id=it.id;ans4--;
            if(x<=l&&y>=r){
                q4.push({x,y,id});ans4++;
                break;
            }
            if(x<=l&&y>=l&&y<=r){
                q5.push({x,y,id});ans5+=y;
                continue;
            }
        }
        while(!q5.empty()){
            auto it=q5.top();q5.pop();
            int x=it.x,y=it.y,id=it.id;ans5-=y;
            if(x<=l&&y>=l&&y<=r){
                q5.push({x,y,id});ans5+=y;
                break;
            }
        }
        num=q5.size();
        int res=size*r-ans2+ans3+ans4*(r-l)+ans5-num*l;
        ans=std::max(ans,res);
        L++;
    }
    std::cout<<ans<<'\n';
}

B 价值

究极分讨树形 DP,但是状态对了也挺好写。
如果没有神必叶子边,直接 DP 就做完了,考虑给 DP 加上一些限制,\(f_{u,0/1,0/1,0/1}\) 表示在 \(u\) 的子树中,\(u\) 是否匹配,最左端的叶子是否和前一个叶子匹配,最右端的叶子是否和后一个叶子匹配。答案就是 \(f_{u,0,0,0}+f_{u,0,1,1}+f_{u,1,0,0}+f_{u,1,1,1}\)。
考虑子树合并的转移,对于所有节点,有初始状态 \(f_{u,0,0,0}=1\),对于叶子,有 \(f_{u,1,0,1}=f_{u,1,1,0}=1\)。对于第一个儿子节点,直接继承转移。
对于一般情况,子节点的状态必须要与合并状态的右端点状态相匹配,知道这个之后就好写多了,具体转移看代码(最短解)。

#include<bits/stdc++.h>
#define fo(i,s,j) for(int i=s;i<=j;++i)
#define int long long
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=1e5+10,mod=998244353;
inline int mo(int x){return x<mod?x:x%mod;}
int n,f[N][2][2][2],la[2][2][2],ans;
std::vector<int> e[N];
inline void dfs(int u){
    f[u][0][0][0]=1;
    if(!e[u].size()){f[u][1][1][0]=f[u][1][0][1]=1;return ;}
    for(int i=0;i<e[u].size();++i){
        int v=e[u][i];dfs(v);
        if(!i){fo(l,0,1)fo(r,0,1)f[u][0][l][r]=mo(f[v][0][l][r]+f[v][1][l][r]),f[u][1][l][r]=f[v][0][l][r];continue;}
        memcpy(la,f[u],sizeof(la));
        fo(l,0,1)fo(r,0,1)f[u][0][l][r]=mo(mo(la[0][l][r]*(f[v][0][r][r]+f[v][1][r][r]))+mo(la[0][l][r^1]*(f[v][0][r^1][r]+f[v][1][r^1][r])));
        fo(l,0,1)fo(r,0,1)f[u][1][l][r]=mo(mo(la[0][l][r]*f[v][0][r][r])+mo(la[0][l][r^1]*f[v][0][r^1][r])+mo(la[1][l][r]*(f[v][0][r][r]+f[v][1][r][r]))+mo(la[1][l][r^1]*(f[v][0][r^1][r]+f[v][1][r^1][r])));
    }
}
signed main(){
    freopen("value.in","r",stdin);freopen("value.out","w",stdout);
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    n=read();fo(i,2,n){int x=read();e[x].emplace_back(i);}dfs(1);
    std::cout<<mo(f[1][0][0][0]+f[1][0][1][1]+f[1][1][0][0]+f[1][1][1][1])<<'\n';

}

C 货币

网络流切糕模型,以后系统地学一下。

D 资本

生成函数,以后系统地学一下。

总结

这场成策略大师了,直接想优先队列能做后就不想别的了,你真以为正解需要六个优先队列,然后对拍调试三个小时,后面暴力都没时间拼。
T2 这种带点构造博弈感觉的树形 DP 就一点都不会,看题解也看不明白,该多练 DP 了。

标签:ch,33,++,id,int,&&,push,CSP,模拟
From: https://www.cnblogs.com/Ishar-zdl/p/18434137

相关文章

  • RSA算法模拟实验报告
    课程名称网络安全实验成绩实验RSA算法模拟学号姓名日期2024.9.24一、实验目的(1)学习RSA基本算法(2)学习指数求模运算(3)学习逆元的求法二、实验原理生成两个大素数 p和 q;计算这两个素数的乘积 n=p*q;计算小于n并且与n互质的整数的个数,即欧拉......
  • [2027届]NOIP2024模拟赛#6
    全真模拟赛。1:30开考。看了T1,发现\(O(m\logn)\)的暴力很好写,直接50pts到手。然后发现每次不用一个一个改,而且改完以后可以直接区间改,但是一直没有找到合适的东西维护复杂度。往下翻了翻数据发现\(2\)的整次幂这个性质很好写,但是写挂了。此时时间已经过去了1.5h,于是......
  • 信息学奥赛复赛复习04-CSP-J2019-04-加工零件-位运算、整数映射0或1、结构体、初始化
    PDF文档回复:20240926<12019CSP-J题目4加工零件[题目描述]凯凯的工厂正在有条不紊地生产一种神奇的零件,神奇的零件的生产过程自然也很神奇。工厂里有n位工人,工人们从1∼n编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带如果......
  • CSP模拟3
    T1奇观挺有趣的思路,每个字母相互独立,\(C\)和\(F\),我们可以把\(C\)分成一个两个端点和一个三个端点的路径(以同一个起点开始),而\(F\)为了方便统计,我们也可以把它分成两个两个端点和一个三个端点的路径(同样是以同一个端点为起点)。那我们定义$s_{i}=\sum_{j}[(i,j)双向......
  • 信息学奥赛复赛复习04-CSP-J2019-04-加工零件-位运算、整数映射0或1、结构体、初始化
    PDF文档公众号回复关键字:2024092612019CSP-J题目4加工零件[题目描述]凯凯的工厂正在有条不紊地生产一种神奇的零件,神奇的零件的生产过程自然也很神奇。工厂里有n位工人,工人们从1∼n编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带......
  • 冲刺CSP联训模拟1
    A.几何设\(f_{i,j,k}\)表示前\(i\)个字符,分为两部分,分别为\(x\)的几倍加\(x\)的前\(j\)位,\(y\)的几倍加\(y\)的前\(k\)位,是否合法分别判断下一位\(i+1\)能否与\(x\)的下一位\(j+1\)和\(y\)的下一位\(k+1\)匹配,匹配上了就转移.最终答案就是\(f_{|s|......
  • 某模拟赛题
    题意有\(n\)个实数,第\(i\)个实数在\([0,2^{a_i}]\)中均匀分布。求任意一个数均小于\(n\)个数和的一半的概率。\(n\le5\cdot10^4,a_i\le50\)。解法题目即求\(\sum\limits_{i=1}^{n}P(x_i>\sum\limits_{j\neqi}x_j)\),由于\(x_i\)和\(2^{a_i}-......
  • (免费源码)计算机毕业设计必看必学 Ssm作业管理系统的设计与实现02334 原创定制程序 jav
    Ssm作业管理系统的设计与实现摘 要科技进步的飞速发展引起人们日常生活的巨大变化,电子信息技术的飞速发展使得电子信息技术的各个领域的应用水平得到普及和应用。信息时代的到来已成为不可阻挡的时尚潮流,人类发展的历史正进入一个新时代。在现实运用中,应用软件的工作规则和......
  • 基于springboot的校园以物易物系统的设计与实现-毕业设计源码33451
    目 录1绪论1.1选题背景1.2研究意义1.3论文结构与章节安排2 校园以物易物系统系统分析2.1可行性分析2.2系统流程分析2.2.1 数据流程3.3.2 业务流程2.3 系统功能分析2.3.1功能性分析2.3.2非功能性分析2.4 系统用例分析2.5本章小结3......
  • kafka生产者、消费者-命令行模式模拟
    win环境下,如果是linux,切换目录,用sh脚本就行kafka安装在上一篇https://www.cnblogs.com/qcy-blog/p/18428599Kraft启动kafkakafka-server-start.bat..\..\config\kraft\server.properties生产者,启动之后,命令行输入要生产的消息kafka-console-producer.bat--topictest-top......