这次周赛质量也是不错的，但是周末我当然是摸了，所以只能周一上午没课的时候把题补了，Profile Here。

Question D Find the String with LCP

题意

对于一个长为n的字符串word，定义它的lcp(longest common prefix)矩阵中的每个元素lcp[i][j]表示为word[i:n-1]和word[j:n-1]的最长公共前缀长度。现在给定一个lcp矩阵，问满足这个lcp矩阵的最小字典序的字符串是什么。

题解

好吧看了讨论区里的题解发现这个构造题我有点想不到，所以我摸了。。

贴一下题解链接

Question C Count the Number of Square-Free Subsets

题意

给定一个长为n的数组nums，定义若一个nums的子集中所有元素的和不能被任何平方数整除则说它是square-free的。求nums的所有square-free的非空子集的数目。
($n\le1000, nums[i]\le30$)

题解

这个问题受到数据范围影响特别大，我们可以首先关注到nums[i]最大只有30，小于30的质数只有2, 3, 5, 7, 11, 13, 17, 19, 23, 29这10个，所以实际上需要枚举的内容很少。题目的要求实际上就是说这个子集中所有元素的乘积分解质因子之后，每个因子最多只能出现一次（当然也可以是0次）。如果这是一个数据范围比较大的题，会需要先用唯一分解定理把所有数做分解质因子，然后dfs对于1-30中所有的合数（注意一下，需要枚举的合数实际上只有8个，有很多合数本身自己就包含了超过2个的相同质因子，这样我们可以减少很多枚举次数）进行选或者不选的枚举就可以了。

还需要注意一下，1比较特殊，选多少个都可以。最后计算完2-30取或不取的方法数res要再乘以pow(2, 1出现的次数)再减1（去掉什么都不选的空集，题目要求的是非空子集）

“复杂度”应该是需要最多计算(10*2^8)次

// 枚举合数的选取情况，对于每种枚举方式看还有哪些质数可以用
typedef long long ll;
const ll MOD = 1e9 + 7;
struct item{
    ll prime, tot;
};
class Solution {
public:
    int flag[31];
    ll res = 0;
    map<int, int> mp;
    map<int, vector<item>> facmp;
    set<map<int, int>> smp;

    vector<item> Prime_Factorization(int x){
        vector<item> ret;
        for (int i = 2; i <= x / i; i++){
            if(x % i == 0){
                int tot = 0;
                while(x % i == 0){
                    x /= i, tot++;
                }
                ret.push_back({i, tot});
            }
        }
        if(x > 1) ret.push_back({x, 1});
        return ret;
    }
    bool check(map<int, int> nusage, map<int, int> now){
        bool ret = true;
        for(auto &it : nusage)
            ret = ret && (it.second <= min(1, mp[it.first]));
        for(auto &it : now)
            ret = ret && (it.second <= 1);
        return ret;
    }
    void dfs(map<int, int> usage, map<int, int> st){
        if(!check(usage, st) || smp.find(usage) != smp.end()){
            return;
        }
        else{
            ll tmp = 1;
            for(auto &it : st){
                if(it.second == 0 && mp[it.first] >= 1)
                    tmp *= (1 + mp[it.first]);
            }
            for(auto &it : usage){
                if(it.second >= 1)
                    tmp *= mp[it.first];
            }
            res = (res + tmp) % MOD;
            smp.insert(usage);
        }
        for(auto &it : usage){
            if(mp[it.first] > 0 && it.second == 0){
                usage[it.first] = 1;
                auto nfac = facmp[it.first];
                for(auto &it : nfac)
                    st[it.prime] += it.tot;

                dfs(usage, st);

                for(auto &it : nfac)
                    st[it.prime] -= it.tot;
                usage[it.first] = 0;
            }
        }
    }
    int squareFreeSubsets(vector<int>& nums) {
        for(auto &it : nums) mp[it] += 1;
        for(auto &it : mp) facmp[it.first] = Prime_Factorization(it.first);
        memset(flag, 0, sizeof(flag));
        flag[2] = flag[3] = flag[5] = flag[7] = flag[11] = flag[13] = flag[17] = flag[19] = flag[23] = flag[29] = 1;
        map<int, int> nusage;
        nusage[6] = nusage[10] = nusage[14] = nusage[15] = nusage[21] = nusage[22] = nusage[26] = nusage[30] = 0;
        map<int, int> nst;
        for(int i = 1; i <= 30; i++) if(flag[i]) nst[i] = 0;
        dfs(nusage, nst);
        for(int i = 0; i < mp[1]; i++)
            res *= 2, res %= MOD;
        return (res - 1 + MOD) % MOD;
    }
};

Question B Minimum Operations to Reduce an Integer to 0

题意

给定一个数n，可以对这个数做若干次操作：每次操作对当前这个数加上或减去一个任意的2的幂。求使n变为0的最少次数。
($n\le1e5$)

题解

由于n的范围很小，不想动脑子的方法就可以直接从0开始反向bfs递推，即先扩散到所有2的幂即需要1次操作的数，再扩散到需要2次操作的数等等。

const int maxn = 1e5 + 10;
class Solution {
public:
    int dp[maxn * 2];
    int minOperations(int n) {
        memset(dp, 0x3f, sizeof(dp));
        queue<pair<int, int>> q;
        dp[0] = 0, q.push({0, 0});
        while(!q.empty()){
            auto now = q.front();
            for(int i = 0; i < 17; i++){
                auto nvalue = now.first + (1 << i);
                if(nvalue <= 2e5 && dp[nvalue] > now.second + 1){
                    dp[nvalue] = now.second + 1, q.push({nvalue, now.second + 1});
                }
                nvalue = now.first - (1 << i);
                if(nvalue >= 0 && nvalue <= 2e5 && dp[nvalue] > now.second + 1){
                    dp[nvalue] = now.second + 1, q.push({nvalue, now.second + 1});
                }
            }
            q.pop();
        }
        return dp[n];
    }
};

Question A Merge Two 2D Arrays by Summing Values

题意

合并两个表示key-value的key按照升序排列的列表(很像是倒排索引的合并)。

代码

可以双指针，这样是线性复杂度。因为数据范围很小，也可以直接用map偷懒。我比赛当然会选择偷懒好写的方法啦。

class Solution {
public:
    vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
        map<int, int> mp;
        for(auto &it : nums1){
            mp[it[0]] += it[1];
        }
        for(auto &it : nums2){
            mp[it[0]] += it[1];
        }
        vector<vector<int>> ret;
        for(auto &it : mp){
            ret.push_back(vector<int>{it.first, it.second});
        }
        return ret;
    }
};