4月24 腾讯全国卷笔试

//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<queue>
//#include<set>
//#include<map>
//#include<unordered_set>
//using namespace std;

// P1 33%
//int main() {
//    int m, n;
//    cin >> n >> m;
//    vector<double> a(m);
//    double ans = n;
//    for (int i = 0; i < m; i++) {
//        cin >> a[i];
//        double t = ans; //lose
//        double q = t / (1 - a[i]) - 1;
//        ans = q;
//    }
//    printf("%d", (int)ans);
//    system("pause");
//    return(0);
//}
//
//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<queue>
//#include<set>
//#include<map>
//#include<unordered_set>
//#define _for(i,j,k) for(int i=j;i<k;i++)
//using namespace std;
//
//// 60% P2
//int main() {
//    int c;
//    cin >> c;
//    vector<vector<double>> a(c, vector<double>(c));
//    vector<double> f(c);
//    _for(i, 0, c)cin >> f[i];
//    double maxV = -1; int maxI = 0;
//    _for(i,0,c){
//        _for(j, 0, c)
//            cin >> a[i][j];
//        double t = 0.0;
//        _for(j, 0, c)
//            t += f[i] * a[i][j];
//        if (t > maxV) {
//            maxV = t;
//            maxI = i;
//        }
//    }
//    cout << maxI;
//    system("pause");
//    return(0);
//}



//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<queue>
//#include<set>
//#include<map>
//#include<cmath>
//#include<unordered_set>
//#define _for(i,j,k) for(int i=j;i<k;i++)
//using namespace std;
//
//// P3 0%
//int main() {
//    int q; cin >> q;
//    double a, b, c;
//    while (q--) {
//        cin >> a >> b >> c;
//        //a = -a;
//        //b = -b;
//        /*double t1 = 2 * a * a * a / 27 + a * b / 3+c,t2=4*pow(3 * b + a * a,3)/729;
//        double a1 = (t1+sqrt(t1*t1-t2))/2;
//        double a2 = (t1-sqrt(t1*t1-t2))/2;
//       cout << pow(a1, 1.0 / 3)<<"\n";
//        cout << pow(a2, 1.0 / 3) <<"\n";
//        cout << a / 3<<"\n";
//        double x = pow(a1, 1.0 / 3) + a2 + a / 3;*/
//
//        double A = a * a - 3 * b,B=a*b-9*(-c),C=b*b-3*a*(-c);
//        double d = B * B - 4 * A * C;
//        if (d > 0) {
//            double y1 = A * a + 1.5 * (-B + sqrt(d));
//            double y2 = A * a + 1.5 * (-B - sqrt(d));
//            double x = (-a - pow(y1,1/3)-pow(y2,1/3)) / 3;
//            printf("%.8f\n", x);
//        }
//        else if (d == 0&&A!=0) {
//            double k = B / A;
//            double x1 = -a + k,x2=-k/2;
//            if (abs(x1 + a * x1 * x1 + b * x1 - c) <= 1e-7) {
//                printf("%.8f\n", x1);
//            }else printf("%.8f\n", x2);
//        }
//    }
//    system("pause");
//    return(0);
//}

