灵犀互娱笔试-8-19C++
第一题求字符数量最多的是不是质数
第二题玩家匹配问题，和要整数一个输出的数
第三题牌堆里面计算相同扑克牌的最短距离，
都是简单题全部过了。
第四题是一个矩阵求从（0，0）到（m-1,n-1）玩家可以获取最大的分数，可以从上下右三个方向走。但是可以上下互通，比如（0,0）到（m-1,0）。我是想用DFS写的，遍及所有情况，后面代码没完成，写好了一部分，但是有bug，通过0。如果有通过的，可以教我一下。
第五题，平面上有n条直线，且无三线共点，只可以相交和平行，问有多少种情况。然后说出每个情况的交点个数。排序输出。
数据形式
如果n=2,则可以为0(平行)或者1(不平行)。输出 0 1。
第五题通过。
这个题以前碰到过，具体就是动态规划来做。
需要构建 平行的集合体 和 不跟这块平行的集合体
假设你现在是n条直线： 你就要考虑 有多少平行 多少相交
如果 你有 n-x 条平行， x 条相交 {//这里指不跟前面的平行}。
那么相交的数量是
相交和平行的交点 ( n - x) * x // 不跟它平行那必然相交
x 这个集合提 有自己的平行和相交的情况。// 遍历它 nums[x]
那么 n 条直线的相交情况为 ( n - x) * x + nums[x] （其中的所用情况）
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<vector<int>> nums(21,vector<int>{0});
//nums[0] = {0};
//nums[1] = {0};
for(int n = 2; n < 21; n++){
for(int i=1; i < n; i++){ // (n-x) = i那块集合体
for(int num : nums[i]){ // 会存在重复 最后去重
nums[n].push_back(i*(n-i) + num);
}
}
}
int n;
cin >> n;
set<int> s(nums[n].begin(),nums[n].end());
//set 默认会有序的
for(auto num : s){
cout << num << " ";
}
cout << endl;
return 0;
}
类似资料：