当前位置：首页 > article >正文

[CSP篇] CSP2024 游记（下）

article 2024/11/1 23:04:39

Part.4 CSP-J2024 复赛

复赛也到来了，我也开始了普及组 $210$ 分钟能力的较量。

CSP-J 的前两道题都极为的水，大约 $30\min$ 写完了它们。

CSP-J 的第三题可以进行打表，可以发现，这是通过很多 $8$ 组成的数字调整而来的。

CSP-J 的第四题较为困难，难度接近 [NOIP2018 普及组] 摆渡车这到题，成为普及组为数不多的蓝题天花板。

由于 CCF 的一些加密措施，我还不确定代码是否正确，如果赛后愿意补题可以继续关注我的博客。

这时代码还没有，考试结束后想要代码的请见：CSP-J代码公示。

Part.5 CSP-S2024 复赛

CSP-J 的 AK 机会深深鼓舞了我，在小时房里短暂地休息一小时后，我进入了提高组的赛场。

这次比赛可根上次有所不同，第一题也有一定的思维量，其实可以发现，我们的怪物从小到大地吃，每次吃掉比他小的怪物中，最大的怪物，贪心即可。

//Wrote by Timmy in October 26th
//I wish I could have 100 points in this problem
#include <bits/stdc++.h>
using namespace std;
multiset <int> st;
int a[100010];
int main(){
    //freopen("duel.in","r",stdin);
    //freopen("duel.out","w",stdout);
    int n,ans; cin>>n; ans=n;
    for (int i=1; i<=n; i++){
        cin>>a[i];
        st.insert(a[i]);
    }sort(a+1,a+n+1);
    for (int i=1; i<=n; i++){
        auto it=st.lower_bound(a[i]);
        if (it!=st.begin()) it--,st.erase(it),ans--;
    }cout<<ans; return 0;
}

通过了 $20\min$ 的调试，我通过了大样例，点开了第二题。

第二题看上去不是那么友好，题目是在很长，但是仔细分析，你会发现他在问两个东西：

有几辆车超速了。
最少保留几个减速器可以使超速车辆不变。

分类讨论，会发现一辆车被识别为超速的检测器形成一个区间（很简单，单调的），贪心解决第二问即可，注意找到这个区间要使用二分查找哦～

//Wrote by Timmy in October 26th
//I wish I could have 100 points in this problem
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int p[N],v[N],a[N],k[N];
pair <int,int> seg[N];
int main(){
    //freopen("detect.in","r",stdin);
    //freopen("detect.out","w",stdout);
    int t; cin>>t;
    while (t--){
        int n,m,x,y,ans=0,tot=0;
        cin>>n>>m>>x>>y;
        for (int i=1; i<=n; i++){
            cin>>p[i]>>v[i]>>a[i];
        }for (int i=1; i<=m; i++) cin>>k[i];
        for (int i=1; i<=n; i++){
            if (v[i]<=y){
                if (a[i]<=0) continue;
                int tmp=p[i]+(y*y-v[i]*v[i])/(2*a[i]);
                int l=upper_bound(k+1,k+m+1,tmp)-k,r=m;
                if (l<=r) seg[++tot]={l,r};
            }else{
                if (a[i]>=0){
                    int l=lower_bound(k+1,k+m+1,p[i])-k,r=m;
                    if (l<=r) seg[++tot]={l,r};
                }else{
                    int l=lower_bound(k+1,k+m+1,p[i])-k;
                    int tmp=p[i]+(v[i]*v[i]-y*y+-2*a[i]-1)/(-2*a[i]);
                    int r=lower_bound(k+1,k+m+1,tmp)-k-1;
                    if (l<=r) seg[++tot]={l,r};
                }
            }
        }cout<<tot<<" ";
        sort(seg+1,seg+tot+1);
        for (int i=1; i<=tot;){
            //cout<<seg[i].first<<" "<<seg[i].second<<"\n";
            int R=seg[i].second;
            while (i<=tot&&seg[i].first<=R){
                i++,R=min(R,seg[i].second);
            }ans++;
        }cout<<m-ans<<"\n";
    }return 0;
}

这道题代码纯属细节较多，大样例的测试也较为花时间，写完这道题已经过去 $100$ 分钟了。

之后，我选择了写第三道题目，可以看出，这道题是 DP 题，DP 题要从部分分开始，把复杂度一步一步地优化到最好。

其实，我们发现 $O(n^2)$ 的非常好写，设立 $f_{i,j,0/1}$ 为填到第 $i$ 位，前一个颜色不同的数是 $j$ 的最大分数。

优化到 $O (n)$ 就很难了，我们把中间隔着其他严格位置的两个相邻数对的贡献加进中间的色块贡献中，在统计最大值时使用蚯蚓那道题的方法就可以了。

//Wrote by Timmy in October 26th
//I wish I could have 100 points in this problem
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 200010
int mx[1000010][2],mx2[2];
int dp[N][2],a[N],w[2];
signed main(){
    //freopen("color.in","r",stdin);
    //freopen("color.out","w",stdout);
    int t; cin>>t;
    while (t--){
        memset(mx,-0x3f,sizeof(mx));
        memset(mx2,0,sizeof(mx2));
        int n; cin>>n; w[0]=w[1]=0; a[n+1]=1e6+5;
        for (int i=1; i<=n; i++) cin>>a[i];
        for (int i=1; i<=n; i++){
            for (int j=0; j<2; j++){
                w[j]+=(a[i]==a[i-1])*a[i];
                mx2[j]=max(mx2[j],dp[i-1][j^1]-w[j]);
                mx[a[i-1]][j]=max(mx[a[i-1]][j],dp[i-1][j^1]-w[j]);
                dp[i][j]=max(mx2[j],mx[a[i+1]][j]+a[i+1])+w[j];
            }
        }cout<<max(dp[n][0],dp[n][1])<<"\n";
    }return 0;
}

第四题十分令人作呕，想都没想直接写 $16$ 分的特殊性质 A。

//Wrote by Timmy in October 26th
//I wish I could have 16 points in this problem
#include <bits/stdc++.h>
using namespace std;
#define int long long
int win[200010][20],ans[200010];
char mp[210][210];
int a[200010],c[200010];
signed main(){
    //freopen("arena.in","r",stdin);
    //freopen("arena.out","w",stdout);
    int n,m; cin>>n>>m; int x=ceil(log2(n));
    for (int i=1; i<=n; i++) cin>>a[i];
    for (int i=1; i<=m; i++) cin>>c[i];
    for (int i=1; i<=x; i++) cin>>mp[i]+1;
    int t,v[4]; cin>>t>>v[0]>>v[1]>>v[2]>>v[3];
    for (int i=1; i<=n; i++) a[i]^=v[i%4];
    for (int i=1; i<=n; i++) win[i][0]=i; ans[1]=1;
    for (int j=1; j<=x; j++){
        for (int i=1; i<=n/2; i++){
            int tmp=(mp[j][i]-'0')^1;
            win[i][j]=(a[win[2*i-tmp][j-1]]>=j?win[2*i-tmp][j-1]:win[2*i-1+tmp][j-1]);
        }ans[(1<<j)]=win[1][j];
    }int ansx=0;
    for (int i=1; i<=m; i++) ansx=ansx^(i*ans[c[i]]);
    cout<<ansx; return 0;
}