A、B、C略
D - Choose Me
设$S$为选择的进行演讲的城镇的集合。那么两个人的选票差为
$$
\sum_{i\in S}(2\times a[i]+b[i])-\sum_{i=1}^na[i]
$$
要使T的选票多于A的选票，即找到一个元素最小的集合$S$，使得该式大于0。
直接按照$2\times a[i]+b[i]$从大到小排序即可。
E - Through Path
每次操作均是对一颗子树或者一颗子树的补集加上一个$x_i$，最后离线询问每一个点的点权。
直接dfs求出dfn，维护子树关系，然后按照dfn差分数组即可。
F - Close Group
这一题比较有意思，当场没有想出来，主要也是没有写过这个类型的题目。
大意是给定一个$n$点$m$边的简单无向图，求出通过删除一定的边后，使得图中的每一个连通分量都是完全图的最小连通分量个数是多少。
解法：首先枚举每一个状态$i$，判断该状态是否构成完全图，如果是，则标记$good[i]=1$。设$dp[i]$为选择了子图$i$后，子图中满足要求的最小连通分量个数。初始化$dp[0]=0$，其它为正无穷。枚举每一个状态，若$good[i]=1$，则$dp[i]=1$；否则，枚举状态的每一个子集j，有方程$dp[i]=min(dp[i],dp[j]+dp[i\hat{}j])$。将状态i用i的子集j和j的补i^j进行转移的原因是：假设存在i是由多个子集共同组合而成是最优的，则这多个子集组合而成的i的子集显然不是最优的，这与假设矛盾。
那么如何枚举每一个子集呢？
对于二进制状态$S$，可以用此方法来进行不重不漏地枚举。
for (int sub = S; sub; sub = (sub - 1) & S) { |
// sub 为 S 的子集 |
} |
假设当前子集$sub=(d_n d_{n-1} \cdots d_k 10\cdots 0)_2$
那么$sub-1=(d_n d_{n-1} \cdots d_k 01\cdots 1)_2$
(sub-1)&S得到的自然就是二进制表示小于sub的最大的子集 。
枚举的时间复杂度$O(3^n)$：
$$
\sum_{i=0}^n\binom{n}{i}\cdot2^i=(1+2)^n
$$
#参考代码
|
|
using namespace std; |
typedef long long ll; |
const int maxn = 1 << 18; |
int n, m; |
bool adj[20][20], good[maxn]; |
int dp[maxn]; |
inline bool judge(int mask) { |
vector<int> temp; |
for(int i = 0; i < n; ++i) |
if(mask >> i & 1) temp.push_back(i); |
for(int i = 0; i < temp.size(); ++i) |
for(int j = i + 1; j < temp.size(); ++j) { |
int u = temp[i], v = temp[j]; |
if(!adj[u][v]) |
return false; |
} |
return true; |
} |
int main() { |
ios::sync_with_stdio(false); |
cin.tie(nullptr), cout.tie(nullptr); |
cin >> n >> m; |
for(int i = 1; i <= m; ++i) { |
int u, v; |
cin >> u >> v; |
u--, v--; |
adj[u][v] = adj[v][u] = 1; |
} |
for(int i = 0; i < (1 << n); ++i) |
good[i] = judge(i); |
memset(dp, 0x3f3f3f3f, sizeof(dp)); |
dp[0] = 0; |
for(int i = 1; i < (1 << n); ++i) { |
if(good[i]) |
dp[i] = 1; |
else { |
for (int j = i; j; j = (j - 1) & i) |
dp[i] = min(dp[i], dp[j] + dp[i ^ j]); |
} |
} |
cout << dp[(1 << n) - 1]; |
return 0; |
} |