题解| 2021牛客OI赛前集训营-普及组(第四场)部分题解
思路：记录叫的次数和分别回应的次数， 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;
} 解析：
- 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.
#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;
} 
投递蚂蚁集团等公司10个岗位 >