以下题目的解法均是他人解法，并非本人贡献
[编程题]数列还原
牛牛的作业薄上有一个长度为 n 的排列 A，这个排列包含了从1到n的n个数，但是因为一些原因，其中有一些位置（不超过 10 个）看不清了，但是牛牛记得这个数列顺序对的数量是 k，顺序对是指满足 i < j 且 A[i] < A[j] 的对数，请帮助牛牛计算出，符合这个要求的合法排列的数目。
输入描述:
每个输入包含一个测试用例。每个测试用例的第一行包含两个整数 n 和 k（1 <= n <= 100, 0 <= k <= 1000000000），接下来的 1 行，包含 n 个数字表示排列 A，其中等于0的项表示看不清的位置（不超过 10 个）。
输出描述:
输出一行表示合法的排列数目。
输入例子:
5 5 4 0 0 2 0
输出例子:
2
#include<iostream> #include<vector> using namespace std; bool find(vector<int> v,int n) //查询v中是否存在整数n { for(int i = 0;i<v.size();++i) if(v[i]==n) return true; return false; } vector<vector<int>> pv; //全局变量 void Perm(vector<int> &v,int st) //对v中的数字进行全排列 { if(st == v.size()) pv.push_back(v); else { for(int i = st;i<v.size();++i) { swap(v[i],v[st]); Perm(v,st+1); swap(v[i],v[st]); } } } void change(vector<int> &v,vector<int> subv,vector<int> vpos)//将v中的0用全排之后的数字分别代替 { for(int i = 0;i<vpos.size();++i) v[vpos[i]] = subv[i]; } int cal(vector<int> v) //计算顺序对的个数 { int cnt = 0; for(int i = 0;i<v.size()-1;++i) for(int j = i+1;j<v.size();++j) if(v[i]<v[j]) ++cnt; return cnt; } int main() { int n,k,tmp; while(cin>>n>>k) { vector<int> v,subv,vpos; for(int i = 0;i<n;++i) { cin>>tmp; v.push_back(tmp); } for(int i = 0;i<v.size();++i) if(v[i]==0) vpos.push_back(i); //记录下vector<int>中0的位置 for(int i = 1;i<=n;++i) if(!find(v,i)) subv.push_back(i); Perm(subv,0); vector<int> vcnt; for(int i = 0;i<pv.size();++i) { change(v,pv[i],vpos); vcnt.push_back(cal(v)); } int vcntk = 0; for(int i = 0;i<vcnt.size();++i) if(vcnt[i]==k) ++vcntk; cout<<vcntk<<endl; } return 0; }
以下是我自己写了一遍的代码
#include<iostream> #include<vector> #include<set> using namespace std; void getBurPos(const vector<int> &arr, vector<int> &Bur, vector<int> &pos); void Per(vector<int>& Bur, int index); void swap(int &A1, int &A2); int getRes(vector<int> arr, vector<int> pos, int n, int k); vector<vector<int>> arrPer; int main() { int n, k; while (cin >> n >> k) { vector<int> arr; int temp; for (int i = 0; i<n; i++) { cin >> temp; arr.push_back(temp); } vector<int> Bur, pos; getBurPos(arr, Bur, pos); Per(Bur, 0); int res = getRes(arr, pos, n, k); cout << res << endl; } return 0; } void getBurPos(const vector<int> &arr, vector<int> &Bur, vector<int> &pos) { set<int> Mark; for (int i = 0; i<arr.size(); i++) { if (arr[i] != 0) Mark.insert(arr[i]); else pos.push_back(i); } for (int i = 1; i<=arr.size(); i++) { if (Mark.find(i) == Mark.end()) Bur.push_back(i); } return; } void Per(vector<int>&Bur, int index) { if (index == Bur.size()) { arrPer.push_back(Bur); return; } for (int i = index; i<Bur.size(); i++) { swap(Bur[index], Bur[i]); Per(Bur, index + 1); swap(Bur[index], Bur[i]); } return; } void swap(int &A1, int &A2) { int temp = A1; A1 = A2; A2 = temp; return; } int getRes(vector<int> arr, vector<int> pos, int n, int k) { int res = 0; int len = pos.size(); for (int i = 0; i<arrPer.size(); i++) { for (int j = 0; j<len; j++) { arr[pos[j]] = arrPer[i][j]; } int cnt = 0; for (int j = 0; j<n; j++) for (int k = j + 1; k<n; k++) { if (arr[j]<arr[k]) cnt++; } if (cnt == k) res++; } return res; }
[编程题]合唱团
有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？
输入描述:
每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含 n 个整数，按顺序表示每个学生的能力值 ai
（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。
输出描述:
输出一行表示最大的乘积。
输入例子:
3 7 4 7 2 50
输出例子:
49
f [ i ] [ j ] [ 最大 / 最小 ]
分别表示，以第i个人为最后一个（也是必选的）人，加上这个人，已经选了 j 个人，最大可能的乘积和最小可能的乘积。
#include <stdio.h> #include <ctype.h> #include <string.h> #include <stdlib.h> #include <limits.h> #include <math.h> #include <algorithm> using namespace std; typedef long long ll; int a[55]; ll f[55][15][2]; int main(){ int n,kk,d; scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d",&a[i]); } scanf("%d%d",&kk,&d); ll ans=0; for(int i=1;i<=n;i++){ f[i][1][0]=f[i][1][1]=a[i]; for(int j=2;j<=kk;++j){ for(int k=i-1;k>=max(i-d,1);--k){ f[i][j][0]=max(f[i][j][0],max(f[k][j-1][0]*a[i],f[k][j-1][1]*a[i])); f[i][j][1]=min(f[i][j][1],min(f[k][j-1][0]*a[i],f[k][j-1][1]*a[i])); } } ans=max(ans,max(f[i][kk][0],f[i][kk][1])); } printf("%lld ",ans); return 0; }