首页 > 其他分享 >2024初三集训模拟测试3

2024初三集训模拟测试3

时间：2024-02-22 21:11:39浏览次数：28  
标签：write char putchar int void 2024 inline 初三 集训

2024初三集训模拟测试3

  1. T1 排序：

    显然贪心。

    将 1ll*a[i]*a[i-1] \(\to\) 1ll*(a[i]*a[i-1]) 囍爆零

    CODE 
    #include<bits/stdc++.h>
using namespace std;
using llt=long long;
using ull=unsigned long long;
#define For(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define For_(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
const int N=1e5+3;
int n,a[N<<2];

namespace IO{
    template<class T> inline void write(T x){
        static T st[45];T top=0;if(x<0)x=-x,putchar('-');
        do{st[top++]=x%10;}while(x/=10);while(top)putchar(st[--top]^48);
    }
    template<class T> T READ_NONPARAMETRIC_INIT;
    template<class T = int> inline T read(T &x=READ_NONPARAMETRIC_INIT<T>){
        char s=getchar();x=0;bool pd=false;while(s<'0'||'9'<s){if(s=='-') pd=true;s=getchar();}
        while('0'<=s&&s<='9'){x=x*10+(s^48),s=getchar();} return (pd?(x=-x):x);
    }
}
namespace IO{
    char NL_C; double NL_F; long double NL_LF;
    inline char read(char &c){c=getchar();while(c<33||c>126) c=getchar();return c;}
    template<int MAXSIZE=INT_MAX> inline int read(char* c){
        char s=getchar();int pos=0;while(s<33||s>126) s=getchar();
        while(s>=33&&s<=126&&pos<MAXSIZE) c[pos++]=s,s=getchar();c[pos]='\0';return pos;
    }
    template<int MAXSIZE=INT_MAX> inline int read(string &c){
        c.clear();char s=getchar();int pos=0;while(s<33||s>126) s=getchar();
        while(s>=33&&s<=126&&pos<MAXSIZE) c.push_back(s),s=getchar(),pos++;return pos;
    }
    inline double read(double &x){scanf("%lf",&x);return x;}
    inline long double read(long double &x){scanf("%Lf",&x);return x;}
    template<class T,class... Args> inline void read(T& x,Args&... args){read(x);read(args...);}
    inline void write(char c){putchar(c);}
    inline void write(char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);}
    inline void write(string &c){int len=c.size();For(i,0,len-1,1) putchar(c[i]);}
    inline void write(const char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);}
    template<int PRECISION=6> inline void write(double x){printf("%.*lf",PRECISION,x);}
    template<int PRECISION=6> inline void write(long double x){printf("%.*Lf",PRECISION,x);}
    template<class T> inline void Write(T x){write(x),putchar(' ');}
    inline void Write(char c){write(c);if(c!='\n') putchar(' ');}
    inline void Write(char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');}
    inline void Write(string &c){write(c);if(c[c.size()-1]!='\n') putchar(' ');}
    inline void Write(const char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');}
    template<class T,class... Args> inline void write(T x,Args... args){write(x);write(args...);}
    template<class T,class... Args> inline void Write(T x,Args... args){Write(x);Write(args...);}
}
using namespace IO;

int main(){
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    read(n);
    For(i,1,n<<2,1) read(a[i]);
    sort(a+1,a+(n<<2)+1);
    llt ans=0;
    For(i,1,n,1) ans-=1ll*a[i]*a[(n<<1)-i+1];
    For_(i,n<<2,(n<<1)+1,2) ans+=1ll*a[i]*a[i-1];
    write(ans);
}

  2. T2 牛吃草：

    显然二分答案。

    考虑 \(dp\) 验证。

    设 \(dp[i][1/0]\) 表示在前 \(i\) 个选、不选的方案数。

    显然转移。

    但是要单调队列优化，

    因为有个常数不好转移，可以同一加上 \(n-i\)，再在查询时减掉。

    CODE 
    #include<bits/stdc++.h>
using namespace std;
using llt=long long;
using ull=unsigned long long;
#define For(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define For_(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
const int N=5e5+3;
int n,w[N],s,dp[N][2],que[N],hd,tl=1;

namespace IO{
    template<class T> inline void write(T x){
        static T st[45];T top=0;if(x<0)x=-x,putchar('-');
        do{st[top++]=x%10;}while(x/=10);while(top)putchar(st[--top]^48);
    }
    template<class T> T READ_NONPARAMETRIC_INIT;
    template<class T = int> inline T read(T &x=READ_NONPARAMETRIC_INIT<T>){
        char s=getchar();x=0;bool pd=false;while(s<'0'||'9'<s){if(s=='-') pd=true;s=getchar();}
        while('0'<=s&&s<='9'){x=x*10+(s^48),s=getchar();} return (pd?(x=-x):x);
    }
}
namespace IO{
    char NL_C; double NL_F; long double NL_LF;
    inline char read(char &c){c=getchar();while(c<33||c>126) c=getchar();return c;}
    template<int MAXSIZE=INT_MAX> inline int read(char* c){
        char s=getchar();int pos=0;while(s<33||s>126) s=getchar();
        while(s>=33&&s<=126&&pos<MAXSIZE) c[pos++]=s,s=getchar();c[pos]='\0';return pos;
    }
    template<int MAXSIZE=INT_MAX> inline int read(string &c){
        c.clear();char s=getchar();int pos=0;while(s<33||s>126) s=getchar();
        while(s>=33&&s<=126&&pos<MAXSIZE) c.push_back(s),s=getchar(),pos++;return pos;
    }
    inline double read(double &x){scanf("%lf",&x);return x;}
    inline long double read(long double &x){scanf("%Lf",&x);return x;}
    template<class T,class... Args> inline void read(T& x,Args&... args){read(x);read(args...);}
    inline void write(char c){putchar(c);}
    inline void write(char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);}
    inline void write(string &c){int len=c.size();For(i,0,len-1,1) putchar(c[i]);}
    inline void write(const char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);}
    template<int PRECISION=6> inline void write(double x){printf("%.*lf",PRECISION,x);}
    template<int PRECISION=6> inline void write(long double x){printf("%.*Lf",PRECISION,x);}
    template<class T> inline void Write(T x){write(x),putchar(' ');}
    inline void Write(char c){write(c);if(c!='\n') putchar(' ');}
    inline void Write(char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');}
    inline void Write(string &c){write(c);if(c[c.size()-1]!='\n') putchar(' ');}
    inline void Write(const char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');}
    template<class T,class... Args> inline void write(T x,Args... args){write(x);write(args...);}
    template<class T,class... Args> inline void Write(T x,Args... args){Write(x);Write(args...);}
}
using namespace IO;
namespace DQ{
    struct Q{int t,id;}que[N];
    int hd=1,tl=0;
    inline void Clr(){hd=1,tl=0;}
    inline void Add(int x,int id){
        while(hd<=tl&&que[tl].t<x) tl--;
        que[++tl]={x,id};
    }
    inline int Get(int l){
        while(hd<=tl&&que[hd].id<l) hd++;
        if(hd>tl) return 0;
        return que[hd].t;
    }
}

inline bool check(int sz){
    memset(dp,0,sizeof dp); DQ::Clr();
    For(i,1,n,1){
        if(i>=sz) DQ::Add(max(dp[i-sz][1],dp[i-sz][0])+n-(i-sz),i-sz);
        dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
        dp[i][1]=max(dp[i][1],DQ::Get(i-w[i])+i-n);
    }
    if(max(dp[n][0],dp[n][1])<s) return 0;
    else return 1;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    read(n);
    For(i,1,n,1) read(w[i]);
    read(s);s=ceil(n*1.0/100*s);
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) l=mid+1;
        else r=mid-1;
    }
    write(r);
}

  3. T3 树上的宝藏：

    考虑先不更换，显然树形 DP。

    因为只能换一条，可以考虑换根，枚举到 \(u\) 子节点 \(v\) 时转移。

    这里用了 \(dp_{0/1}\) 表示不更换以 \(1\) 为根选、不选的方案数，\(s_{u,0/1}\) 表示不更换以 \(u\) 为根选、不选的方案，\(ans_{u,0/1}\) 表示将 \(fa_u \to u\) 替换后选、不选的方案。

    可以少用一个，但无所谓。

  4. T4 MEX：

    不会，先咕了。

