ACGO挑战赛题解#17

༺ A MC Lover ༻

2025-04-21 12:03:40

发布于：浙江

41阅读

0回复

0点赞

这次挑战赛怎么评价呢：冰火两重天

1-2题羊了个羊第一关，易如反掌，有手就行

建议打回欢乐赛

3-4题中规中矩

5-6题：

超标! 太超标了！！！

不会简化代码的同学千万不要尝试，分分钟TLE，直接体验 “代码火葬场” 的酸爽！

T1凤梨酥
我盯着题目思考了 0.01 秒，突然意识到 ——

这不是在考我，是在给我送分！

主办方也太贴心了，下次别送了，真的，我怕骄傲。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    if(a>=50&&b>=30)cout<<1<<endl;
    else if(a>=50&&b>=15&&b<30)cout<<2<<endl;
    else cout<<3<<endl;
    return 0;
}

T2 买凤梨1
这道题目无脑算回文数，只需要把a[i]的每一位数字拆开倒着组合一遍，再看下是否与原数相等就行了。什嘛？！你不会拆位？！~~统统吃掉！！！~~

#include<bits/stdc++.h>
using namespace std;
bool AC(int x){
    int t=x,r=0;
    while(t){
        r=r*10+t%10;
        t/=10;
    }
    return r==x;
}
int main(){
    int n,ans=0;cin>>n;
    for(int i=0;i<n;i++){
        int w;cin>>w;
        if(w>=500&&w<=10000&&AC(w))ans++;
    }
    cout<<ans<<endl;
    return 0;
}

T3 集训课
这道题要看你脑子转地够不够快，我们可以定义一个time[]数组，然后不断的输入，一单遇到1就time[day]++，最后看time内的数据是否等于n就可以了_{（我代码里定义了个啥你不要管）}

#include<bits/stdc++.h>
using namespace std;
int main(){
    int ACGO[510]={},n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int op;cin>>op;
            if(op)ACGO[j]++;
        }
    }
    int Max=0,as=0;
    for(int i=1;i<=m;i++){
        if(ACGO[i]==n)as++;
        else if(Max<as){Max=as;as=0;}
    }
    cout<<Max<<endl; 
    return 0;
}

T4 摸鱼
这道题和T3一个德行啊，解题思路一毛一样，我都怀疑主办方同一道题发了两遍

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,T,a;cin>>n>>T>>a;
    bool time[T+20]={0};
    int l,r;
    for(int i=1;i<=n;i++){
        cin>>l>>r;
        for(;l<=r;l++){
            time[l]=1;
        }
    }
    /*for(int i=1;i<=T;i++){
    	cout<<time[i]<<" ";
	}cout<<endl;*/
    int ans=0,res=0;time[T+1]=1;
    for(int i=1;i<=T+1;i++){
        if(time[i]==0)res++;
        else {ans+=res/a;res=0;}
       // cout<<res<<" "<<ans<<endl;
    }
    cout<<ans<<endl;
    return 0;
}

T5 买凤梨2
这道题他还是和T3一个德行，但是我一看取值范围

《1 ≤n, k, q≤200000 1≤l,r≤200000》

那我们看下我们原来的解题思路，好家伙，两个双重循环，这代码复杂度直接来到了n的二次方
所以我连夜修改代码，给大家推出一种新的算法：差分

当我们输入l和r时，可以让数组diff[l]加1，让diff[r+1]减1，之后在循环外再搞个循环，通过sweet[i]=sweet[i-1]+diff[i];把数据存入sweet[]就可以了，至于代码的底层逻辑，我放在下面：

比方说我输入了1 4，那么diff就会是：

1	2	3	4	5	6	……
1	0	0	0	-1	0	……

再之后的循环中sweet就会变成这样：

0	1	2	3	4	5	6	…
0	sweet[1-1]+diff[1];	sweet[2-1]+diff[2];	sweet[3-1]+diff[3];	sweet[4-1]+diff[4];	sweet[5-1]+diff[5];	sweet[6-1]+diff[6];	…
0	1	1	1	1	0	0	…

这样代码复杂度就变成了O(n)
很简单对吧，在存储上化简了还不够，我们还要在输出上化简

我们可以定义一个ans[]把ans的每一位赋值为：ans[i]=ans[i-1]+(sweet[i]>=k?1:0);
比方说现在sweet[]={0 1 0 1 1 0}，k=1
那么ans就会变成：

0	1	2	3	4	5	6	……
0	ans[i-1]+(sweet[i]>=k?1:0);	ans[i-1]+(sweet[i]>=k?1:0);	……	……	……	……	……
0	0	1	1	2	3	3	……

之后我们询问l号到r号，就直接输出ans[r]-ans[l-1]就可以了
下面是代码：

#include<bits/stdc++.h>
using namespace std;
int sweet[200010]={0};
int diff[200010]={0};
int ans[200010]={0};
int main(){
    int n,k,q;cin>>n>>k>>q;
    
    for(int i=1;i<=n;i++){
        int l,r;cin>>l>>r;
        diff[l]++;diff[r+1]--;
    }
    for(int i=1;i<200010;i++){
    	sweet[i]=sweet[i-1]+diff[i];
	}
	for(int i=1;i<200010;i++){
		ans[i]=ans[i-1]+(sweet[i]>=k?1:0);
	}
    for(int i=1;i<=q;i++){
        int l,r;cin>>l>>r;
        cout<<ans[r]-ans[l-1]<<endl;
    }
    return 0;
}

T6 美丽子序列
我也不知道我代码怎么了,TM的就是AC与WA交织，哪位大神帮我看下错哪了

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],qmin[N],qmax[N];
int hhmin=0,ttmin=-1,hhmax=0,ttmax=-1;
int main(){
    int n,k;cin>>n>>k;
    for(int i=0;i<n;i++)cin>>a[i];
    long long ans=0;
    for(int r=0,l=0;r<n;r++){
        while(hhmin<=ttmin&&a[qmin[ttmin]]>=a[r])ttmin--;
        qmin[++ttmin]=r;
        while(hhmax<=ttmax&&a[qmax[ttmax]]<=a[r])ttmax--;
        qmax[++ttmax]=r;
        while(l<=r&&a[qmax[hhmax]]-a[qmin[hhmin]]>=k){
            ans+=n-r;
            l++;
            while(hhmin<=ttmin&&qmin[hhmin]<l)hhmin++;
            while(hhmax<=ttmax&&qmax[hhmax]<l)hhmax++;
        }
    }
    cout<<ans<<endl;
    return 0;
}