北京科技大學(xué)算法分析與設(shè)計(jì)計(jì)蒜客-創(chuàng)新互聯(lián)

北京科技大學(xué) 算法分析與設(shè)計(jì) 計(jì)蒜客平時(shí)作業(yè)及實(shí)驗(yàn)代碼 2022年（僅供參考）

十余年的靈壽網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開(kāi)發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。全網(wǎng)整合營(yíng)銷推廣的優(yōu)勢(shì)是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整靈壽建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無(wú)論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。成都創(chuàng)新互聯(lián)從事“靈壽網(wǎng)站設(shè)計(jì)”,“靈壽網(wǎng)站推廣”以來(lái)，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。

作業(yè)一

買房子

[USACO Open08]農(nóng)場(chǎng)周圍的道路

國(guó)王的魔鏡?

作業(yè)二

蝸牛旅游

[NOIP2001]求先序排列

作業(yè)三?

二分查找

白菜君的三角形

壓縮歌曲

作業(yè)四?

踩方格

最長(zhǎng)上升子序列

作業(yè)五

劃分整數(shù)

神奇的口袋

作業(yè)六

代碼填空：全排列

自然數(shù)拆分

文具店?

實(shí)驗(yàn)

實(shí)驗(yàn)一書架

實(shí)驗(yàn)二封印之門

實(shí)驗(yàn)三?銀行貸款

實(shí)驗(yàn)四防御導(dǎo)彈

作業(yè)一買房子

//買房子
#includeusing namespace std;
int main(){
    int N, K;
    cin >>N >>K;
    double price = 200.0;
    double ratio = K * 0.01 + 1;
    int year = 1;
    while(1){
        if(year >= 20){
            cout<< "Impossible";
            break;
        }
        if(price - year * N<= 0){
            cout<< year;
            break;
        }
        price *= ratio;
        year++;
    }
    return 0;
}

[USACO Open08]農(nóng)場(chǎng)周圍的道路

//[USACO Open08]農(nóng)場(chǎng)周圍的道路
#includeusing namespace std;

int res;

void MyCount(int N,int K){
    int temp = N - K;
    if( temp<= 0 || temp & 1 == 1){
        res++;
        return;
    }
    else{
        MyCount(temp / 2 + K , K);
        MyCount(temp / 2 , K);
    }
}

int main(){
    res = 0;
    int  N,K;
    cin >>N >>K;
    MyCount(N , K);
    cout<< res;
    return 0;
}

國(guó)王的魔鏡?

//國(guó)王的魔鏡
#include#include
using namespace std;

int main(){
    string s;
    cin >>s;
    while(1){
        int len = s.size();
        string t = s;
        if( len & 1 == 1){
            cout<< len;
            break;
        }            
        reverse(s.begin(), s.end());
        if( t == s) 
            s = t.substr(0, len / 2);
        else{
            cout<< s.size();
            break;
        }
    }
    return 0;
}

作業(yè)二蝸牛旅游

//蝸牛旅游
#include#include#includeusing namespace std;

int main() {
    int n;
    cin >>n;
    vectorlandscape(n);
    for (auto &i : landscape) cin>>i;
    unordered_mapMap;
    int res = 0;
    int len = 0;
    for (int i = 0; i< n; i++) {
        if (!Map.count(landscape[i])) {
            Map[landscape[i]] = i;
            len++;
        }
        else {
            int t_len = i - Map[landscape[i]];
            if (t_len >len) len++;
            else len = t_len;
            Map[landscape[i]] = i;
        }
        res = max(res,len);
    }
    cout<< res;
    return 0;
}

[NOIP2001]求先序排列

//[NOIP2001]求先序排列
#include#include
using namespace std;

void CreatePreorder(string inorder, string post) {
    if (inorder.size() >0) {
        char now = post.back();
        cout<< now;
        int k = inorder.find(now);
        //遍歷左子樹(shù)
        CreatePreorder(inorder.substr(0, k), post.substr(0, k));
        //遍歷右子樹(shù)
        CreatePreorder(inorder.substr(k + 1), post.substr(k, inorder.size() - k - 1));
    }
}

int main() {
    string inorder_string, postorder_string;
    cin >>inorder_string >>postorder_string;
    CreatePreorder(inorder_string, postorder_string);
    return 0;
}

作業(yè)三? 二分查找

