测试总结：温州中学 2011年11月月赛 Day1

xiaoxiao2025-03-23 24

T1 食物中毒

参考代码

const int MAXN = 60; int n,m,mi,ki; bool state; long long require,selected; long long medicine[MAXN]; void readdata() { for (int i = 1;i <= m;++i) { scanf("%d",&mi); require |= (long long)1 << (mi - 1); } for (int i = 1;i <= n;++i) { scanf("%d",&ki); for (int j = 1;j <= ki;++j) { scanf("%d",&mi); medicine[i] ^= (long long)1 << (mi - 1); } } } void init() { state = false; require = 0; memset(medicine,0,sizeof(medicine)); } void dfs(int itemID) { if ((selected | require) == selected) { state = true; return; } if (itemID == n + 1) return; long long tmp = selected; selected ^= medicine[itemID]; dfs(itemID + 1); selected = tmp; dfs(itemID + 1); } int main() { while (scanf("%d%d",&n,&m) != EOF) { init(); readdata(); dfs(1); if (state) puts("Possible"); else puts("Impossible"); } return 0; }

分析

选取的所有药物中，必须出现所有需要的化学物质，也可以出现不需要的化学物质。

看到题目中的描述：

“两个相同的化学物质在一起，它们的药性会同时消失变为一种无毒物质。”

可以想到开一个辅助数组，记录每种药物中每种化学物质的出现次数，再判断这种化学物质是否存在。这是处理单个药物的方法。后面在选取药物的时候，也可以运用同样的方法。

由于每种药物只有一个，即每种药物的决策只有选与不选两种，可以直接枚举所有方案数，共 $2^{20} = 1048576$ 种方案。

当然，由于每种药物的决策只有选与不选两种，我们还可以利用位运算来加快计算速度。

require |= (long long)1 << (mi - 1);（置1，代表含有这种化学物质）medicine[i] ^= (long long)1 << (mi - 1);（单身狗操作）selected ^= medicine[itemID];（选用当前这种药物）if ((selected | require) == selected)（判断当前选出的所有药物是否已经凑齐所需的化学物质）

是不是很方便？

有一些细节需要注意：

long long tmp = selected; selected ^= medicine[itemID]; dfs(itemID + 1); selected = tmp; dfs(itemID + 1); /* 为什么不这样写： dfs(itemID + 1); selected ^= medicine[itemID]; dfs(itemID + 1); */

为什么先选用这种药物，然后再不选用呢？

考虑到selected是一个全局变量，如果最后选用这种药物，那么在返回上一层递归时，这种药物依然是被选中的状态。而最后不选用的写法，恰好起到了一个“清零”的作用。

T2 消息传递

参考代码

