关于vector的reserve函数
  • 板块学术版
  • 楼主WanderingTrader
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/7/16 08:04
  • 上次更新2023/11/3 09:36:50
查看原帖
关于vector的reserve函数
270791
WanderingTrader楼主2023/7/16 08:04

查了下reference,感觉这个函数只会对运行效率有影响?但昨晚ABC的D,照着官方解答 O(n×n!)O(n\times n!) 的思路打了一下,发现如果不加reserve会WA。代码如下:

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int hate[N],t,n,m,ans;
vector<int> teams;
void dfs(int x)
{
	if(x>=n){if((int)teams.size()==t)++ans;return;}
	for(auto& team:teams)
		if(!(team&hate[x]))
		{
			team^=(1<<x);
			dfs(x+1);
			team^=(1<<x);
		}
	if((int)teams.size()<t)
	{
		teams.push_back(1<<x);
		dfs(x+1);
		teams.pop_back();
	}
}
int main()
{
	scanf("%d%d%d",&n,&t,&m);
	for(int i=1,a,b;i<=m;++i)
	{
		scanf("%d%d",&a,&b); --a;--b;
		hate[b]|=(1<<a);
	}
	teams.reserve(t);  //here
	dfs(0);
	printf("%d\n",ans);
	return 0;
}

标有注释的那一行,如果删去会WA。

请问哪位大佬可以帮忙分析一下是什么原因?

2023/7/16 08:04
加载中...