正式赛

A. 送个分吧

暴力求所有子串复杂度接近5e3*5e3*5e3，substr的复杂度是线性的，考虑拼接，如果枚举所有的字符串，取5个最小的放到SET里面比较，大的删了复杂度可能也刚好爆了。

因为K很小，所以太长的字符串永远不需要，只需要暴力枚举长度为1~5的子串就行了，然后取第k个。

也可以直接从最小的地方开始找5个。

#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define all(x) x.begin(),x.end()
#define EX exit(0)
#define fr first
#define se second
#define endl '\n'
using namespace std;
using ll=long long;

void solve(){
    string s;
    int k;
    cin>>s>>k;

    map<string,int>mp;
    per(i,0,s.length()-1){
        mp[s.substr(i)] = 1;
    }

    set<string>st;
    for(auto [str,v]:mp){
        for(int i = 1;i<=str.size();++i){
            string t = str.substr(0,i);
            if(st.count(t))continue;
            k--;
            st.insert(t);
            if(k==0){
                cout<<t;
                return;
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int t=1;
    while(t--)solve();
    return 0;
}

E. 语言学习中

2H<->1X

2X<->1H

add 3H,3X

对于任意位置的X，我们只能把它变成：HH（或者使用免费的add）

所以对于询问中的两个串，能形成本质区别的，只有前面两个等价式，第三个是免费操作，所以没区别。

那么我们把串全部变成H，显然如果变成H之后两个串的差值是3的倍数（可以使用免费操作），那就有解。

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
string h,x;
int preh[100001],prex[100001],q;
int main(){
    cin>>h>>x;
    for (int i=1;i<=h.size();++i){
        preh[i]=preh[i-1];
        if(h[i-1]=='H')preh[i]++;
    }
    for (int i=1;i<=x.size();++i){
        prex[i]=prex[i-1];
        if(x[i-1]=='H')prex[i]++;
    }
    cin>>q;
    for (int i=1;i<=q;++i){
        int l1,r1,l2,r2,len1,len2,h1,h2;
        cin>>l1>>r1>>l2>>r2;
        len1=r1-l1+1,len2=r2-l2+1;
        h1=preh[r1]-preh[l1-1];
        h2=prex[r2]-prex[l2-1];
        len1-=h1,len2-=h2;
        h1+=len1*2,h2+=len2*2;
        if(abs(h1-h2)%3==0){
            cout<<"YES"<<endl;
        }
        else cout<<"NO"<<endl;
    }
    return 0;
}

G. 随机汉堡店

这里题目描述其实有点问题，至少包含 p 个食材，而不是至少包含 p 个不同的食材，所以这道题生菜-生菜 汉堡是合理的，不会被投诉（此处歧义）。

如果贪心，每次压缩最前面和最后面的，那会漏情况。

比如：1 1 2 1 2。这样最后一个2就压不掉了，所以这道题需要动态考虑，每个点到底和谁压缩。

那就直接动态规划。

定义 dp[i] 为使用前 i 个食材可以组成的最大美味总和。

如果不使用第 i 个，显然 dp[i]=dp[i-1]

如果使用第 i 个，显然从 1~i-1 里面找到食材和 i 一样的，压缩在一起，取最大的那个。

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,k,p,t[1000001],d[1000001],dp[1000001],prefix[1000001];
vector<ll>a[1000001];
int main(){
    cin>>n>>k>>p;
    for (ll i=1;i<=n;++i)scanf("%lld",&t[i]),a[t[i]].push_back(i);
    for (int i=1;i<=n;++i)scanf("%lld",&d[i]),prefix[i]=prefix[i-1]+d[i];
    for (ll i=1;i<=n;++i){
        dp[i]=dp[i-1];
        for(auto j:a[t[i]]){
            if(j==i)break;
            if(i-j+1>=p){
                dp[i]=max(dp[i],dp[j-1]+prefix[i]-prefix[j-1]);
            }
        }
    }
    cout<<dp[n];
    return 0;
}

注意这道题输入比较多，如果没有ios的cin会超时。

因为提交了一下就过了，所以不需要再优化内部循环的取最大值。

tip：优化具体看评论区，单调队列来优化是错的。

H. 密码是多少？

模拟签到。

J. 开着我的小新车

这里给个思路，没有正式做出来，题面好多错误。

题意槽点（可以跳过往下拉看题目思路）

1、题目保证 xi-xi-1<=L，结果样例里面就出现了一个xi-xi-1>L的情况，然而解释却是不会影响做法。

如果有人使用ST表倍增这种全局考虑的算法，那这道题就爆了，所以这个保证了一个寂寞。。

2、题目说新车续航最多2L，超过L就要休息一天，不打算压榨新车，要爱护汽车来开，啥意思，不能用2L？开了2L就是压榨了吗？。。

根据样例得出结论1 3 6 13 15 18 19 29，L=10，如果第一次开2L，我们可以到达19，休息一天，然后开L，一共三天就能到达目的地，然而样例给的答案是4天，所以这道题不能使用2L，也就是使用L才是保护电池的做法。

3、车只能停在x序列上的具体点上，不能停在野区。

如：1 3 6 13 15 18 19 29，L=10，最右边和最左边差值28，如果可以停在非x序列的位置上，那么依旧是3天就可以完成，1+30=31>29，第四天就回家了，花费3天，所以得出结论，车只能停在x序列的点上。

思路分析

由于比赛结束了不能提交，补题可能要后续压力主办方搞渠道弄开。

因为每个点开L之后经过的点数量不一样，所以我们预处理一下。

定义 dp[i] 为，在 i 点往右开 L 距离能到达的下一个点。

然后我们就可以根据dp写出一个暴力往后跳的代码

然而这样复杂度可能会被卡成n*n，所以想办法跳的时候智能一点，或者说是否有些步骤重复跳了。

可以发现假如1->3->5->7，这样访问的时候 l 从 1,3,5,7任意一个都可以在这条链上二分 r 的位置来找到答案。

如果2->3 链到了原来的链上，那么后面肯定也是一样的，即2->3->5->7

所以 2 开头的在这上面二分查找几个，而我们修改链的操作是O（1）

如果后面都不一样 2->4->6，也不会影响总复杂度，可以发现每个元素最多被选中一次。

考虑对询问的 l，r以 l 进行升序排序，然后构造合法的链，或者修改即可。

总复杂度nlogn，应该可以通过。

（不能补题就放个思路算了）

暴力代码参考

#include <bits/stdc++.h>
#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define all(x) x.begin(),x.end()
#define EX exit(0)
#define fr first
#define se second
#define endl '\n'
using namespace std;
using ll=long long;

void solve(){
    int n;
    cin>>n;

    int x[n+1];
    per(i,1,n)cin>>x[i];

    int L;
    cin>>L;

    int dp[n+1];
    per(i,1,n){
        //当前在x[i]
        //找到x[i]+L能到达的最远距离（用二分，不然复杂度爆了）

        int val=x[i]+L;
        int l=i+1,r=n;
        while(l<r){
            int mid=(l+r)>>1;
            if(x[mid]>val){//无法到达  mid舍弃
                r=mid-1;
            }else l=mid;//则l为最终答案

            if(l==r-1){//极限只会取左边,再判断一下r是否可行就退出
                if(x[r]<=val)l=r;
                break;
            }
        }
        //l就是能达到的最远距离
        dp[i]=l;
    }

    int q;
    cin>>q;

    per(i,1,q){
        int l,r;
        cin>>l>>r;
        if(l>r)swap(l,r);

        int now=l;
        int res=1;
        while(dp[now]<r)now=dp[now],res++;
        cout<<res<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int t=1;
    while(t--)solve();
    return 0;
}

测试赛

B. IMissYou!

求和输出就行了，字符串容易看走眼打错，直接复制题目的。

#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define all(x) x.begin(),x.end()
#define EX exit(0)
#define fr first
#define se second
#define endl '\n'
using namespace std;
using ll=long long;

void solve(){
    int a[8];
    a[0]=0;
    per(i,1,7)cin>>a[i],a[0]+=a[i];

    if(a[0]>0){
        cout<<"IMissYou!"<<endl<<a[0];
    }else{
        cout<<"OvO";
    }
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int t=1;
    while(t--)solve();
    return 0;
}

A. Jargonless

累计方案数很容易想到，对于S中所有存在的T，均取头和尾的位置相乘，就是当前合法T的所有方案。

但是这样会重复计算，比如头去掉0个和尾去掉0个，下一个也会去掉头0个和尾0个。

给出一个显然的结论：

假如第一个合法的T在S中的位置是，L~R，那么下一个合法T的位置，一定从L+1开始，且一定没有R-1。

所以当头移除1~3位置对上4~5的时候

下一个字符串移除1~3位置也一定只能对上4~5的位置，不会有1~3对上3~5，所以前一个位置的L就不需要了，我们只需要累计当前newL~L之间的新长度即可。

那么考虑移动L的左端点，求差值即可去除重复。

#include <bits/stdc++.h>
#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define all(x) x.begin(),x.end()
#define EX exit(0)
#define fr first
#define se second
#define endl '\n'
using namespace std;
using ll=long long;

void solve(){
    string s,t;
    cin>>s>>t;
    s="0"+s;
    t="0"+t;

    //    123
    //    i j

    int l=0,ans=0;
    per(i,1,s.length()-1){
        if(s[i]==t[1]){
            int now=2;
            per(j,i+1,s.length()-1){
                if(s[j]==t[now])now++;
                if(now==t.length()){
                    ans+=(i-l)*(s.length()-1-j+1);
                    l=i;
                    break;
                }
            }
        }
    }

    cout<<ans;
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int t=1;
    while(t--)solve();
    return 0;
}