爱奇艺算法岗笔试编程题
1.输入N，然后 输入大小为N-1的数组A，只包含0和1；现在对1到N的元素进行排序得到数组P，要求：
如果 对所有A[i]=0, 有P[i] < P[i+1]; 所有A[i]=1, P[i] > P[i+1].
这样的排列是一个有效的排列，找到符合要求的有效排序的个数。输出排列个数对 (10^9+7)的模。
#include <iostream>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;
bool isValidPerm(vector<int>& perms, vector<int>& standards) {
for (int i = 0; i < standards.size(); i++) {
if (standards[i] == 0) {
if (perms[i] >= perms[i + 1])
return false;
}
else if(standards[i] == 1) {
if (perms[i] <= perms[i + 1])
return false;
}
}
return true;
}
void numberOfPermutations() {
int N;
cin >> N;
long long cnt = N-1;
int val;
vector<int> standards, perms;
while (cnt--) {
cin >> val;
standards.push_back(val);
}
cnt = 1;
while (cnt <= N) {
perms.push_back(cnt);
cnt++;
}
cnt = 0;
do {
if (isValidPerm(perms, standards))
cnt++;
} while (next_permutation(perms.begin(), perms.end()));
cout << (cnt % static_cast<long long>(pow(10.0, 9) + 7)) << endl;
}
int main() {
numberOfPermutations();
return 0;
}
输入：m,n
输出：A胜利的概率，保留5位小数（补零）
#include <iostream>
#include <iomanip>
using namespace std;
double res = 0;
void winProbality(double m, double n, double& lastRoundNotWin) {
if (m + n <= 0) return;
if (m < 0 || n < 0) return;
double total = m + n;
double curRoundWin = 0;
curRoundWin = lastRoundNotWin * (double(n) / total); //当前这轮胜利
res += curRoundWin;
lastRoundNotWin = m / total * (--m / --total); //A没赢，B没赢
double dir1 = lastRoundNotWin * (m - 1) / (total - 1);//C选了m
winProbality(m - 1, n, dir1);
double dir2 = lastRoundNotWin * n / (total - 1); //C选了n
winProbality(m, n - 1, dir2);
}
void solution() {
double m, n;
cin >> m >> n; // blue red
double lastRoundNotWin = 1;
res = 0;
winProbality(m, n, lastRoundNotWin);
cout.setf(ios::fixed);
cout << fixed << setprecision(5) << res << endl;
}
int main() {
solution();
return 0;
}
第一题AC 36%，第二题AC 9%，大佬能否告诉下问题出在哪？？？
查看13道真题和解析
