【比赛报告】牛客NOIP暑期七天营-普及组1 报告

T1

T1难度并不高，只不过是开一个数组存储罢了，水题。
开一个num[]数组，每次遇到一个字符时，把对应的“桶”加一便可以轻松拿到满分。

代码

#include <bits/stdc++.h>
using namespace std;
int num[200];
int main()
{
    string s;
    int len;
    scanf("%d",&len);
    cin>>s;
    for(int i=0;i<len;++i)
        num[s[i]]++;
    for(int i='a';i<='z';++i)
        printf("%d ",num[i]);
    printf("\n");
}

T2

T2照理来说应该是一道模拟的暴力题。
然鹅…… 粗心的作者脑子发昏的写了一段代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    string s;
    scanf("%d%d",&n,&m);
    cin>>s;
    string t,q;
    int len,f,ans=0;
    while(m--)
    {
        ans=0;
        cin>>q;
        len=q.length();
        t=s;
        for(int i=0;i<len;++i)
        {
            f=t.find_first_of(q[i]);
            if(f==-1)
                continue;
            t=t.substr(f);
            ans++;
        }
        printf("%d\n",ans);
    }
}

虽然跑得飞快(好像最慢的点也跑了50ms)。
but 答案错误 30
但这段代码没有考虑一种情况：

5
abcde
aebcd

对于这组数据，答案应该是4，取a,b,c,d；
然而上面的这段程序运行时则会输出2，因为上面的程序会直接取e，而放弃选择后边的b,c,d，但显然，当然是选b,c,d才是正解。
所以…… 让我们快(chui)快(tou)乐(sang)乐(qi)地写模拟吧~~~。

官方题解

对于，直接按题目模拟就好。每次两个指针扫一下就是的了。整个加起来是的复杂度。可以结合代码理解。

官方代码

#include <bits/stdc++.h>
using namespace std;
const int N=10100;
int n,m;
char s[N],t[N];
int main() 
{
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    for(int i = 1; i <= m; ++i) 
    {
        scanf("%s",t+1);
        int cur=1,len=strlen(t+1);
        for(int j=1;j<=n;++j) 
            if(s[j]==t[cur]&&cur<=len) 
                ++cur;
        printf("%d\n", cur-1);
    }
}

T3

天哪！看到题目的第一眼就蒙了。
眼看一点思路都木有，于是，果断把“残缺的std”补全，拿到了10分。
即使是现在，还是有点不理解……，顺便也吐槽一下，官方题解也写得太简单了吧！
即使正常人看了都会蒙圈。

官方题解

对于直接copy代码然后完善一下头文件什么的就行了。
考虑这个是在干什么，其实就是求对于每个位置往前的前大的数的和。
那么对于,直接删掉第三重循环（考虑如果不选这个数，可以直接直接从转移，所以第三重循环完全多余）
对于,用一个数据结构动态维护前大即可。（这里用或者小根堆，都行）
复杂度

官方代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
const int N=1e6+10;
int n,m,a[N];
int sum=0,ans=0;
multiset<int> s;
void inc(int &a, int b) 
{
    if(a>=mod) 
        a-=mod;
    if(b>=mod) 
        b-=mod;
    a+=b;
    if(a>=mod) 
        a-=mod;
    if(a<0) 
        a+=mod;
}
int main() 
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) 
        scanf("%d",&a[i]);
    for(int i=1;i<=m;++i) 
    {
        s.insert(a[i]);
        inc(sum, a[i]);
    }
    inc(ans,sum);
    for(int i=m+1;i<=n;++i) 
    {
        inc(sum,a[i]);
        s.insert(a[i]);
        int t=*s.begin();
        inc(sum,-t);
        s.erase(s.begin());
        inc(ans,sum);
    }
    printf("%d\n",ans);
}

QwQ，完全看不懂在干哈子…… 55555……

T4

第四题画一个表格就知道了。

随机画一个表格，然后选择随便一块：

显然，绿***域的和为。
再选几块比较之后可知：

然后求出两个序列中的最大子串和一乘就是答案。
且慢……这题的数据范围有可能为，明显爆int，不开long long见祖宗啊……

代码

#include <bits/stdc++.h>
using namespace std;
int a[100010],b[100010];
int maxsum(int arr[], int n)
{
    int sum,maxx,i;
    maxx=0,sum=0;
    for(i=1;i<=n;i++)
    {
        sum+=arr[i];
        if(sum>maxx)
            maxx=sum;
        else if(sum<0)
            sum=0;
    }
    return maxx;
}
int minsum(int arr[],int n)
{
    int sum,minn,i;
    minn=0,sum=0;
    for(i=1;i<=n;i++)
    {
        sum+=arr[i];
        if(sum<minn)
            minn=sum;
        else if(sum>0)
            sum=0;
    }
    return minn;
}
int minarr(int arr[],int n)
{
    int ret=99999999;
    for(int i=1;i<=n;++i)
        if(abs(arr[i])<abs(ret))
            ret=arr[i];
    return ret;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int j=1;j<=m;++j)
        scanf("%d",&b[j]);
    int maxa,maxb;
    maxa=maxsum(a,n);
    maxb=maxsum(b,m);
    int mina,minb;
    mina=minsum(a,n);
    minb=minsum(b,m);
    long long ans;
    ans=((long long)(maxa))*((long long)(maxb));
    ans=max(ans,((long long)(mina))*((long long)(minb)));
    if(ans==0)
        ans=minarr(a,n)*minarr(b,m);
    printf("%lld\n",ans);
}