文远知行8月20日笔试

感觉是最近写的最难的题。。。

2个小时就三道编程题

第一题：

是设定两个针对0或1的计算操作(1）或运算（2）与运算,与运算的优先级比或高。

给定一个包含+,* ,(,)是个符号的字符串表示省略01的计算表达式，+代表或运算，*代表与运算。要求填充01，统计最后表达式计算值为0的个数。

思路：这道题有点像加乘计算器，只不过因为要统计个数，所以数字应该是一个pair。 pair.first 代表0的个数，pair.second代表1的个数。然后利用双栈存储nums和ops。好久没写计算器这道题了，这个破题就写了1个小时。

第二题：

给定n个坐标点，求构成简单多边形的最大边长。

这道题我感觉的思路是先算出两点之间距离，然后再dfs遍历取边。比较重要的是判断是否为简单多边形，也就是两个线段是否相交。然后考场上写了一个函数来判断，主要是解一个二元方程组，当时是这样写的：

bool _isInteract(pair<double, double>& a, pair<double, double>& b,
                 pair<double, double>& c, pair<double, double>& d) {
    double a11 = a.first - b.first;
    double a12 = -c.first + d.first;
    double a21 = a.second - b.second;
    double a22 = -c.second + d.second;
    double b1 = d.first - b.first;
    double b2 = d.second - b.second;
    double delta =  a11 * a22 - a12 * a21;
    a11 = a22 / delta;
    a12 = a21 / delta;
    a21 = a12 / delta;
    a22 = a11 / delta;
    double x1 = a11 * b1 + a12 * b2, x2 = a21 * b1 + a22 * b2;
    return x1 > 0 && x1 < 1 && x2 > 0 && x2 < 1;
}

然后整体上最后是这样的：

#include <climits>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
double final_res = 0;
double temp_res = 0;
vector<pair<int, int>> edges;
int n;

bool _isInteract(pair<double, double>& a, pair<double, double>& b,
                 pair<double, double>& c, pair<double, double>& d) {
    double a11 = a.first - b.first;
    double a12 = -c.first + d.first;
    double a21 = a.second - b.second;
    double a22 = -c.second + d.second;
    double b1 = d.first - b.first;
    double b2 = d.second - b.second;
    double delta =  a11 * a22 - a12 * a21;
    a11 = a22 / delta;
    a12 = a21 / delta;
    a21 = a12 / delta;
    a22 = a11 / delta;
    double x1 = a11 * b1 + a12 * b2, x2 = a21 * b1 + a22 * b2;
    return x1 > 0 && x1 < 1 && x2 > 0 && x2 < 1;
}

double dis(pair<double, double>& a, pair<double, double>& b) {
    double res = pow(a.first - b.first, 2) + pow(a.second - b.second, 2);
    return sqrt(res);
}
bool isInteract(vector<pair<double, double>>& nodes,
                pair<double, double>& c, pair<double, double>& d) {
    for (auto& edge : edges) {
        if (_isInteract(nodes[edge.first], nodes[edge.second], c, d))
            return true;
    }
    return false;
}

bool _check(vector<int>& is_vis){
    for(auto& iter: is_vis)
        if(iter != 2)
            return false;
    return true;
}

void dfs(vector<vector<bool>>& is_vis_edge, vector<pair<double, double>>& nodes,
         vector<vector<double>>& adj,
         vector<int>& is_vis) {
    if (edges.size() == n) {
        if(_check(is_vis))
            final_res = max(final_res, temp_res);
        return;
    }

    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (is_vis[i] < 2 && is_vis[j] < 2 && !is_vis_edge[i][j] &&
                    !isInteract(nodes, nodes[i], nodes[j])) {
                temp_res += adj[i][j];
                ++is_vis[i];
                ++is_vis[j];
                is_vis_edge[i][j] = true;
                edges.emplace_back(i,j);
                dfs(is_vis_edge,nodes,adj,is_vis);
                temp_res -= adj[i][j];
                --is_vis[i];
                --is_vis[j];
                is_vis_edge[i][j] = false;
                edges.pop_back();
            }

}

int main() {
    cin >> n;
    if(n <= 1){
        printf("%.2f",0.00);
        return 0;
    }
    vector<pair<double, double>> nodes(n, {0, 0});
    vector<vector<double>> adj(n, vector<double>(n, 0));
    for (int i = 0; i < n; ++i)
        cin >> nodes[i].first >> nodes[i].second;

    for (int i = 0; i < n; ++i)
        for (int j = i+1; j < n; ++j)
            adj[i][j] = dis(nodes[i], nodes[j]);
    vector<int> is_vis(n, 0);
    vector<vector<bool>> is_vis_edge(n, vector<bool>(n, false));
    dfs(is_vis_edge,nodes,adj,is_vis);
    printf("%.2f",final_res);
    return 0;
}
// 64 位输出请用 printf("%lld")

这个代码样例可以过，然后提交只过15%，不知道为啥。。。

第三题甚至没来得及看，感觉寄了。

#文远知行##Weride#