本场周赛总结

本场周赛只做出来两题并且名次不是很好,一是以为迟到,二是在第一题异或问题上浪费太多时间,第三题已经想到了思路,但是在找两个集合中有多少个不同的元素的过程中没有想到排序后双指针的方法,差一点做出来,有些可惜。前两题属于送分题,第三题蛮有意思,第四题一个很经典的状压dp问题。

第三题

1722执行交换操作后的最小汉明距离

这题本身是考察并查集,因为可以将交换次数建模成为一个图,在一个联通块内的元素下标是可以任意交换的,所以只要在一个联通块下标里找两个数组中不同的元素即可,这个找的过程使用排序后双指针来找,比赛的时候用集合交集运算试了半天答案不对,思路还是比较畅通的。

class DSU:
def __init__(self,n: int):
self.p = [i for i in range(n)]

def find(self,x: int) -> int:
if x != self.p[x]: self.p[x] = self.find(self.p[x])
return self.p[x]

def merge(self,x: int,y: int):
rx , ry = self.find(x) , self.find(y)
if rx == ry: return
self.p[rx] = ry
return
class Solution:
def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
if len(allowedSwaps) == 0:
return hanming(source,target)
n = len(target)
dsu = DSU(n)
for i,j in allowedSwaps:
dsu.merge(i,j)
cnt = 0
f = []
for idx,c in enumerate(dsu.p):
if idx==dsu.p[idx]:
cnt += 1
f.append(idx)
print(cnt)
print(dsu.p)

mp = collections.defaultdict(list)
for i in range(n):
fa = dsu.find(i)
mp[fa].append(i)
res = 0
print(mp)
for k, v in mp.items():
s1 = []
s2 = []
for idx in v:
s1.append(source[idx])
s2.append(target[idx])
s1.sort()
s2.sort()
ans = len(v)
i = j = 0
while(i < len(s1) and j < len(s1)):
if s1[i] == s2[j]:
i+=1
j+=1
ans -= 1
elif s1[i] < s2[j]:
i += 1
else:
j += 1

res += ans

return res

这里依旧使用的是我们的并查集的板子。

第四题

1723完成所有工作的最短时间

这题是一个典型的状压问题,并且是一个极大极小化问题(意味着可以用二分来做)

思路,这里我们假设所有的n个job可以用一个n位的二进制数来进行表示,其中0表示没有被选中,1表示被选中,这样这个工作就被分成$2^n$个集合,我们对每一个集合用一个唯一的$i$来表示这个$state$,那么我们可以计算出每一个state对应的job时间总和用$tot[i]$来表示,现在我们假设$dp[j][i]$表示i状态的工作分配给j个工人需要花费的工作时间的最小值。假如前$j-1$个人完成了状态为$s$的工作,那么接下来剩余的$i-s$个工作只能给地$j$个人,那么此时需要花费的时间就是
$$
dp[j][i] = max(dp[j-1][s],tot[i-s])
\
min(s\in i)
$$
我们在每一种分配方式中找到最小值最为$j,i$的最终状态。那么最终结果一定是使用完所有的人,并且所有的工作都被做过,即$dp[k-1][(1<<n)-1]$

代码如下:


class Solution {
public:
int minimumTimeRequired(vector<int>& jobs, int k) {
int n = jobs.size();
vector<int> tot(1 << n, 0);
for (int i = 1; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) == 0) continue;
int left = (i - (1 << j));
tot[i] = tot[left] + jobs[j];
break;
}
}

vector<vector<int>> dp(k, vector<int>(1 << n, -1));
for (int i = 0; i < (1 << n); i++) {
dp[0][i] = tot[i];
}

for (int j = 1; j < k; j++) {
for (int i = 0; i < (1 << n); i++) { // 枚举所有的状态
int minv = INT_MAX;
for (int s = i; s; s = (s - 1) & i) { // 枚举 i 的全部子集
int left = i - s;
int val = max(dp[j-1][left], tot[s]);
minv = min(minv, val);
}
dp[j][i] = minv;
}
}
return dp[k-1][(1<<n)-1];
}
};

同样也可以用二分法

class Solution {
public:
int minimumTimeRequired(vector<int>& jobs, int k) {
int n = jobs.size();
vector<int> tot(1 << n, 0);
for (int i = 1; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) == 0) continue;
int left = (i - (1 << j));
tot[i] = tot[left] + jobs[j];
break;
}
}

int l = *max_element(jobs.begin(), jobs.end());
int r = accumulate(jobs.begin(), jobs.end(), 0);
while (r > l) {
int mid = (l + r) / 2;
vector<int> dp(1 << n, INT_MAX / 2);
dp[0] = 0;
for (int i = 0; i < (1 << n); i++) {
for (int s = i; s; s = (s - 1) & i) {
if (tot[s] <= mid) {
dp[i] = min(dp[i], dp[i-s] + 1);
}
}
}
if (dp[(1<<n) - 1] <= k) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
};