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

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

image.png

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

展开讨论
共 9 个讨论

赞这次题目质量,第三题是工作中经常碰到的场景「输入联想」,比如各种网站输入框,帮你把形近字和音近字罗列出来构成句子去库里匹配

第一题:

额,这题全靠肉眼识别,n+1n+1 的二进制,去掉第一位就行了

import java.math.*;

class Solution {
    public String encode(int num) {
        return BigInteger.valueOf(num + 1).toString(2).substring(1);
    }
}

第二题:

这题把字符串看成结点,每一行第一个元素是后面所有元素的父亲结点,题目就是求两个结点的最近公共祖先

解法:先分别把两个节点的祖先们求出来,然后再从第一个祖先开始匹配,直到第一次不匹配的上一个祖先就是结果

class Solution {
public:
    vector<string> find(map<string, string> &m, string region) {
        vector<string> p;
        string res = region;
        while (1) {
            p.push_back(res);
            auto it = m.find(res);
            if (it == m.end()) {
                break;
            }
            res = it->second;
        }
        return p;
    }
    string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
        map<string, string> m;
        for (auto& region: regions) {
            for (int i = 1;i < region.size();i++) {
                m[region[i]] = region[0];
            }
        }
        vector<string> p1 = find(m, region1), p2 = find(m, region2);
        
        int i1 = p1.size() - 1;
        int i2 = p2.size() - 1;
        while (true) {
            if (i1 >= 0 && i2 >= 0 && p1[i1] == p2[i2]) {
                i1--;
                i2--;
            } else {
                break;
            }
            
        }
        return p1[i1 + 1];
    }
};

第三题:

先把所有的近义词集合求出来。题目中 AABB 的近义词,如果 AABB 的近义词,AACC 的近义词,那么 AABBCC 都是近义词,这一步如果数据量大需要用到并查集,数据量小,瞎搞搞咯

然后再dfs,把句子中每个词的近义词都拿出来计算一次。。。

import java.util.*;

class Solution {
    private void dfs(Map<String, Set<String>> map, String[] col, List<String> result, int index) {
        if (index == col.length) {
            result.add(String.join(" ", col));
            return;
        }
        if (map.containsKey(col[index])) {
            String s = col[index];
            for (String sub: map.get(col[index])) {
                col[index] = sub;
                dfs(map, col, result, index + 1);
            }
            col[index] = s;
        } else {
            dfs(map, col, result, index + 1);
        }
    }
    public List<String> generateSentences(List<List<String>> synonyms, String text) {
        Map<String, Set<String>> map = new HashMap<>();
        
        for (List<String> synonym: synonyms) {
            Set<String> s1 = map.getOrDefault(synonym.get(0), new HashSet<>());
            Set<String> s2 = map.getOrDefault(synonym.get(1), new HashSet<>());
            if (s1 == s2) {
                continue;
            }
            HashSet<String> ret = new HashSet<>();
            ret.addAll(s1);
            ret.addAll(s2);
            ret.add(synonym.get(0));
            ret.add(synonym.get(1));
            
            for (String sub: ret) {
                map.put(sub, ret);
            }
        }

        String[] col = text.split(" ");
        List<String> result = new ArrayList<>();
        dfs(map, col, result, 0);

        Collections.sort(result);
        return result;
    }
}

第四题:

看到例子,1,1,5,141,1,5,14,明显卡特兰数啊

f(n)=i=0n1f(i)f(ni1)f(n)=\sum_{i=0}^{n-1}f(i)*f(n-i-1)

证明:

假设 nn 无限大,考察点 11

  1. 11 如果跟点 22 连接,那么有 f(n2)f(n-2) 种方法
  2. 11 如果跟点 33 连接,点 22 不管跟啥点连接都会跟 1>1-> 3相交,冲突
  3. 11 如果跟点 44 连接,那么 1>41->4 将空间划成两边,2233 两个点,有 f(2)f(2) 个方法连接,另外一边是 n4n-4 个点,有 f(n4)f(n-4) 个方法连接,那么总方法数是 f(2)f(n4)f(2)*f(n-4)
  4. 。。。
class Solution {
public:
    vector<int> cal;
    void init() {
        if (cal.size() != 0) {
            return;
        }
        cal.push_back(1);
        cal.push_back(1);
        for (int i = 2;i <= 500;i++) {
            int res = 0;
            for (int j = 0;j < i;j++) {
                res += (long long)cal[j] * cal[i - 1 - j] % 1000000007;
                            res %= 1000000007;
            }
            cal.push_back(res);
        }
    }
    int numberOfWays(int num_people) {
        init();
        return cal[num_people / 2];
    }
};
17

第一题 加密数字

其实题目很水找规律

  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

有没有大佬第三题用JS做卡在

[["OP","JcT"]]
"AfUCr JcT I AfUCr JcT AfUCr a tn uoV a"

这组数据上的 我空函数提交报语法错误 是不是输入有问题啊

1

1.和转换二进制差不多,注意边界
2.建一个hash_map存储所有单词的上级,储存其中一方到根的路径即可。注意相互包含的情况
3.数据规模很小,直接暴力判断近义词的合并,暴力查找句子里每个词是不是近义词,再递归即可。看看有没有优雅的写法
4.公式是

for(int j = 0; j < i; j++)
                array[i] += array[j] * array[i - j - 1];

然后确保不越界就完了

1

我想知道Catalan那题,如果用的是JavaScript,当数字很大时是不是总mod不准?用JS的朋友们能解答下吗?

image.png

第二题最后想了好久最后才突然顿悟r1包含r2和r3,r2一定不包含r3是什么意思,拿草稿纸画了半小时才发现自己想多了

请问双周赛有积分奖励吗

放个python3的题解链接就跑,菜鸡瑟瑟发抖。
https://www.bilibili.com/read/cv3983991

2

难倒是不难,麻烦是真的麻烦。。连easy题都不出了么