专栏文章

海亮 2025暑 VII

sskyx
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio81vyx
此快照首次捕获于
2025/12/02 14:53
3 个月前
此快照最后确认于
2025/12/02 14:53
3 个月前
查看原文

0818

NOIP 模拟赛结算

  • 打了 55 场模拟赛，具体得分：
    • 【提高/提高+】20250716NOIP模拟赛：5+10+10+10（蓝紫紫黑）
    • 【提高/提高+】20250717NOIP模拟赛：100+0+0+0（蓝紫紫紫）
    • 【提高/提高+】20250722NOIP模拟赛：30+30+0+0（蓝绿紫紫）
    • 【提高/提高+】20250815模拟赛：85+0+30+0（绿蓝蓝紫）
    • 【提高/提高+】NOIP模拟赛20250818：40+10+10+45（蓝蓝紫紫）
    • 总得分：35+100+60+115+105=415。达成 5 场总 得分 AK noip 的目标。
  • 重要挂分 （部分分没拿到）
    • 【提高/提高+】20250716NOIP模拟赛 T3 60pts。
    • 【提高/提高+】20250716NOIP模拟赛 T2 30pts。
    • 【提高/提高+】20250722NOIP模拟赛 T3 20pts。
    • 【提高/提高+】20250815模拟赛 T1 15pts。

T1

Alice和 Bob 在玩一个游戏:他们有两个正整数 nn 和 kk。定义一次操作为：选择任意一个 p≥2p≥2，将 nn 写成 рр 进制数，并删去末尾的至少 kk 个 00。注意，若末尾没有 kk 个 00，则不能选取 pp 进行操作。
不能操作的人将输掉这场游戏。二人都采取最优策略，问游戏的获胜者是谁？
解释为什么「末尾有 kk 个 0」会等价于 n=m⋅pk且p∤mn = m \cdot p^k \quad \text{且} \quad p \nmid m
在 pp 进制下，一个数 nn 可以写成：n=a0+a1p+a2p2+⋯+arpr n = a_0 + a_1 p + a_2 p^2 + \dots + a_r p^r ，其中每个 aia_i 都是 0≤ai<p0 \le a_i < p 的整数。
「末尾有 1 个 0」在 pp 进制下表示 a0=0a_0 = 0。
这说明：
n=a1p+a2p2+⋯+arpr=p>⋅(a1+a2p+⋯+arpr−1),n = a_1 p + a_2 p^2 + \dots + a_r p^r = p >\cdot (a_1 + a_2 p + \dots + a_r p^{r-1}),
也就是说 p∣np \mid n。
「末尾有 2 个 0」表示 a0=a1=0a_0 = a_1 = 0。于是：
n=a2p2+a3p3+⋯+arpr=>p2⋅(a2+a3p+⋯+arpr−2),n = a_2 p^2 + a_3 p^3 + \dots + a_r p^r = >p^2 \cdot (a_2 + a_3 p + \dots + a_r p^{r-2}),
所以 p2∣np^2 \mid n。
「末尾有 kk 个 0」表示 a0=a1=⋯=ak−1=0a_0 = a_1 = \dots = a_{k-1} = 0，但 ak≠0a_k \neq 0。
于是：
n=akpk+ak+1pk+1+⋯+ar>pr=pk⋅(ak+ak+1p+⋯+>arpr−k),n = a_k p^k + a_{k+1} p^{k+1} + \dots + a_r >p^r = p^k \cdot (a_k + a_{k+1} p + \dots + >a_r p^{r-k}),
其中括号里的数记作 mm。
因为 ak≠0a_k \neq 0，所以 mm 不可能再被 pp 整除。
「末尾有 kk 个 0」⇔ n=m⋅>pkn = m \cdot >p^k，并且 p∤mp \nmid m。
  • 有指数 ≥k\ge k → 先手一次性除尽该质因子，使后手无招可走 → 先手必胜（输出 Alice）。
  • 所有指数 <k<k → 起手即无合法操作 → 先手输（输出 Bob）。
  • 特例 k=1k=1 → 只要 n>1n>1 必有质因子，先手必胜。

0821

1. 强连通分量

原理

  • 在有向图中，强连通分量是一个极大点集，使得点集内任意两点 u,vu,v 都能互相到达。
  • 常用算法：Tarjan 算法 / Kosaraju 算法。
  • 在代码里：
    • 用 dfn[] 和 low[] 标记时间戳和能追溯到的最早节点。
    • 用 栈 st 来保存当前递归路径。
    • 当 dfn[u]==low[u] 时，找到一个 SCC。

特点

  • 只能用于有向图。
  • 输出的是多个强连通分量，每个分量是一个环状的“互相可达”的子图。
  • 在代码里要把边重新缩点（scc[] + ng[]），然后再拓扑 DP 求最大权值。

2. 割点

