第一题，并查集 100% // // Created by Chaopeng Zhang on 2019-08-25. // #include <iostream> using namespace std; #include <vector> class Solution { public:     int findDouYouNum(vector <vector<int>> &M) {         if (!M.size())             return 0;         int n = M[0].size();         count = n;         id.resize(n);         sz.resize(n);         for (int i = 0; i < n; ++i) {             id[i] = i;             sz[i] = 1;         }         for (int i = 0; i < n - 1; ++i) {             for (int j = i + 1; j < n; ++j) {                 if (M[i][j] >= 3) {                     Union(i, j);                 }             }         }         return count;     }     int Find(int i) {         while (i != id[i])             i = id[i];         return i;     }     void Union(int i, int j) {         int p = Find(i);         int q = Find(j);         if (p == q)             return;         if (sz[p] < sz[q]) {             id[p] = q;             sz[q] += sz[p];         } else {             id[q] = p;             sz[p] += sz[q];         }         count--;     }     vector<int> id;     vector<int> sz;     int count; }; int main() {     vector<vector<int>> input;     int n;     cin>>n;     for (int i = 0; i < n; ++i) {         vector<int> v;         for (int j = 0; j < n; ++j) {             int num;             cin>>num;             v.push_back(num);         }         input.push_back(v);     }     Solution s;     cout<<s.findDouYouNum(input); } 第二题 100% // // Created by Chaopeng Zhang on 2019-08-25. // #include <iostream> using namespace std; const int mod = 1000000007; long long d[1001] = {1}; int main() {     int n;     cin >> n;     for (int i = 2; i <= n; i += 2) {         for (int j = 0; j <= i - 2; j += 2) {             d[i] = (d[i] + d[j] * d[i - 2 - j] % mod) % mod;         }     }     cout << d[n] << endl;     return 0; } 第三题 30%，后来优化了但没时间交了 // // Created by Chaopeng Zhang on 2019-08-25. // #include <iostream> #include <vector> using namespace std; class Solution { public:     vector<vector<int>> solve(vector<vector<int>> &mat, int dir) {         if (dir == 1) {             Up(mat);         } else if (dir == 2) {             Down(mat);         } else if (dir == 3) {             Left(mat);         } else {             Right(mat);         }         return mat;     }     vector<int> merge(vector<int> line) {         vector<int> ans;         vector<int> postive;         for (int i = 0; i < line.size(); ++i) {             if (line[i] > 0)                 postive.push_back(line[i]);         }         postive.push_back(0);         for (int j = 1; j < postive.size(); ++j) {             if (postive[j] == postive[j - 1]) {                 ans.push_back(2 * postive[j - 1]);                 j++;             } else {                 ans.push_back(postive[j - 1]);             }         }         for (int k = ans.size(); k < 4; ++k) {             ans.push_back(0);         }         return ans;     }     void Up(vector<vector<int>> &mat) {         for (int i = 0; i < 4; ++i) {             moveUp(mat, i);         }     }     void Down(vector<vector<int>> &mat) {         for (int i = 0; i < 4; ++i) {             moveDown(mat, i);         }     }     void Left(vector<vector<int>> &mat) {         for (int i = 0; i < 4; ++i) {             moveLeft(mat, i);         }     }     void Right(vector<vector<int>> &mat) {         for (int i = 0; i < 4; ++i) {             moveRight(mat, i);         }     }     void moveUp(vector<vector<int>> &mat, int col) {         vector<int> v;         for (int i = 0; i < 4; ++i) {             v.push_back(mat[i][col]);         }         vector<int> ans = merge(v);         for (int j = 0; j < 4; ++j) {             mat[j][col] = ans[j];         }     }     void moveDown(vector<vector<int>> &mat, int col) {         vector<int> v;         for (int i = 3; i >= 0; --i) {             v.push_back(mat[i][col]);         }         vector<int> ans = merge(v);         for (int i = 3; i >= 0; --i) {             mat[i][col] = ans[3-i];         }     }     void moveLeft(vector<vector<int>> &mat, int row) {         vector<int> v;         for (int i = 0; i < 4; ++i) {             v.push_back(mat[row][i]);         }         vector<int> ans = merge(v);         for (int j = 0; j < 4; ++j) {             mat[row][j] = ans[j];         }     }     void moveRight(vector<vector<int>> &mat, int row) {         vector<int> v;         for (int i = 3; i >= 0; --i) {             v.push_back(mat[row][i]);         }         vector<int> ans = merge(v);         for (int i = 3; i >= 0; --i) {             mat[row][i] = ans[3-i];         }     } }; int main() {     int dir;     cin >> dir;     vector<vector<int>> input;     for (int i = 0; i < 4; ++i) {         vector<int> v;         for (int j = 0; j < 4; ++j) {             int a;             cin >> a;             v.push_back(a);         }         input.push_back(v);     }     vector<vector<int>> ans;     Solution s;     ans = s.solve(input, dir);     for (auto i:ans) {         for (auto j:i) {             cout << j << " ";         }         cout << endl;     } } 第四题 还是并查集，70%， 合并那里是N^2的，不知道咋优化成logN // // Created by Chaopeng Zhang on 2019-08-25. // #include <iostream> using namespace std; #include <math.h> #include <unordered_map> #include <vector> class Solution { public:     int gcd(int i, int j) {         int min_num = min(i, j);         int max_num = max(i, j);         int temp;         while (min_num > 0) {             temp = max_num % min_num;             max_num = min_num;             min_num = temp;         }         return max_num;     }     int findCandy(vector<int> &M) {         if (!M.size())             return 0;         int n = M.size();         count = n;         id.resize(n);         sz.resize(n);         for (int i = 0; i < n; ++i) {             id[i] = i;             sz[i] = 1;         }         //n^2         for (int i = 0; i < n - 1; ++i) {             for (int j = i + 1; j < n; ++j) {                 if (gcd(M[i], M[j]) > 1) {                     Union(i, j);                 }             }         }         unordered_map<int, int> cnt;         int ans = INT32_MIN;         int id_num;         for (int k = 0; k < n; ++k) {             id_num = Find(k);             cnt[id_num] += 1;             ans = max(ans, cnt[id_num]);         }         return ans;     }     int Find(int i) {         while (i != id[i])             i = id[i];         return i;     }     void Union(int i, int j) {         int p = Find(i);         int q = Find(j);         if (p == q)             return;         if (sz[p] < sz[q]) {             id[p] = q;             sz[q] += sz[p];         } else {             id[q] = p;             sz[p] += sz[q];         }         count--;     }     vector<int> id;     vector<int> sz;     int count; }; int main() {     ios_base::sync_with_stdio(false);     cin.tie(nullptr);     Solution s;     int n;     cin>>n;     vector<int> v;     while(n)     {         int a;         cin>>a;         v.push_back(a);         n--;     }     cout<<s.findCandy(v); }