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

前言

  • 总分 \(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\)

T4 city

  • 先看一些抽象的玩意:


    (图扣自 https://www.cnblogs.com/xrlong/p/18018174)

  • 考完后教练让 \(whk\) 打了一个 \(special~judge\) 易碎物品请勿随意蹂躏。赛时没有,导致最高只能拿 \(60\) 分(和我直接输出-1是一样的 😅😆😝)。

  • 思路:

    很麻烦的一个题,但没有用到很难的知识,算是大模拟了。

    所谓 “城市群”,就是有向图的强连通分量,但这题用不到,用并查集即可。

    难点在于判断是否无解。

    首先,要求限制的城市一定要在一个并查集里,先把他们合并。

    之后搞出以每一个点为祖先的并查集,此时前面合并过的,会有一部分内部有多个点的和一部分内部不存在点的;剩下的都是以自身为祖先,仅有一个点的。此处可以用 \(vector\) 维护。

    这样的话就会形成一些块,内部没有点的自然就淘汰掉。此时也就是块最多的情况,如果此时块的数量仍 \(<X\) ,则必定无解。

    之后便是合并,直到块的数量 \(=X\) 为止,此处其实怎么搞都可以,为了方便将他都合并到一个里。

    在合并之前先按照块内点的数量从大到小排序,这样合并完所剩的孤点便是最多的。

    之后求出需要最小的边,每个块内想要形成环,需要 \(size\) 条边( \(size\) 表示其内点的数量);同时孤点是不用加边的,这也是保留更多孤点的原因。

    则所需最小边的数量也出来了,如果给定的边数量比这还小,那必定无解了。

    其实还应该搞出最大值,但是发现最大值是恐怖的,而且数据比较水,要是把这玩意真搞出来的话恐怕要高精了,\(m<1e5\) ,所以鉴于数据水,就不处理了。

    无解的问题就解决了,接下来连边就可以了。

    此处注意不要自边不要重边就可以了,同时方向也要注意固定,不然可能不小心出来重边。

    1. 块内连接成环,即求最小值时那些边。
    2. 不够继续连,块内每个点都可以和剩下的点连一条。
    3. 不够就和别的块连,但是这里两个快之间每对点都必须沿着同一固定方向连一条,不能形成环。
    4. 再不够就和孤点连,和上面一样,不能形成环。

    其实上面就是最大值,可以发现数量是非常巨大的,所以用不了这么多,通常到第二步已经完事了。记录边数,到 \(m\) 了就停,一边连一边输出。

  • 代码如下(漏洞百出但能过):

#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
const int N=5e5+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,m,k,q,a[N],minn,tot,x,y,cnt,f[N];
vector<int>e[N];
int find(int x)
{
    if(x!=f[x]) f[x]=find(f[x]);
    return f[x];
}
void hebing(int x,int y)
{
    x=find(x),y=find(y);
    f[y]=x;
}
bool cmp(vector<int> a,vector<int> b) {return a.size()>b.size();}
signed main()
{
	// #ifndef ONLINE_JUDGE
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // #endif
    freopen("city.in","r",stdin);
    freopen("city.out","w",stdout);
    read(n),read(m),read(k),read(q);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=q;i++) 
        read(x),read(y),
        hebing(x,y);
    for(int i=1;i<=n;i++) 
        e[find(i)].push_back(i);
    stable_sort(e+1,e+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        if(e[i].empty()) break;
        tot++;
    }
    if(tot<k) cout<<-1,exit(0);
    int num=tot;
    for(int i=2;i<=num;i++)
    {
        if(tot==k) break;
        int len=e[i].size();
        for(int j=len-1;j>=0;j--)
            e[1].push_back(e[i][j]),
            e[i].pop_back();
        tot--;
    }
    if(tot>k) cout<<-1,exit(0);
    stable_sort(e+1,e+1+n,cmp);
    for(int i=1;i<=tot;i++)
    {
        int len=e[i].size();
        minn+=(len<=1)?0:len;
    }
    if(m<minn) cout<<-1,exit(0);
    for(int i=1;i<=tot;i++)
    {
        int len=e[i].size();
        if(len<=1) continue;
        for(int j=1;j<len;j++)
        {
            cout<<e[i][j-1]<<' '<<e[i][j]<<endl;
            cnt++;
            if(cnt==m) exit(0);
        }
        cout<<e[i][len-1]<<' '<<e[i][0]<<endl;
        cnt++;
        if(cnt==m) exit(0);
    }
    for(int l=1;l<=n;l++)
    {
        int len=e[l].size();
        for(int i=0;i<=len-2;i++)
            for(int j=0;j<=len-1;j++)
            {
                if(i==j||i+1==j) continue;
                cout<<e[l][i]<<' '<<e[l][j]<<endl;
                cnt++;
                if(cnt==m) exit(0);
            }
        for(int i=1;i<=len-2;i++)
        {
            cout<<e[l][len-1]<<' '<<e[l][i]<<endl;
            cnt++;
            if(cnt==m) exit(0);
        }
    }
}

总结

有一定收获,名次也比较靠前了,再骗 \(20\) 就榜一了,主要是细心了一点,没有挂分。

题目不难,但是 \(T3\) 思路十分巧妙,\(T4\) 又十分麻烦且离谱,第一次做这种题,但是赛时没有 \(special~judge\) 差评。

学会了 \(getline\) 的食用方法,之前都用 \(fgets\) 的,但那玩意不怎么好用。

赛后再打 \(T2\) 才发现 \(DP\) 这么好想,以后可以多尝试一下 \(DP\)

今天好像光搞这个玩意儿了。

热门相关:北宋闲王   神秘老公,晚上见!   锦桐   甜蜜隐婚:老公大人,宠上瘾   资本大唐