//二分查找
#include#include
using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
	int n, m;
	cin >>n >>m;
    int *arr = new int [n];
	for (int i = 0; i< n; i++) cin >>arr[i];
	sort(arr, arr + n);
    int loc;
    int minN = arr[0];
    int maxN = arr[n-1];
	for(int i = 0; i< m; i++) {
        int t; 
        cin >>t;
        if(t<= minN) {
            cout<< -1<< '\n';
            continue;
        }
        if(t >maxN) {
            cout<< maxN<< '\n';
            continue;
        }
		loc = lower_bound(arr, arr + n, t) - arr;
		if (loc >0) cout<< arr[loc - 1]<< '\n';
		else cout<< -1<< '\n';
	}
	return 0;
}

白菜君的三角形

//白菜君的三角形
#includeusing namespace std;

int func(int n) {
    int target = n * n;
    int sum = 0;
    int down = 3;
    int top = n - 1;
    //雙指針 慢速收縮
    while (down< top) {
        int now = down * down + top * top;
        if (now< target) down++;
        else if (now >target) {
            top--;
        }
        else {
            sum += down / 2;
            down++;
            top--;
        }
    }
    return sum;
}

int main() {
    int n;
    cin >>n;
    cout<< func(n);
    return 0;
}

壓縮歌曲

//壓縮歌曲
#include#include
#includeusing namespace std;

typedef long long ll;

int main() {
	ll n, m;
	cin >>n >>m;
	vectorinitial(n);
	vectorcompress(n);
	vectordifference(n);
	ll minN = 0;
    for(ll i = 0; i< n; i++) {
    	cin >>initial[i] >>compress[i];
    	difference[i] = initial[i] - compress[i];
    	minN += compress[i];
    }
    if(minN >m) cout<< -1;
    else if(minN == m) cout<< n;
    else {
    	ll leave = m - minN;
        sort(difference.begin(), difference.end());
        //貪心
        for(auto i:difference) {
        	leave -= i;
        	if(leave >= 0) n--;
        }
        cout<< n;
    }
	return 0;
}

作業(yè)四? 踩方格

// 踩方格
#includeusing namespace std;

int getNumber(int n) {
	if(n == 0) return 0;
	int north = 1;
	int east_west = 2;
	while(--n) {
		int t_north = east_west + north;
		int t_east_west = north * 2 + east_west;
		north = t_north;
		east_west = t_east_west;
	}
	return north + east_west;
} 

int main(){
	int n;
	cin >>n;
	cout<< getNumber(n);
	return 0;
}

最長(zhǎng)上升子序列

// 最長(zhǎng)上升子序列
#include#include#include 
#includeusing namespace std; 

const int N = 1e5 + 10; 

struct Lsh {
    int id;
    int value; 
} lis[N];

int a[N], LIS, n;

int t[N], arr1[N], arr2[N], num[N]; 

inline bool cmp(Lsh x, Lsh y){
    return x.value< y.value; 
}

int main() {
	std::ios::sync_with_stdio(false);
    cin.tie(0);
    freopen("lis.in", "r", stdin); 
    freopen("lis.out","w", stdout); 
    cin >>n;
    for(int i= 1; i<= n; i++) {
        cin >>lis[i].value;
        lis[i].id = i;
    }
    sort(lis + 1, lis + 1 + n, cmp);
    
    int index = 0;
    lis[0].value = -1;
    
    for (int i = 1; i<= n; i++) {
        if(lis[i].value != lis[i - 1].value) index++;
        a[lis[i].id] = index;
    }

    for(int i = 0; i< N; i++) t[i] = 2147483647;
    t[0] = 0;

    for (int i = 1; i<= n; i++) {
        arr1[i] = lower_bound(t + 1, t + 1 + n, a[i]) - t;
        t[arr1[i]] = a[i];
        LIS = max(LIS, arr1[i]);
    }

    for(int i = 0; i< N; i++) t[i] = 2147483647;
    t[0] = 0;
    
    for (int i = n; i >= 0; i--) {
        arr2[i] = lower_bound(t + 1, t + 1 + n, -a[i]) - t; 
        t[arr2[i]] = -a[i];
    }
    
    for(int i= 1; i<= n; i++) {
        if(arr1[i] + arr2[i] == LIS + 1)
            num[arr1[i]]++;
    }
    
    for (int i = 1; i<=n; i++) {
        if(arr1[i] + arr2[i] == LIS + 1 && num[arr1[i]] ==1) 
            cout<< LIS - 1<< ' ';
        else
            cout<< LIS<< ' '; 
    }
}

