CSP 2024 游寄

leozhao123 · 2024-10-27 06:49:42 · 生活·游记

: )

2024.10.26，8:30\~12:00 / 14:30\~18:30，杭州师范大学下沙校区。

估分

$S=45+40+0+0=85$。 **Update 2025.2.10** J 组 T3 多送了 10pts，所以实际 $J=280$。（别问为什么时隔 3.5 个月（。。。 # 10.17 做了 2022 [解密](/problem/P8814)。二分答案，一直卡 10pts。不会调。 # 10.19 上午做 2021 2022 T2。解密重写了一遍，以为能过，结果还 10pts。和 std 对了一下，发现没判输出顺序。有人还用解方程做的。下午讲了长达 $80$ 页的 PDF 防止爆 0。水了一道高精。离开前十分钟教练突然叫我们做下 [3-1](/problem/P9304)，说今年可能考树。 # 10.20 上午打了梦熊模拟赛，$90+60+0+0=150$。T2 做了 $\mathcal{O}(n\times\min\{m_i\})$ 偏分。补 T1。下午还要上课。。。晚上做了一道水紫 [[ICPC2020 Nanjing R]](/problem/P9622)。 # 10.24 抽空看了图论相关，回顾一下两种遍历，[查找文献](/problem/P5318) 一遍过。 # 10.26 上午 505 机房 A39，看见同队。半小时解 T1 T2。想 T3。想出 70pts。写。想满分。写。没调出来。出来估分有点虚高（？）。下午 505 机房 A37。写 T1 45pts。看 T2，不会。看 T3，写。发现想简单了。回看 T2，写 20pts。又写 20pts。然后想不出来了，开始坐牢。 # 解法记录 ## J-T1 $\texttt{poker}

略。

J-T2 \texttt{explore}

