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

还好第一题的记忆化搜索做出来了，不然就废了

A.跑步

link

这道题使用记忆化搜索就可以过了，记得开long long

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Problem:Luogu P1806 跑步

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,f[1010][1010];
int dfs(int sum,int lst)//sum表示总和，lst表示当前选择的圈数
{
	if(f[sum][lst]!=-1)return f[sum][lst];
	if(sum==n)return 1;
	int p=0;
	for(int i=lst+1;i<=n-sum;i++)
		p+=dfs(i+sum,i);
	return f[sum][lst]=p;
}
signed main()
{
	memset(f,-1,sizeof(f));
	cin>>n;
	cout<<dfs(0,0)-1;
	return 0;
}

B. [POI 2018 R2] 自行车道 Bike paths

link

这道题考的是tarjan缩点

缩点完这个图就成了一个DAG（有向无环图），然后就可以打记忆化搜索了

转移方程就是：
$$
dp_u=\sum dp_v\
v是u的儿子
$$
初始化就是：
$$
dp_u=scc_u\
scc_u就是u所属的强连通分量的大小
$$
注意的是节点本身并不计入答案

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
// Problem:Luogu P12760 [POI 2018 R2] 自行车道 Bike paths

#include<bits/stdc++.h>
using namespace std;
const int MAXN=50010;
int n,m;
vector <int> g1[MAXN],g2[MAXN];
int dfn[MAXN],low[MAXN],idx;
int stk[MAXN],top;
bool ins[MAXN];
int scc[MAXN],scccnt;
vector <vector<int> > _scc;
void tarjan(int u,int fa)
{
	dfn[u]=low[u]=++idx;
	stk[++top]=u;
	ins[u]=1;
	for(auto v:g1[u])
		if(!dfn[v])
		{
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
		}
		else if(ins[v])
			low[u]=min(low[u],dfn[v]);
	if(low[u]==dfn[u])
	{
		vector <int> v;
		while(top>0&&stk[top]!=u)
		{
			v.push_back(stk[top]);
			ins[stk[top]]=0;
			scc[stk[top]]=scccnt;
			top--;
		}
		v.push_back(stk[top]);
		ins[u]=0;
		scc[u]=scccnt;
		top--;
		_scc.push_back(v);
		scccnt++;
	}
}
int dp[MAXN];
void dfs(int u)
{
	if(dp[u])return ;
	for(auto v:g2[u])
		dfs(v),dp[u]+=dp[v];
	dp[u]+=_scc[u].size();
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		g1[u].push_back(v);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])tarjan(i,0);
	for(int i=0;i<scccnt;i++)
		for(auto v:_scc[i])
			for(auto j:g1[v])
				if(scc[j]!=i)
					g2[i].push_back(scc[j]);
	for(int i=0;i<scccnt;i++)
		if(!dp[i])dfs(i);
	for(int i=1;i<=n;i++)
		cout<<dp[scc[i]]-1<<endl;
	return 0;
}

C.[HNOI2013] 比赛

link

直接暴力dfs，但是需要加一些剪枝

  1. 考虑到最后再来判断太浪费，在搜索时就限制每人的得分不得超过总分
  2. 如果对于第$u$个人来说，它赢下所有以后的比赛也打不出自己的总分（最后的分数也需要等于总分）
  3. 考虑$sx$表示分出胜负的总场数，$sy$表示所有队的总得分。那么显然有$sx+sy=\frac{n(n-1)}{2}$，且$3sx+2sy=su$，由此可以截除$sx$和$sy$。在搜索时，可利用其限制胜利场次
  4. 利用人数为$X$，分数集合为$A的比赛方案数一定，它与某人具体的得分是无关的。因此可以利用记忆化索索，把最后剩余的几个人的分数哈希存储起来（这可能并不算是剪枝）
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
// Problem:Luogu P3230 [HNOI2013] 比赛

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1010;
const int B=78,mod=1000000007;
int n,sum[MAXN],a[MAXN],b[MAXN],su,sx,sy;
map <int,int> ha;
int dfs(int u,int v)
{
	if(u==n)return 1;
	if(a[u]+3*(n-v+1)<sum[u])return 0;
	int ret=0;
	if(v>n)
	{
		for(int i=u+1;i<=n;i++)b[i]=sum[i]-a[i];
		sort(b+u+1,b+n+1,less<int>());
		int h=0;
		for(int i=u+1;i<=n;i++)h=h*B+b[i];
		if(ha.find(h)!=ha.end())return ha[h];
		else return ha[h]=dfs(u+1,u+2);
	}
	if(a[u]+3<=sum[u]&&sx)
		a[u]+=3,sx--,ret+=dfs(u,v+1),a[u]-=3,sx++;
	if(a[u]+1<=sum[u]&&a[v]+1<=sum[v]&&sy)
		a[u]++,a[v]++,sy--,ret+=dfs(u,v+1),a[u]--,a[v]--,sy++;
	if(a[v]+3<=sum[v]&&sx)
		a[v]+=3,sx--,ret+=dfs(u,v+1),a[v]-=3,sx++;
	return ret%mod;
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>sum[i],su+=sum[i];
	sx=su-n*n+n;
	sy=(su-3*sx)>>1;
	sort(sum+1,sum+n+1,less<int>());
	cout<<dfs(1,2);
}

D.[MtOI2018] 衣服？身外之物！

link

用7进制做状压dp，然后7788搞下就可以了

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
// Problem:Luogu P4928 [MtOI2018] 衣服？身外之物！

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=10,MAXM=2010;
int n,m,x[MAXN],y[MAXN],z[MAXM],ans=LLONG_MIN;
int f[2][120010];
int p[]={0,1,7,49,343};
bool vis[120010];
vector <int> a[2];
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int nxt(int zt,int now)
{
	int res=zt;
	for(int i=1;i<=n;i++)
		if(i==now)res+=y[i]*p[i];
		else if(zt/p[i]%7!=0)res-=p[i];
	return res;
}
signed main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)x[i]=read();
	for(int i=1;i<=n;i++)y[i]=read();
	for(int i=1;i<=m;i++)z[i]=read();
	a[0].push_back(0);
	bool op=0;
	for(int i=1;i<=m;i++)
	{
		memset(f[op^1],-63,sizeof(f[op^1]));
		a[op^1].clear();
		for(int j=0;j<a[op].size();j++)vis[a[op][j]]=0;
		for(int j=0;j<a[op].size();j++)
		{
			int zt=a[op][j];
			for(int k=1;k<=n;k++)
				if(zt/p[k]%7==0)
				{
					int now=nxt(zt,k);
					if(!vis[now])a[op^1].push_back(now),vis[now]=1;
					f[op^1][now]=max(f[op^1][now],f[op][zt]+z[i]*x[k]);
				}
		}
		op^=1;
		if(!a[op].size())
		{
			puts("gcd loves her clothes!");
			return 0;
		}
	}
	for(int i=0;i<a[op].size();i++)
		ans=max(ans,f[op][a[op][i]]);
	cout<<ans;
}
游记
#集训
【题解】10-2提高组模拟
http://j27egu.github.io/2025/10/02/【题解】10-2提高组模拟/
作者
j27eGU
发布于
2025年10月2日
许可协议