中国矿业大学2021学年算法设计与分析实验课OJ

1.Contest2411 - 毕老师算法A作业一
传送门在这里
题目总览:
中国矿业大学2021学年算法设计与分析实验课OJ
文章图片

A.进制转换

#include using namespace std; long Revert(long x) { long ans = 0; long mutiply = 1; while(x) { ans += ((x%8) * mutiply); mutiply *= 10; x /= 8; } return ans; } int main() { int x, ans; cin>>x; ans = Revert(x); cout<

B.排列问题
// B.排列问题 #include //奇怪之处就在于基本上所有的代码只要用了这个头文件就不再写其他头文件了。 using namespace std; vector ans; void Perm(string str, int low, int high) { if(low == high) { ans.push_back(str); return; } for(int i=low; i<=high; ++i) { if(i>0 && str[i]==str[i-1]) continue; //判断重复 swap(str[i], str[low]); Perm(str, low+1, high); swap(str[i], str[low]); } } int main() { string str; cin>>str; str.pop_back(); sort(str.begin(), str.end()); Perm(str, 0, str.size()-1); sort(ans.begin(), ans.end()); for(const auto x:ans) cout<

C.快速幂
#include using namespace std; const long long mm = 100000007; typedef long long ll; ll mostfastPow(ll base, ll power) { ll result = 1; while(power>0) { if(power&1) { power = power - 1; result = result * base % mm; } power >>= 1; base = base * base % mm; } return result; } ll myPow(int x) { ll ans = 0; for(int i=1; i<=x; ++i) { ans += mostfastPow(i, i); } return (ans+1)%mm; } int main() { int x; while(scanf("%d", &x)) { cout<

D.求第k小
// D.求第k个小的数 #include using namespace std; int Partition(int a[], int low, int high); template int RandomizedPartition(Type a[], int p, int r); template void RandomizedQuickSort(Type a[], int p, int r); template Type RandomizedSelect(Type a[], int p, int r, int k); int main() { int a[100], n; while(~scanf("%d", &n)) { memset(a, 0, sizeof(a)); for(int i=0; i // void RandomizedQuicksort(Type a[], int p, int r)//随机快排 // { //if(p Type RandomizedSelect(Type a[], int p, int r, int k)//随机划分,选择 { if(p == r) return a[p]; int loc = RandomizedPartition(a, p ,r); int count = loc-p+1; //count为a[p:loc]中的元素个数 if(k<=count) return RandomizedSelect(a, p, loc, k); else return RandomizedSelect(a, loc+1, r, k-count); }

E.沙子的质量
#include using namespace std; const int inf=0x3f3f3f3f; int a[1005],sum[1005]={0}; int f[1005][1005]; int main() { int n; cin>>n; for(int i=1; i<=n; i++){ cin>>a[i]; } //初始化赋值为最大值 memset(f,inf,sizeof(f)); for(int i=1; i<=n; i++){ f[i][i]=0; sum[i]=sum[i-1]+a[i]; } //区间dp,首先确定区间长度len,区间长度便是动态规划的阶段。 for(int len=2; len<=n; len++){//阶段:区间长度len for(int L=1; L<=n-len+1; L++){ //状态左端点L取值范围 int r=L+len-1; //区间右端点r for(int k=L; k

F.最长公共子序列
// F.最长公共子序列 #include using namespace std; int longestCommonSubsequence(string a, string b) { int M = a.size(); int N = b.size(); vector> dp(M+1, vector(N+1, 0)); for(int i=1; i<=M; ++i) { for(int j=1; j<=N; ++j) { if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1]+1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } return dp[M][N]; } int main() { string a, b; cin>>a>>b; cout<

G.sort
// Sort #include using namespace std; const int Maxn = 1000001; int a[Maxn]; int main() { int n, m; while(~scanf("%d%d", &n, &m)) { memset(a, 0, sizeof(a)); for(int i=0; i0; --i) { if(a[i]) { if(m>1) printf("%d ", i-500000); else printf("%d\n", i-500000); m--; } } } return 0; }

H.Joseph
// 约瑟夫环 #include using namespace std; const int maxn = 15; int num[maxn]; int main() { for(int i=1; i<=14; ++i) { int m = i+1; //报号数从i+1开始 int sum = i*2; //总人数sum int j,pre=0,cur=0; //pre表示之前杀死的一个人,cur表示当前杀死的人的位置 for(j = 0 ; j < i ; ++j) //一共要杀死i个人 { cur = (pre+m-1)%(sum-j); //sum-j表示剩余的人数//牢记此表达式! cur = (pre+m-1)%(sum-j) if(cur

