第一题，并查集 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);
}