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

2024初三年后集训模拟测试1

时间：2024-02-17 18:55:37浏览次数：22  
标签：int sum long 2024 freopen define 集训 模拟 getchar

前言

image

  • 总分 \(310\)

    • \(T1~100\)

    • \(T2~100\)

    • \(T3~50\)

      题解方法属实巧妙，考场上想到了枚举平均值和前缀和，但没想到满足 \(sum_{l-1}=sum_r\) （见下面题解）。

    • \(T4~60\)

      离谱题：

      存在多组可能的解，输出满足条件的一组解即可。

      评测方式：文本比较。

      没有 \(special~judge\) ，只能得输出 \(-1\) 的 \(60\) 分（但我只写了 \(-1\) ，赚大了）。

  • 比赛链接

T1 edit

  • 没什么好说的，使用 \(getline\) 以方便读入空格，像这种第一题尤其注意审题仔细，不要手残即可。
  • \(getline\) 食用指南：
cin.getline(s,1000,'\n');//1000是长度，到换行符结束。
  • 代码如下：
#include<bits/stdc++.h>
#define int long long 
#define enl '\n'
using namespace std;
const int N=20,M=3e6+10;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    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);
}
char s[110];
signed main()
{
	// #ifndef ONLINE_JUDGE
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // #endif
    freopen("edit.in","r",stdin);
    freopen("edit.out","w",stdout);
    cin.getline(s,1000,'\n');
    int len=strlen(s);
    for(int i=0;i<len;i++)
    {
        if(i==0) cout<<s[i];
        else if(s[i]==' ') cout<<' ';
        else 
        {
            if(s[i-1]>='0'&&s[i-1]<='9'&&s[i]!=' '&&(s[i]<'0'||s[i]>'9'))
                cout<<' '<<s[i];
            else if(s[i]>='0'&&s[i]<='9'&&s[i-1]!=' '&&(s[i-1]<'0'||s[i-1]>'9'))
                cout<<' '<<s[i];
            else cout<<s[i];
        }
    }
}

T2 game

  • 暴力：

    最优策略下 \(A,B\) 都取最大值，故此先排序。

    \(A\) 取最大值显然，而 \(B\) 为了不让 \(A\) 取到最大值，也取最大值。

    \(A\) 可以每次取多个，\(B\) 每次仅能取一个，\(A\) 是先手。

    不难发现，在 \(a_i>0\) 的时候，\(A\) 是必取的，反之，若 \(a_i<0\) ，\(A\) 尽可能少取。

    所以在第一回合 \(A\) 取的时候，必然要取所有的正数。

    之后为了尽可能少的取到负数，\(A\) 从此一次只取一个，由此 \(B,A,B,A…\) 轮流取，\(A\) 每两个取一个，当然每次取的都是最大值。

    但同时，继续思考并不是完全如此，为了避免取到一个极大的，或者为了少取一个复值，在第一次 \(A\) 取的时候，\(A\) 可能会取几个负值。

    那么就可以在正数全部取的条件下，枚举 \(A\) 第一次取时截止到的位置，剩下的 \(B,A\) 轮流，因为已经排好序，每次取的定为最大值。

    那么剩下这些轮流的部分每次都现求是绝对不行的，\(n\leq 1e5\) ，故此不妨使用前缀和，但魔改一下。

    可以理解成分成了两组的前缀和，一组是奇数的，一组是偶数的（下标）。

    处理前缀和也没那么麻烦，不必真的分两组，直接

    sum[i]=sum[i-2]+a[i];

    即可。

    而枚举时，也是正常的用，但同时要选对的一组，如果剩下个数为偶数，则 \(A\) 能轮到 \(a_n\)，反之 \(A\) 轮到 \(a_{n-1}\)，由此：

    if((n-i)%2==0) ans+=sum[n]-sum[i];
else ans+=sum[n-1]-sum[i];

    • \(\color{red}{Hack} ：\)

      数据：

      5
-5121313 -81 -713 -25 -479

      即全部为负值的情况，仔细阅读体面，\(A\) 为先手，必须至少取一个。如果直接按照上述思路，因为我们搞的是先把正数取了，后面轮流，但是在这里就会导致 \(B\) 成了先手。

      也很好解决，当只有负数的时候，让 \(A\) 先把第一个取了，再接着搞就好了。

      考试时没想到 \(Hack\) ，但数据 \(\color{blue}{水}\)。

    • 代码如下：

    #include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
