【题解】2020牛客寒假算法基础集训营第三场

这个题解写得超详细了啊，非常适合我这种萌新学习！(之前有的题解就一句话鬼知道他说了什么嘛)

E题没打有个地方没打1ll<<i，打了1<<i，直接在e题debug凉凉了，没ak真的遗憾

/*    dfs实际上是个模拟 */ //len表示判断的是哪一位 ll dfs(ll len,int maxi,int k,int f){     //dp[len][k][f]存储的是到长度为len为止，第k位为0和第k位为1的数是多少     //maxi标志的是上一位模拟的数是不是等于num的这一位的数     /*        我们还是拿100来举例子，因为最高位我们得到的一定为1，所以传进来的时候maxi就是1        那么我们第一位既可以模拟0也可是模拟1        模拟0的时候，i != a[len]所以maxi = false，之后也都是false        我们下一位就可以模拟00X跟01X，剩下的类似        模拟1的时候，i == a[len]所以maxi = true        我们就可以模拟1XX        但是由于这时a[2] = 0所以只能模拟10X        差不多就已经很清楚了     */     //dp[len][k][f]这里其实就是记忆化搜索，如果之前出现过，就直接返回结果就好。     if(dp[len][k][f] != -1 && maxi == 0)         return dp[len][k][f];     //只有当第k位为1的情况这里才会加上1     if(!len)         return f;     ll cnt = 0;     int maxn = maxi ? a[len] : 1;     //i这里代表着第len位的数字是多少     //那么f||len == k && i就是判断这次模拟的数的第k位是否为1     for(int i = 0;i <= maxn;i++){         cnt += dfs(len - 1,maxi && i == a[len],k,f||len == k&&i);     }     //只有当maxi等于false的时候，我们模拟了下一位为0，1的全部情况,此时才更新dp的值     //表示不受之前的数的限制，所求的只是[0,1 << (len) - 1]]满足条件的数     return maxi ? cnt : dp[len][k][f] = cnt; } //二进制拆分数位,返回的结果是第k位为1的数总共有几个 ll div(ll num,int k){     memset(a,0,sizeof(a));     int index = 0;     while(num){         a[++index] = num % 2;         num /= 2;     }     return dfs(index,1,k,0); } E题最简单数位DP标程，本菜鸡的一点个人解读，希望可以帮到跟我一样的萌新新理解，个人一点愚见，如果有不正确的地方，还请大佬们们斧正ORZ

I题打表过了。。

I题递推：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42887735 dp[i][j][k]表示在第i种情况下n层汉诺塔产生第k中操作的次数

题解写的真棒！

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42890352 I题的递推这样应该更符合萌新。 A->B=（上一次）A->C->B B->C=（上一次）B->A->C C->A=（上一次）C->B->A

被零封也很遗憾

C题对于用java的也太不友好了吧，居然是分语言的题目，也是醉了

前三场里最长的题解了ORZ

太良心啦，感谢出题人！

B2真的妙

优秀题解，有心了，来得早不如来得好

标数法就是签到吧

#include <bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <set> #include <queue> const int maxn = 1e5 + 7; typedef long long ll; using namespace std; const ll mod = 1e9 + 7; int main(){     ll n;     cin >> n;     int k = 1;     char ch;     ll ans[maxn];     ll a[maxn] = {0};     ll sum = 0;     getchar();     for (int i = 1; i <= n; i++){         scanf("%c",&ch);         if (ch == '1')             ans[k++] = i, sum += i, sum %= mod;     }     a[0] = sum % mod;     ll s = 0;     for (int i = 1; i < k; i++)         a[i] = a[i-1] - ans[i-1], a[i] %= mod;     for (int i = 1; i < k; i++){         s += (a[i] - ans[i] * (k-i));         s %= mod;     }     cout << s << endl;     return 0; } 大佬能看看我的代码哪里错了吗？77.78的通过率

最后一道题用二分的思想，我用set和map被tle了，改成vec只用500耗时，差距这么大么

E可以这样考虑，把x转换成二进制形式，如101010（从高位到低位），现在考虑某一位1出现的次数，如10 1 010，那么只要这个位前面的进制小于10，即0~(10-1)，那么后面就有000~111，共(10)*(111+1)种选法，再考虑如果前面的等于10，后面有000~010共(010+1)种选法，当然如果当前位为0就不需要计算这种情况。 至于0的数量就可以用区间的总量减去1的数量得到了。

