HRBU 2021暑期训练解题报告阶段三Day1

目录

A - Similar Strings

B - card card card

C - String

D - Complete the Sequence

E - u Calculate e

F - Maximum Subrectangle

G - Producing Snow

A - Similar Strings

题意：

给定字符串A与字符串B，如果有A的子串A'与B的子串B'满足条件：

1. length(A')==length(B')
2. A'与B‘在相同位置上最多有k个字符不同

我们就认为A'与B'棒极了。

现在我想知道A'与B'最长是多长?

思路：

对两个字符串分别进行尺取。

• 不断枚举字符串B的子串B'的开始位置对字符串A进行尺取
• 不断枚举字符串A的子串A'的开始位置对字符串B进行尺取

• 考察点：字符串，尺取，枚举，暴力

代码：

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int ans,k,t;
int len1,len2;

int main(){

    cin>>t;
    while(t--){
        cin>>k;
        cin>>s1;
        cin>>s2;
        ans=-1;
        len1=s1.size(),len2=s2.size();
        for(int i=0;i<len1;i++){
            int l=0,r=0,cnt=0;
            while(i+r<len1&&r<len2){
                if(s1[i+r]!=s2[r])
                    cnt++;
                while(cnt>k){
                    if(s1[i+l]!=s2[l])
                        cnt--;
                    l++;
                }
                ans=max(ans,r-l+1);
                r++;
            }
        }
        for(int i=0;i<len2;i++){
            int l=0,r=0,cnt=0;
            while(r<len1&&i+r<len2){
                if(s1[r]!=s2[i+r])
                    cnt++;
                while(cnt>k){
                    if(s1[l]!=s2[i+l])
                        cnt--;
                    l++;
                }
                ans=max(ans,r-l+1);
                r++;
            }
        }
        cout<<ans<<endl;
    }
}
           

B - card card card

题意：

有一个长度为 n 的扑克牌序列a，当你拿第i张牌的时候有一个惩罚值bi，我们开始从第一张牌开始取牌，只要拿的扑克牌点数之和不小于对应的惩罚值之和，则所拿扑克合法。

求在保证可以拿到的扑克牌点数之和最大的情况下，初始最少要拿几张牌放到序列后面去？

思路：

首先既然需要将部分字符串放置在尾部，干脆存两倍长度（复制一份放在后面）。对序列进行尺取，分别计算(ai - bi)与ai的和，前者用来判断取值结束，后者存储最大值。

• 考察点：尺取，序列和

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+100;
int a[maxn],b[maxn];  ///a[i]:第i张牌的价值  b[i]:第i张牌的惩罚值
int c[maxn];          ///c[i]:第i张牌的纯收益  c[i]=a[i]-b[i]
int main()
{
    int n;
    ios::sync_with_stdio(false);
    while(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]=a[i]-b[i];
        for(int i=n;i<2*n;i++)
            c[i]=a[i%n]-b[i%n];
        int l=0,r=0;
        int sum=0,ans=0,sumc=0,cnt=0;  ///ans：最大价值  sumc：当前收益 sum:当前的价值
        while(l<n){
            while(r<2*n&&sumc+c[r]>=0)
            {
                sumc+=c[r];
                r++;
                sum+=a[r];
            }
            if(sum>ans){
                ans=sum;
                cnt=l;
            }
            sumc-=c[l];
            sum-=c[l];
            l++;
        }
        cout<<cnt<<endl;
    }
}
           

C - String

题意：

给定一个字符串S，求出S有多少个子串满足：

子串S'中不同字母的数量至少有k个。

思路：

对字符串S进行尺取。

当前尺取出的子串S'若满足条件，则以它为开始字符串的子串都满足条件。

• 考察点：尺取，思维，字符串

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+100;
char ss[maxn];
int num[30];

int num_len()
{
    int len=0;
    for(int i=0;i<26;i++)
        if(num[i]) len++;
    return len;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int k;
        scanf("%s",ss);
        scanf("%d",&k);
        memset(num,false,sizeof(num));
        ll ans=0;
        int l=0,r=0,len=strlen(ss);
        while(true){
            while(num_len()<k&&r<len){
                num[ss[r++]-'a']++;
            }
            if(num_len()<k)
                break;
            ans+=len-r+1;
            num[ss[l++]-'a']--;
        }
        printf("%lld\n",ans);
    }
}
           

D - Complete the Sequence

题意：

根据给定的长度为S的序列的规律算出接下来C个元素的值。

思路：

如果数学好的话不难看出这题用到了拉格朗日插值法。

简而言之就是多维差分数组。

解释样例：

