2023JSCPC江苏省赛

2023江苏省赛

Dashboard - 2023 Jiangsu Collegiate Programming Contest, 2023 National Invitational of CCPC (Hunan), The 13th Xiangtan Collegiate Programming Contest - Codeforces

I - Elevator

void solve()
{
    cin>>n>>m;
    cout<<n-m+1<<endl;
}

H - Neil's Machine

/*
 * @Author     : Danc1ng
 * @Date       : 2024-05-07 19:17:01
 * @FilePath   : H - Neil's Machine
 * @Origin     :
 * @Description:
 * @Solution   :
 */
#include <bits/stdc++.h>
#define bug cout << "***************" << endl
#define look(x) cout << #x << " -> " << x << endl
#define endl '\n'
#define int long long
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;

using namespace std;
typedef pair<int, int> PII;

constexpr int N = 2e5 + 10 , INF = 2e9;

int n;
char a[N],b[N];
int c[N];

void solve()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];

    for(int i=0;i<n;i++)
    {
        c[i]=((b[i]-a[i])%26+26)%26;
        // cout<<c[i]<<" \n"[i==n-1];
    }

    int ans=0;
    bool flag=false;
    int l=n;
    for(int i=0;i<n;i++)
    {
        if(c[i]!=0)
        {
            l=i;
            break;
        }
    }

    if(l==n)
    {
        cout<<0<<endl;
        return;
    }

    int tp=0;
    for(int i=l;i<n;i++)
    {
        ans++;
        tp=(tp+c[i])%26;
        while(c[i+1]==c[i]&&i+1<n) i++;
    }

    cout<<ans<<endl;
}


signed main()
{
    //freopen("check.in","r",stdin);
    //freopen("check.out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    solve();



    return 0;
}

J - Similarity (Easy Version)

/*
 * @Author     : Danc1ng
 * @Date       : 2024-05-07 19:22:16
 * @FilePath   : J - Similarity (Easy Version)
 * @Origin     :
 * @Description:
 * @Solution   :
 */
#include <bits/stdc++.h>
#define bug cout << "***************" << endl
#define look(x) cout << #x << " -> " << x << endl
#define endl '\n'
#define int long long
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;

using namespace std;
typedef pair<int, int> PII;

constexpr int N = 2e5 + 10 , INF = 2e9;

int n;
string s[N];

int calc(string a,string b)
{
    int len1=a.size(),len2=b.size();
    vector<vector<int>> dp(len1+1,vector<int>(len2+1));

    for(int i=0;i<len1;i++)
        for(int j=0;j<len2;j++)
            dp[i][j]=0;


    int ans=0;
    for(int i=1;i<=len1;i++)
        for(int j=1;j<=len2;j++)
        {
            if(a[i-1]==b[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
                ans=max(ans,dp[i][j]);
            }
            else dp[i][j]=0;
        }

    return ans;
}

void solve()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
    }

    int ans=0;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            ans=max(ans,calc(s[i],s[j]));
        }
    }

    cout<<ans<<endl;
}


signed main()
{
    //freopen("check.in","r",stdin);
    //freopen("check.out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T;
    //T=1;
    cin>>T;
    while(T--)
    {
      solve();
    }



    return 0;
}

A - Today's Word

思路：

考虑当\(Sk\)长度超过\(2m\)时，再进行一次操作后，其长度为$ m\(的后缀只会进行\)next(·)\(变换，把这个长为\)m\(的后缀的 每个字符变成下一个字符。因此考虑暴力将\)S_0$按构造方式 操作，求出一个长度大于\(2m\)的\(S_k\)，取\(S_k\)长度为\(m\)的后 缀进行\(next(·)\)变换即可。 容易观察到\(next(·)\)变换操作的循环节为26，因此只需对这个后缀进行\((10^{100}−k)mod26\)次\(next(·)\)变换即可，也就是将这个长为m的后缀中的每个字母变为它后面第 \((10^{100}−k)mod26\)个字母，经过简单计算即可求出

/*
 * @Author     : Danc1ng
 * @Date       : 2024-05-07 19:45:12
 * @FilePath   : A - Today's Word
 * @Origin     :
 * @Description:
 * @Solution   :
 */
#include <bits/stdc++.h>
#define bug cout << "***************" << endl
#define look(x) cout << #x << " -> " << x << endl
#define endl '\n'
#define int long long
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;

using namespace std;
typedef pair<int, int> PII;

constexpr int N = 100 + 10 , INF = 2e9,mod=26;

int n,m;
string s;

string next(string s,int k)
{
    for(int i=0;i<s.size();i++)
    {
        s[i]=((s[i]-'a')+k)%26+'a';
    }
    return s;
}