原理

  • 在无向图中，某个点如果删除，会使得图的连通分量数增加，则它是割点。
  • Tarjan 判断条件：
    • 如果 fa≠ufa \neq u 且存在子节点 vv 使得 low[v] >= dfn[u]，则 uu 是割点。
    • 如果 uu 是 DFS 树的根，并且有两个或以上子树，则 uu 也是割点。

特点

  • 针对 无向图。
  • 输出的是割点个数与编号。
  • 核心条件：low[v] >= dfn[u]。

3. 割边（桥）

原理

  • 在无向图中，某条边如果删除，会使得图的连通分量数增加，则它是割边。
  • Tarjan 判断条件：
    • 如果存在子节点 vv 使得 low[v] > dfn[u]，那么边 (u,v)(u,v) 是割边。

特点

  • 针对 无向图。
  • 输出所有割边，常常要排序。
  • 核心条件：low[v] > dfn[u]。

4. 点双连通分量

原理

  • 在无向图中，如果不存在割点，则图是点双连通的。
  • 点双连通分量：图中极大的“在删除任意一个点后仍然连通”的子图。
  • 实现：
    • 用栈保存当前遍历的节点。
    • 当 low[v] >= dfn[u] 时，找到一个点双分量。
    • 与割点紧密相关，因为割点是点双分量的“连接点”。

特点

  • 针对 无向图。
  • 输出的是点双连通分量的集合（每个分量可能会有公共点）。
  • 核心条件：low[v] >= dfn[u]，并且要把整个分量输出。

5. 边双连通分量

原理

  • 在无向图中，如果不存在割边，则图是边双连通的。
  • 边双连通分量：图中极大的“删除任意一条边后仍然连通”的子图。
  • 实现：
    • 用栈保存边或节点。
    • 当 dfn[u] == low[u] 时，找到一个边双分量。
    • 与割边紧密相关，因为割边是边双分量的“分割点”。
    • 为什么是 dfn[u] == low[u]
      在 Tarjan 遍历时：当递归到某个 uu，若发现 dfn[u] == low[u]，说明：uu 及其子树 无法通过返祖边回到更高层的祖先。从 uu 到 DFS 栈顶的路径，正好形成了一个“封闭”的边双连通分量。类比强连通分量。

特点

  • 针对 无向图。
  • 输出的是边双连通分量。
  • 核心条件：low[v] >= dfn[u]，但是关注的是边而不是点。
算法作用对象条件判断关注重点结果
强连有向图dfn[u]==low[u]栈中的点每个强连通分量
割点无向图low[v] >= dfn[u]点哪些点是割点
割边无向图low[v] > dfn[u]边哪些边是割边
点双无向图low[v] >= dfn[u]点集输出点双分量
边双无向图dfn[u]==low[u]边集/点集输出边双分量

受欢迎的牛 G

  • 由于同一个强连通分量，可以相互喜欢，缩点，将强连通分量作为一个整体。
  • 缩点后的图是一个DAG，看一下叶子节点有几个，如果叶子节点有多个，它们相互不是粉丝，因此没有牛会是全牛明星。
  • 当叶子节点只有一个时，这个节点就是全牛明星，这个节点的大小就是答案。

校园网络

很多情况我们需要 DAG，对有环图，考虑通过强连通分量来缩点。
  • 问 1：所有入度为 00 的点往后传显然可以完成。
  • 问 2：入度为 00 的点和出度为 00 的点连一条边就构成了环，整个图为一个环即可（取两者数量多者）。
CPP
int main()
{
	cin>>n;
	for(int i=1; i<=n; i++)
	{
		a[i]=1;
		int x;
		while(1)
		{
			cin>>x;
			if(x==0) break;
			g[i].push_back(x);
		}
	}
	for(int i=1; i<=n; i++)
	{
		if(!dfn[i]) tarjan(i);
	}
	for(int i=1; i<=n; i++)
	{
		for(int v:g[i])
		{
			int x=scc[i];
			int y=scc[v];
			if(x!=y)
			{
				rd[y]++;
				cd[x]++;
			}
		}
	}
	int ans=0;
	for(int i=1; i<=num; i++)
	{
		if(rd[i]==0)
		{
			ans++;
		}
	}
	if(num==1) cout<<1<<endl;
	else cout<<ans<<endl;
	int ans1=0;
	for(int i=1; i<=num; i++)
	{
		if(cd[i]==0)
		{
			ans1++;
		}
	}
	if(num==1) cout<<0<<endl;
	else cout<<max(ans,ans1)<<endl;
	return 0;
}

