【题解】10-5入门组模拟

这次考的倒挺均衡

A.[蓝桥杯 2013 国 C] 危险系数

lnk

这道题用DFS/BFS都可以过，枚举$n$个节点被删除的情况，数据够小，$\text{MAXN}=1000$。

由于同学DFS没调出来，我帮他写了一个栈模拟的DFS，顺便附上我的BFS。

DFS（栈模拟）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1010; 
int n,m;
vector <int> g[MAXN];
int cnt[MAXN];
bool vis[MAXN];
stack <int> stk; 
bool solve(int s,int t,int ban)
{
	memset(vis,0,sizeof(vis));
	while(!stk.empty())stk.pop();
	stk.push(s);
	vis[s]=1;
	while(!stk.empty())
	{
		int u=stk.top();
		stk.pop();
		for(auto v:g[u])
			if(!vis[v]&&v!=ban)
			{
				if(v==t)return 0;
				stk.push(v);
				vis[v]=1;
			}
	}
	return 1;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int u,v,ans=0;
	cin>>u>>v;
	if(solve(u,v,-1))
	{
		puts("-1");
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		if(i==u||i==v)continue;
		ans+=solve(u,v,i);
	}
	cout<<ans;
	return 0;
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1010; 
int n,m;
vector <int> g[MAXN];
int cnt[MAXN];
bool vis[MAXN];
queue <int> q;
bool solve(int s,int t,int ban)
{
	memset(vis,0,sizeof(vis));
	while(!q.empty())q.pop();
	q.push(s);
	vis[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(auto v:g[u])
		{
			if(!vis[v]&&v!=ban)
			{
				if(v==t)return 0;
				q.push(v);
				vis[v]=1;
			}
		}
	}
	return 1;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int u,v,ans=0;
	cin>>u>>v;
	if(solve(u,v,-1))
	{
		puts("-1");
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		if(i==u||i==v)continue;
		ans+=solve(u,v,i);
	}
	cout<<ans;
	return 0;
}

B.【XR-3】小道消息

lnk

根据切比雪夫定理（虽然我没用到）：

  • 当$k+1$是质数时，且$1$ 到$ n$没有$k$的倍数，就能在$\bf 1$天内传播完
  • 否则就只能在$\bf 2$天内传播完
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
#define int long long
bool is_prime(int n)
{
	if(n==2)return 1;//! 
	for(int i=2;i*i<=n;i++)
		if(n%i==0)return 0;
	return 1;
}
signed main()
{
	int n,k;
	cin>>n>>k;
	if(is_prime(k+1)&&(k<<1)>=n)cout<<1;
	else cout<<2;
}

C.[ICPC 2013 WF] Low Power

二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1010; 
int n,m;
vector <int> g[MAXN];
int cnt[MAXN];
bool vis[MAXN];
stack <int> stk; 
bool solve(int s,int t,int ban)
{
	memset(vis,0,sizeof(vis));
	while(!stk.empty())stk.pop();
	stk.push(s);
	vis[s]=1;
	while(!stk.empty())
	{
		int u=stk.top();
		stk.pop();
		for(auto v:g[u])
			if(!vis[v]&&v!=ban)
			{
				if(v==t)return 0;
				stk.push(v);
				vis[v]=1;
			}
	}
	return 1;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int u,v,ans=0;
	cin>>u>>v;
	if(solve(u,v,-1))
	{
		puts("-1");
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		if(i==u||i==v)continue;
		ans+=solve(u,v,i);
	}
	cout<<ans;
	return 0;
}

D.[APIO2009] 采油区域

前缀和+暴力

dalao说这题很水……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>
using namespace std;
int mp[2000][2000];
int a[2000][2000],b[2000][2000],c[2000][2000],d[2000][2000];
int n,m,k;
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	int x;
	int cnt=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&x);
			mp[i][j]=mp[i-1][j]+mp[i][j-1]-mp[i-1][j-1]+x;
		}
	}
	for(int i=n;i>=k;i--)
	{
		for(int j=m;j>=k;j--)
		{
			mp[i][j]-=mp[i-k][j]+mp[i][j-k]-mp[i-k][j-k];
		}
	}
	for(int i=k;i<=n;i++)
	{
		for(int j=k;j<=m;j++)
		{
			a[i][j]=max(mp[i][j],max(a[i-1][j],a[i][j-1]));
		}
	}
	for(int i=k;i<=n;i++)
	{
		for(int j=m;j>=k;j--)
		{
			b[i][j]=max(mp[i][j],max(b[i-1][j],b[i][j+1]));
		}
	}
	for(int i=n;i>=k;i--)
	{
		for(int j=k;j<=m;j++)
		{
			c[i][j]=max(mp[i][j],max(c[i+1][j],c[i][j-1]));
		}
	}
	for(int i=n;i>=k;i--)
	{
		for(int j=m;j>=k;j--)
		{
			d[i][j]=max(mp[i][j],max(d[i+1][j],d[i][j+1]));
		}
	}
	int ans=0;
	for(int i=k;i<=n-k;i++)
	{
		for(int j=k;j<=m-k;j++)
		{
			ans=max(ans,a[i][j]+b[i][j+k]+c[i+k][m]);
		}
	}
	for(int i=k;i<=n-k;i++)
	{
		for(int j=k;j<=m-k;j++)
		{
			ans=max(ans,a[i][m]+c[i+k][j]+d[i+k][j+k]);
		}
	}
	for(int i=k;i<=n-k;i++)
	{
		for(int j=k;j<=m-k;j++)
		{
			ans=max(ans,a[i][j]+b[n][j+k]+c[i+k][j]);
		}
	}
	for(int i=k;i<=n-k;i++)
	{
		for(int j=k;j<=m-k;j++)
		{
			ans=max(ans,a[n][j]+b[i][j+k]+d[i+k][j+k]);
		}
	}
	for(int i=k;i<=n-k;i++)
	{
		for(int j=k+k;j<=m-k;j++)
		{
			ans=max(ans,a[n][j-k]+b[n][j+k]+mp[i][j]);
		}
	}
	for(int i=k+k;i<=n-k;i++)
	{
		for(int j=k;j<=m-k;j++)
		{
			ans=max(ans,a[i-k][m]+c[i+k][m]+mp[i][j]);
		}
	}
	printf("%d",ans);
	return 0;
}
游记
#集训
【题解】10-5入门组模拟
http://j27egu.github.io/2025/10/06/【题解】10-5入门组模拟/
作者
j27eGU
发布于
2025年10月6日
许可协议