I.Factstone Benchmark
// Factstone等级被定义为这样的最大整数n,使得n!可以表示为一个计算机字中的无符号整数(比如1960年的4位计算机可表示3!=6,而不能表示4!=24)。 // n! < pow(2, m) m为多少位计算机,求出最大的n值 // 使用对数计算 ln(n!) < mlog(2) 大大减少数值 即ln(n)+ln(n-1)+...+ln(1) < mln(2) #include using namespace std; int Rating(int year) { int m = pow(2, (year-1940)/10); cout<year) { if(year==0) break; cout< /*int main(){ double sum; for (int i = 4, j = 0; j <= 20; i *= 2, j++){ int k = 1; sum = 0; while (sum < i){ sum += log2(k); k++; } printf("%d\n", k - 2); } }*/ int main(){ int year; int ans[21] = { 3, 5, 8, 12, 20, 34, 57, 98, 170, 300, 536, 966, 1754, 3210, 5910, 10944, 20366, 38064, 71421, 134480, 254016 }; while (scanf("%d", &year) && year != 0){ getchar(); year = (year - 1960) / 10; printf("%d\n", ans[year]); } return 0; }

J.Ants
// J.Ants // 我傻了,很简单的问题:蚂蚁相遇之后往相反方向走,其实并没有什么影响,因为蚂蚁若是按照原方向走本来还是要走这么远,只是换了一只蚂蚁走而已. // 我们不必要关心具体的蚂蚁,不管它相遇不相遇,其实结果就是一样的,我们可以认为是保持原样交错而过 #include #include using namespace std; int main() { int num; cin>>num; while(num--) { int len,n; int max1=0,min1=0; cin>>len>>n; for(int i=0; i>pos; max1 = max(max1, max(pos, len-pos)); //找每只蚂蚁距离两端的最大值max(pos, len-pos),在这些最大值里面找到最大的 min1 = max(min1, min(pos, len-pos)); //找每只蚂蚁距离两端的最小值min(pos, len-pos),在这些最小值里面找到最大的 } cout<

K.Matches Game
// Bouton定理:先手能够在非平衡尼姆博弈中取胜,而后手能够在平衡的尼姆博弈中取胜。 // 具体解释请访问: [乔治的编程小屋---尼姆博弈](http://www.pgcode.top/2021/09/16/%e5%b0%bc%e5%a7%86%e5%8d%9a%e5%bc%88/) #include using namespace std; int main() { int n, a; while(scanf("%d", &n)!=EOF) { int ans = 0; for(int i=0; i

L.Sort2
// Sort2 #include using namespace std; const int Maxn = 1000001; int a[Maxn]; int main() { int n, m; while(~scanf("%d%d", &n, &m)) { for(int i=0; i0; --i) { if(a[i]) { for(int j=0; j1) printf("%d ", i-500000); else printf("%d\n", i-500000); m--; } } } } return 0; }

2.Contest2417 - 毕老师算法A作业二
传送门在这里
题目总览:
中国矿业大学2021学年算法设计与分析实验课OJ
文章图片

A.单词排序
// A.单词排序 #include #include #include #include using namespace std; int main() { int n; cin>>n; vector vec; string str; for(int i=0; i>str; vec.push_back(str); } sort(vec.begin(), vec.end()); for(const auto x:vec) cout<

B.求数组的最长递减子序列
// B.求数组的最长递减子序列(注意不是不递增序列) #include #include #include using namespace std; // DP int PosOfLDS(vector &nums, vector &memo)//返回最长递减子序列最后一个元素的下标,然后 { int n = nums.size(); if(n == 0) return 0; vector dp(n, 1); // vector memo(n, -1); for(int i=0; i &nums, vector &memo, int pos) { if(memo[pos] == -1) { cout< nums(n); for(int i=0; i memo(n, -1); int max_pos = PosOfLDS(nums, memo); PrintOfLDS(nums, memo, max_pos); } system("pause"); return 0; }// // 方法二.找出与降序排好的数组的最长公共子序列 // const int Size = 1010; //尽量用全局变量 // int DP[Size][Size]; // int DIR[Size][Size]; // bool compare(int a, int b)//降序排列 // { //return a>b; // } // int LCS_length(vector &a, vector &b) // { //int M = a.size(); //int N = b.size(); //for(int i=1; i<=M; i++) //{ //for(int j=1; j<=N; j++) //{ //if(a[i-1] == b[j-1]) //{ //DP[i][j] = DP[i-1][j-1] + 1; //DIR[i][j] = 1; //} //else if(DP[i-1][j] >= DP[i][j-1]) //{ //DP[i][j] = DP[i-1][j]; //DIR[i][j] = 2; //} //else //{ //DP[i][j] = DP[i][j-1]; //DIR[i][j] = 3; //} //} //} //return DP[M][N]; // } // void LCS(vector &a, int i, int j) // { //if(i==0 || j==0) return; //if(DIR[i][j] == 1) //{ //LCS(a, i-1, j-1); //cout< A(a, a+n), B(b, b+n); //cout<

