2020牛客寒假算法基础集训营3

F 牛牛的Link Power I
思路：
当前遍历到的数若为1，则加上与前方所有数的距离（sum）；
当前遍历数若为0，则加上已经有的1的数量（cnt），已有1更新，（cnt++）。
O(n)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;

ll sum,ans,cnt;
string s;

int main(){
	int n;
	cin >> n;
	cin >> s;
	for(int i=0;i<n;i++){
		sum = (sum + cnt) % mod;
		if(s[i] == '1'){
			ans = (ans + sum) % mod;
			cnt++;
		}
	}
	cout << ans << endl;
	return 0;
}

H 牛牛的k合因子数
思路：
埃氏筛筛合数并将该合数及其倍数的合数因子数量更新。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
 
using namespace std;
typedef long long ll;
const ll MAXN = 1e5 + 5;
 
bool vis[MAXN];
ll cnt[MAXN];
ll num[MAXN];
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n,m,k,x;
    cin >> n >> m;
    for(int i=2;i<=n;i++){
        if(vis[i]){
            for(int j=i;j<=n;j+=i) num[j]++;//该合数及其倍数++
        }else{
            for(int j=i+i;j<=n;j+=i) vis[j]=1;//标记合数
        }
    }
    for(int i=1;i<=n;i++) cnt[num[i]]++;//num[i]为每个合数的合数因子数量 cnt数组记录k合因子的数量
    while(m--){
        cin >> x;
        cout << cnt[x] <<'\n';
    }
    return 0;
}

I 牛牛的汉诺塔
所给条件（伪代码）：

Function Hanoi(n,a,b,c)
    if n==1 then
        print(a+'->'+c)
    else
        Hanoi(n-1,a,c,b)
        print(a+'->'+c)
        Hanoi(n-1,b,a,c)
    end if
end Function 

思路：
由题意的递归关系式想到dp
dp递推式：
f[i][1]=f[i-1][2]+f[i-1][6];
f[i][2]=f[i-1][1]+1+f[i-1][4]; //+1表示最后一个要放回到C
f[i][3]=f[i-1][4]+f[i-1][5];
f[i][4]=f[i-1][3]+f[i-1][2];
f[i][5]=f[i-1][6]+f[i-1][3];
f[i][6]=f[i-1][5]+f[i-1][1];

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 1e6 + 5;
 
ll f[70][10];
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    f[1][2]=1;
    for(int i=2;i<=n;i++){
        f[i][1]=f[i-1][2]+f[i-1][6];
        f[i][2]=f[i-1][1]+1+f[i-1][4];
        f[i][3]=f[i-1][4]+f[i-1][5];
        f[i][4]=f[i-1][3]+f[i-1][2];
        f[i][5]=f[i-1][6]+f[i-1][3];
        f[i][6]=f[i-1][5]+f[i-1][1];
    }
    cout << "A->B:" << f[n][1] << endl;
    cout << "A->C:" << f[n][2] << endl;
    cout << "B->A:" << f[n][3] << endl;
    cout << "B->C:" << f[n][4] << endl;
    cout << "C->A:" << f[n][5] << endl;
    cout << "C->B:" << f[n][6] << endl;
    cout << "SUM:" << (ll)pow(2,n)-1 << endl;
    return 0;
}