首页 > 其他分享 >初三奥赛模拟测试4

初三奥赛模拟测试4

时间：2024-04-06 15:11:55浏览次数：24  
标签：int max sum mid read 奥赛 初三 模拟 define

前言

image

\(CSP-S\) 模拟赛，确实比前几次简单多了。

  • \(T1~100pts\) ： 签到题。

  • \(T2~100pts\) ：二分直接跑即可。

  • \(T3~40pts\) ：

    首先他给的这个快读没法用。

    赛时 joker 了，打了个 \(n^2~DP\) ，然后优化了 \(50min\) 换了个转移方程还是 \(n^2\) ，复杂度打假了。

    因为赛时懒得跑线段树，而且知道这玩意常数太大过不去，赛后听有人说 \(ST\) 表才恍然大悟，成 joker 了 。

  • \(T4~0pts\) ：光顾着调 \(T3\) 了，没怎么看。

  • 比赛链接 。

\(T1\) 最后一课

签到题，没什么好说的，将军饮马问题 。

点击查看代码 
#include<bits/stdc++.h>
#define int __int128
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=true;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
void wt(int x){if(x>9)wt(x/10);putchar((x%10)+'0');}
void write(int x){if(x<0)putchar('-'),x=~x+1;wt(x);}
int k,x,y,xx,yy;
signed main()
{
	#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    read(k),read(x),read(y),read(xx),read(yy);
    if((y<=k&&yy<=k)||(y>=k&&yy>=k))
    {
        y=k*2-y;
        write((xx-x)*(xx-x)+(yy-y)*(yy-y));
        return 0;
    }
    write((xx-x)*(xx-x)+(yy-y)*(yy-y));
}

\(T2\) 日常

二分直接跑即可，记得排序。

点击查看代码 
#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e5+10;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=true;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
void wt(int x){if(x>9)wt(x/10);putchar((x%10)+'0');}
void write(int x){if(x<0)putchar('-'),x=~x+1;wt(x);}
int n,m,k;
bool v[N];
struct aa
{
    int l,r,x,y;
}e[N];
bool cmp(aa a,aa b) {return a.l==b.l?a.r<b.r:a.l<b.l;}
int ask1(int i)
{
    int l=1,r=n,mid,ans=0;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(e[mid].l>i) r=mid-1;
        if(e[mid].r<i) l=mid+1;
        if(e[mid].l<=i&&e[mid].r>=i) 
        {
            ans=mid;
            break;
        }
    }
    return ans;
}
int ask2(int i)
{
    int l=1,r=n,mid,ans=0;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(e[mid].x>i) r=mid-1;
        if(e[mid].y<i) l=mid+1;
        if(e[mid].x<=i&&e[mid].y>=i) 
        {
            ans=mid;
            break;
        }
    }
    return ans;
}
signed main()
{
	#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    read(n),read(m),read(k);
    for(int i=1,l,r,x,y;i<=n;i++)
    {
        read(l),read(x),read(y),read(r);
        e[i]={l,r,x,y};
    }
    sort(e+1,e+1+n,cmp);
    for(int i;k>=1;k--)
    {
        read(i);
        int ans=ask1(i),anss=ask2(i);
        if(ans==0) puts("Failed");
        else if(v[ans]) puts("Again");
        else if(anss) puts("Perfect");
        else puts("Normal");
        v[ans]=1;
    }
}

\(T3\) 渡尘

部分分

  • \(20pts\) ：

    纯暴力跑，\(O(n^2m)\) 。

  • \(40pts\) ：

    \(O(n^2)\) 区间 \(DP\) 。

    转移方程：

    \[f_{l,r}=\max\{f_{l,r},abs(sum_r-sum_{l-1}),f_{l+1,r},f_{l,r-1}\} \]

    点击查看代码 
    #include<bits/stdc++.h>
