2024年ACM新生训练赛（D-F）

2024-09-28

字数统计: 1.3k | 阅读时长≈ 6 分钟

本大二老蒟蒻的第一篇题解，如有错误或表述不当之处请联系QQ3488643420，请多多包涵！

本次校内新生赛，俺老黄瓜刷绿漆，与各级各院高手同台竞技，不胜荣幸！

前六题基本上是语法题，难度不大，没用到什么复杂的算法。

最后一个多小时对着G坐牢太过难受，还是要多多提升自己，不然就要被后浪狠狠拍在沙滩上了T^T。

D

#include <bits/stdc++.h>
#define fast                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(nullptr);
using namespace std;
typedef long long ll;
ll l,r,ans;
int main()
{
    fast;
    ans=0;
    cin>>l>>r;
    if(l<=2) l=3;
    if(l%2==0) l--;
    if(r%2==0) r++;
    ans=(r-l)/2;
    //cout<<ans;
    //if(l<=2) ans--;
    if(r<=2) ans=0;
    cout<<ans;
    return 0;
}

本题与哥德巴赫猜想有关，任何大于2的偶数都能够写成两个质数相加的形式，虽然尚未被证明，但也没被证伪，我们可以运用该猜想。

要注意特判一下范围是否包括2，l、r都要特判。（本蒟蒻没判断r，WA了好几发QAQ)

E

#include <bits/stdc++.h>
#define fast                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(nullptr);
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int n;
void solve()
{
    cin >> n;
    if (n <= 6)
    {
        cout << "NO\n";
        return;
    }
    n -= 1;
    int x = 2;
    while (!(x % 3 && (n - x) % 3))
    {
        x++;
        if (x == n - x||n-x==1)
        {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n"
         << 1 << ' ' << x << ' ' << n - x << '\n';
}
int main()
{
    fast;
    int _ = 1;
    cin >> _;
    while (_--)
        solve();
    return 0;
}

注意三个数不能相同

F

#include <bits/stdc++.h>
#define fast                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(nullptr);
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int n,k;
string s;
void solve()
{
    string t;
    cin >> t;
    int len = t.size();
    if(len>s.size())
    {
        cout<<"NO\n";
        return;
    }
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] != t[i % len])
            {
                cout << "NO\n";
                return;
            }
        }
    cout << "YES\n";
}
int main()
{
    fast;
    cin>>n>>k;
    cin>>s;
    while (k--)
    {
        solve();
    }
    
    return 0;
}

无回溯的子串匹配，用不到KMP

注意特判一下t的长度大于s的情况。

G

//=========================================================

// #include <bits/stdc++.h>
// #define fast                          \
//     std::ios::sync_with_stdio(false); \
//     std::cin.tie(nullptr);
// using namespace std;
// typedef long long ll;
// const int N = 2e5 + 10;
// ll n,k;
// ll x[N],a[N],b[N];
// int main()
// {
//     fast;
//     cin>>n>>k;
//     for(int i=1;i<=n;i++) cin>>x[i];
//     for(int i=1;i<=n;i++) cin>>b[i];
//     //k%=(n-1);
//     while(k--)
//     {
//         for(int i=1;i<=n;i++) a[i]=b[i];
//         for(int i=1;i<=n;i++) b[i]=a[x[i]];
//         // for (int i = 1; i <= n; i++)
//         //     cout << b[i] << ' ';
//         // cout<<'\n';
//     }
//     for (int i = 1; i <= n; i++) cout<<b[i]<<' ';
//     return 0;
// }

//=========================================================

// #include <bits/stdc++.h>
// #define fast                          \
//     std::ios::sync_with_stdio(false); \
//     std::cin.tie(nullptr);
// using namespace std;
// typedef long long ll;
// const int N = 2e5 + 10;
// ll n,k;
// ll x[N],a[N],b[N];
// int main()
// {
//     fast;
//     cin>>n>>k;
//     for(int i=1;i<=n;i++) cin>>x[i];
//     for(int i=1;i<=n;i++) cin>>b[i];
//     while(k--)
//     {
//         for(int i=1;i<=n;i++) x[i]=x[x[i]];
//     }
//     for(int i=1;i<=n;i++) cout<<b[x[i]]<<' ';
//     return 0;
// }

// #include <bits/stdc++.h>
// #define fast                          \
//     std::ios::sync_with_stdio(false); \
//     std::cin.tie(nullptr);
// using namespace std;
// typedef long long ll;
// const int N = 2e5 + 10;
// int n;
// ll k;
// int x[N],y[N],z[N],b[N];
// int main()
// {
//     fast;
//     cin >> n >> k;
//     for (int i = 1; i <= n; i++)
//         cin >> x[i],z[i]=x[i];
//     for (int i = 1; i <= n; i++)
//         cin >> b[i];
//     k %= (n - 1);
//     for(int i=1;i<k;i++)
//     {
//         for(int j=1;j<=n;j++)
//         {
//             //if(j>1) z[j]=y[j];
//             y[j]=x[x[j]];
//         }
//         // for (int j = 1; j <= n; j++)
//         //     cout << b[x[i][j]] << ' ';
//         // cout<<'\n';
//     }
//     for (int i = 1; i <= n; i++)
//         cout << b[y[i]] << ' ';
//     return 0;
// }

//=========================================================
// #include <bits/stdc++.h>
// #define fast                          \
//     std::ios::sync_with_stdio(false); \
//     std::cin.tie(nullptr);
// using namespace std;
// typedef long long ll;
// const int N = 5 + 10;
// int n;
// ll k;
// int x[N], y[N],t[N], b[N];
// int main()
// {
//     fast;
//     cin >> n >> k;
//     for (int i = 1; i <= n; i++)
//         cin >> x[i],y[i]=x[i];
//     for (int i = 1; i <= n; i++)
//         cin >> b[i];
//     k %= (n - 1);
//     for (int i = 1; i < k; i++)
//     {
//         for (int j = 1; j <= n; j++)
//         {
//             t[j]=y[j];
//             y[j]=x[x[j]];
//             x[j]=t[j];
//         }
//         // for (int j = 1; j <= n; j++)
//         //     cout << b[x[i][j]] << ' ';
//         // cout<<'\n';
//     }
//     for (int i = 1; i <= n; i++)
//         cout << b[y[i]] << ' ';
//     return 0;
// }

史山也贴出来吧，毕竟也做了一个多小时（虽然是无用功）

做出来俩种方法，一种超时间限制，一种超空间限制。

应该继续考虑优化存储方式，减少空间占用。