北京科技大学 算法分析与设计 计蒜客平时作业及实验代码 2022年（仅供参考）

十余年的灵寿网站建设经验，针对设计、前端、开发、售后、文案、推广等六对一服务，响应快，48小时及时工作处理。全网整合营销推广的优势是能够根据用户设备显示端的尺寸不同，自动调整灵寿建站的显示方式，使网站能够适用不同显示终端，在浏览器中调整网站的宽度，无论在任何一种浏览器上浏览网站，都能展现优雅布局与设计，从而大程度地提升浏览体验。成都创新互联从事“灵寿网站设计”,“灵寿网站推广”以来，每个客户项目都认真落实执行。

目录

作业一

买房子

[USACO Open08]农场周围的道路

国王的魔镜 

作业二

蜗牛旅游

[NOIP2001]求先序排列

作业三 

二分查找

白菜君的三角形

压缩歌曲

作业四 

踩方格

最长上升子序列

作业五

划分整数

神奇的口袋

作业六

代码填空：全排列

自然数拆分

文具店 

实验

实验一 书架

实验二 封印之门

实验三 银行贷款

实验四 防御导弹

---

作业一 买房子

//买房子
#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]农场周围的道路

//[USACO Open08]农场周围的道路
#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;
}

国王的魔镜 

//国王的魔镜
#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;
}

作业二 蜗牛旅游

//蜗牛旅游
#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);
        //遍历左子树
        CreatePreorder(inorder.substr(0, k), post.substr(0, k));
        //遍历右子树
        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;
}

作业三  二分查找

//二分查找
#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;
}

作业四  踩方格

// 踩方格
#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;
}

最长上升子序列

// 最长上升子序列
#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<< ' '; 
    }
}

作业五 划分整数

// 划分整数
#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;
}

作业六 代码填空：全排列

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

自然数拆分

// 自然数拆分
#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;
	// 字符串长度与水彩笔数相等
	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;
}

实验 实验一 书架

// 书架
#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;
}

实验二 封印之门

本题要求使用回溯法解题，但实际上使用 Dijkstra 或 Floyd 算法更好

Floyd算法：

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

#define MAXN 26

vector>shortPath(MAXN, vector(MAXN, MAXN)); // 各顶点间的最短距离

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;
}

回溯法： 

// 回溯 
// 有一个用例一直过不了，鉴定为恶心人
// 下列代码仍可优化，有兴趣可以试试
#include#include
#includeusing namespace std;

#define MAXN 26

int shortPath[MAXN][MAXN]; // 各顶点间的最短距离

void dfs(int init, int target, int now, int num) {
	if(now == target) {
		shortPath[init][target] = min(shortPath[init][target], num);
		return;
	}
	// 剪枝: 超过目前 shortPath[init][target] 必不可能产生新的最小值
	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++) {
			// 相等或路径已存在则无需继续寻找
			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++) {
		// 相等无需操作，跳过
		if(initial[i] == target[i]) continue;
		int a = initial[i] - 'a';
		int b = target[i] - 'a';
		// 无法操作，退出循环，输出 -1
        if(shortPath[a][b] == 26) {
            res = -1;
            break;
        }
		res += shortPath[a][b];
	}
	cout<< res;
	return 0;
}

实验三 银行贷款

// 银行贷款
#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;
}

实验四 防御导弹

动态规划：

// 动态规划
#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;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章题目：北京科技大学算法分析与设计计蒜客-创新互联
文章出自：http://kswjz.com/article/dspcsc.html