【思特奇杯·云上蓝桥-算法集训营】第3周_随笔

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

1.杨辉三角

#include
#include
#include
#include

using namespace std;

typedef long long ll;

int n;

ll C(int a, int b)
{
    ll res = 1;
    for(ll up = a, down = 1; down <= b; up --, down ++)
    {
        res = res * up / down;
        if(res > n) return res;
    }
    return res;
}

bool check(int j)
{
    ll l = 2 * j, r = max((ll)n, l);
    while(l < r)
    {
        ll k = l + r >> 1;
        if(C(k, j) >= n) r = k;
        else l = k + 1;
    }
    
    if(C(r, j) != n) return false;
    
    cout<<(r + 1) * r / 2 + j + 1<>n;
    for(int j=16; ;j--)
        if(check(j))
            break;
        
    return 0;
}

2.节点选择

#include

using namespace std;

vector > v;//存放树形结构 

int dp[100005][2] = {0};

void dfs(int a, int pre){
	for(int i = 0; i < v[a].size(); i++){
		int t = v[a][i];
		if(t != pre){//只要不是相邻节点就符合题意 
			dfs(t, a);
			dp[a][0] += max(dp[t][0], dp[t][1]);//不选择该节点，保存下一节点的最大值 
			dp[a][1] += dp[t][0];//选择该节点，下一节点只能不选择 
		}
	}
}
int main(){
	int n, a, b;
	cin >> n;
	v.resize(n + 1);//给定数据大小 
	for(int i = 1; i <= n; i ++)
		cin >> dp[i][1];//输入节点的权重 
	for(int i = 0; i < n-1; i ++){
		cin >> a >> b;//输入节点之间的关系 
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1, 0);
	cout << max(dp[1][0], dp[1][1]) << endl;
	return 0;
}

3.耐摔指数

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
const int maxn=1e5+5;
typedef long long ll;
using namespace std;
int f2[105],f3[105];
int main(){
	int n;
	while(~scanf("%d",&n)){
		int i=0;
		while(f3[i] 
4.K好数 
#include
using namespace std;
int K, L;
long long int m1[1000],m2[1000];
int i0;//fun
//根据进制数进行初始化
void fun_extra() {
	i0 = L;
	for (int i = 0; i < K; i++) {
		if (i == 0) {
			m1[i] = 0;
		}
		else {
			m1[i] = 1;
		}
		m2[i] = 0;
	}
}

void fun(long long int * m0_1, long long int *m0_2) {
	for (int i = 0; i < K; i++) {
		m0_2[i] = 0;
		for (int j = 0; j < K; j++) {
			if (j != i + 1 && j != i - 1) {
				m0_2[i] += m0_1[j];
			}
		}
		m0_2[i] %= 1000000007;
	}
	i0--;
	if (i0 > 1) {
		fun(m0_2, m0_1);
	}
	else {
		long long int sum = 0;
		for (int i = 0; i < K; i++) {
			sum += m0_2[i];
		}
		cout<< sum % 1000000007;
	}
}
//K进制数；L位数；
int main() {
	cin >> K >> L;
	fun_extra();
	fun(m1, m2);
	return 0;
}
 
Leetcode 
509.斐波那契数 
class Solution {
public:
    int fib(int N) {
        if (N <= 1) {
            return N;
        }
        return memoize(N);
    }

public:
    int memoize(int N) {
        vector temp(N+1);
        temp[0] = 0;
        temp[1] = 1;
        for (int i = 2; i <= N; i++) {
            temp[i] = temp[i - 1] + temp[i - 2];
        }
        return temp[N];
    }
};
 
1137. 
class Solution {
public:
    int tribonacci(int n) {
 if (n <= 1) {
            return n;
        }
        if (n == 2) return 1;
        return memoize(n);
    }

public:
    int memoize(int n) {
        int sum = 0;
        int first = 0;
        int second = 1;
        int third = 1;
        for (int i = 3; i <= n; i++) {
            sum = first + second+third;
            first = second;
            second = third;
            third = sum;
        }
        return sum;
    }
};
 
70. 
public class 爬楼梯_for循环 {
    public static void main(String[] args) {
        int result = climbStairs(4);
        System.out.println(result);
    }

    public static int climbStairs(int n) {
        //小于等于2的时候，直接返回n
        if (n <= 2) {
            return n;
        }
        int a = 1;
        int b = 2;
        int temp=0;
        for (int i = 3; i < n+1; i++) {
            temp=b;
            b=a+b;
            a=temp;
        }
        return b;
    }
}
 
746. 
public class minCostClimbingStairs746 {
    public static void main(String[] args) {
        int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
        System.out.println(minCostClimbingStairs(cost));
    }

    public static int minCostClimbingStairs(int[] cost) {
        int length = cost.length;
        int[] f = new int[length+1];       //设定每次的0最优代价
        f[0] = 0;                   //初始化来到第一个台阶的最小代价
        f[1] = 0;                   //初始化来到第二个台阶的最小代价
        for (int i = 2; i < length+1; i++) {
            f[i] = Math.min(f[i-2]+cost[i-2],f[i-1]+cost[i-1]);
        }
        return f[length];
    }
}
 
121. 
class Solution {
public:
    int maxProfit(vector& prices) {
        
       if(prices.size()==0) return 0;
       int minprices=prices[0];
       int profit=0;
       for(int i=1;iprices[i]?prices[i]:minprices;
       }
       
       return profit;
    }
};
 
1143. 
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        l = [[0]*(n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i-1] == text2[j-1]:
                    l[i][j] = l[i-1][j-1] + 1
                else:
                    l[i][j] = max(l[i-1][j], l[i][j-1])
        return l[-1][-1]
 
					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5713854.html

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

发表评论

评论列表（0条）