const int MAXN = 100005; struct edge { int to,nxt; }info[MAXN << 1]; int n,m,e,ui,vi,top,Index,cid; int head[MAXN],dfn[MAXN],low[MAXN],inStack[MAXN],Stack[MAXN],color[MAXN],cnt[MAXN]; template<typename T> void qread(T &sum) { sum = 0; register char ch = getchar(); while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') { sum = (sum << 1) + (sum << 3) + ch - '0'; ch = getchar(); } } template<typename T> void qwrite(const T x) { if (x < 0) {putchar('-'); qwrite(-x);} else { if (x >= 10) qwrite(x / 10); putchar(x % 10 + '0'); } } inline void addedge(int from,int to) { info[++e].to = to; info[e].nxt = head[from]; head[from] = e; } void tarjan(int u) { Index++; dfn[u] = low[u] = Index; Stack[++top] = u; inStack[u] = true; for (int i = head[u];i;i = info[i].nxt) { int v = info[i].to; if (!dfn[v]) { tarjan(v); low[u] = min(low[u],low[v]); } else if (inStack[v]) low[u] = min(low[u],dfn[v]); } if (dfn[u] == low[u]) { color[u] = ++cid; cnt[cid]++; inStack[u] = false; while (Stack[top] != u) { color[Stack[top]] = cid; cnt[cid]++; inStack[Stack[top]] = false; top--; } top--; } } void init() { scanf("%d%d",&n,&m); for (int i = 1;i <= m;++i) { qread(ui); qread(vi); addedge(ui,vi); } } void work() { for (int i = 1;i <= n;++i) if (!dfn[i]) tarjan(i); for (int i = 1;i <= n;++i) { if (cnt[color[i]] > 1) puts("T"); else puts("F"); } }

分析

裸的 $\operatorname{Tarjan}$ 吧……只需要在最后判断是否有只有一个节点作为强连通分量的，由于不能自己把消息传给自己，这样是非法的。

T3 周年纪念日

参考代码

#define int long long const int MAXN = 100005; struct edge { int to,nxt,wgt; } info[MAXN << 1]; struct node { int from,to,wgt; friend bool operator <(const node &na,const node &nb) { return na.wgt < nb.wgt; } } Edge[MAXN << 1]; int n,m,e,ui,vi,wi,cost,maxd,minID = INT_MAX; long long mind = LLONG_MAX; int head[MAXN],ufs[MAXN],sumPopulation[MAXN],population[MAXN]; long long dist[MAXN]; template<typename T> void qread(T &sum) { sum = 0; register char ch = getchar(); while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') { sum = (sum << 1) + (sum << 3) + ch - '0'; ch = getchar(); } } inline void addedge(int from,int to,int wgt) { info[++e].to = to; info[e].wgt = wgt; info[e].nxt = head[from]; head[from] = e; } inline int find(int u) { return ufs[u] == u ? u : ufs[u] = find(ufs[u]); } void preDfs(int u,int f) { for (int i = head[u]; i; i = info[i].nxt) { int v = info[i].to; if (v == f) continue; preDfs(v,u); sumPopulation[u] += sumPopulation[v]; dist[u] += dist[v] + sumPopulation[v] * info[i].wgt; } } void postDfs(int u,int f) { for (int i = head[u]; i; i = info[i].nxt) { int v = info[i].to; if (v == f) continue; dist[v] = dist[u] - sumPopulation[v] * info[i].wgt + (sumPopulation[1] - sumPopulation[v]) * info[i].wgt; postDfs(v,u); } } void init() { scanf("%lld%lld",&n,&m); for (int i = 1; i <= n; ++i) ufs[i] = i; for (int i = 1; i <= n; ++i) { qread(population[i]); sumPopulation[i] = population[i]; } for (int i = 1; i <= m; ++i) { qread(Edge[i].from); qread(Edge[i].to); qread(Edge[i].wgt); } sort(Edge + 1,Edge + m + 1); } void work() { int used = 0; for (int i = 1; i <= m; ++i) { if (used == n - 1) break; int u = find(Edge[i].from); int v = find(Edge[i].to); if (u != v) { ufs[u] = v; cost += Edge[i].wgt; maxd = max(maxd,Edge[i].wgt); addedge(Edge[i].from,Edge[i].to,Edge[i].wgt); addedge(Edge[i].to,Edge[i].from,Edge[i].wgt); used++; } } preDfs(1,0); postDfs(1,0); for (int i = 1; i <= n; ++i) { if (mind > dist[i]) { minID = i; mind = dist[i]; } } printf("%lld %lld\n%lld %lld",cost,maxd,minID,mind); } #undef int

分析

既然修路的费用就是路的长度了，那么求最小费用就是求一个MST；还要让MST中最大边权值最小，后者就是Kruskal的特性。

那么现在只需要在MST上找一点，使得其余点到这一点的距离（带了权值Pi，下同）最小。

考虑二次扫描换根法，使用两遍DFS，第一次由下到上计算出：

sumPopulaition[i]：表示以i为根的子树中，包括节点i的总人数。dist[i]：表示以i为根的子树中，其所有儿子节点到根的距离。

第二次由上到下计算出：

dist[i]：表示除了节点i的所有节点到节点i的距离。

有一些细节需要注意：

dist[u] +=dist[v]+ sumPopulation[v] * info[i].wgt;

如果不加上dist[v]，那么sumPopulation[v] * info[i].wgt只代表以v为根的子树中，所有人口经过道路i的“不高心度”。这没有把v的所有儿子节点中的人口走到节点v的“不高心度”计算在内。

dist[v] = dist[u] - sumPopulation[v] * info[i].wgt + (sumPopulation[1] - sumPopulation[v]) * info[i].wgt;

这句话看起来有些难以理解，其实它本来应该是这样的：

dist[v] = dist[v] + dist[u] - (dist[v] + sumPopulation[v] * info[i].wgt) + (sumPopulation[1] - sumPopulation[v]) * info[i].wgt;

这里和上边是一样的解释：

dist[v]是本来节点v的所有儿子节点到v的不高兴度； dist[u] - (dist[v] + sumPopulation[v] * info[i].wgt)是除了v和v的所有儿子节点外，所有点到v的父节点的“不高兴度”¹。 (sumPopulation[1] - sumPopulation[v]) * info[i].wgt;是其他节点通过边i产生的“不高兴度”。

可以发现，dist[v]被消掉了。于是就产生了源代码中的转移方程。

总结

从T1可以知道，当一个事件的决策只有选与不选两种时，可以利用位运算来简化代码实现、优化计算速度。

从T2可以知道，上课要认真听 $q w q$

从T3可以知道，一是对于一些基本的模板，以及它们的性质要熟悉，二来是要注意换根的时候，要加上原来的标记（感性理解一下吧）。

由于第二次DFS由上向下计算，计算dist[v]时，dist[u]已经代表所有节点到u的“不高兴度”了。 ↩︎

最新回复(0)