这份代码使用了 dfs,复杂度显然不对,有没有入能卡掉它

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f;
const int inff=0x3f3f3f3f3f3f3f3f;
const int N=505;
const int M=1e5+5;
const int mod=1e9+7;
const int Root=500;
int head[N],Next[M],edge[M],ver[M],vis[N];
int n,tot=-1,ans=0,siz[N],f=0,x=0;
double startclock;
string s[105];
void add(int x,int y,int z){
	ver[++tot]=y;
	Next[tot]=head[x];
	edge[tot]=z;
	head[x]=tot;
}
void dfs(int root,int sum){
	x++;
	if(x%10000==0){
		if(clock()-startclock>=900000){
			f=1;
			return ;
		}
	}
	vis[root]=1;
	for(int i=head[root];~i;i=Next[i]){
		if(f==1){
			return ;
		}
		// cout<<i<<' '<<ver[i]<<'\n';
		if(vis[ver[i]]){
			// cout<<'a';
			continue;
		}
		dfs(ver[i],sum+siz[ver[i]]);
	}
	ans=max(ans,sum);
	// cout<<sum<<' '<<head[Root]<<' '<<vis[4]<<'\n';
	vis[root]=0;
}
void fast(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
signed main(){
//	freopen("ex.in","r",stdin);
//	freopen("ex.out","w",stdout);
//	fast();
	memset(head,-1,sizeof(head));
	startclock=clock();
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		siz[i]=s[i].size();
		// cout<<siz[i]<<'\n';
		s[i]=" "+s[i];
		add(Root,i,siz[i]);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i>j&&s[i][siz[i]]==s[i][1]&&s[j][siz[j]]==s[j][1]&&s[j][siz[j]]==s[i][1]){
				continue;
			}
			if(s[i][siz[i]]==s[j][1]){
				// cout<<i<<' '<<j<<'\n';
				add(i,j,siz[j]);
			}
		}
	}
	dfs(Root,0);
	cout<<ans;
	return 0;
}

(在devc++中将第 23 行的 900000 改为900)

4 条评论

  • @ 2026-10-17 11:46:28

    随机化应该过不了,因为正确的情况很少(只有 1 种)

    • @ 2026-10-17 11:43:36

      尝试随机化(?)

      • @ 2026-10-17 11:33:40

        值得注意的是,利用相似的思路,可以卡掉这种dfs 的大部分变体。

        • @ 2026-10-17 11:28:52

          Hack:

          in:

          16
          kkkkkkkkkkkkkkkkkkkkkkkkkkkkhhhhhhhhhhhhhhhzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
          ad
          dae
          dbe
          dce
          dde
          dee
          dfe
          dge
          ead
          ebd
          ecd
          edd
          eed
          efd
          egd
          
          

          ans: 72

          • 1

          信息

          ID
          917
          时间
          1000ms
          内存
          256MiB
          难度
          7
          标签
          (无)
          递交数
          56
          已通过
          11
          上传者