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

2024-02-17 21:46 由卡布叻_周深发表于 #后端开发

前言

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

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

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