竞赛讨论区 > 题解| 2021牛客OI赛前集训营-普及组(第四场)部分题解

题解| 2021牛客OI赛前集训营-普及组(第四场)部分题解

头像
昴星团
发布于 2021-10-13 00:39:28 APP内打开
赞 1 | 收藏 0 | 回复0 | 浏览386


思路:记录叫的次数和分别回应的次数, cnt 统计几次叫满(都回应了),k 统计几次至少回应了一次,对比即可。

代码:

#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
#include<bitset>
using namespace std;
const int N=1e5+5;
int n,m,T,cnt,a[N],b[N],v[N],num[N];
int main(){
    scanf("%d",&T);
    while(T--){
        memset(num,0,sizeof(num));
        memset(v,0,sizeof(v));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
            ++num[a[i]];//num[a[i]]:该语言牛牛叫了多少次
        }
        for(int i=1;i<=n;++i){
            scanf("%d",&b[i]);
            if(b[i]==1) ++v[a[i]];//v[a[i]]:被回应的次数
        }
        int dire=0,k=0,cnt=0;
        for(int i=1;i<=m;++i)
            if(v[i]>0&&num[i]>0){
                ++k;//该种语言至少被回应了一次
                if(num[i]==v[i]) ++cnt,dire=i;//对该种语言每次都做出了回应
            }
        if(k>=2) printf("^v^\n");//猫对≥2种语言的叫声做出了回应
        else if(k==0) printf(">-<\n");//猫根本就不回应牛牛的任意一次叫声
        else {//对1种语言做出过回应
            if(cnt>0) printf("%d\n",dire);//对该种语言的每次叫声都做出回应
            else printf("^v^\n");//没有对每次该语言的叫声做出回应
        }
    }
    return 0;
}


B题:double u (  B-double u_2021牛客OI赛前集训营-普及组(第四场) (nowcoder.com) )

思路:先把所有"w""m"扩展为"uu""nn",将长度逐渐最大化,若仍然未枚举到目标长度,再进行合并来缩短长度。可以用链表(STL:list)实现,代码逻辑性更强。

代码:

#include<iostream>
#include<cstring>
#include<list>
using namespace std;
int n,T,l,flag;
string temp;
int main() {
    cin>>T;
    while(T--) {
        cin>>n>>temp;
        list<char> t;
        for(int i=0; i<temp.size(); ++i) t.push_back(temp[i]);
        l=t.size(),flag=0;
        for(auto i=t.begin(); i!=t.end(); )
            if((*i)=='w'||(*i)=='m') {
                char x=((*i)=='w'?'u':'n');
                i=t.insert(t.insert(t.erase(i),x),x);
                ++i,++i,++l;
                if(l==n) {
                    flag=1;
                    break;
                }
            } else ++i;
        if(!flag)
            for(auto i=t.begin(); i!=t.end();) {
                auto p=i;
                ++p;
                if(p!=t.end()&&(((*i)=='u'&&(*p)=='u')||((*i)=='n'&&(*p)=='n'))) {
                    char x=((*i)=='u'?'w':'m');
                    i=t.insert(t.erase(t.erase(i)),x);
                    ++i,--l;
                    if(l==n) break;
                } else ++i;
            }
        for(auto i=t.begin(); i!=t.end(); ++i) cout<<(*i);
        cout<<'\n';
    }
    return 0;
}



解析:

  1. O(n²):暴力

很容易联想到完全背包,但又有些许不同。因为每次放的时候要看目前总重量,我们就记为 j ;然后要再选一个物品,这个物品就记作 i ;即 F[j] 意味着总重量为 j 时的方案数,且下面要选的物品是 i 。要注意的是,i 为所选物品,要作为阶段放在外面。

首先,易得 1<=i<=j , i!=y 且 i>=j (题目的特殊要求), j+i<=x (最多放满) . 那么,又选了个 i ,总重量就为 j+i ,即 F[j] -> F[j+i] += F[j]. F[1] 赋初值为 1 。

然后就可以愉快地写代码了。
#include<cstdio>
using namespace std;
constintN=1e5+5,P=998244353;
intn,x,y,f[N];
intmain() {
    scanf("%d%d%d",&n,&x,&y);
    f[0]=1;
    for(inti=1;i<=n;++i)
       if(i!=y)
          for(intj=0;i>=j&&j+i<=x;++j)
             f[j+i]=(f[j+i]+f[j])%P;
    printf("%d",f[x]);
    return0;
}

分数:65 ~ 75 分(不同的写法,不同的输入,不同的分数)

2.O(n):前缀和优化后的正解

注意 F[j+i] += F[j], 即为 F[j] += F[j-i] ,就是每一个 k(枚举前一个重量) + i(选的物品) = j(现在的重量).

根据题目限制,j-i<=j/2 , 也就是 i <= j/2 (注意,这里要上取整). 因为 k = j - i > 0, 所以 i < j. 于是 i 的范围即为 j/2 <= i <= j. 这样就可以把第一维度完全弄掉,取而代之用前缀和维护(内层循环就变成唯一一层循环了)。设 sum[i] = F[0] + F[1] +...+ F[i], 即重量小于等于 i 的方案数。

F[j] += F[j-i] (j-i<=j/2),就变成了 F[j] = F[0] + F[1]+...+F[j/2] = sum[j/2].

但要注意两点:

(1). k + i = j , 其中 j - k = i <= n. 如果 j <= n ,那以上等式一定成立;但如果 j > n, 那就不一定了:对于一些较小的 k , j - k > n . 此时 k < j - n, 也就是 k <= j - n - 1. 所以,对于所有 k <= j - n - 1 的情况,都是多算的不合法的情况,应当舍去。而这些 k 所组成的 F[k] 之和,就是 F[0] + F[1] +...+ F[j-n-1] = sum[j-n-1] , 即当 j > n 时,F[j] = sum[j/2] -sum[j-n-1].

(2). 有可能 sum[i/2] 把 y 所参与的 k 也算进去了。我们要认识到,y 是增长的量,也就是上文的 i ,所以 k + y = j,k = j - y. 由于 i 的取值范围是 j/2 <= i <= j ,如果 y 在这个范围内,j/2 <= y <= j, 就说明我们把 y 也算进去了。那么,多的那个 F[k] ,就是 F[j-y] ,去掉即可。所以,当 j/2 <= y <= j 时, F[j] = sum[j/2] - F[j-y].

但是,这两者可能有交集,所以要先把 F[j] 赋值为 sum[j/2],再对应减去多余的部分。

C++ 取模时,为避免结果变成负数,减法要先加后模,即 ans = (a1 - a2 + P) % P.

下面就可以写代码啦( 前缀和要赋初值为 F[0], 而 F[0] = 1 ):
#include<cstdio>
#include<cmath>
using namespace std;
constintN=1e5+5,P=998244353;
intn,x,y,f[N],sum[N];
intmain() {
    scanf("%d%d%d",&n,&x,&y);
    f[0]=1,sum[0]=f[0];
    for(intj=1; j<=x; ++j) {
        f[j]=sum[j/2];//总更新
        if(j>n) f[j]=(f[j]-sum[j-n-1]+P)%P;//情况一
        if(y>=ceil(j/2.0)&&y<=j) f[j]=(f[j]-f[j-y]+P)%P;//情况二
        sum[j]=(sum[j-1]+f[j])%P;//前缀和
    }
    printf("%d",f[x]);
    return0;
}

D题:抱歉,作者还不会做......

0条回帖

回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