128 条题解
-
2冲啊小笼包 LV 9 @ 2015-10-15 19:20:46
很简单的一道题。关键就是深搜(DFS)要想好。
我们对目前的“龙”设定为NOW变量。假设他现在是ABCDE。
枚举所有还能用的字符串(用use来统计被用了几次) 比如,有个字符串是DEAAA;
因为不能是包含关系
我们先从now中取出BCDE。看看能不能跟需要的拼接上,显然前4位是DEAA,不可以。
一直取,当我们取到DE的时候正好匹配。那么拼接上,now变成了ABCDEAAA,继续回溯。这里有个剪枝。就是我们DE的时候匹配OK了,接下来就不用匹配这个字符串了,因为很容易证明,就算又一次匹配上了也不会比现在的结果要好。(想想看?对吧);
但是实际上这个剪纸有没有都无所谓。时间是足够的。
最后匹配结束后,计算now的长度是否大于ans。是就保存
最后退出给出如下代码。
###pascal code
program CODE1018;
var s:array[1..25] of string;
ans,i,n:longint;
use:array[1..25] of longint;
f:string;
procedure main(now:string);
var i,j,len:longint;
a,b:string;
begin
len:=length(now);
for i:=1 to n do
if use[i]<2 then
for j:=2 to length(now) do
begin
a:=copy(now,j,length(now)); b:=copy(s[i],1,length(now)-j+1);
if a=b then
begin
inc(use[i]); now:=now+copy(s[i],length(now)-j+2,length(s[i]));
main(now);
dec(use[i]); now:=copy(now,1,len);
end;
end;
if length(now)>ans then
ans:=length(now);
end;begin
readln(n); ans:=0; fillchar(use,sizeof(use),0);
for i:=1 to n do
readln(s[i]);readln(f);
for i:=1 to n do
if s[i][1]=f then
begin
inc(use[i]); main(s[i]); dec(use[i]);
end;
write(ans);
end. -
12018-02-04 23:26:27@
不是很懂第7个点Otz,于是借(zhao)鉴(ban)了楼下的方法,DFS时长达0.8s就停止搜索
#include <iostream> #include <ctime> class Timer { public: struct NeverUsedException {}; private: enum class _Status { NeverUsed, Running, Stopped }; clock_t _startClock; clock_t _endClock; _Status _status; public: Timer():_status(_Status::NeverUsed) {} void start() { _status = _Status::Running; _startClock = clock(); } void stop() { if (_status == _Status::Running) { _status = _Status::Stopped; _endClock = clock(); } } bool isRunning() { return _status == _Status::Running; } bool isStopped() { return _status == _Status::Stopped; } double ellapse() { switch(_status) { case _Status::Running: return 1.0 * (clock() - _startClock) / CLOCKS_PER_SEC; case _Status::Stopped: return 1.0 * (_endClock - _startClock) / CLOCKS_PER_SEC; case _Status::NeverUsed: throw NeverUsedException(); } } }; using namespace std; int N; string str[20]; char firstCh; int dist[20][20]; // linkable[a][b] = true if str[a] -> str[b] int vis[20]; Timer timer; void input() { cin >> N; for (int i = 0; i < N; i++) cin >> str[i]; cin >> firstCh; } int getDist(const string& A, const string& B) { size_t maxLen = min(A.length(), B.length()) - 1; for (size_t len = 1; len <= maxLen; len++) { bool success = true; for (size_t i = A.length() - len, j = 0; j < len; i++, j++) if (A[i] != B[j]) success = false; if (success) return (int)(B.length() - len); } return -1; } void judgeLinkable() { for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) dist[i][j] = getDist(str[i], str[j]); } int dfs(int cur) { int ans = 0; vis[cur] += 1; for (int to = 0; to < N; to++) if (vis[to] < 2 && dist[cur][to] != -1 && timer.ellapse() < 0.8) ans = max(ans, dist[cur][to] + dfs(to)); vis[cur] -= 1; return ans; } int main() { input(); judgeLinkable(); timer.start(); int ans = 0; for (int i = 0; i < N; i++) if (str[i][0] == firstCh) ans = max(ans, (int)str[i].length() + dfs(i)); printf("%d\n", ans); return 0; }
-
02017-08-08 20:15:39@
#include <iostream>
#include <cstring>
#include <time.h>
using namespace std;
clock_t start, finish;
char primary_data[45][500],s,present_dragon[500];
bool judge[25][2];
int n,present_max,present_length=1,common_length;
bool judge_dragon(char a[],char b[])
{
int length_a,length_b;length_a=strlen(a);
length_b=strlen(b);for(int i=1;i<=min(length_a,length_b-1);i++)
{
bool present_judge=1;
for(int j=length_a-i;j<=length_a-1;j++)
{
if(a[j]!=b[j-length_a+i])
present_judge=0;
}
if(present_judge)
{
common_length=i;
return 1;
}
}
return 0;
}
void dfs(int p)
{
finish = clock();
if(finish-start>900000)
return;
for(int i=1;i<=n;i++)
{
if((judge[i][0]==0||judge[i][1]==0)&&judge_dragon(present_dragon,primary_data[i]))
{
int l,l2;
l=strlen(present_dragon);
l2=strlen(primary_data[i]);
judge[i][0]==0?judge[i][0]=1:judge[i][1]=1;
for(int j=l;j<=l+l2-common_length;j++)
present_dragon[j]=primary_data[i][common_length+j-l];present_max=max(l+l2-common_length,present_max);
dfs(p+1);
judge[i][0]==1?judge[i][0]=0:judge[i][1]=0;
for(int j=l;j<=l+l2-common_length;j++)
present_dragon[j]=0;
}
}return;
}
int main()
{
ios::sync_with_stdio(false);
start = clock();cin>>n;
for(int i=1;i<=n;i++)
cin>>primary_data[i];
cin>>s;
present_dragon[0]=s;
dfs(0);
cout<<present_max<<endl;
return 0;
} -
02017-01-22 17:35:54@
const
maxn=20;
var
s:array[1..maxn] of string;
head:char;
best,i,n:integer;
add:array[1..maxn,1..maxn] of integer;
used:array[1..maxn] of integer;procedure calcadd;
var
i,j,k,t,min:integer;
ok:boolean;
begin
for i:=1 to n do
for j:=1 to n do
begin
if length(s[i])<length(s[j]) then min:=length(s[i]) else min:=length(s[j]);
for k:=1 to min-1 do
begin
{check}
ok:=true;
for t:=1 to k do
if s[j,t]<>s[i,length(s[i])-k+t] then
begin
ok:=false;
break;
end;
if ok then break;
end;
if ok then
add[i,j]:=length(s[j])-k
else
add[i,j]:=0;
end;
end;procedure search(last,len:integer);
var
i:integer;
begin
if len>best then
best:=len;
for i:=1 to n do
if (add[last,i]>0)and(used[i]<2) then
begin
inc(used[i]);
search(i,len+add[last,i]);
dec(used[i]);
end;
end;begin
readln(n);
for i:=1 to n do
readln(s[i]);
readln(head);
calcadd;
best:=0;
fillchar(used,sizeof(used),0);
for i:=1 to n do
if s[i,1]=head then
begin
used[i]:=1;
search(i,length(s[i]));
used[i]:=0;
end;
writeln(best);
end. -
02016-08-02 10:26:17@
这卡时搜索很可以。。。
另:数据存在没有龙的情况
``` c++
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstring>
using namespace std;string stra[30];
int times[30];
clock_t b;
string beg;
int n;
int ans = 0;bool ispre(string &pre, string &str)
{
return str.find(pre) == 0 && pre != str;
}size_t dfs(const string & str)
{
//cout << str << endl;
if (clock() - b >= 800) return 0;
size_t len = str.length();
string beh;
size_t cnt = 0;
for (size_t i = len-1; i >= 1; i--) {
beh = str[i]+beh;
for (size_t j = 1; j <= n; j++) {
if (times[j] && ispre(beh, stra[j])) {
times[j]--;
cnt = max(cnt, dfs(stra[j]) + stra[j].size() - len + i);
times[j]++;
}
}
}
return cnt;
}int main()
{
b = clock();
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> stra[i];
times[i] = 2;
}
cin >> beg;
beg = "s"+beg;
size_t ans = dfs(beg);
if (ans == 0) cout << 0 << endl;
else cout << ans+1 << endl;
return 0;
} -
02016-07-18 20:21:39@
什么叫不能存在真包含 DEFGEF 和EFG不能相连? 看你们的程序没对这点处理啊
-
02016-03-27 17:54:27@
呵呵~~ 第六个点超时过不去吗?
这时就要用到**FP的系统单元**了**!**
开始程序时计时,当到0.9秒时输出。。因为第六个数据卡时间,而算到后面的结果都是都是一样的。
测试数据 #0: Accepted, time = 0 ms, mem = 920 KiB, score = 12
测试数据 #1: Accepted, time = 0 ms, mem = 916 KiB, score = 12
测试数据 #2: Accepted, time = 0 ms, mem = 920 KiB, score = 12
测试数据 #3: Accepted, time = 15 ms, mem = 916 KiB, score = 12
测试数据 #4: Accepted, time = 0 ms, mem = 916 KiB, score = 12
测试数据 #5: Accepted, time = 0 ms, mem = 916 KiB, score = 12
测试数据 #6: Accepted, time = 906 ms, mem = 928 KiB, score = 16
测试数据 #7: Accepted, time = 0 ms, mem = 920 KiB, score = 12
Accepted, time = 921 ms, mem = 928 KiB, score = 100
```pascal
uses sysutils;
type int=longint;
var
time,tt:tdatetime;
n,max,i,ans:int;
s:array[0..21]of string;
f,long:array[0..21]of int;
m:char;
procedure dfs(x:int);
var
i,t,j:int;
begin
if ans>max then max:=ans;
tt:=now*86400;
if tt-time>0.9 then
begin
writeln(max);
halt;
end;
for i:=1 to n do if f[i]<2 then
begin
if long[x]<long[i] then t:=long[x]-1 else t:=long[i]-1;
for j:=long[x] downto long[x]-t+1 do
if copy(s[x],j,long[x]-j+1)=copy(s[i],1,long[x]-j+1) then
begin
inc(f[i]);
ans:=ans+long[i]-long[x]+j-1;
dfs(i);
ans:=ans-long[i]+long[x]-j+1;
dec(f[i]);
break;
end;
end;
end;begin
readln(n); max:=0;
for i:=1 to n do
begin
readln(s[i]);
long[i]:=length(s[i]);
end;
for i:=1 to n do f[i]:=0;
readln(m);
time:=now*86400;
for i:=1 to n do if s[i][1]=m then
begin
inc(f[i]);
ans:=long[i];
dfs(i);
dec(f[i]);
end;
writeln(max);
end.
```
不用谢我,我叫**红领巾!** -
02016-03-18 23:32:51@
#include <iostream> #include <cmath> #include <queue> using namespace std; int n,m,ans; char list[110][110]; pair <int,int> p0; queue<pair <int,int> > q; int dx[12] = {-1,-1,-1,0,0,1,1,1,-2,0,0,2}, dy[12] = {-1,0,1,-1,1,-1,0,1,0,-2,2,0}; void bfs(pair <int,int> p0) { pair <int,int> p; q.push(p0); list[p0.first][p0.second] = '-'; while(q.size()) { p = q.front(); q.pop(); for (int i = 0; i < 12; i++) { pair <int,int> np; np.first = p.first + dx[i]; np.second = p.second + dy[i]; if (abs(np.first-p.first)+abs(np.second-p.second) <= 2 && list[np.first][np.second] == '#') { q.push(np); list[np.first][np.second] = '-'; } } } } int main() { int i,j; while (cin >> n >> m) { for (i = 0; i < n; i++) for (j = 0; j < m; j++) cin >> list[i][j]; for (i = 0; i < n; i++) for (j = 0; j < m; j++) if (list[i][j] == '#') { ans++; p0.first = i; p0.second = j; bfs(p0); } cout << ans << endl; } return 0; }
-
02015-12-25 14:27:01@
适时地使用windows API可以帮助AC
朴素搜索有一个点卡时间。经过推测可知该测试点一定是极端数据,搜出的所有解应该都是一样的。
于是启用 GetTickCount() 函数,当程序运行超过900ms时直接输出答案结束程序,ACvoid search(int index, int length, const int numWords){
int i;
if(length > maxLength)
maxLength = length;
if(GetTickCount()-beginTime >= 900){
printf("%d\n", maxLength);
exit(0);
}
for(i=0; i<numWords; i++){
if(graph[index][i] && usedTimes[i]<2){
usedTimes[i]++;
search(i, length+graph[index][i], numWords);
usedTimes[i]--;
}
}
} -
02015-09-17 20:34:30@
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN = 50;vector<pair<int, int> > v[MAXN];
char s[MAXN][MAXN], a;
int slen[MAXN], ans = 0, big = 0;
int vis[MAXN];void dfs(int node){
for(int i=0; i<v[node].size(); i++)
if(vis[v[node][i].first] < 2){
vis[v[node][i].first]++;
ans += v[node][i].second;
dfs(v[node][i].first);
vis[v[node][i].first]--;
ans -= v[node][i].second;
}
big = max(big, ans);
}int main()
{
int n;
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%s", s[i]);
slen[i] = strlen(s[i]);
}
scanf("%s", &a);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++){
int len = slen[i] - slen[j];
if(len < 0)
len = 0;
for(int z=slen[i]-1; z>=len; z--){
int flag = 1;
for(int y=z; y<slen[i]; y++)
if(s[i][y] != s[j][y-z]){
flag = 0;
break;
}
if(flag){
v[i].push_back(make_pair(j, slen[j]-slen[i]+z));
break;
}
}
}
for(int i=1; i<=n; i++)
if(s[i][0] == a){
memset(vis, 0, sizeof(vis));
ans = slen[i];
vis[i]++;
dfs(i);
}
printf("%d", big);
return 0;
}
只需要暴力即可 -
02015-08-10 15:38:40@
其实spfa更快但是也接近了0ms吧
记录信息
评测状态 Accepted
题目 P1311 单词接龙
递交时间 2015-08-10 15:37:27
代码语言 C++
评测机 VijosEx
消耗时间 27 ms
消耗内存 564 KiB
评测时间 2015-08-10 15:37:28评测结果
编译成功
foo.cpp: In function 'int dfs(int, int)':
foo.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( i = 0 ; i < linker[ pos ].size() ; i++ )
^测试数据 #0: Accepted, time = 0 ms, mem = 560 KiB, score = 16
测试数据 #1: Accepted, time = 12 ms, mem = 556 KiB, score = 16
测试数据 #2: Accepted, time = 15 ms, mem = 560 KiB, score = 16
测试数据 #3: Accepted, time = 0 ms, mem = 564 KiB, score = 16
测试数据 #4: Accepted, time = 0 ms, mem = 560 KiB, score = 16
测试数据 #5: Accepted, time = 0 ms, mem = 560 KiB, score = 16
Accepted, time = 27 ms, mem = 564 KiB, score = 96
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>using namespace std;
int n;
char s[20 + 2][2000 + 2];
int i , j , k , l , f;
int len[20 + 2];
bool flag;vector < int > linker[20 + 2];
vector < int > di[20 + 2];int max( int a , int b )
{
if( a > b )
return a;
return b;
}
int power[20 + 2] = { 0 , 1 , 3 , 9 , 27 , 81 , 243 , 729 , 2187 , 6561 , 19683 , 59049 , 177147 , 531441 , 1594323 , 4782969 , 14348907 , 43046721 , 129140163 , 387420489 , 1162261467 };int dfs( int pos , int sta )
{
int i;
int c[20 + 2];
int t = sta;
for( i = n ; i >= 1 ; i-- )
{
c[i] = t / power[i];
t %= power[i];
}
int ans = 0;
for( i = 0 ; i < linker[ pos ].size() ; i++ )
if( c[ linker[ pos ][i] ] != 2 )
ans = max( ans , dfs( linker[ pos ][i] , sta + power[ linker[ pos ][i] ] ) + di[ pos ][i] );
return ans;
}int main()
{
scanf( "%d" , &n );
for( i = 1 ; i <= n + 1 ; i++ )
cin >> s[i];
for( i = 1 ; i <= n + 1 ; i++ )
len[i] = strlen( s[i] );
for( i = 1 ; i <= n + 1 ; i++ )
for( j = 1 ; j <= n ; j++ )
{
k = len[i];
while( 1 )
{
k--;
flag = 0;
if( len[i] - k > len[j] - 1 )
break;
for( f = k , l = 0 ; f < len[i] && l < len[j] - 1 ; f++ , l++ )
if( s[i][f] != s[j][l] )
{
flag = 1;
break;
}
if( !flag )
{
linker[i].push_back( j );
di[i].push_back( len[j] - ( len[i] - k ) );
break;
}
if( k == 0 )
break;
}
}
cout << dfs( n + 1 , 0 ) + 1 << endl;
system( "pause" );
return 0;
} -
02015-08-07 16:18:28@
然而我就来发题解。
#include<cstdio>
#include<cstring>
int a[25],b[25],ans,n;
char ss[25][110];
void dfs(int x,int y)
{
int i,j,k,l;
for(i=1;i<=n;i++)
if(b[i]<2)
for(j=0;j<a[x];j++)
if(ss[i][0]==ss[x][j])
{
for(l=1,k=j+1;k<a[x]&&ss[i][l]==ss[x][k];k++,l++);
if(k<a[x]) continue;
b[i]++;
dfs(i,y+a[i]-l);
b[i]--;
}
if(y>ans)ans=y;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;a[i]=strlen(ss[i]),i++) scanf("%s",ss[i]);
scanf("%s",ss[0]);
a[0]=strlen(ss[0]);
dfs(0,a[0]);
printf("%d\n",ans);
return 0;
} -
02015-06-22 10:54:50@
用邻接矩阵+dfs即可,感谢楼下各位神犇的错误总结
#include<stdio.h>
#include<string.h>
int n;
char s[21][2000];
int way[21][21],length[21]={0},hash[21]={0};
char st;
int max=-1;int min(int a,int b)
{
if(a<b) return a;
else return b;
}void dfs(int s,int ans)
{
int i,flag=0;for(i=1;i<=n;i++)
if(way[s][i]!=0 && hash[i]<2) {hash[i]++;dfs(i,ans+length[i]-way[s][i]);hash[i]--;flag=1;}if(flag==0 && ans>max) max=ans;
}int main( )
{int i,j,k,z,flag=0;
scanf("%d\n",&n);
for(i=1;i<=n;i++)
{
gets(s[i]);
length[i]=strlen(s[i]);
}st=getchar( );
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
way[i][j]=0;for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{for(k=1;k<=min(length[i],length[j])-1;k++)
{
flag=0;for(z=1;z<=k;z++)
if(s[j][k-z]!=s[i][length[i]-z]) {flag=1;break;}if(flag==0) {way[i][j]=k;break;}
}}
for(i=1;i<=n;i++)
if(s[i][0]==st) {hash[i]++;dfs(i,length[i]);hash[i]--;}printf("%d",max);
return 0;
} -
02015-05-26 16:12:38@
此水题本人交了3次才过,特此总结一下下面的先人犯的错:
1、“包含关系”指两个不同字符串间存在某个字符串是另一个字符串的前缀或后缀,同一个字符串间是没有“包含”这个可能的,即可以自连(如tact自连成为tactact);
2、两个字符串间应删去尽可能少的字符,如hexe和exet合并后应为hexexet(删去了重复的一个e,而不是exe)。 -
02014-08-16 17:29:00@
#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;
string str[21];
int n,f[21][21],sum[21]={0},ans=0;
char ch;
int check(int x,int y)
{
int d;
for(d=1;d<min(str[x].size(),str[y].size());d++)
if(str[x].substr(str[x].size()-d,d)==str[y].substr(0,d))
return d;
return 0;
}
void dfs(int x,int len)
{
int i;
if(len>ans)
ans=len;
for(i=1;i<=n;i++)
if(f[x][i]&&sum[i]<2)
{
sum[i]++;
dfs(i,len+str[i].size()-f[x][i]);
sum[i]--;
}
}
main()
{
ios::sync_with_stdio(0);
int i,j;
cin>>n;
for(i=1;i<=n;i++)
cin>>str[i];
cin>>ch;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
f[i][j]=check(i,j);
for(i=1;i<=n;i++)
if(str[i][0]==ch)
{
sum[i]++;
dfs(i,str[i].size());
sum[i]--;
}
cout<<ans;
} -
02013-08-15 14:43:43@
本来WA三个点然后瞎改改竟然AC了==|||
Var n,i,ans:longint;
k:char;
f:array[1..100] of boolean;
a:array[1..100] of string;
Function gcd(a,b:string):longint;
Var i,j:longint;
Begin
For i:=length(a) downto 1 do If copy(a,i,length(a)-i+1)=copy(b,1,length(a)-i+1) then exit(length(a)-i+1);
exit(0);
End;
Function max(a,b:longint):longint;
Begin
If a>b then exit(a) else exit(b);
End;
Function work(word:string):longint;
Var i,j:longint;
Begin
work:=length(word);
For i:=1 to n do
If not f[i] then
If (gcd(word,a[i])<>0) and (gcd(word,a[i])<>length(word)) then
Begin
f[i]:=true;
work:=max(work,work(a[i])+length(word)-gcd(word,a[i]));
f[i]:=false;
End;
End;
Begin
readln(n);
For i:=1 to n do Begin readln(a[i]); a[n+i]:=a[i]; End;
n:=n*2;
readln(k);
For i:=1 to trunc(n/2) do
If a[i,1]=k then
Begin
fillchar(f,sizeof(f),false);
f[i]:=true;
ans:=max(ans,work(a[i]));
End;
writeln(ans);
readln;
End. -
02009-11-10 13:21:09@
预处理一下。
搜索一下。
AC一下。就好了。
-
02009-11-06 20:53:11@
真是悲剧……
每次在学校做嗷嗷错……
结果回家重新写一遍直接就AC……
狂郁闷啊!!
呜呜~~~~(>_
-
02009-11-04 17:10:23@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms -
02009-10-30 20:31:23@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms我就是按照题目中的描述去做了,感觉题目描述的很清楚。。貌似没有楼下的各位所说的特殊情况,一次AC