const int N=1e5+10;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    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);
}
int n,a[N],ans=-0x7f7f7f7f,tot,sum,num,s[N];
bool cmp(int a,int b) {return a>b;}
signed main()
{
    // #ifndef ONLINE_JUDGE
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // #endif
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    read(n);
    for(int i=1;i<=n;i++) 
    {
        read(a[i]);
        if(a[i]>=0) sum+=a[i],tot++;
    }
    stable_sort(a+1,a+1+n,cmp);
    if(tot==0) tot=1,sum=a[1];
    for(int i=1;i<=n;i++)
        s[i]=s[i-2]+a[i];
    for(int i=tot;i<=n;i++)
    {
        if(i!=tot) sum+=a[i];
        num=sum;
        if((n-i)%2==0) num+=s[n]-s[i];
        else num+=s[n-1]-s[i];
        ans=max(num,ans);
    }
    cout<<ans;
}//枚举A第一次取直接截止到的位置，之后每两个取一个，前缀和维护。

  • \(DP\) ：

    打 \(DP\) 前没想到能这么简单。

    也是先排一遍序，道理同上。

    \(f[i][1]\) 表示 \(A\) 选择 \(a_i\) ，\(f[i][0]\) 表示 \(A\) 不选，即 \(B\) 选。

    \(\color{red}{Hack}\) 也好解决，初始值 \(f[1][1]=a[1],f[1][0]=-1e18\) 即可，因为第一个 \(A\) 必须选，附上极小值后面肯定不会有他了。

    转移方程更好想

    f[i][1]=max(f[i-1][1],f[i-1][0])+a[i];
f[i][0]=f[i-1][1];//若此处 B 选，则上一个必须为 A 选，因为 $B$ 只能选一个。
    • 代码如下：
    #include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
const int N=1e5+10;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    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);
}
int n,a[N],f[N][2];
bool cmp(int a,int b) {return a>b;}
signed main()
{
    // #ifndef ONLINE_JUDGE
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // #endif
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    stable_sort(a+1,a+1+n,cmp);
    f[1][1]=a[1];
    f[1][0]=-1e18;
    for(int i=2;i<=n;i++)
        f[i][1]=max(f[i-1][1],f[i-1][0])+a[i],
        f[i][0]=f[i-1][1];
    cout<<max(f[n][1],f[n][0]);
}

  • 复杂度卡到 \(O(n\log(n))\) ，无法改善了，光排序已经 \(O(n\log(n))\) 了。

T3 score

  • 部分分：

    • \(50\) ：前缀和维护暴力。
    • \(70\) ：在上面基础上特殊考虑 \(a_i\leq 2\) 的一组情况。

  • 正解：

    看了题解后感觉很巧妙也很简单，但考场上竟然没有一个人 \(AC\) 。

    从最小值到最大值枚举可能的平均值 \(t\) ，那么如果该区间的平均值为 \(t\) ，则满足 \(\sum\limits_{i=l}^ra_i-t=0\) 。

    同时前缀和维护也是显然的，那么怎样将他们联系到一起。

    可以先讲每个 \(a_i-t\) ，得到 \(b\) 序列，处理出 \(b\) 序列的前缀和 \(sum\) ，那么出现 \(sum_{l-1}=sum_r\) 的时候，则该区间符合。

    想到这里便会恍然大悟，接下来就变得简单了，排一遍序，方便找相等的项，求的是有几对相等的 \(sum\) ，那么求出 \(sum\) 序列中每个数出现的个数，分别记作 \(num\) ，\(num\) 个数两两配对，也就是 \(\text{C}_{num}^2\) ，即 \(ans+=(num-1)\times num÷2\) 。

  • 代码如下：

#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
const int N=1e5+10;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    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);
}
int n,a[N],b[N],s[N],ans,maxx,minn=0x3f3f3f3f;
signed main()
{
	// #ifndef ONLINE_JUDGE
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // #endif
    freopen("score.in","r",stdin);
    freopen("score.out","w",stdout);
    read(n);
    for(int i=1;i<=n;i++) 
        read(a[i]),
        minn=min(minn,a[i]),
        maxx=max(maxx,a[i]);
    for(int t=minn;t<=maxx;t++)
    {
        for(int i=1;i<=n;i++) 
            b[i]=a[i]-t,
            s[i]=s[i-1]+b[i];
        stable_sort(s,s+1+n);
        int sum=1;
        for(int i=1;i<=n;i++)
            if(s[i]==s[i-1]) 
                sum++;
            else 
                ans+=(sum-1)*sum/2,
                sum=1;
        ans+=(sum-1)*sum/2;
    }
    cout<<ans;
}
  • 复杂度最劣情况为 \(O(100n\log(n))\) ，因为 \(a_i\leq 100\) 。

