- 单词接龙
谁能卡掉这份代码
- @ 2026-10-17 11:05:47
这份代码使用了 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 条评论
-
caohongxuan LV 8 @ 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:52Hack:
in:
16 kkkkkkkkkkkkkkkkkkkkkkkkkkkkhhhhhhhhhhhhhhhzzzzzzzzzzzzzzzzzzzzzzzzzzzzz ad dae dbe dce dde dee dfe dge ead ebd ecd edd eed efd egdans: 72
- 1
信息
- ID
- 917
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 56
- 已通过
- 11
- 上传者