#define int long long 
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=5010;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=true;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
void wt(int x){if(x>9)wt(x/10);putchar((x%10)+'0');}
void write(int x){if(x<0)putchar('-'),x=~x+1;wt(x);}
int n,m,a[N],sum[N],f[N][N];
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    read(n),read(m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f[i][j]=-0x3f3f3f3f;
    for(int i=1;i<=n;i++)
        read(a[i]),
        sum[i]=sum[i-1]+a[i],
        f[i][i]=abs(a[i]);
    for(int i=1;i<=n;i++)
        for(int j=i-1;j>=1;j--)
            f[i][j]=max({
                f[i][j],
                abs(sum[i]-sum[j-1]),
                abs(sum[i]-sum[j]),
                abs(sum[i-1]-sum[j-1]),
                f[i][j+1],f[i-1][j],f[i-1][j+1]
                });
    for(int l,r;m>=1;m--)
        read(l),read(r),
        write(f[r][l]),puts("");
}

  • \(70pts\) ：

    线段树维护区间最大子段和，类似 山海经 这道题。

    记录每个区间的最大前缀和，最大后缀和，最大字段和，区间和。

    • 最大字段和 \(=\) 左区间最大后缀 \(+\) 右区间最大前缀。

    • 最大前缀和 \(=\max\{\) 左区间最大前缀和，左区间和 \(+\) 右区间最大前缀和 \(\}\) 。最大后缀和同理。

    复杂度 \(O(m\log(n))\) ，理论可过，但由于线段树的超级常数，只能拿 \(70pts\) 。

    代码没打，沾 \(Hangry\) 的了。

    点击查看代码 
    #include <bits/stdc++.h>
#define int long long 
#define lson (id << 1) 
#define rson (id << 1 | 1)
using namespace std ; 
const int N = 2e5 + 100 ; 
inline int read() {
    int x = 0 , f = 1 ; 
    char c = getchar() ; 

    while ( c < '0' || c > '9' ) {
        if ( c == '-' ) f = -f ;  
        c = getchar() ; 
    }

    while ( c >= '0' && c <= '9' ) {
        x = x * 10 + c - '0' ; 
        c = getchar() ; 
    }

    return x * f ; 
}
int n , m ; 
int a[N] ; 
class AVST {
    public: 
        int Max , sum ; 
        int left_min , right_min ; 
        int left_max , right_max ; 
} t[N << 2] ; 
inline unsigned int Absolute ( int x ) {
    return x >= 0 ? x : -x ; 
}
inline int max( int a , int b ) {
    return a > b ? a : b ; 
}
inline int min( int a , int b ) {
    return a < b ? a : b ; 
}
inline void push_up( AVST &Main , AVST Lson , AVST Rson ) {
    Main.sum = Lson.sum + Rson.sum ; 
    Main.left_max = max( Lson.left_max , Lson.sum + Rson.left_max ) ; 
    Main.left_min = min( Lson.left_min , Lson.sum + Rson.left_min ) ; 
    Main.right_max = max( Rson.right_max , Rson.sum + Lson.right_max ) ; 
    Main.right_min = min( Rson.right_min , Rson.sum + Lson.right_min ) ; 
    Main.Max = max( max( Main.sum , max( Lson.Max , Rson.Max ) ) , max( Absolute( Lson.right_max + Rson.left_max ) , Absolute( Lson.right_min + Rson.left_min ) ) ) ; 
}
void build( int id , int l , int r ) {
    if ( l == r ) {
        t[id].Max = Absolute( a[l] ) ; 
        t[id].sum = t[id].left_max = t[id].left_min = t[id].right_max = t[id].right_min = a[l] ; 
        return ; 
    }
    int mid = ( l + r ) >> 1 ; 
    build( lson , l , mid ) ; build( rson , mid + 1 , r ) ; 
    push_up( t[id] , t[lson] , t[rson] ) ; 
}
AVST Query( int id , int l , int r , int x , int y ) {
    if ( x <= l && r <= y ) {
        return t[id] ; 
    }
    int mid = ( l + r ) >> 1 ; 
    if ( x <= mid && mid < y ) {
        AVST reso = {0 , 0 , 0 , 0 , 0 , 0} , lef , rig ; 
        lef = Query( lson , l , mid , x , y ) ; 
        rig = Query( rson , mid + 1 , r , x , y ) ; 
        push_up( reso , lef , rig ) ; 
        return reso ; 
    } else {
        if ( x <= mid ) return Query( lson , l , mid , x , y ) ; 
        if ( y >= mid + 1 ) return Query( rson , mid + 1 , r , x , y ) ; 
        AVST bre ; return bre ; 
    }
}
signed main() {
#ifndef ONLINE_JUDGE
    freopen( "1.in" , "r" , stdin ) ; 
    freopen( "1.out", "w" ,stdout ) ; 
#endif
    n = read() ; m = read() ; 
    for ( int i = 1 ; i <= n ; ++ i ) {
        a[i] = read() ; 
    }
    build( 1 , 1 , n ) ; 
    int x , y ; 
    for ( int i = 1 ; i <= m ; ++ i ) {
        x = read() , y = read() ; 
        if ( i == m ) printf( "%lld" , Query( 1 , 1 , n , x , y ).Max ) ;
        else printf( "%lld\n" , Query( 1 , 1 , n , x , y ).Max ) ;  
    }
}

  • \(100pts\) ：

    因为没有修改，用猫树维护，\(O(n\log(n)+m)\) ，但是我不会。