原始数据：1 1 1 1 1 1 1 1 1 2 11 56
一阶差分：0 0 0 0 0 0 0 0 1 9 45
二阶差分：0 0 0 0 0 0 0 1 8 36
三阶差分：0 0 0 0 0 0 1 7 28
四阶差分：0 0 0 0 0 1 6 21
五阶差分：0 0 0 0 1 5 15
六阶差分：0 0 0 1 4 10
七阶差分：0 0 1 3 6 
八阶差分：0 1 2 3
九阶差分：1 1 1
      

博主比较笨，懂，但不知道怎么描述。

• 考察点：拉格朗日插值，差分数组

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int num[500][500];
int main()
{
    int t,s,c;
    cin>>t;
    while(t--){
        cin>>s>>c;
        for(int i=0;i<s;i++)
            cin>>num[0][i];
        for(int i=1;i<s;i++){
            for(int j=0;j<s-i;j++)
                num[i][j]=num[i-1][j+1]-num[i-1][j];
        }
        for(int i=1;i<s+c;i++)
            num[s-1][i]=num[s-1][0];  //复制最后一层
        for(int i=s-2;i>=0;i--){
            for(int j=s-i;j<s+c;j++)
                num[i][j]=num[i+1][j-1]+num[i][j-1];  //倒推上一层
        }

        for(int i=0;i<c;i++){
            if(i) cout<<" ";
            cout<<num[0][s+i];
        }
        cout<<endl;
    }
    return 0;
}
           

E - u Calculate e

题意：

对于题目中给定的公式，求出n取值从0到9时e对应的值，并按照规定格式输出。

思路：

没有思路，暴力打表，阿巴阿巴

• 考察点：暴力，枚举

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    printf("n e\n");
    printf("- -----------\n");
    printf("0 1\n");
    printf("1 2\n");
    printf("2 2.5\n");
    printf("3 2.666666667\n");
    printf("4 2.708333333\n");
    printf("5 2.716666667\n");
    printf("6 2.718055556\n");
    printf("7 2.718253968\n");
    printf("8 2.718278770\n");
    printf("9 2.718281526\n");
    return 0;
}
           

F - Maximum Subrectangle

题意：

给定长度为n的序列a与长度为m的序列b，你可以得到一个n*m的矩阵c，满足：

C( i , j )==Ai * Bj

现在找出C矩阵的最大子矩阵使得：

1. 矩阵元素尽可能的多
2. 矩阵和小于等于x

输出这个矩阵的元素个数。

思路：

首先分别对序列a，序列b求前缀和。

然后贪心出当序列a的子串长度为i时，序列a的子序列和的最小值，存储起来。同时贪心出当序列b的子串长度为i时，序列b的子序列和的最小值，存储起来。

接下来就通过两个最小子序列和数组相乘得答案。

• 考察点：前缀和，贪心

代码：

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f
using namespace std;
typedef long long ll;
ll a[2005];
ll b[2005];
ll mina[2005];
ll minb[2005];
int main()
{
    int n,m;
    ll x;
    cin>>n>>m;
    a[0]=b[0]=0;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        a[i]+=a[i-1];
    }
    for(int i=1; i<=m; i++)
    {
        cin>>b[i];
        b[i]+=b[i-1];
    }
    cin>>x;
    memset(mina,inf,sizeof(mina));
    memset(minb,inf,sizeof(minb));
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
        mina[i]=min(mina[i],a[j]-a[j-i]);
    for(int i=1;i<=m;i++)
        for(int j=i;j<=m;j++)
        minb[i]=min(minb[i],b[j]-b[j-i]);
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
    {
        //cout<<i<<" "<<j<<" "<<mina[i]*minb[j]<<endl;
        if(mina[i]*minb[j]<=x){

            ans=max(ans,i*j);
        }
    }
    cout<<ans<<endl;
}
           

G - Producing Snow

题意：

每一天在你家门口会形成不同的雪堆。

每天早上形成高度为ai米的雪堆，晚上会因为温度关系，所有雪堆最多减少bi米。

请给出每天晚上当天融化了多少雪？

思路：

对每天的雪的融化量求前缀和。

对于每次的融化量考虑三种情况：

1. 第i个雪堆高度大于等于融化量
2. 第i个雪堆高度小于融化量
3. 第i个雪堆高度为0

• 考察点：前缀和，思维

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+100;

ll a[maxn],b[maxn],c[maxn];
ll sur[maxn],num[maxn];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    c[0]=0;
    for(int i=1;i<=n;i++){
        cin>>b[i];
        c[i]=c[i-1]+b[i];
    }
    memset(num,0,sizeof(num));
    for(int i=1;i<=n;i++){
        int pos=upper_bound(c+1,c+1+n,a[i]+c[i-1])-c;
        sur[pos]+=a[i]+c[i-1]-c[pos-1];
        num[i]++;
        num[pos]--;
    }
    ll cnt=0;
    for(int i=1;i<=n;i++){
        cnt+=num[i];
        if(i!=1) cout<<" ";
        cout<<sur[i]+cnt*b[i];
    }
    cout<<endl;
}