标签：int,sum,long,2024,freopen,define,集训,模拟,getchar
From： https://www.cnblogs.com/Charlieljk/p/18018057

相关文章

  • 2024初三集训模拟测试1
    2024初三集训模拟测试1\(T1\)edit\(100pts\)字符串模拟即可。貌似不能写成while(cin>s)，因为每两个单词中可能不只有一个空格。点击查看代码strings;intmain(){ freopen("edit.in","r",stdin); freopen("edit.out","w",stdout); getline(cin,s); cou......
  • Codeforces 解题报告（202402）
    CodeforcesRound926D-SashaandaWalkintheCitydp，主要难点在于设状态。发现子树内一旦存在一个点，到当前子树的根节点路径上有两个危险点，那么除了那条链所属的子树，其他的点就都不能选了。所以把这个性质放进状态，设\(f_{u,0/1}\)表示以\(u\)为根的子树内，是否存在一......
  • 2024初三集训模拟测试1
    2024初三集训模拟测试1所以正解和一行\(-1\)等分T1edit：语法题。考getline正确使用T2game：简单\(dp\)也可以贪心，见The_Shadow_Dragon。注意初始化。CODE#include<bits/stdc++.h>usingnamespacestd;usingllt=longlong;usingull=unsignedlonglong;......
  • 2024.2.17模拟赛T1题解
    先考虑\(q=(1...n)\)的情况：发现如果设\(divcnt(p)\)表示将\(p\)划分为极小值域连续段的个数，那满足\(divcnt(p)\gem\)的排列都是合法的。那现在要求出有多少个排列符合条件可以先算出长度为\(i\)，\(divnct\)为\(1\)的排列个数，这可以用dp解决然后再背包一下，就能求......
  • 2024-02-17-物联网C语言(4-预处理)
    4.预处理4.1c语言的编译过程gcc-Ehello.c-ohello.i#1.预编译gcc-Shello.i-ohello.s#2.编译gcc-chello.s-ohello.o#3.汇编gcchello.o-ohello_elf#4.链接预编译将.c中的头文件展开、宏展开编译将预处理之后的.i文件生成.s汇编文件......
  • IDEA 2024.1：Spring支持增强、GitHub Action支持增强、更新HTTP Client等
    有段时间没有更新IDEA了，早上看到IntelliJIDEA2024.1EAP5发布的邮件提示，瞄了一眼，发现真的是越来越强了，其中不少功能对我来说还是非常有用的。也许这些能力对关注DD的小伙伴也有帮助，所以搞篇博客介绍和推荐一下。Spring、Quarkus等主流框架的支持增强SearchEverywhere功能......
  • 2024寒假集训纪要 & 闲话 (下半)
    2.16本来说要写\(4\)道多项式的题的，到最后算上\(\text{AC}\)自动机之类的也没\(4\)道题\(\color{white}{唔，我好想补完春节期间在家看的『约会大作战(第三部)』啊，但是我没有【数据删除】所以看不了诶}\)明天似乎有模拟赛？寄寄寄寄寄寄寄寄寄寄搞了个题单，但是看起来意义不......
  • 2024-02-17 有一个观点有松动了，没房没车没存款，配不配
       2024-02-17     好像挺根深蒂固的，没房没车没存款，都没有资格结婚恋爱，在女人面前也很自卑。   直到我叔和婶娘，跟我说，这个不讲配不配得上，而是讲缘分的。举了现实的例子，富家女嫁穷小伙的，帮穷小伙买车买房。   还有一些外省嫁过来的。还有我们家，几个叔......
  • 2024-02-17-物联网C语言(3-函数)
    3.函数3.1函数的概念函数是c语言的功能单位，实现一个功能可以封装一个函数实现。定义一个函数的时候需要一切以功能为目的，根据功能去定义函数的参数和返回值。3.2函数的分类3.2.1从定义角度分类库函数（c库实现）自定义函数（程序员自定义函数）系统调用（操作系统实现的函数）3.......
  • 2024 寒假做题总结
    P2146[NOI2015]软件包管理器思路分析树链剖分板子，每次安装时，将\(1\)到\(x\)的链变为\(1\)，卸载时，将\(x\)的子树变为\(0\)。代码#include<iostream>usingnamespacestd;inlineintread(){registerintx=0,f=1;registercharc=getchar();while(c<'0'......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99