灵犀互娱笔试-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;
}