string change(string s)
{
    int len=s.size()/2;
    string res=s.substr(0,len);
    res+=s;
    res+=next(s.substr(len),1);
    return res;
}

void solve()
{
    cin>>n>>m;
    cin>>s;

    int cur=0;
    while(s.size()<m*2)
    {
        cur++;
        s=change(s);
    }

    s=next(s,((16-cur)%26+26)%26);
    cout<<s.substr(s.size()-m)<<endl;
}


signed main()
{
    //freopen("check.in","r",stdin);
    //freopen("check.out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    solve();

    return 0;
}

F - Timaeus

题意：

你有A个原料，每B个合成一个产品。每一次合成你可以选择下列两种buff的任意一种：

1.P%的概率合成双倍产物

2.Q%的概率返还一个原料 求期望最多合成多少产物。

思路：

设\(dp[i]\)表示还剩下i个原料时的最大期望，则\(dp[i]=max\{P\times(dp[i-B]+2)+(1-P)\times(dp[i-B]+1),Q\times(dp[i-B+1]+1)+(1-Q)\times(dp[i-B]+1)\)

当\(B=1\)时选择第二种buff是最优的，有\(Q%\)的概率不需要花费，也就是\(1-Q%\)的概率消耗一个原料，

/*
 * @Author     : Danc1ng
 * @Date       : 2024-05-07 20:48:38
 * @FilePath   : F - Timaeus
 * @Origin     : https://codeforces.com/gym/104396/problem/F
 * @Description:
 * @Solution   :
 */
#include <bits/stdc++.h>
#define bug cout << "***************" << endl
#define look(x) cout << #x << " -> " << x << endl
#define endl '\n'
#define int long long
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;

using namespace std;
typedef pair<int, int> PII;

constexpr int N = 1e6 + 10 , INF = 2e9;

int a,b;
double p,q;
double dp[N];

void solve()
{
    cin>>a>>b>>p>>q;

    p/=100,q/=100;
    for(int i=b;i<=a;i++)
    {
        dp[i]=max(p*(dp[i-b]+2)+(1-p)*(dp[i-b]+1),q*(dp[i-b+1]+1)+(1-q)*(dp[i-b]+1));
    }

    double ans;
    if(b==1) ans=max(a*1.0/(1-q),dp[a]);
    else ans=dp[a];

    cout<<fixed<<setprecision(12)<<ans<<endl;

}


signed main()
{
    //freopen("check.in","r",stdin);
    //freopen("check.out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    solve();

    return 0;
}

K - Similarity (Hard Version)

题意：

构造\(n\)个不同的长度为\(k\)的只由小写字符组成的字符串， 使得其两两之间最长公共子串的最大值等于\(m\)。

思路：

• \(m=0,n>26\)时，无解
• \(m\neq 0,m>=k\)时，无解

\(m=0\)时，直接输出长度为\(k\)的只由第\(i\)个字母组成的小写字母组成的串即可。

\(m\neq0\)时，构造出\(a_1a_2a_1a_2a_1a_2a_1a_2···\)的字符串

那么对于这种类型的串一共有\(\frac{25×(25−1)}2 =300\)种，两两之 间的最长公共子串长度均不超过1。

那么答案构造即可为，取上述形式的串前\(k−m+1\)位，拼上\(m−1\)位z即可得到满足题目要求的\(n\)个串。

#include <bits/stdc++.h>
#define bug cout << "***************" << endl
#define look(x) cout << #x << " -> " << x << endl
#define endl '\n'
#define int long long
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;

using namespace std;
typedef pair<int, int> PII;

constexpr int N = 300 + 10 , INF = 2e9;

int n,m,k;
vector<pair<char,char>> vi;

void print(char c)
{
    cout<<c;
}

void print_1()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
            print(i+'a'-1);
        cout<<endl;
    }
}

void print_2()
{
    for(int i=1;i<=k;i++) print('a');
        cout<<endl;
        for(int i=1;i<=k;i++)
            i<=m?print('a'):print('b');
        cout<<endl;

        for(int i='a';i<='z';i++)
            for(int j=i+1;j<='z';j++)
            {
                vi.push_back({i,j});
            }

        for(int i=3;i<=n;i++)
        {
            char c1=vi[i-2].first,c2=vi[i-2].second;
            for(int j=1;j<=k;j++)
            {
                if(j&1) print(c1);
                else print(c2);
            }
            cout<<endl;
        }
}

void solve()
{
    cin>>n>>m>>k;

    if(m>=k||m==0&&n>26)
        cout<<"No\n";
    else
    {
        cout<<"Yes\n";
        if(m==0) print_1();
        else print_2();
    }

}


signed main()
{
    //freopen("check.in","r",stdin);
    //freopen("check.out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    solve();

    return 0;
}