牛客多校2

牛客暑期多校2

比赛链接

A. Floor Tiles

题目链接

找规律的题目，看题解即可

B.MST

题目链接

解：一道使用根号分治的暴力题目。

首先我们一共有两种暴力方式，一种是$O(n^2)$的遍历任意给定的两个点，得到我需要的合法边，再对边进行kruskal算法得到最小生成树

还有另一种方法是$O(m)$的枚举我所有的边，看这个边的两端是否都在集合中，这一步骤相当于是做了一遍kruskal。

第一种方式的时间复杂度是$O(q\times |q|^2\log{n})$，第二种的时间复杂度是$O(qm\log{n})$

对此我们进行根号分治对于$q\le \sqrt{n}$时，我们采用第一种策略，此时方案的整体复杂度是$O(n^{1.5}\log{n})$

而对于$q \gt \sqrt{n}$的情况，我们采用第二种策略，此时方案的整体复杂度为$O(\sqrt{n}\times m \times \log{m})$

G.The Set of Squares

原题链接

解：一道十分经典的质因数状态压缩 + 分组背包的题目。

先看一道例题Free from square

我们发现小于$\sqrt{n}$的质数很少，只有8个，所以可以把这些质数的状态记录下来。为什么这里只需要考虑小于$\sqrt{n}$的整数呢？因为大于等于$\sqrt{n}$的整数在同一个数字中只会出现一次。

我们设$dp[i][j][k]$表示前$i$个数，选择了$j$个物品，剩余的状态是$k$。当然这里的$i$可以被滚动掉。

那么分组背包在哪里体现呢？体现在前面没有被记录状态的大于等于$\sqrt{n}$的大质数。对于拥有相同大质数的$a,b$我们可以考虑把他们放在同一组中。这样的话，就不需要考虑没有被记录的大质数对答案的影响了。

那么这个状态如何转移呢？考虑从$status$转移过来，有$dp[i][j+1][k | status]+=dp[i-1][j]status$，为什么呢？因为当且仅当$status \&u=0$时，前后两者的质因数才没有交集，不会出现非法情况

最后一个问题，对于可以被小于$\sqrt{n}$的质数进行质因数分解的数字$i$，是存在$v[1]$的背包里，还是存在$v[i]$的背包里呢？在这道题目中，当然是放在$v[i]$的背包中，因为这里的1是要单独讨论的。

void solve() {
    int n, k, cur = 0;
    cin >> n >> k;
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    for (int i = 1;i <= n;i++) {
        if (flag[i] || v[i].empty()) continue;
        int nxt = cur ^ 1;
        for (int j = k;j >= 0;j--) {
            for (int u = 0;u < (1 << 8);u++) {
                for (auto &x : v[i]) {
                    dp[nxt][j][u] = dp[cur][j][u];
                    if (x > n) continue;
                    if ((state[x] & u) == 0) 
                        dp[nxt][j + 1][u | state[x]] = 
                        (dp[nxt][j + 1][u | state[x]] + dp[cur][j][u]) % mod;
                }
            }
        }
        cur = nxt;
    }
    int ans = 0;
    for (int i = 1;i <= k;i++) {
        for (int u = 0;u < (1 << 8);u++) {
            ans = (ans + dp[cur][i][u]) % mod;
        }
    }
    cout << ans << endl;
}

回到牛客的这道题目。他是要求乘积得到一个平方数。

这时我们的预处理和前面的例题是相同的，分组后得到每个数的$val$和$state$

之后我们选择把能分解干净的数字全部放在$v[1]$位置，因为这样可以避免把1单独拿出来讨论。

另一点，这里我们需要考虑对于同一组的数字，如果选择两个，也要考虑他们的贡献。这个应该如何实现呢？我们可以在原来的状态基础上再增加一位表示大质数的个数。

接下来考虑该如何转移，我们设$dp[i]$表示剩余状态是$i$的时候，我的最大收益。

对于从状态$s$，数字$j$转移过来，我们考虑他们的贡献，一个是大质数可能的贡献$j$，以及小质数重合产生平方得到的贡献

有$dp[i \land j]= dp[i \land j]+dp[j]\times val \times w[i\land j] \times 大质数$。

为什么前面有一个异或呢？因为我选择$j$状态后，会抵消之前的重复的1

为什么后面是与，与得到的就是重合的小质数，$w[i\land j]$就是得到他们的值。

最后一个问题，为什么最后的结果要减1，因为我最开始为了计算强行给$dp[0]=1$，导致计数增加

for (int i = 0;i < n;i++) cin >> a[i];
	for (int i = 0;i < n;i++) {
		int x = a[i];
		int tmp = 0, val = 1;
		for (int i = 0;i < 11;i++) {
			int cnt = 0;
			while (x % primes[i] == 0) {
				x /= primes[i];
				if (tmp & (1 << i)) val = (val * primes[i]) % mod;	
				tmp ^= (1 << i);
			}
		}
		v[x].emplace_back(val, tmp);
	}
	vector<int> dp(1 << 12, 0);
	dp[0] = 1;
	for (int i = 1;i <= 1000;i++) {
		if (v[i].empty()) continue;
		for (auto [val, mask] : v[i]) {
			if (i != 1)
				mask |= (1 << 11);	//大质数存在第十一位上
			auto b = dp;
			for (int j = 0;j < (1 << 12);j++) {
				int tmp = mask ^ j, newval = dp[j] * val, same = mask & j;
				for (int k = 0;k < 11;k++) {
					if (same & (1 << k)) {
						newval = (newval * primes[k]) % mod;
					}
				}
				if (same & (1 << 11)) newval = (newval * i) % mod;
				b[tmp] = (b[tmp] + newval) % mod;
			}
			dp = std::move(b);
		}
		for (int j = (1 << 11);j < (1 << 12);j++) dp[j] = 0;
	}
	cout << (dp[0] - 1 + mod) % mod << endl;	

I.Red Playing Cards

原题链接

把$[l,r]$消去得到$a[l]\times len$的$val$，我们可以把他看成把$[l,r]$全部变成$a[l]$得到的结果

所以我们设$dp[i]$表示消去数字$i$得到的最大价值，$g[j]$表示消去i数字的时候在$j$位置得到的最大价值

如何转移呢？$g[i]= \begin{cases} g[i-1]+num &\text{others} \\ g[l[a_i]-1]+dp[a_i] &\text{if i =a[j] and l[a[i]] > l[num]} \end{cases}$

这个式子很显然，不过多解释。

最后提醒一点，根据$len$长度从小到大排完序后，依次进行dp