//
//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<queue>
//#include<set>
//#include<map>
//#include<cmath>
//#include<unordered_set>
//#include<unordered_map>
//#define _for(i,j,k) for(int i=j;i<k;i++)
//using namespace std;
//// 区间修改，区间查询
//class TreeArray {
//private:
//	int n;
//	vector<int> tree1;
//	vector<int> tree2;
//
//	inline int lowbit(int x) {
//		return x & (-x);
//	}
//
//	void updata(int i, int val) {
//		for (int p = i; i <= n; i += lowbit(i)) {
//			tree1[i] += val;
//			tree2[i] += p * val;
//		}
//	}
//
//	int query(int i) {
//		int sum = 0;
//		for (int n = i; i > 0; i -= lowbit(i)) {
//			sum += (n + 1) * tree1[i] - tree2[i];
//		}
//		return sum;
//	}
//
//public:
//	TreeArray() {}
//	TreeArray(int n) :n(n), tree1(n + 1), tree2(n + 1) {}
//
//	// 区间修改
//	void rangeUpdate(int left, int right, int val) {
//		updata(left, val);
//		updata(right + 1, -val);
//	}
//	// 区间查询
//	int rangeQuery(int left, int right) {
//		return query(right) - query(left - 1);
//	}
//
//};
//
//// P4 100%
//int main() {
//	int n, m, t, q, le, re; cin >> n >> m;
//	vector<int> r(n), b(m);
//	set<int>s;
//	_for(i, 0, n) {
//		cin >> r[i];
//		s.insert(r[i]);
//	}
//	_for(i, 0, m) {
//		cin >> b[i];
//		s.insert(b[i]);
//	}
//	cin >> q;
//	vector<vector<int>> que;
//	_for(i,0,q) {
//		cin >> le >> re;
//		que.push_back({ le,re });
//		s.insert(le);
//		s.insert(re);
//	}
//	int id = 1;
//	unordered_map<int, int> mid;
//	for (auto i : s)
//		mid[i] = id++;
//	TreeArray red(id), blue(id);
//	_for(i, 0, n)
//		red.rangeUpdate(mid[r[i]], mid[r[i]], 1);
//	_for(i, 0, m)
//		blue.rangeUpdate(mid[b[i]], mid[b[i]], 1);
//
//	int nr, nb, an = 0, bn = 0, cn = 0;
//	_for(i, 0, q) {
//		nr = red.rangeQuery(mid[que[i][0]], mid[que[i][1]]);
//		nb = blue.rangeQuery(mid[que[i][0]], mid[que[i][1]]);
//		if (nr > nb)an++;
//		else if (nr == nb) bn++;
//		else cn++;
//	}
//	cout << an << " " << bn << " " << cn;
//	system("pause");
//	return(0);
//}


#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<unordered_set>
#define _for(i,j,k) for(int i=j;i<k;i++)
using namespace std;
struct ListNode {
    int val;
    struct ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
    
};
 struct TreeNode {
 	int val;
 	struct TreeNode *left;
 	struct TreeNode *right;
 	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 };
 // P5 最后半分钟写完提交，显示超出内存 0%
class Solution {
    vector<ListNode*> cmlist;
    vector<int> e[1001];
    void traverse(TreeNode* r) {
        if (r->left) {
            e[r->val].push_back(r->left->val);
            e[r->left->val].push_back(r->val);
            traverse(r->left);
        }
        if (r->right) {
            e[r->val].push_back(r->right->val);
            e[r->right->val].push_back(r->val);
            traverse(r->right);
        }
    }
    vector<int> find(int a, int b) {
        if (a == b) {
            return vector<int>(1,a);
        }
        queue<int> q;
        q.push(a);
        int v[1001] = { 0 };
        v[a] = -1;
        while (!q.empty()) {
            int t=q.front();
            q.pop();
            if (t == b)break;
            for (auto node : e[t]) {
                if (v[node] != 0) {
                    v[node] = t;
                    q.push(node);
                }
            }
        }
        vector<int> ans;
        while (v[b] != -1) {
            ans.push_back(b);
            b = v[b];
        }
        return ans;
    }
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 你需要返回m个指针，每个指针指向一条链，表示树上的一条链。
     * @param root TreeNode类 表示题目给出的树;
     * @param b int整型vector<vector<>> 第二维给出4个值，依次表示x,y,u,v;
     * @return ListNode类vector
     */

    vector<ListNode*> solve(TreeNode* root, vector<vector<int> >& b) {
        for (auto& q : b) {
            vector<int> p1 = find(q[0], q[1]);
            vector<int> p2 = find(q[2], q[3]);
            map<int, int> fan;
            _for(i, 0, p2.size())
                fan[p2[i]] = i;
            vector<int> cl;
            for(int i=0;i<p1.size();i++)
                if (fan.count(p1[i])) {
                    int j = fan[p1[i]];
                    while (i < p1.size() && j < p2.size() && p1[i] == p2[j]) {
                        cl.push_back(p1[i]);
                        i++, j++;
                    }
                }
            if (cl.size() == 0) {
                cmlist.push_back({});
                continue;
            }
            vector<int> cl2 = cl;
            reverse(cl2.begin(), cl2.end());
            _for(i,0,cl.size())
                if (cl[i] > cl2[i]) {
                    cl = cl2;
                    break;
                }
            ListNode* qq=new ListNode(cl[0]);
            for (int i = 1; i < cl.size(); i++)
            {
                qq->next = new ListNode(cl[i]);
                qq = qq->next;
            }
            cmlist.push_back(qq);
        }
        return cmlist;
    }
};

int main() {

    return 0;
}