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\) ,所以鉴于数据水,就不处理了。
无解的问题就解决了,接下来连边就可以了。
此处注意不要自边,不要重边就可以了,同时方向也要注意固定,不然可能不小心出来重边。
- 块内连接成环,即求最小值时那些边。
- 不够继续连,块内每个点都可以和剩下的点连一条。
- 不够就和别的块连,但是这里两个快之间每对点都必须沿着同一固定方向连一条,不能形成环。
- 再不够就和孤点连,和上面一样,不能形成环。
其实上面就是最大值,可以发现数量是非常巨大的,所以用不了这么多,通常到第二步已经完事了。记录边数,到 \(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\) 。
今天好像光搞这个玩意儿了。
热门相关:北宋闲王 神秘老公,晚上见! 锦桐 甜蜜隐婚:老公大人,宠上瘾 资本大唐