作業(yè)五劃分整數(shù)

// 劃分整數(shù)
#include#includeusing namespace std;

typedef long long ll;
    
ll getNumber(int n, int m) {
	if(m == 1) return 1;
	vector>dp(n + 1, vector(m + 1));
	for(int i = 1; i<= n; i++) {
		for(int j = 1; j<= m; j++) {
            if(i == 1 || j == 1) dp[i][j] = 1;
            else if(j >i) dp[i][j] = dp[i][i];
            else if(i == j) {
                dp[i][j] = dp[i][j - 1] + 1;
            }
            else {
                dp[i][j] = dp[i][j - 1] + dp[i - j][j];
            }
		}
	}
	return dp[n][m];
}

int main() {
	int n, k;
	cin >>n >>k;
    cout<< getNumber(n, k);
    return 0;
}

神奇的口袋

// 神奇的口袋
#include#include#include#include#include#include
using namespace std;

typedef long long ll;
#define RG register
#define MAX 1111

inline int read() {
	RG int x = 0, t = 1;
	RG char ch = getchar();
	while ((ch< '0' || ch>'9') && ch != '-') ch = getchar();
	if (ch == '-') {
		t = -1;
		ch = getchar();
	}
	while (ch<= '9' && ch >= '0') {
		x = x * 10 + ch - 48;
		ch = getchar();
	}
	return x * t;
}

struct BigInt {
	int s[20000], ws;
	void init() {
		s[1] = 1;
		ws = 1;
	}
	void Multi(int x) {
		for (int i = 1; i<= ws; ++i) s[i] = s[i] * x;
		for (int i = 1; i<= ws; ++i) {
			s[i + 1] += s[i] / 10;
			s[i] %= 10;
		}
		while (s[ws + 1]) {
			++ws;
			s[ws + 1] = s[ws] / 10;
			s[ws] %= 10;
		}
	}
	void output() {
		for (int i = ws; i; --i)
			printf("%d", s[i]);
	}
}Ans1, Ans2;

int pri[20001], tot;
bool zs[20001];

void getpri() {
	zs[1] = true;
	for (int i = 2; i<= 20000; ++i) {
		if (!zs[i]) pri[++tot] = i;
		for (int j = 1; j<= tot && i * pri[j]<= 20000; ++j) {
			zs[i * pri[j]] = true;
			if (i % pri[j] == 0)break;
		}
	}
}

int Mul[20001], Div[20001];
int sum, a[MAX];
int n, m, D;

void Calc(int x, int* f) {
	for (int i = 1; i<= tot; ++i) {
		while (x % pri[i] == 0) {
			f[pri[i]]++;
			x /= pri[i];
		}
	}
}

int main() {
	n = read();
	m = read();
	D = read();
	for (int i = 1; i<= n; ++i) {
		a[i] = read();
		sum += a[i];
	}
	getpri();
	for (int i = 1; i<= m; ++i) {
		int x = read(), y = read();
		if (!a[y]) {
			puts("0/1");
			return 0;
		}
		Calc(a[y], Mul);
		Calc(sum, Div);
		a[y] += D;
		sum += D;
	}
	for (int i = 1; i<= 20000; ++i) {
		if (Div[i] >= Mul[i]) {
			Div[i] -= Mul[i];
			Mul[i] = 0;
		}
		else {
			Mul[i] -= Div[i];
			Div[i] = 0;
		}
	}
	Ans1.init();
	Ans2.init();
	for (int i = 1; i<= 20000; ++i)
		for (int j = 1; j<= Mul[i]; ++j)
			Ans1.Multi(i);
	for (int i = 1; i<= 20000; ++i)
		for (int j = 1; j<= Div[i]; ++j)
			Ans2.Multi(i);
	Ans1.output();
	putchar('/');
	Ans2.output();
	puts("");
	return 0;
}

作業(yè)六代碼填空：全排列

// 代碼填空：全排列
vis[j] && str[i] == str[j]

自然數(shù)拆分

// 自然數(shù)拆分
#include#includeusing namespace std;

vectormatrix(20);
int n, m;

