牛客周赛68文字版题解
A.三途川的摆渡人（二）
求给定的字符串有多少个 0，直接统计即可。
void solve(){
int n;
cin>>n;
string s;
cin>>s;
cout<<count(s.begin(),s.end(),'0');
}
B 魔法之森的蘑菇（二）
只需要枚举左上角和右下角，然后遍历查询该矩形内有没有 * 即可，然后当查询到更大的矩阵时依次更新下标。
由于 ，所以
可以通过，也可以用二维前缀和优化，时间复杂度
。
void solve(){
int n,m;
cin>>n>>m;
vector<string>a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]='%'+a[i];
}
vector<vector<int>>s(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(a[i][j]=='.');
}
}
auto get=[&](int a,int b,int c,int d){
return s[c][d]-s[c][b-1]-s[a-1][d]+s[a-1][b-1];
};
int ansx1,ansy1,ansx2,ansy2,smax=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int x=i;x<=n;x++){
for(int y=j;y<=m;y++){
if(get(i,j,x,y)==(x-i+1)*(y-j+1)){
if((x-i+1)*(y-j+1)>smax){
smax=(x-i+1)*(y-j+1);
ansx1=i;
ansy1=j;
ansx2=x;
ansy2=y;
}
}
}
}
}
}
cout<<ansx1<<" "<<ansy1<<" "<<ansx2<<" "<<ansy2;
}
C 迷途之家的大贤者（二）
首先进行操作一，两个容器要先计算自己消除的次数，分别为 。
此时得到两个无重集 ，两个容器可能不等长，存在相等的元素。
我们现在要消除相同元素，先统计相同元素，当存在相同元素时，我们可以在操作一中次数较少的时候同时消除此元素。
若 ，则说明需要另外的次数去操作，由于两个人是同时操作，所以相同的元素可以同时消除
个，例如:
，那第一个人可以消除
，第二个人可以消除
，这样
，当然有可能只存在奇数个相等元素，所以额外的次数除以
时要向上取整。
void solve(){
int n;
cin>>n;
vector<int>a(n),b(n);
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
vector<int>p,q;
map<int,int>cnt;
int ans1=0,ans2=0;
for(int i=0;i<n;i++){
if(cnt[a[i]]==0){
p.push_back(a[i]);
}else{
ans1++;
}
cnt[a[i]]++;
}
cnt.clear();
for(int i=0;i<n;i++){
if(cnt[b[i]]==0){
q.push_back(b[i]);
}else{
ans2++;
}
cnt[b[i]]++;
}
cnt.clear();
for(int i=0;i<p.size();i++) cnt[p[i]]++;
for(int i=0;i<q.size();i++) cnt[q[i]]++;
int ans=0;
for(auto t:cnt){
if(t.second==2){
if(ans1>ans2) ans2++;
else if(ans1<ans2) ans1++;
else ans++;
}
}
ans=(ans+1)/2;
if(ans==0){
cout<<max(ans1,ans2);
}else{
cout<<ans1+ans;
}
}
D.红魔馆的馆主（二）
:代码量的题，复制粘贴效率最快
分解后
，先考虑不
的情况，直接算出对数，不能
枚举，对于一个数我们只需要算出这个数缺多少个
，然后找到前缀中有多少个满足乘上后可以是
的倍数。
的情况同上算一下，然后记得先减去之前的贡献，取较大值的答案即可，算完之后再恢复不
的贡献。
int cnt[2][2][3];
void solve(){
int n;
cin>>n;
vector<i64>a(n+1);
for(int i=1;i<=n;i++) cin>>a[i];
i64 ans=0;
for(int i=1;i<=n;i++){
int cnt5=0,cnt11=0,cnt3=0;
int temp=a[i];
while(temp%5==0) temp/=5,cnt5++;
while(temp%11==0) temp/=11,cnt11++;
while(temp%3==0) temp/=3,cnt3++;
ans+=cnt[max(1-cnt5,0)][max(1-cnt11,0)][max(2-cnt3,0)];
for(int x=0;x<=min(1,cnt5);x++){
for(int y=0;y<=min(1,cnt11);y++){
for(int z=0;z<=min(2,cnt3);z++){
cnt[x][y][z]++;
}
}
}
}
//考虑当前元素加 1
i64 fans=ans;
for(int i=1;i<=n;i++){
int cnt5=0,cnt11=0,cnt3=0;
int temp=a[i];
while(temp%5==0) temp/=5,cnt5++;
while(temp%11==0) temp/=11,cnt11++;
while(temp%3==0) temp/=3,cnt3++;
for(int x=0;x<=min(1,cnt5);x++){
for(int y=0;y<=min(1,cnt11);y++){
for(int z=0;z<=min(2,cnt3);z++){
cnt[x][y][z]--;
}
}
}
i64 res=ans-cnt[max(1-cnt5,0)][max(0,1-cnt11)][max(2-cnt3,0)];
temp=a[i]+1;
cnt3=cnt5=cnt11=0;
while(temp%5==0) temp/=5,cnt5++;
while(temp%11==0) temp/=11,cnt11++;
while(temp%3==0) temp/=3,cnt3++;
res+=cnt[max(1-cnt5,0)][max(1-cnt11,0)][max(2-cnt3,0)];
fans=max(fans,res);
temp=a[i];
cnt3=cnt5=cnt11=0;
while(temp%5==0) temp/=5,cnt5++;
while(temp%11==0) temp/=11,cnt11++;
while(temp%3==0) temp/=3,cnt3++;
for(int x=0;x<=min(1,cnt5);x++){
for(int y=0;y<=min(1,cnt11);y++){
for(int z=0;z<=min(2,cnt3);z++){
cnt[x][y][z]++;
}
}
}
}
cout<<fans;
}
E.博丽神社的巫女（二）
我们用数组 考虑枚举到第
个数且当前
通过操作可以凑出
的可行性。
那么初始状态就是 。
通过枚举每个位置操作多少次，不然发现最多 次，所以直接枚举操作次数以及凑出的数字，假设当前除完的数字是
，那么
。
最后即可判断是否能出 。
由于要输出方案，所以我们记录 的转移路径，考虑当前第
个位置凑出的数字是由
总和为多少转移过来的，即
。
最后从最后一个位置还原回去即可，看当前这个数是需要多少，即代码中的 然后把
一直除到
，同时维护操作次数和当前前缀总和即可。
i64 dp[101][100001];
int pos[101][100001];
void solve(){
int n;
cin>>n;
vector<i64>a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
dp[0][0]=1;
for(int i=1;i<=n;i++){
int temp=a[i];
int cnt=0;
for(int j=0;cnt<2;j++){
for(int k=100000;k>=temp;k--){
if(dp[i][k]==0&&dp[i-1][k-temp]!=0){
pos[i][k]=k-temp;
}
dp[i][k]|=dp[i-1][k-temp];
}
temp/=2;
if(temp==0) cnt++;
}
}
if(dp[n][100000]==0){
cout<<"-1";
return ;
}
int s=100000;
vector<int>ans(n+1);
int idx=n;
while(1){
int temp=pos[idx][s];
int c=s-temp;
while(a[idx]!=c) a[idx]/=2,ans[idx]++;
idx--;
s=s-c;
if(idx==0) break;
}
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
}
F.雾之湖的冰精（三）
对于一条路径仅可能存在两种情况，即
先考虑第一种，即 可以直接从
的路径总数转移过来。
定义 为结点
为路径的一个端点，且路径总和不超过
的方案总数，那么状态便可以从
转移过来。然后每到一个结点把答案加上。
对于第二种情况，就是第一种中的乘法原理，从中任选一条路径给 ，然后转移就可以。
每到一个结点，统计以 为端点且总和不超过
的路径总数，记
为
的同父结点下，路径总和不超过
的路径总数。
那么对于
而言就是加上
，其中
，这里记得把
算进去，因为它也在路径里。
void solve(){
int n;
cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
vector<vector<int>>e(n+1);
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
vector<vector<i64>>dp(n+1,vector<i64>(10));
i64 ans=0;
auto dfs=[&](auto &&self,int u,int fa)->void {
vector<i64>s(10);
for(auto v:e[u]){
if(v==fa) continue;
self(self,v,u);
for(int i=a[u];i<=9;i++){
dp[u][i]=dp[u][i]+dp[v][i-a[u]];
}
for(int i=0;i<=9;i++){
for(int j=0;j<=9-i-a[u];j++)
ans+=dp[v][i]*s[j];
}
for(int i=0;i<=9;i++){
s[i]+=dp[v][i];
}
}
for(int i=0;i<=9;i++) ans+=dp[u][i];
dp[u][a[u]]++;
};
dfs(dfs,1,0);
cout<<ans;
}
查看2道真题和解析