看到数据 n,m\le10^3,T\le5，直接模拟。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e3+2;
ll t,n,m,k,x,y,d,ans,tpx,tpy;
char mp[N][N];
bitset<N>vst[N];
int main() {
    cin>>t;
    while(t--) {
        for(int i=0;i<=n;++i) vst[i].reset();
        memset(mp,0,sizeof mp);//初始化!!
        cin>>n>>m>>k>>x>>y>>d;
        ans=1;
        vst[x][y]=1;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j) cin>>mp[i][j];
        while(k--) {
            if(d==0) tpx=x,tpy=y+1;
            if(d==1) tpx=x+1,tpy=y;
            if(d==2) tpx=x,tpy=y-1;
            if(d==3) tpx=x-1,tpy=y;
            if(tpx>=1&&tpx<=n&&tpy>=1&&tpy<=m&&mp[tpx][tpy]=='.') {
                x=tpx,y=tpy;
                if(!vst[x][y]) vst[x][y]=1,++ans;
            }
            else d=(d+1)%4;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

J-T3 \texttt{sticks}

TestPoint 1

**部分代码**： ```cpp const int mp[25]={ -1,-1,1,7,4,2,6,8,10,18, // 0 1 2 3 4 5 6 7 8 9 22,20,28,68,88,108,188,200,208,288,688 // 10 11 12 13 14 15 16 17 18 19 20 }; ``` ### TestPoint 2 $n\le50$，打表有点困难，直接放弃。 ### TestPoint 3~5 $n=7k$。想到要使位数少，就要让每一位用掉尽量多的木棍。结合性质，不难想到（？）输出 $k$ 个 $8$ 即可。 **部分代码**： ```cpp void s1(ll n) { n/=7; while(n--) cout<<8; } ``` ### TestPoint 6~8 $n=7k+1$。与上面思想相似。若低位全是 $8$，则会多出 $1$ 根木棍，所以必须将其中一个 $8$ 拆开。想到可以拆成 $\textbf0$ 和 $\textbf1$ **根木棍**，于是输出 $10$ 和 $k-1$ 个 $8$ 即可。 **部分代码**： ```cpp void s2(ll n) { cout<<"10"; n=n/7-1; while(n--) cout<<8; } ``` ### TestPoint 9~10 根据打表时技巧，想到 DFS，但有玄学错误，复杂度也很高。 ### 完整代码 ```cpp #include<bits/stdc++.h> using namespace std; using ll=long long; const int mp[25]={ -1,-1,1,7,4,2,6,8,10,18, // 0 1 2 3 4 5 6 7 8 9 22,20,28,68,88,108,188,200,208,288,688 // 10 11 12 13 14 15 16 17 18 19 20 }; void s1(ll n) { n/=7; while(n--) cout<<8; } void s2(ll n) { cout<<"10"; n=n/7-1; while(n--) cout<<8; } int main() { ll t,n; cin>>t; while(t--) { cin>>n; if(n<=20) cout<<mp[n]; //实际上应该考虑 n=0,1 的情况，但它被包含在 n<=20 里了 else if(n%7==0) s1(n); else if(n%7==1) s2(n); cout<<'\n'; } return 0; } ``` ## J-T4 $\texttt{chain}

想完 T3 只剩一个小时，脑子也没了。最后 10 分钟想出来 5 分解法，但写错了。

S-T1 \texttt{duel}

贪心，考虑每次让 r_i 严格次小的与最小的决斗。

复杂度 \mathcal{O}(n^2)，只能过 9 个点。赛后才发现有 r_i\le2 的性质没用上。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+2;
ll n,r[N],ans;
int main() {
    cin>>n;
    ans=n;
    for(int i=0;i<n;++i) cin>>r[i];
    sort(r,r+n);
    for(int i=1;i<n;++i) {
        int j=i-1;
        for(;j>=0;--j)
            if(r[j]<r[i]&&r[j]!=0) break;
        if(j!=-1) r[j]=0,--ans;
    }
    cout<<ans;
    return 0;
}

S-T2 \texttt{detect}

为方便表述，记每组数据的 2 个输出内容分别为 ans_0,ans_1。
匀加速运动：当一辆车的初速度为 v_0、加速度 a \neq 0，做匀加速运动，则当它的位移（即行驶路程）为 s 时，这辆车的瞬时速度为 \sqrt{v_0^2+2\times a\times s}。
TestPoint 3~4

意味着所有车都匀速，超速的车不管在哪里遇到测速仪都会被判为超速。因此 ans_0 即为所有 d_i\le p_m 且 v_i>V 的车的数量。

对 ans_1，有 2 种情况：

当 ans_0=0 时，即没有车被判为超速，则所有测速仪都可关闭，ans_1=m。
当 ans_0\ne0 时，即有车被判为超速，则除了第 m 个测速仪以外的都可关闭，ans_1=m-1。

部分代码：

void s1() {
    ll p;
    for(int i=0;i<m;++i) cin>>p;
    for(int i=0;i<n;++i)
        if(d[i]<=p&&v[i]>V) ++ans;
    if(m==0) ans=ans1=0;
    else if(ans==0) ans1=m;
    else ans1=m-1;
}

TestPoint 5~6

意味着所有车都加速，则在 $[p_1,p_m]$ 会超速的车在 $p_m$ **一定会被判为超速**。因此 $ans_0$ 即为所有 $d_i\le p_m$ 且 $\sqrt{v_i^2+2\times a_i\times (p_m-d_i)}>V$ 的车的数量。对 $ans_1$，有 $2$ 种情况同上文。 **部分代码**： ```cpp void s2() { ll p; for(int i=0;i<m;++i) cin>>p; for(int i=0;i<n;++i) if(d[i]<=p&&sqrtl(1.0*v[i]*v[i]+2.0*a[i]*(p-d[i]))>1.0*V) ++ans; if(m==0) ans=ans1=0; else if(ans==0) ans1=m; else ans1=m-1; } ``` ### TestPoint 7~8 $a_i<0$。想用相似的办法，但发现 $ans_1$ 不再满足 $2$ 种情况的性质。 ### TestPoint 1\~2,9\~10 可以将 $3$ 个特殊性质的代码糅合一下即可。这部分没做，因为性质 C 没想出来。 ### 完整代码 ```cpp #include<bits/stdc++.h> using namespace std; using ll=long long; const int N=1e6+2; ll t,n,m,L,V,d[N],v[N],a[N],ans,ans1; void s1() { ll p; for(int i=0;i<m;++i) cin>>p; for(int i=0;i<n;++i) if(d[i]<=p&&v[i]>V) ++ans; if(m==0) ans=ans1=0; else if(ans==0) ans1=m; else ans1=m-1; } void s2() { ll p; for(int i=0;i<m;++i) cin>>p; for(int i=0;i<n;++i) if(d[i]<=p&&sqrtl(1.0*v[i]*v[i]+2.0*a[i]*(p-d[i]))>1.0*V) ++ans; if(m==0) ans=ans1=0; else if(ans==0) ans1=m; else ans1=m-1; } int main() { cin>>t; while(t--) { cin>>n>>m>>L>>V; ans=ans1=0; for(int i=0;i<n;++i) cin>>d[i]>>v[i]>>a[i]; if(a[0]==0) s1(); if(a[0]>0) s2(); cout<<ans<<' '<<ans1<<'\n'; } return 0; } ``` ## S-T3 $\texttt{color}

开始题目读错了，我以为大概是这样：

如果 A_i 左侧没有与其同色的数，则令 C_i = 0。
否则，令 C_i = A_i。

于是暴力判断即可。后来发现错误，但也没想出来解法。

S-T4 \texttt{arena}

没写。赛后看洛谷难度，果真是黑题。