正解

用 \(sum_i\) 表示前缀和。

则区间 \([l\sim r]\) 和的绝对值就是 \(\max(sum_r-sum_{l-1},sum_{l-1}-sum_r)\) 。

那么问题就转化为在区间 \([l-1\sim r]\) 中找一个最大的 \(sum_x\) 和一个最小的 \(sum_y\) ，\(sum_x-sum_y\) 即为所求。

直接用 \(ST\) 表维护即可，复杂度 \(O(n\log(n)+m)\) 。

注意预处理时循环从 \(0\) 开始，因为 \(l-1\) 可能 \(=0\) 。

这个正解甚至比那些歪解简单得多。

点击查看代码 
#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=true;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
void wt(int x){if(x>9)wt(x/10);putchar((x%10)+'0');}
void write(int x){if(x<0)putchar('-'),x=~x+1;wt(x);}
int n,m,a[N],sum[N],mx[N][30],mi[N][30];
void RMQ()
{
    for(int i=0;i<=n;i++)
        for(int j=0;j<=log2(n);j++)
            mi[i][0]=mx[i][0]=-0x3f3f3f3f;
    for(int i=0;i<=n;i++)
        mx[i][0]=sum[i],
        mi[i][0]=-sum[i];
    for(int j=1;j<=log2(n);j++)
        for(int i=0;i<=n-(1<<j)+1;i++)
            mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]),
            mi[i][j]=max(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
}
int ask_mx(int l,int r)
{
    int t=log2(r-l+1);
    return max(mx[l][t],mx[r-(1<<t)+1][t]);
}
int ask_mi(int l,int r)
{
    int t=log2(r-l+1);
    return max(mi[l][t],mi[r-(1<<t)+1][t]);
}
signed main()
{
	#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    read(n),read(m);
    for(int i=1;i<=n;i++)
        read(a[i]),
        sum[i]=sum[i-1]+a[i];
    RMQ();
    for(int l,r;m>=1;m--)
        read(l),read(r),
        write(ask_mx(l-1,r)+ask_mi(l-1,r)),puts("");
}

标签：int,max,sum,mid,read,奥赛,初三,模拟,define
From： https://www.cnblogs.com/Charlieljk/p/18117457