C.矩形滑雪场
#include #include using namespace std; const int maxn = 100; int r, c; int max_len[maxn][maxn], mp[maxn][maxn]; int get_len(int i, int j) { if (max_len[i][j]) { return max_len[i][j]; } int max_neighbor = 0; if (i-1 >= 0 && mp[i][j] > mp[i-1][j]) { max_neighbor = max(max_neighbor, get_len(i-1, j)); } if (i+1 < r && mp[i][j] > mp[i+1][j]) { max_neighbor = max(max_neighbor, get_len(i+1, j)); } if (j-1 >= 0 && mp[i][j] > mp[i][j-1]) { max_neighbor = max(max_neighbor, get_len(i, j-1)); } if (j+1 < c && mp[i][j] > mp[i][j+1]) { max_neighbor = max(max_neighbor, get_len(i, j+1)); } max_len[i][j] = max_neighbor + 1; return max_len[i][j]; } int main() { //freopen("test.txt", "r", stdin); cin >> r >> c; int i, j; for (i=0; i> mp[i][j]; } } int res = 0; for (i=0; i

D.Homework
#include using namespace std; bool cmp(pair a, pair b) { return a.second/a.first > b.second/b.first; } int main() { int M, N; while(scanf("%d%d", &M, &N) && (M && N)) { vector> vec; double time, value; for(int i=0; i(time, value)); } sort(vec.begin(), vec.end(), cmp); double TimeTotal = N; double ValueTotal = 0; //double类型,如果写为int类型答案错误 for(const auto x:vec) cout<<"("< x:vec) { if(TimeTotal-x.first >= 0) { cout<<"Flag1"<

E.区间包含问题
// E.区间包含问题 // 贪心算法类似于活动安排问题 #include using namespace std; const int maxn = 10010; struct Node { int left, right; }node[maxn]; bool cmp(Node a, Node b) { return a.right < b.right; } int main() { int n, m; scanf("%d %d", &n, &m); for(int i=0; i=pos && node[j].right<=r) { cout<

F.最长子序列
// F.最长子序列(最大子段和) #include using namespace std; // 1.递归分治法 // f(i) = max(f(i-1)+nums[i], nums[i])考虑f(i-1)带来的是正能量还是负能量 // f(i) 代表以第 i 个数结尾的「连续子数组的最大和」,那么很显然我们要求的答案就是: // max(0-i-1){f[i]} int maxSubArray(vector &nums) { int n = nums.size(); if(n==0) return {}; if(n==1) return nums[0]; vector f(n); f[0] = nums[0]; for(int i=1; i &nums) { int n = nums.size(); if(n==0) return {}; int pre = 0, maxAns = nums[0]; for(const intx:nums) { pre = max(pre+x, x); //pre记录当前x前面的连续子数组的最大和,即f[i-1],不断更新. 类似于滚动数组 maxAns = max(maxAns, pre); } return maxAns; } int main() { int n; while(~scanf("%d", &n)) { vector nums(n); for(int i=0; i

G.元素整除问题
// G.元素整除问题 #include using namespace std; // O(n^2) int main() { int a[20]; for(int i=0; i<20; i++) scanf("%d", &a[i]); sort(a, a+20); for(int i=1; i<20; i++) { for(int j=0; j

H.渊子赛马
// H.渊子赛马 #include using namespace std; int main() { int n; while(scanf("%d", &n) && n) { int *a = new int[n], *b = new int[n]; for(int i=0; ib[i])//找到一个最近的大于b[i]的 { count++; pos = j; cout<<"count:"<
I.The hardest problem ever
// I.?-???ü?? #include using namespace std; int main() { freopen("I_in.txt","r",stdin); freopen("I_out2.txt","w",stdout); // string model = "VWXYZABCDEFGHIJKLMNOPQRSTU"; string str; while(cin>>str) { if(str=="ENDOFINPUT") break; if(str=="START") continue; if(str=="END") { printf("\n"); continue; } for(int i=0; i

