【题解】10-1提高组模拟

图论啥的都不会了，还有救吗？

USACO的第一个测试点是样例，可以骗分的……

A.公路通行税

link

这题就是找出图中的最长不重复的道路

在注意到$1 \leq n \leq 10^3$，想也不用想就可以排除掉Floyd

由于每个道路的长度都是$1$，所以就可以直接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
// Problem:Luogu P2185 公路通行税

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1010;
vector <int> g[MAXN];
int n,m,ans;
bool vis[MAXN];
void bfs(int s)
{
	queue <pair<int,int>> q;
	q.push({s,0});
	vis[s]=1;
	while(!q.empty())
	{
		int u=q.front().first,dis=q.front().second;
		ans=max(ans,dis);
		q.pop();
		for(auto v:g[u])
			if(!vis[v])
				vis[v]=1,q.push({v,dis+1});
	}
}
void solve()
{
	ans=-1;
	for(int i=1;i<=n;i++)g[i].clear();
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));
		bfs(i);
	}
	cout<<ans*100<<'\n';
}
int main()
{
	while(1)
	{
		cin>>n>>m;
		if(n&&m)solve();
		else break;
	}
	return 0;
}

B. [USACO22OPEN] Visits S

link

这题想亻乙想就知道这题的答案就是非环部分的叫声总和加上环上部分总和减去环上部分的最小值（因为绕一圈回来肯定有一个去朋友家了，所以贪心舍弃最小值）

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
// Problem:Luogu P8269 [USACO22OPEN] Visits S

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200010;
#define int long long
int a[MAXN],v[MAXN],indeg[MAXN],n,ans,minn=LLONG_MAX;
bool vis[MAXN];
void topo()
{
	queue <int> q;
	for(int i=1;i<=n;i++)
		if(!indeg[i])q.push(i);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		ans+=v[u];
		vis[u]=1;
		indeg[a[u]]--;
		if(!indeg[a[u]])q.push(a[u]);
	}
}
void dfs(int u)
{
	vis[u]=1;
	minn=min(minn,v[u]);
	if(!vis[a[u]])dfs(a[u]);
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>v[i];
		indeg[a[i]]++;
	}
	topo();
	for(int i=1;i<=n;i++)
		if(!vis[i])ans+=v[i];
	for(int i=1;i<=n;i++)
		if(!vis[i])
		{
			minn=LLONG_MAX;
			dfs(i);
			ans-=minn;
		}
	cout<<ans;
	return 0;
}

C. [USACO3.1] 丑数 Humble Numbers

这题一看就是一种恶心人的数学

可以用多次乘来得到第$n$小的丑数

怎么做呢？

先假设$1$是丑数，然后再用指针记录，分别乘$S$中的数，接下来对指针进行更新

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
// Problem:Luogu P2723 [USACO3.1] 丑数 Humble Numbers

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[110],f[114514],idx[110];
signed main()
{
	int k,n;
	cin>>k>>n;
	for(int i=1;i<=k;i++)cin>>a[i];
	f[0]=1;//假设1也是丑数
	for(int i=1;i<=n;i++)
	{
		int minn=LLONG_MAX;
		for(int j=1;j<=k;j++)
			minn=min(minn,f[idx[j]]*a[j]);//分别相乘找到最小的乘积
		f[i]=minn;
		for(int j=1;j<=k;j++)
			if(f[idx[j]]*a[j]==minn)//如果有多个相同的质因数相乘等于最小值，就将指针累加
				idx[j]++;
	}
	cout<<f[n];
	return 0;
}

原先用stl做的超时了……

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
// Problem:Luogu P2723 [USACO3.1] 丑数 Humble Numbers

#include<bits/stdc++.h>
using namespace std;
#define int long long
set <int> st;
priority_queue <int,vector <int>,greater<int> > q;
int a[100010];
signed main()
{
	int k,n;
	scanf("%lld%lld",&k,&n);
	for(int i=1;i<=k;i++)scanf("%lld",&a[i]);
	q.push(1);
	st.insert(1);
	int cnt=0,front;
	while(cnt<=n)
	{
		cnt++;
		front=q.top();
		q.pop();
		for(int j=1;j<=k;j++)
		{
			int num=front*a[j];
			if(!st.count(num))
			{
				q.push(num);
				st.insert(num);
			}
		}
	}
	printf("%d",front);
	return 0;
}

D. [TJOI2013] 黄金矿工

link

这题的数据非常💧，导致01背包的模板都能过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Problem:Luogu P3961 [TJOI2013] 黄金矿工

#include<bits/stdc++.h>
using namespace std;
const int MAXN=210;
int v[MAXN],w[MAXN],dp[40010],t,n;
int main()
{
	cin>>n>>t;
	for(int i=1;i<=n;i++)
	{
		int tmp;
		cin>>tmp>>tmp>>v[i]>>w[i];
	}
	for(int i=1;i<=n;i++)
		for(int j=t;j>=v[i];j--)
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
	cout<<dp[t];
	return 0;
}

《天津省选》

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
// Problem:Luogu P3961 [TJOI2013] 黄金矿工

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int x,y,t,v;
	double b;//斜率
}pos[2010];
bool cmp(node a,node b)
{
	if(a.b==b.b)return a.y<b.y;
	return a.b<b.b;
}
int n,T,gold[2010],t[2010][2010],v[2010][2010],f[40010],cnt;
int main()
{
	cnt=0;
	cin>>n>>T;
	for(int i=1;i<=n;i++)
	{
		cin>>pos[i].x>>pos[i].y>>pos[i].t>>pos[i].v;
		pos[i].b=pos[i].y*1.0/pos[i].x;//求斜率
	}
	sort(pos+1,pos+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		if(i==1||pos[i].b!=pos[i-1].b)cnt++;
		if(gold[cnt]==0)
		{
			gold[cnt]=1;
			t[cnt][1]=pos[i].t;//第cnt组1个金子的时间
			v[cnt][1]=pos[i].v;//第cnt组1个金子的价值
		}
		else
		{
			gold[cnt]++;
			t[cnt][gold[cnt]]=t[cnt][gold[cnt]-1]+pos[i].t;
			v[cnt][gold[cnt]]=v[cnt][gold[cnt]-1]+pos[i].v;
		}
	}
	memset(f,0,sizeof(f));
	for(int i=1;i<=cnt;i++)
		for(int j=T;j>=t[i][1];j--)
		{
			int maxn=f[j];
			for(int k=1;k<=gold[i];k++)
				if(j>=t[i][k])
					maxn=max(maxn,f[j-t[i][k]]+v[i][k]);
			f[j]=maxn;
		}
	cout<<f[T];
	return 0;
}
游记
#集训
【题解】10-1提高组模拟
http://j27egu.github.io/2025/10/01/【题解】10-1提高组模拟/
作者
j27eGU
发布于
2025年10月1日
许可协议