萌新贴G求教有没有更好的办法 #include <bits/stdc++.h> using namespace std; const int mod=1e9+7; const int maxn=5e5+5; long long t1[maxn]={0},t2[maxn]={0},t3[maxn]={0},t4[maxn]={0}; string str; int n,m; int main() { cin>>n; cin>>str; int deep=0; int w=n; while (w) deep++,w/=2; int be=pow(2,deep),en; int bbe=be; for (int i=0;i<str.size();i++) t1[be+i]=str[i]=='1'; int dep=deep-1; int dis=1; while (dep>=0) { be=pow(2,dep);en=pow(2,dep+1); for (int i=be;i<en;i++) { t1[i]=t1[2*i]+t1[2*i+1]; t2[i]=t2[2*i]+t2[2*i+1]+dis*t1[2*i+1];             t2[i]%=mod; t3[i]=t3[2*i]+t3[2*i+1]+dis*t1[2*i];             t3[i]%=mod; t4[i]=t4[2*i]+t4[2*i+1]+t1[2*i]*t2[2*i+1]+t1[2*i+1]*t3[2*i]+t1[2*i]*t1[2*i+1];             t4[i]%=mod; } dep--; dis*=2; } cout<<t4[1]<<endl; cin>>m; while (m--) {//for (int i=1;i<pow(2,deep+1);i++) cout<<t1[i]<<" "<<t2[i]<<" "<<t3[i]<<" "<<t4[i]<<" "<<endl; int q,pos; cin>>q>>pos; pos=pos+bbe-1; //cout<<"#"<<pos<<endl; if (q==1) t1[pos]=1; else t1[pos]=0; dis=1; pos/=2; while(pos>0) { int i=pos; t1[i]=t1[2*i]+t1[2*i+1]; t2[i]=t2[2*i]+t2[2*i+1]+dis*t1[2*i+1];             t2[i]%=mod; t3[i]=t3[2*i]+t3[2*i+1]+dis*t1[2*i];             t3[i]%=mod; t4[i]=t4[2*i]+t4[2*i+1]+t1[2*i]*t2[2*i+1]+t1[2*i+1]*t3[2*i]+t1[2*i]*t1[2*i+1];             t4[i]%=mod; pos/=2; dis*=2; } cout<<t4[1]<<endl; } return 0; }

等明天再来康康完整的8

a=[[0,1,0,0,0,0]] for i in range(1,61): t=a[-1][:] s=2*2**i-1 if i&1: t[0]=t[3]=t[1]+t[2] t[4]=s-sum(t[:4])-t[5] else: t[2]=t[5]=t[3]+t[4] t[1]=s-sum(t[2:])-t[0] a.extend([t]) n=int(input())-1 print(f'A->B:{a[n][0]}') print(f'A->C:{a[n][1]}') print(f'B->A:{a[n][2]}') print(f'B->C:{a[n][3]}') print(f'C->A:{a[n][4]}') print(f'C->B:{a[n][5]}') print(f'SUM:{2*2**n-1}') 汉诺塔的题，上面是我excel找规律找到的规律，做的递推式 下面是别人的思路，比较清奇 a={"AB":0,"AC":1,"BA":0,"BC":0,"CA":0,"CB":0} n=int(input()) for i in range(2,n+1):a["AB"],a["AC"],a["BA"],a["BC"],a["CA"],a["CB"]=a["AC"]+a["BA"],1+a["AB"]+a["BC"],a["CA"]+a["AB"],a["CB"]+a["AC"],a["CB"]+a["BA"],a["BC"]+a["CA"] for i in a.items():print(i[0][0],"->",i[0][1],":",i[1],sep='') print('SUM:',2**n-1,sep='') n=int(input()) u=[0, 1, 0, 0, 0, 0] for i in range(1,n): v=[0]*6 v[3]=v[0]=u[1]+u[2] v[4]=u[2]+u[5] v[5]=v[2]=u[0]+u[4] v[1]=2**(i+1)-1-sum(v) u=v print(f'A->B:{u[0]}') print(f'A->C:{u[1]}') print(f'B->A:{u[2]}') print(f'B->C:{u[3]}') print(f'C->A:{u[4]}') print(f'C->B:{u[5]}') print(f'SUM:{2**n-1}') x=2 n=int(input());ab=ba=bc=ca=cb=0;ac=1 for i in range(1,n): if i&1: ab+=x//3+1 bc+=x//3+1 ca+=x//3 else : ac+=x//3+1 ba+=x//3 cb+=x//3 x<<=1 print(f"A->B:{ab}") print(f"A->C:{ac}") print(f"B->A:{ba}") print(f"B->C:{bc}") print(f"C->A:{ca}") print(f"C->B:{cb}") print(f"SUM:{2**n-1}")