J.Rock-Paper-Scissors Tournament
// J.Rock-Paper-Scissors Tournament #include #include #include using namespace std; #define mm(a) memset(a, 0, sizeof(a)); int i, j, n, k; string s; int t = 0; int win[105] = {0}; int lose[105] = {0}; int main() { // freopen("J_in.txt", "r", stdin); // freopen("J_out.txt", "w", stdout); while(1) { scanf("%d%d", &n, &k); if(n==0) break; mm(win); mm(lose); if(t++) printf("\n"); for(i=0; i

K.Balloon Robot
// K.Balloon Robot #include using namespace std; /* 假设初始机器人从位置1开始,计算做完每道题总共有多少不开心值 将不开心值从小到大排序 然后枚举每一道题解出时,机器人就在座位旁的情况。 对于第i道题目,因为位置往后走,后面的题目的时间就会减少tid[i],前面的题目的时间就会增加m-tid[i]. 因此递推式是sum - (p-i)*tid[i] + i*(m-tid[i]) = sum + m * (i - 1) - tid[i] * p; */ typedef long long ll; const int N = 2e5+10; ll tid[N], id[N]; //id数组用来记录每个队伍所在的位置 int main() { freopen("K_in.txt","r",stdin); int t; scanf("%d", &t); //测试用例组数 while(t--) { ll n, m, p; scanf("%lld%lld%lld", &n, &m, &p); //n个队伍,m个位置,一共解决了p个题目 for(int i=1; i<=n; ++i) scanf("%lld",&id[i]); //n个队伍分别在哪几个位置 ll ans=1e18, sum = 0; for(int i=1; i<=p; i++) { ll a,b; scanf("%lldlld", &a, &b); tid[i] = (id[a]-1-b+m)%m; //计算不开心值,不开心值=位置a-第一个位置-AC的时间 sum += tid[i]; } sort(tid+1, tid+p+1); for(int i=1; i<=p; ++i) ans = min(ans, sum+m*(i-1)-tid[i]*p); //sum = sum-(p-i)*tid[i]+i*(m-tid[i]) = sum+m*(i-1)-tid[i]*p printf("%lld\n", ans); } }

2.Contest2420 - 毕老师算法A作业三
传送门在这里
题目总览:
中国矿业大学2021学年算法设计与分析实验课OJ
文章图片

A.Brackets Sequence
#include #include #include #include #define INF 0x3f3f3f3f using namespace std; int f[105][105],pos[105][105]; char s[105]; void fun(int x,int y) { if(x>y) return; if(x==y){ if(s[x]=='('||s[x]==')') printf("()"); if(s[x]=='['||s[x]==']') printf("[]"); } else if(x0; i--){ s[i]=s[i-1]; f[i][i]=1; } for(int l=1; l<=len; l++){ for(int i=1; i<=len-l; i++){ int j=l+i; f[i][j]=INF; if((s[i]=='('&& s[j]==')')||(s[i]=='['&&s[j]==']')){ if(f[i+1][j-1]

B.Dollars
// B.Dollars #include using namespace std; int money[] = {1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000}; //除以五,1美元等于100美分 const int N = 6010; long long f[N]; int main() { std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // 打表法 f[0] = 1; for(int i=0; i<=10; i++) for(int j=money[i]; j<=6000; j++) f[j] += f[j-money[i]]; double ans; while(cin>>ans && ans!=0) { int pos = (ans*100)/5; printf("%6.2lf%17lld\n", ans, f[pos]); } return 0; }

C.Longest Match
// C.Longest Match #include using namespace std; vector split(string str)//将一个字符串从空格处分开,非字符也算作空格 { vector vec; int len = str.length(); bool flag = true; //表示一个新单词开始与否 int start = 0; //每个单词开始的下标 for(int i=0; i

D.History Granding
#include using namespace std; int order[30]; int node[30],arry[30][30]; int main() { int num; cin>>num; int i,j,k; for(i=0; i>k; order[k-1]=i+1; } while(cin>>k) { node[k-1]=1; for(i=1; i>k; node[k-1]=i+1; } memset(arry,0,sizeof(arry)); for(i=1; i<=num; i++) { for(j=1; j<=num; j++) { if(node[i-1]==order[j-1]) arry[i][j]=arry[i-1][j-1]+1; else arry[i][j]=max(arry[i-1][j],arry[i][j-1]); } } cout<