void dfs(int num, int init, int sum) {
	if(sum == n) {
        cout<< n<< "=";
		for(int i = 1; i<= num - 1; i++) {
			cout<< matrix[i];
			if(i != num - 1)
				cout<< "+";
		}
		cout<< "\n";
		return;
	}
    if(sum + init >n) return;
	for(int i = init; i<= n - 1; i++) {		
		if(sum + i<= n) {
			matrix[num] = i;
			dfs(num + 1, i, sum + i);
		}
	}
}

int main() {
	cin >>n;
	dfs(1, 1, 0);
	return 0;
}

文具店?

// 文具店
#include#include#include
using namespace std;

typedef long long ll;

void dfs(string s, int k, ll t, ll &res) {
	if(k == 1) {
        ll tmp = 0;
		for(auto i : s) tmp =  tmp * 10 + i - '0';
		res = min(t + tmp, res);
		return;
	}
	if(s.size()<= k) {
		for(auto i : s) t += i - '0';
		res = min(t, res);
		return;
	}
	ll tmp = 0;
	for(int i = 0; i + k - 1< s.size(); i++) {
		tmp = tmp * 10 + s[i] - '0';
		dfs(s.substr(i + 1), k - 1, t + tmp, res);
	}
}

ll Mycount(string s, int k) {
	ll res = 0;
	// 字符串長(zhǎng)度與水彩筆數(shù)相等
	if(s.size() == k) {
		for(auto i : s) res += i - '0';
		return res;
	}
	res = 1e9;
	dfs(s, k, 0, res);
	return res;
}

int main() {
	string s;
	int k;
	cin >>s >>k;
    cout<< Mycount(s, k);
    return 0;
}

實(shí)驗(yàn) 實(shí)驗(yàn)一書架

// 書架
#include#include#include
#includeusing namespace std;

int main() {
	int n;
	int target;
	cin >>n >>target;
	vectorcows(n);
	for(auto &i: cows) cin >>i;
	sort(cows.begin(), cows.end(), greater());
	int count_num = 0;
	while(target >0) {
		target -= cows[count_num];
		count_num++;
	}
	cout<< count_num;
	return 0;
}

實(shí)驗(yàn)二封印之門

本題要求使用回溯法解題，但實(shí)際上使用 Dijkstra 或 Floyd 算法更好

Floyd算法：

// Floyd 算法
#include#includeusing namespace std;

#define MAXN 26

vector>shortPath(MAXN, vector(MAXN, MAXN)); // 各頂點(diǎn)間的最短距離

int main() {
	string initial;
	string target;
	int n;
	cin >>initial >>target >>n;
	for(int i = 0; i< MAXN; i++) shortPath[i][i] = 0;
	for(int i = 0; i< n; i++) {
		char a, b;
		cin >>a >>b;
		if(a == b) continue;
		shortPath[a - 'a'][b - 'a'] = 1;
	}
    
    for(int i = 0; i< MAXN; i++) {
        for(int j = 0 ; j< MAXN; j++) {
            for(int k =0; k< MAXN; k++) {
                // 更新最小路徑
                if(shortPath[j][k] >shortPath[j][i] + shortPath[i][k]){         
                    shortPath[j][k] = shortPath[j][i] + shortPath[i][k];  
                }
            }
        }
    }
    
    int res = 0;
    int len = initial.size();
    for(int i = 0; i< len; i++) {
    	if(initial[i] != target[i]) {
    		int a = initial[i] - 'a';
    		int b = target[i] - 'a';
    		if(shortPath[a][b] == MAXN) {
    		    res = -1;
    		    break;
    		}
    		else res += shortPath[a][b];
    	}
    }
    cout<< res;
	return 0;
}

回溯法：?

// 回溯 
// 有一個(gè)用例一直過(guò)不了，鑒定為惡心人
// 下列代碼仍可優(yōu)化，有興趣可以試試
#include#include
#includeusing namespace std;

#define MAXN 26

int shortPath[MAXN][MAXN]; // 各頂點(diǎn)間的最短距離

