C

给出一串字符串,是一些字典中的单词小写反序后组成的,输出一个原字符串

dp+hash
由于只需输出任意一个,用dp记录当前位置结尾的一个串的长度,字符串hash后加快比较速度

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int mod = 786433;
const int maxn = 1e4 + 10;
const int maxm = 1e5 + 10;
int n,m;

char s[maxn];
vector<int> vis[mod];

char w[maxm][1010];
int lens[maxm];
int d[maxn];
vector<int> ans;

int main()
{
//freopen("test.txt","r",stdin);
scanf("%d %s %d",&n,s,&m);
int maxlen = 0;
for(int i=0;i<m;++i)
{
scanf("%s",w[i]);
int len = strlen(w[i]);
lens[i] = len;
int t = 0;
for(int j=len-1;j>=0;--j)
t = (t*26 + (tolower(w[i][j]) - 'a')) %mod;
vis[t].push_back(i);
maxlen = max(maxlen,len);
}
d[0] = -1;
for(int i=0;i<n;++i)
{
if(!d[i]) continue;
int t = 0;
for(int j=0;j<maxlen;++j)
{
if(i+j >= n) break;
t = (t*26 + (s[i+j] - 'a')) %mod;
if(d[i+j+1]) continue;
for(int k=0;k<vis[t].size();++k)
{
if(j+1 == lens[vis[t][k]])
{
bool flag = true;
for(int l=0;l<j;++l) if(s[i+j-l] != tolower(w[vis[t][k]][l])) {flag=false;break;}
if(!flag) continue;
d[i+j+1] = vis[t][k]+1;
break;
}
}
}
}
for(int i=n;;i -= lens[d[i]-1])
{
if(d[i] == -1) break;
ans.push_back(d[i]-1);
}
reverse(ans.begin(),ans.end());
for(int i=0;i<ans.size();++i) printf("%s ",w[ans[i]]);
puts("");
return 0;
}

D

给n个数,选择两个数作为$f_0,f_1$,然后求最长的满足$f_{n+2} = f_{n+1} + f_n$的排列长度

暴力
考虑到斐波那契数的增长很快,这个序列不会太长,直接排序后暴力二分即可
注意特判$f_0 = f_1 = 0$的情况

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 1010;
int n;
int a[maxn],cnt[maxn];
LL f[maxn];

int main()
{
//freopen("test.txt","r",stdin);
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%d",a+i);
int pn = 0;
sort(a,a+n);
for(int i=0;i<n;++i)
{
cnt[pn] = 1;
a[pn] = a[i];
while(i+1 < n && a[i] == a[i+1])
{
++cnt[pn];
++i;
}
++pn;
}
int ans = 2;
for(int i=0;i<pn;++i)
{
--cnt[i];
for(int j=0;j<pn;++j)
{
if(!cnt[j]) continue;
if(a[i] == 0 && a[j] == 0)
{
ans = max(ans,cnt[i]+1);
continue;
}
--cnt[j];
f[0] = a[i];
f[1] = a[j];
int k;
for(k=2;;)
{
f[k] = f[k-1] + f[k-2];
int p = lower_bound(a,a+pn,f[k]) - a;
if(p < pn && a[p] == f[k] && cnt[p])
{
--cnt[p];
++k;
}
else break;
}
ans = max(ans,k);
while(k > 2)
{
--k;
int p = lower_bound(a,a+pn,f[k]) - a;
++cnt[p];
}
++cnt[j];
}
++cnt[i];
}
printf("%d\n",ans);
return 0;
}