[NOIP 2009 提高组] 最优贸易

  • 可以使用 tarjan 算法求最大强连通分量，并进行缩点，记录缩点后每个顶点的最小 minw 和 最大 maxw。
  • 缩点后的图是 DAG， 使用 toposort 求出到 原顶点 nn 所在缩点的 minw 和 最大 maxw, 答案即为 maxw−minwmaxw−minw。
  • 对于 顶点 11 所在缩点 ss 不能到达的缩点 vv，不要加入到新图中。代码中以起点和终点各做了一遍 bfs 来完成。
CPP
void tarjan(int x)
{
	dfn[x] = low[x] = ++idx;
	st.push(x);
	for (int y : g[x])
	{
		if (!dfn[y])
		{
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if (!scc[y])
		{
			low[x] = min(low[x], dfn[y]);
		}
	}
	if (low[x] == dfn[x])
	{
		++num;
		int t;
		maxw[num] = -1;
		minw[num] = 0x3f3f3f3f;
		do
		{
			t = st.top();
			st.pop();
			scc[t] = num;
			maxw[num] = max(maxw[num], a[t]);
			minw[num] = min(minw[num], a[t]);
		}
		while (t != x);
	}
}
void toposort()
{

	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		if (dp[x] != INF) ans = max(ans, maxw[x] - dp[x]);

		for (int y : ng[x])
		{
			if (!(vis1[y] && vis2[y])) continue;
			if (dp[x] != INF) dp[y] = min(dp[y], min(dp[x], minw[y]));
			if (--ind[y] == 0) q.push(y);
		}
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];

	for (int i = 1; i <= m; i++)
	{
		cin >> u[i] >> v[i] >> z[i];
		g[u[i]].push_back(v[i]);
		if (z[i] == 2) g[v[i]].push_back(u[i]);
	}

	for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
	for (int i = 1; i <= m; i++)
	{
		int x = scc[u[i]], y = scc[v[i]];
		if (z[i] == 1)
		{
			if (x != y)
			{
				ng[x].push_back(y);
				rng[y].push_back(x);
				rd[y]++;
			}
		}
		else
		{
			if (x != y)
			{
				ng[x].push_back(y);rng[y].push_back(x);rd[y]++;
				ng[y].push_back(x);rng[x].push_back(y);rd[x]++;
			}
		}
	}

	int S = scc[1], T = scc[n];
	while(!q.empty()) q.pop();
	q.push(S);
	vis1[S] = 1;
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (int y : ng[x]) 
			if (!vis1[y])
			{
				vis1[y] = 1;
				q.push(y);
			}
	}
	
	while(!q.empty()) q.pop();
	q.push(T);
	vis2[T] = 1;
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (int y : rng[x]) 
			if (!vis2[y])
			{
				vis2[y] = 1;
				q.push(y);
			}
	}
	for (int x = 1; x <= num; x++)
	{
		if (!(vis1[x] && vis2[x])) continue;
		for (int y : ng[x])
		{
			if (vis1[y] && vis2[y]) ind[y]++;
		}
	}

	for (int i = 1; i <= num; i++) dp[i] = INF;

	while(!q.empty()) q.pop();
	
	if (vis1[S] && vis2[S])
	{
		if (ind[S] == 0) q.push(S);
		dp[S] = minw[S];
	}

	for (int i = 1; i <= num; i++)
	{
		if (i != S && vis1[i] && vis2[i] && ind[i] == 0)
		{
			q.push(i);
		}
	}
	if (vis1[S] && vis2[S]) ans = max(ans, maxw[S] - dp[S]);
	toposort();
	cout << ans << '\n';
	return 0;
}

[ZJOI2004] 嗅探器

  • 如果这个点是割点且删去后，aa 和 bb 在不同的连通块就可行。标记 bb 在节点另外一边的存在性。
  • 不能是 aa 或 bb。
CPP
void tarjan(int u, int fa)
{

	int child = 0;
	vis[u]=1;
	low[u]=dfn[u]=++idx;
	hasb[u]=(u==b);
	for(int v : g[u])
	{
		if(v==fa) continue;
		if(!vis[v])
		{

			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(hasb[v] && fa!=u && low[v]>=dfn[u] && u!=a&& u!=b)
			{
				ans=min(ans,u);
			} 
			if(hasb[v]) hasb[u]=1;
		}
		else if(v!=fa)
		{
			low[u]=min(low[u],dfn[v]);
		}
	}

}

int main()
{
	cin >> n ;
	for (int i = 1; i <= 50000000; i++)
	{
		int x, y;
		cin >> x >> y;
		if(x==0 && y==0 ) break;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	cin>>a>>b;
	
	tarjan(a, -1);

	if(ans==0x3f3f3f3f)
	{
		cout<<"No solution"<<endl;
	}
	else cout<<ans<<endl;
	return 0;
}

间谍网络

  • 与上一题类似的，缩点以后统计每个点需要的最小价值。
  • DAG 不联通则无解，否则为入度为 00 者加起来。
CPP
void tarjan(int u)
{
	dfn[u]=low[u]=++idx;
	st.push(u);
	for(int v:g[u])
	{
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!scc[v]) low[u]=min(low[u],dfn[v]);
	}
		if(low[u]==dfn[u])
		{
			int t;
			num++;
			do
			{
				t=st.top();
				st.pop();
				scc[t]=num;
				w[num]=min(w[num],my[t]);
			}
			while(t!=u);
		}

}