E.滑雪
#include #include #include using namespace std; int n ,m; struct node{ int x; int y; int data; }; bool cmp(node a, node b){ return a.data < b.data; } bool check(int x, int y){ if( x >= 1 && y >= 1 && x <= n && y <= m) return 1; else return 0; } int main (){ int high[105][105]; int maxLen[105][105]; int to[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; int ans = 1; cin >> n >> m; int k = 0; node s[10006]; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ scanf("%d", &high[i][j]); s[++k].data = https://www.it610.com/article/high[i][j]; s[k].x = i; s[k].y = j; maxLen[i][j] = 1; } } sort(s + 1, s + k + 1, cmp); for(int i = 1 ; i <= k; i++){ int x1, y1; for(int j = 0; j < 4; j++){ int x = s[i].x; int y = s[i].y; x1 = x + to[j][0]; y1 = y + to[j][1]; if(check(x1, y1)){ if(high[x][y]> high[x1][y1]){ maxLen[x][y] = max(maxLen[x1][y1] + 1, maxLen[x][y]); ans = max(ans, maxLen[x][y]); } } } } cout << ans <

F.Wavio Sequence
// Wavio Sequence // 贪心算法 + 二分查找 求最长上升子序列的长度O(nlogn) // 考虑一个简单的贪心,如果我们要使上升子序列尽可能的长,则我们需要让序列上升得尽可能慢,因此我们希望每次在上升子序列最后加上的那个数尽可能的小。 // 维护一个一维数组B,并且这个数组是动态扩展的,初始大小为1,B[i]表示最长上升子序列长度是i的所有子串中末尾最小的那个数, // 我们依次遍历数组 nums 中的每个元素,并更新数组 B 和 len 的值。如果nums[j] > B[len] 则更新 len = len + 1 // 否则在 B[1...len] 中 找到 B[i-1] < nums[j] using namespace std; const int inf = 10000; int lengthOfLIS(vector &nums, int end)//得到数组nums[1..end]的最大上升子序列长度 { int n = nums.size(); if(n0) return 0; vector B(n+1, 0); B[1] = nums[0]; int len = 1; //记录最长上升子序列的长度 for(int i=1; i B[len]) B[++len] = nums[i]; else { int l = 1, r = len, pos = 0; while(l <= r) { int mid = (l+r) >> 1; if(B[mid] < nums[i]) { pos = mid; l = mid+1; } else r = mid-1; } B[pos+1] = nums[i]; } } return len; } int Ans(vector &nums) { int n = nums.size(); vector LIS_length; vector LIS_length_Reverse; for(int i=1; i<=n; i++) LIS_length.push_back(lengthOfLIS(nums, i)); //i为end,所以i<=n reverse(nums.begin(), nums.end()); //反转数组 for(int i=1; i<=n; i++) LIS_length_Reverse.push_back(lengthOfLIS(nums, i)); for(int i=0; i>n && n) { vector nums(n); for(int i=0; i>nums[i]; cout<

【中国矿业大学2021学年算法设计与分析实验课OJ】G.FatMouse's Trade
#include #include #include #include using namespace std; int N,M; struct node{ int x,y; double s; }a[1000]; double cmp(node aa,node bb){ return aa.s>bb.s; } int main(){ double sum,ans; while(~scanf("%d %d",&M,&N)){ if(M==-1&&N==-1) break; for(int i=0; i

H.Schedule
// Schedule // 贪心算法 // 题目大意:有 N个时间表,他们分别有自己的开始时间和结束时间, // 同时,也有很多机器,时间表上的时间是使用机器的时间,然而, // 一台机器不能在重复的时间被使用,所以,要完成时间表的任务,可能需要多台机器, // 题目要求的就是符合要求的最少机器数和相应时间之和(机器等待的时间也算)。 #include using namespace std; struct Node { int T; int flag; //1表示该节点是开始时间,2表示是结束时间 }nodes[200000]; bool cmp(Node &a, Node &b) { if(a.T != b.T) return a.T b.flag; } int main() { int x; scanf("%d", &x); while(x--) { int count; int pos = 0; //表示节点数组的位置 int machine = 0; int ans_mach = 0; long long ans_sum = 0; stack endtime; //结束时刻存放在栈中 scanf("%d", &count); while(!endtime.empty()) endtime.pop(); //保证endtime数组清空 for(int i=0; i
I.Gene Assembly
#include using namespace std; int n; struct p { int start,end,pos; }s[1000]; bool cmp(p a,p b) { return a.end
中国矿业大学2021学年算法设计与分析实验课OJ
文章图片
中国矿业大学2021学年算法设计与分析实验课OJ
文章图片

(~ ̄▽ ̄)~
除了几个题因为时间缘故或者是太难了的原因不是自己写的,其余的都是自己的劳动成果.由于最近时间紧张,题解就不写了.
如果大家觉得本篇文章对自己有所帮助的话,不妨去我的个人博客---乔治的编程小屋逛逛吧,相信你会发现更精彩的内容.

    推荐阅读