标签：write,char,putchar,int,void,2024,inline,初三,集训
From： https://www.cnblogs.com/xrlong/p/18028210

相关文章

  • 2024初三年后集训模拟测试4
    前言比赛链接普及模拟赛，但是分拿的不高，主要想\(T1\)想时间太长了，别的没时间做了，时间分配有问题。\(T1~100pts:\)模拟+打表，立体的骰子不太容易想，规律也不好找，但发现规律后超级简单，我敢说我发现的规律是全机房最简便的。但是想的时间用太长了，已经做出来了还验证半天。......
  • 2024/2/22 还是要记录才算学了
    什么是Cmake？打个比喻，小明在路边卖煎饼赚了300万准备买房，但是小明这一麻袋的5毛、一块、十块、五十、一百售楼处的小姐姐嫌麻烦不想收这些钱，那怎么办呢？小姐姐建议小明把钱拿到银行去换成一张银行卡，然后直接来刷卡就行啦！CMake这里就扮演银行的角色。MinGW提供了一套简单方便的Win......
  • 龙哥盟 Python 译文集 2024.2 更新
    每个程序员都应该知道的40个算法Python数学应用Python入门指南Python物联网入门指南Python比特币编程实用指南Python密码学实用指南Python数据结构和算法实用指南Python企业自动化实用指南PythonGPU编程实用指南Python物联网项目LearningScrapy中文版通......
  • 2024初三集训模拟测试4
    打了一场模拟赛又没命了2024初三集训模拟测试4题目难度T4\(\le\)T2\(\le\)T3\(\le\)T1T1打赌非常好题目，使我骰子旋转定义三个变量记录当前状态：上，前，左横着旋转，四个一循环，\(ans\)直接加$14$(模拟模拟模拟模拟)模拟一下就可以码#include<bits/stdc++.h>......
  • 【2024.02.22】构图练习（滨田英明）
    ......
  • Jenkins CLI 任意文件读取漏洞（CVE-2024-23897）复现
    0x00漏洞简介Jenkins是一款基于JAVA开发的开源自动化服务器。Jenkins使用args4j来解析命令行输入，并支持通过HTTP、WebSocket等协议远程传入命令行参数。在args4j中，用户可以通过@字符来加载任意文件。这一特性存在安全风险，攻击者可以利用它来读取服务器上的任意文件。0x01影响......
  • 2024-02-21-物联网Shell语言(2-系统调用)
    2.系统调用2.1系统编程概述操作系统的职责：操作系统用来管理所有的资源，并将不同的设备和不同的程序关联起来Linux系统编程：在有操作系统打的环境下编程，并使用操作系统提供的系统调用及库函数，对系统资源进行访问系统编程就是为了让用户更方便的操作硬件设备,并且对硬件设备起到......
  • dp 学习笔记 （2024/2/22 - ）
    计数[ARC107D]NumberofMultisets[ARC104D]MultisetMean大值域限制偏序计数[CF1295F]GoodContest[ARC104E]RandomLIS......
  • 2024初三集训模拟测试4
    2024初三集训模拟测试4\(T1\)打赌\(0pts\)\(T2\)舞会\(0pts\)\(T3\)最小生成树\(0pts\)经打表，有最小生成树的边权和为\(n-1\)，构造每条边上的两端点互质即可。故\(\prod\limits_{i=1}^{n}\varphi(i)\)即为所求。点击查看代码constllp=100000007;llph......
  • 2024初三集训模拟测试4
    T1打赌简单题，模拟一下即可。T2舞会小贪心，尽量找离自己最近的防止后面的不能找。T3最小生成树显然权值和为\(n-1\)，就是连互质的数，然后要求父亲小于儿子，所以欧拉函数一乘即可。T4买汽水正解是分成两组后搜索加剪枝，随机化也能过，数据很水。......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99