挑战赛#17 全题解
2025-04-22 19:46:31
发布于：北京
48阅读
0回复
0点赞
再也不打欢乐赛了（上白银了）
T1
简单的判断：
cin>>a>>b;
if(a>=50&&b>=30)cout<<1;
else if(a>=50&&15<=b&&b<30)cout<<2;
else cout<<3;
T2
判断+简单循环
判断一个数是回文数：把这个数倒过来，判断是否与原数相同。
bool check(int x)
{
int X=x,sum=0;//保存原数
while(x)//循环直至x为零
{
sum=sum*10+x%10;//每次让最后一位加到倒转数的后面，这样最后整个数就会倒过来
x/=10;//不要忘记去除最后一位
}
return X==sum;
}
剩下的就是简单判断循环了，相信大家都能写出来。
T3
预处理一个布尔数组，值为这一天是否全部都有空。
然后直接求最大值就行了。
int n,m,i,j,a[505][505],maxn,cnt;
bool b[505];
signed main()
{
cin>>n>>m;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)cin>>a[i][j];
}
for(i=1;i<=m;i++)
{
bool f=1;
for(j=1;j<=n;j++)
{
if(a[j][i]!=1)
{
f=0;
break;
}
}
b[i]=f;
}
for(i=1;i<=m;i++)
{
if(b[i])
{
cnt++;
maxn=max(maxn,cnt);
}
else cnt=0;
}
cout<<maxn;
return 0;
}
T4
我不知道我是怎么在赛时写了个[已编辑]东西吃了 发罚时，最后气急败坏打了个暴力（结果还吃了一发）
思路就是用一个布尔数组储存每个时间段是否有常客，暴力，最后统计的时候用一个计数器算没有常客的连续时长，除上 就行。
signed main()
{
cin>>n>>T>>a;
for(i=1;i<=n;i++)
{
cin>>l>>r;
for(j=l;j<=r;j++)mp[j]=1;
}
for(i=0;i<=T;)//坑点，计数是求从i+1开始的，不能让开始i=1，就是这里暴力错了一次
{
cnt=0;
for(j=i+1;mp[j]==0&&j<=T;j++)cnt++;
sum+=cnt/a;
i=j;
}
cout<<sum;
return 0;
}
T5
差分（当然用线段树/树状数组也行，这里就不展示了，毕竟不是动态查询，直接差分完了）
这题是个原题，我之前做过，CF的一道，好像是什么饮料的推荐温度。
[补]就是，原题链接，洛谷链接
差分：差分是前缀和的逆运算，也就是说差分数组前缀和以后就是原数组。于是我们注意到，区间 只要让差分数组的第 位加 ，第 位减 ，前缀和后 就整体加一了，而这就能运用到本题上了。
前缀和：定义前缀和数组 ，，注意到求区间 和只需求 即可（）。
然后用前缀和算 所有推荐次数大于等于 的就行了。
signed main()
{
cin>>n>>k>>q;
for(i=1;i<=n;i++)
{
cin>>l>>r;
d[l]++;
d[r+1]--;
}
for(i=1;i<200005;i++)d[i]+=d[i-1];
for(i=1;i<200005;i++)sum[i]=sum[i-1]+(d[i]>=k);
while(q--)
{
cin>>l>>r;
cout<<sum[r]-sum[l-1]<<endl;
}
return 0;
}
T6
写了个线段树，这题就是求 的数量，实际上就是线段树（似乎树状数组也行，但是不知道为啥写了线段树，可能是想练练抄书）求逆序对板子改点。
struct Node
{
int maxn;
}tree[4000005];
void build(int id,int L,int R)
{
if(L==R)
{
if(L<=n)tree[id]={a[L]};
else tree[id]={INT_MIN};
return ;
}
int mid=L+(R-L)/2,lc=2*id+1,rc=2*id+2;
build(lc,L,mid);
build(rc,mid+1,R);
tree[id]={max(tree[lc].maxn,tree[rc].maxn)};
}
int query(int id,int L1,int R1,int L2,int R2,int t)
{
if(R1<L2||L1>R2||tree[id].maxn<t)return -1;
if(L1==R1)return (tree[id].maxn>=t)?L1:-1;
int mid=L1+(R1-L1)/2,lc=2*id+1,rc=2*id+2;
int rs=query(rc,mid+1,R1,L2,R2,t);
if(rs!=-1)return rs;
int ls=query(lc,L1,mid,L2,R2,t);
return ls;
}
signed main()
{
cin>>n>>k;
for(i=1;i<=n;i++)cin>>a[i];
build(0,1,n);
for(i=1;i<=n;i++)
{
int t=a[i]+k,id=-1;
if(L<i&&n>0)id=query(0,1,n,L,i-1,t);
if(id!=-1)L=id;
sum+=i-L;
}
cout<<n*(n+1)/2-sum;//总数-非逆序对
return 0;
}
有帮助，赞一个