相关文章

  • 150行Python代码模拟太阳系行星运转
    今天我们用Python来模拟一下太阳系行星运动轨迹~先上成品图（运行效果含音乐的呦）想要实现这样的效果并不难准备材料首先我们需要准备这样一些材料宇宙背景图背景透明的行星图 编写代码代码分块详解导入需要的模块import pygame  import sys ......
  • c语言字符串函数（strlen strcpy strcat strcmp等使用及模拟）
    在编程的过程中，我们经常要处理字符和字符串，为了方便操作字符和字符串，C语⾔标准库中提供了一系列库函数，接下来我们就学习一下这些函数。目录1、strlen的使用及模拟实现。2、strcpy的使用及模拟实现。3、strcat的使用及模拟实现。4、strcmp的使用及模拟实现。5、strncpy的......
  • 【三十五】【算法分析与设计】综合练习（2），22。 括号生成，77。 组合，494。 目标和，模拟树递
    22.括号生成数字n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。示例1：输入：n=3输出：["（（（）））"，"（（）（））"，"（（））（）"，"（）（（））"，"（）（）（）"]示例2：输入：n=1输出：["（）"]提示：1<=n<=8【三十五】【算法分析与设计】综合练习（2），......
  • BNDS 2024/4/6模拟赛题解
    T1方程描述给出非负整数\(N\)，统计不定方程\(X+Y^2+Z^3=N\)的非负整数解\((X,Y,Z)\)的数量。输入输入数据，包含一个非负整数\(N\)。输出输出数据，包含一个非负整数表示解的数量。数据范围40%的数据，\(N<=10000\)60%的数据，\(N<=10^8\)100%的数据，\(N<=10^{16}\)分析......
  • #线段树，模拟费用流#CF280D k-Maximum Subsequence Sum
    题目给定一个大小为\(n\)的序列，要求支持单点修改和查询区间内至多\(k\)个不交子区间之和的最大值（可以不取）分析考虑源点向每个点、每个点向汇点流流量1费用0的边，每个点向右边的点流流量1费用\(a_i\)的边，流量最大为\(k\)，这样构建出一个费用流的模型。很显然，退流相当于给区......
  • 2024.2.18 模拟赛
    A.小学数学20分暴力即可。40分将询问拆为\(\leqt\)减去\(<s(\leqs-1)\)的两个问题，然后将询问排序后做前缀和即可。满分要求强制在线，将矩阵中所有元素排序，然后分成\(\sqrt{nm}\)个块，每个块记录二维前缀和（出现了多少次块内的数）。每次询问时先处理整块，对于整块外的数再单......
  • 2024.1.23 模拟赛
    郊游首先需要快速找到当前适配度最大的一对小朋友。容易发现\(a,b\)的适配度即为\(a,b\)二进制下最长公共后缀的长度，于是先翻转所有数的二进制串并插入到Trie中。那么\(a,b\)的适配度即为\(a,b\)所代表叶子节点的\(\rmLCA\)（最近公共祖先）深度。若Trie中以\(x\)......
  • 2024.3.17 模拟赛
    A贸易题目保证输入的边\(u<v\)，说明题目中的图是一个有向无环图\(DAG\)，但是不一定连通。可以记录\(f[i]\)表示到达\(i\)之前能遇到的最小的价格，使用拓扑排序进行\(dp\)转移。对于每一个点\(i\),如果其价格为\(a[i]\),就可以用\(a[i]-f[i]\)更新答案，取最大值即......
  • P9902 『PG2』模拟最大流 题解
    首先最大流等于最小割，然后就能很容易地想到一个状压dp做法：记\(f_{i,s}\)表示使得前\(i\)个点中，最后\(k\)个点与点\(1\)的联通情况为\(s\)的最小代价。然后考虑下一个点是否联通直接转移即可，然后就做完了。时间复杂度\(\mathcalO(n2^k)\)。参考代码：#include<bits/s......
  • 2024.2.25 模拟赛
    A按题意直接模拟即可。也就是每次取出一些字符，放入字符串\(P\)中。注意实现时的时间复杂度，不要写成\(O(n^2)\)的。#include<bits/stdc++.h>usingnamespacestd;chars[1000010],t[1000010];inthd1=1,hd2=1,n,m,x,y;charans[2000010];intmain(){ scanf("%s",s+1);n......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99