void dfs(int init, int target, int now, int num) {
	if(now == target) {
		shortPath[init][target] = min(shortPath[init][target], num);
		return;
	}
	// 剪枝: 超過(guò)目前 shortPath[init][target] 必不可能產(chǎn)生新的最小值
	if(num >= shortPath[init][target]) return;
	// 剪枝: shortPath[now][target] 最短路徑存在直接使用
	if(shortPath[now][target]< MAXN) {
		if(shortPath[init][target] >num + shortPath[now][target])
		    shortPath[init][target] = num + shortPath[now][target];
		return;
	}
	for(int i = 0; i< MAXN; i++) {
	    if(now != i && shortPath[now][i]< MAXN) {
	    	dfs(init, target, i, num + shortPath[now][i]);
	    }
	}
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
	string initial;
	string target;
	int k;
	cin >>initial >>target;
	cin >>k;
	for(int i = 0; i< MAXN; i++) {
		for(int j = 0; j< MAXN; j++) {
	        if(i == j) shortPath[i][j] = 0;
	        else shortPath[i][j] = MAXN;
	    }
	}
	for(int i = 0; i< k; i++) {
		char a, b;
		cin >>a >>b;
		if(a == b) continue;
		shortPath[a - 'a'][b - 'a'] = 1;
	}
	for(int i = 0; i< MAXN; i++) {
		for(int j = 0; j< MAXN; j++) {
			// 相等或路徑已存在則無(wú)需繼續(xù)尋找
			if(i == j || shortPath[i][j]< MAXN) continue;
            else {
            	dfs(i, j, i, 0);
            }
		}
	}
	int res = 0;
	int len = initial.size();
	for(int i = 0; i< len; i++) {
		// 相等無(wú)需操作，跳過(guò)
		if(initial[i] == target[i]) continue;
		int a = initial[i] - 'a';
		int b = target[i] - 'a';
		// 無(wú)法操作，退出循環(huán)，輸出 -1
        if(shortPath[a][b] == 26) {
            res = -1;
            break;
        }
		res += shortPath[a][b];
	}
	cout<< res;
	return 0;
}

實(shí)驗(yàn)三?銀行貸款

// 銀行貸款
#include#include 
#include#includeusing namespace std;

bool check(int x, int y, int n, double mid) {
	double t = 0.0;
	for (int i = 1; i<= n; i++) {
		t += (double)(y / pow(mid, i));
	}
	if (t >x) return true;
	else return false;
}

double half_search(int x, int y, int n) {
	if (x == n * y) return 1.0;
	double left = 1.0;
	double right = 11.0;
	double mid = 0.0;
	double precision = 1e-4;
	while (right - left >precision) {
		mid = (right - left) / 2.0 + left;
		if (check(x, y, n, mid)) left = mid;
		else right = mid;
	}
	return left;
}

int main() {
	int x, y, n;
	cin >>x >>y >>n;
	cout<< fixed;
	cout<< setprecision(1)<< (half_search(x, y, n) - 1.0) * 100;
	return 0;
}

實(shí)驗(yàn)四防御導(dǎo)彈

動(dòng)態(tài)規(guī)劃：

// 動(dòng)態(tài)規(guī)劃
#include#include
#includeusing namespace std;

int main() {
    int n;
    cin >>n;
    vectormissiles(n);
    vectordp(n);
    for(int i = 0; i< n; i++) {
        cin >>missiles[i];
    }
    int res = 0;
    for(int i = 0; i< n; i++) {
    	dp[i] = 1;
    	for(int j = 0; j< i; j++) {
    		if(missiles[j]< missiles[i]) {
    			dp[i] = max(dp[i], dp[j] + 1);
    		}
    	}
    	res = max(res, dp[i]);
    }
    cout<< res;
    return 0;
}

模擬：?

// 模擬
#include#includeusing namespace std;

int main() {
    int n;
    cin >>n;
    vectormissiles(n);
    vectorsystems;
    for(int i = 0; i< n; i++) {
        cin >>missiles[i];
    }
    for(int i = 0; i< n; i++) {
    	int high = 30001;
        int index = -1;
    	int len = systems.size();
    	for(int j = 0; j< len; j++) {
    		if(systems[j] >= missiles[i] && systems[j]< high) {
                high = systems[j];
    			index = j;
    		}
    	}
    	if(index == -1) systems.emplace_back(missiles[i]);
    	else systems[index] = missiles[i];
    }
    cout<< systems.size();
    return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

新聞名稱：北京科技大學(xué)算法分析與設(shè)計(jì)計(jì)蒜客-創(chuàng)新互聯(lián)
URL標(biāo)題：http://muchs.cn/article32/dspcsc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信公眾號(hào)、品牌網(wǎng)站設(shè)計(jì)、品牌網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作、企業(yè)建站、靜態(tài)網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容