讨论/题目交流/🐱 第 13 场夜喵双周赛/
🐱 第 13 场夜喵双周赛

欢迎在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

4 分 - 加密数字
5 分 - 最小公共区域
6 分 - 近义词句子
6 分 - 不相交的握手

展开讨论

第一题 加密数字

其实题目很水找规律

  1. 将给你的数+1
  2. 写出他的二进制表示法(这题一看0101的就知道要二进制...)
  3. 去掉开头的一,就是答案
    code:
class Solution {
public:
    string encode(int num) {
        string ans;
        string tmp;
        num++;
        while (num) {
            tmp.push_back(num % 2 == 0 ? '0' : '1');
            num >>= 1;
        }
        for (int i = tmp.size() - 2; i >= 0; i--) {
            ans.push_back(tmp[i]);
        }
        return ans;
    }
};

第二题 最小公共区域

又是一个很垃圾的题目
LCA就行了...还不用优化...
code:

struct node {
    string data;
    int depth;
    int fa;
    vector<int> chi;
}TN[100001];
class Solution {
public:
    map<string, int> m;
    map<int, string> m2;
    int msize = 0;
    string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
        TN[1].depth = 0;
        TN[1].fa = 1;
        for (int i = 0; i < regions.size(); i++) {
            string a = regions[i][0];
            if (m[a] == 0) {
                msize++;
                m[a] = msize;
                m2[msize] = a;
            }
            TN[m[a]].data = regions[i][0];
            for (int j = 1; j < regions[i].size(); j++) {
                string b = regions[i][j];
                if (m[b] == 0) {
                    msize++;
                    m[b] = msize;
                    m2[msize] = b;
                }
                TN[m[b]].data = regions[i][j];
                TN[m[a]].chi.push_back(m[b]);
                TN[m[b]].fa = m[a];
                TN[m[b]].depth = TN[m[a]].depth + 1;
            }
        }
        int x = m[region1];
        int y = m[region2];
        while (TN[x].depth < TN[y].depth) {
            y = TN[y].fa;
        }
        while (TN[x].depth > TN[y].depth) {
            x = TN[x].fa;
        }
        while (1) {
            if (x == y) break;
            x = TN[x].fa;
            y = TN[y].fa;
        }
        return m2[x];
    }
};

第三题 近义词句子

本题全场最困(jian)难(dan),胆小勿入
反正我是写了101行...
经典并查集+并查集的思路的题目
老师只给你们讲了并查集的思路吗???
这题要理解思路才能将知道正解
话说"小白二号"又在骂我咯...
其实,我这代码调了50min...
其实其实,没多说的...
code:

class Solution {
public:
    int msize = 0;
    map<string, int> m;
    map<int, string> m2;
    int fa[25];
    vector<int> fa_chi[25];
    void initset() {
        for (int i = 1; i < 25; i++) {
            fa[i] = i;
        }
        return;
    }
    int findroot(int x) {
        if (fa[x] != x) return fa[x] = findroot(fa[x]);
        else return x;
    }
    void mergeset(int u, int v) {
        int x = findroot(u), y = findroot(v);
        if (x == y) return;
        fa[x] = y;
        fa_chi[y].push_back(x);
        for (int i = 0; i < fa_chi[x].size(); i++) {
            fa_chi[y].push_back(fa_chi[x][i]);
        }
        return;
    }
    vector<string> abc(string txt) {
        string tmp;
        vector<string> ans;
        for (int i = 0; i < txt.size(); i++) {
            if (txt[i] != ' ') {
                tmp.push_back(txt[i]);
            }
            else {
                if (m[tmp] == 0) {
                    vector<string> ret = abc(txt.substr(i + 1, txt.size() - i - 1));
                    for (int i = 0; i < ret.size(); i++) {
                        ans.push_back(tmp + " " + ret[i]);
                    }
                    sort(ans.begin(), ans.end());
                    return ans;
                }
                else {
                    vector<string> ret = abc(txt.substr(i + 1, txt.size() - i - 1));
                    int x = m[tmp];
                    int xx = findroot(x);
                    tmp = m2[xx];
                    for (int i = 0; i < ret.size(); i++) {
                        ans.push_back(tmp + " " + ret[i]);
                    }
                    for (int i = 0; i < fa_chi[m[tmp]].size(); i++) {
                        for (int j = 0; j < ret.size(); j++) {
                            ans.push_back(m2[fa_chi[m[tmp]][i]] + " " + ret[j]);
                        }
                    }
                    sort(ans.begin(), ans.end());
                    return ans;
                }
            }
        }
        if (m[tmp] == 0) {
            ans.push_back(tmp);
            return ans;
        }
        else {
            int x = m[tmp];
            int xx = findroot(x);
            tmp = m2[xx];
            ans.push_back(tmp);
            for (int i = 0; i < fa_chi[m[tmp]].size(); i++) {
                ans.push_back(m2[fa_chi[m[tmp]][i]]);
            }
            sort(ans.begin(), ans.end());
            return ans;
        }
    }
    vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
        initset();
        string tmp;
        for (int i = 0; i < synonyms.size(); i++) {
            string a = synonyms[i][0];
            string b = synonyms[i][1];
            if (m[a] == 0) {
                msize++;
                m[a] = msize;
                m2[msize] = a;
            }
            if (m[b] == 0) {
                msize++;
                m[b] = msize;
                m2[msize] = b;
            }
            mergeset(m[a], m[b]);
        }
        for (int i = 1; i <= msize; i++) {
            sort(fa_chi[i].begin(), fa_chi[i].end());
        }
        return abc(text);
    }
};

第四题 不相交的握手

这这这,Catalan要复习么???
自己查百度...
code:

class Solution {
public:
    int h[1001];
    int numberOfWays(int num_people) {
        int n = num_people / 2;
        h[0] = 1;
        for (int i = 1; i <= n; ++i)
            for (int j = 0; j < i; ++j)
                h[i] = (h[i] + 1ll * h[j] * h[i - 1 - j]) % 1000000007;
        return h[n];
    }
};

广告

小白二号在每次比赛都写题解
我也要写!!!
至于有些网友说小白二号一些题解写的是其他乱搞的Java
于是我每次双周赛(周赛没空...)都会写全C++的代码
记得关注哦!!!

2
展开全部 9 讨论