思特奇杯·云上蓝桥-算法集训营】第三周

1.杨辉三角

#include
using namespace std;
int N;
long long C(int n,int m){
    long long t=1;
    for(int i=0;i         t = t*(n-i)/(i+1);
        if(t>N)return t;
    }
    return t;
}                   
bool find(int L,int R,int x){   
    long long ans=0,M=0;
    while(R>=L){
        int T = (R+L)>>1; 
        ans = C(T,x);
        if(ans<=N)M=T,L=T+1;
        else R = T-1;
    }
    if(C(M,x)==N){
        cout << (1+M)*M/2 + x+1;
        return true;
    }
    return false;
}
 
int main(){
    cin>>N;
    if(N==1)cout<<1;
    else for(int i=17;i>0;i--)if(find(i*2,N,i))break;
    return 0;
}

2.节点选择

#include
using namespace std;
const int M = 100;    
int max(int x,int y){return x int n,a[M+5],p[M+5];    
int son[M+5][M+5];  
bool bo[M+5];    
int find(int x,bool can){   
    if(!p[x])return can?a[x]:0;   
    int ans=0;
    for(int i=0;i     if(can){
        int t = a[x];
        for(int i=0;i         ans = max(ans,t);
    }
    return ans;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i         int t1,t2;
        cin>>t1>>t2;
        son[t1][p[t1]++] = t2;
    }
    cout << find(1,true);    
    return 0;
}

3.耐摔指数

#include 
using namespace std;
int dp[2][10001];
int main(){
    int n;
    cin>>n;
    int i=0;
    while(dp[1][i]         i++;
        dp[0][i]=dp[0][i-1]+i;
        dp[1][i]=dp[1][i-1]+dp[0][i-1]+1;
    }
    cout<< i <     return 0;
}
 

4.k好数

#include
using namespace std;
const long long MOL = 1000000007;
const int M = 105;
long long K,L,dp[2][M+5],sum[2];
int main(){
    cin>>K>>L;    dp[i][j]=sum(dp[i-1])-dp[i-1][j-1]-dp[i-1][j+1],
    
    for(int i=1;i     sum[1] = K-1;
    
    for(int i=2;i<=L;i++){
        sum[i&1] = 0;
        for(int j=0;j             dp[i&1][j] = sum[i&1^1];
            if(j!=0)dp[i&1][j]-=dp[i&1^1][j-1];
            dp[i&1][j]-=dp[i&1^1][j+1];
            if(dp[i&1][j]<0)dp[i&1][j]+=MOL;
            if(dp[i&1][j]<0)dp[i&1][j]+=MOL;
            
            sum[i&1] = (sum[i&1]+dp[i&1][j])%MOL;
        }
    }
    cout << sum[L&1];
    return 0;
}