int main()
{
	int p;
	cin>>n>>p;
	for(int i=1;i<=n;i++)
	{
		my[i]=0x3f3f3f3f;
		w[i]=0x3f3f3f3f;
		
	}
	for(int i=1; i<=p; i++)
	{
		int hao,shu;
		cin>>hao>>shu;
		my[hao]=shu;
	}
	int r;
	cin>>r;
	for(int i=1;i<=r;i++)
	{
		cin>>u[i]>>v[i];
		g[u[i]].push_back(v[i]);
	} 
	for(int i=1; i<=n; i++)
	{
		if(!dfn[i]&& my[i]!=0x3f3f3f3f ) tarjan(i);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
		{
			cout<<"NO"<<endl;
			cout<<i<<endl;
			return 0;
		}
	}
	for(int i=1; i<=r; i++)
	{
		int x=scc[u[i]];
		int y=scc[v[i]];
		if(x!=y)
		{
			ng[x].push_back(y);
			rd[y]++;
		}
	}

	int ans=0;
	for(int i=1; i<=num; i++)
	{
		if(rd[i]==0)ans+=w[i];
	}
	cout<<"YES"<<endl<<ans<<endl;
	return 0;
}

[POI 2008] BLO-Blockade

  • 求类似于割点状物，割开以后子树和非子树相乘有贡献。
  • 下面的点和上面的点有贡献。
  • 自己和任何其他点有贡献。
  • 图一定联通，跑一遍 tarjan 即可。
CPP
void tarjan(int u, int fa)
{
	sz[u]=1;
	int child = 0;
	vis[u]=1;
	low[u]=dfn[u]=++idx;int sum=0;
	for(int v : g[u])
	{
		if(!vis[v])
		{
			child++;
			tarjan(v,u);
			sz[u]+=sz[v];
			low[u]=min(low[u],low[v]);
			if( low[v]>=dfn[u])
			{
				flag[u]=1;
				sum+=sz[v];
				ans[u]+=(ll)(sz[v]*(n-sz[v]-1));
				
			} 
		}
		else if(v!=fa)
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(fa==u && child>=2)
	{
		flag[u]=1;
	}
	if(flag[u])
	{
		ans[u]+=(ll)sum*(n-1-sum);
	}
	ans[u]+=(ll)(2*(n-1));
}

signed main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	tarjan(1,1);

	for(int i=1;i<=n;i++)
	{
		cout<<ans[i]<<endl;
	}
	return 0;
}

[APIO2009] 抢掠计划

  • 和模板题十分相似。
  • 统计答案时注意，应当比较酒吧所在的 scc 的答案。
CPP
void tarjan(int u)
{
	dfn[u] = low[u] = ++idx;
	st.push(u);
	for (int v : g[u])
	{
		if (!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (!scc[v])
		{
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (low[u] == dfn[u])
	{
		int t;
		++num;
		do
		{
			t = st.top();
			st.pop();
			scc[t] = num;
			w[num] += a[t];
		}
		while (t != u);
	}
}
void toposort(int ss)
{

	queue<int> q;
	q.push(ss);

	for (int i = 1; i <= num; i++)
	{
		if (rd[i] == 0 && i!=ss ) q.push(i);
	}
		
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		if (dp[u] < 0) continue;
		for (int v : ng[u])
		{
				if (dp[v] < dp[u] + w[v])
				{
					dp[v] = dp[u] + w[v];
				}
			if (--rd[v] == 0) q.push(v);
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin>>n>>m;
	for(int i=1; i<=m; i++)
	{
		cin>>u[i]>>v[i];
		g[u[i]].push_back(v[i]);
	}
	for(int i=1; i<=n; i++)
	{
		cin>>a[i];
	}
	int s,p;
	cin>>s>>p;

	for(int i=1; i<=p; i++)
	{
		cin>>bar[i];
	}
	tarjan(s);
	for(int i=1; i<=m; i++)
	{
		int x=scc[u[i]],y=scc[v[i]];
		if(x!=y && y!=0 && x!=0)
		{
			ng[x].push_back(y);
			rd[y]++;
		}
	}
	for(int i=1; i<=num; i++)
	{
		dp[i]=-1;
	}
	int ss = scc[s];
	dp[ss] = w[ss];

	toposort(ss);


	ll ans = 0;
	for (int i=1; i<=p; i++)
	{
		ans = max(ans, dp[scc[bar[i]]]);
	}

	cout << ans <<endl;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...