北京科技大学算法分析与设计计蒜客-创新互联
北京科技大学 算法分析与设计 计蒜客平时作业及实验代码 2022年（仅供参考）
目录
作业一
买房子
[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]农场周围的道路
#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]求先序排列
#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://azwzsj.com/article/dspcsc.html
