A

模拟 

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

int n;
char s[200];

bool solve()
{
for(int i=0;i<n;++i) if(s[i]=='*'){
for(int j=1;i+4*j<n;++j){
int cnt=1;
for(int k=1;i+k*j<n && k<5;++k)
if(s[i+k*j]=='*') ++cnt;
else break;
if(cnt>=5) return true;
}
}
return false;
}

int main()
{
//freopen("test","r",stdin);
scanf("%d",&n);
scanf("%s",s);
puts(solve()?"yes":"no");
return 0;
}

B

模拟,或者说是贪心,从叶子结点向父节点更新状态,如标记处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;

const int maxn=2<<12;
int n;
int a[maxn];

int main()
{
//freopen("test","r",stdin);
scanf("%d",&n);
long long ans=0;
for(int i=2;i<(1<<(n+1));++i) scanf("%d",&a[i]);
for(int i=(1<<(n+1))-1;i>=3;i-=2){
ans+=abs(a[i]-a[i-1]);
a[i/2]+=max(a[i],a[i-1]); //更新状态
}
cout<<ans<<endl;
return 0;
}

C

分类暴搜,小白书原题
设w1为两者中较大的
1.w1较大时:
枚举w1的个数,直到大于n,再计算处w2个数得出结果
ans=max(ans,h1*i+(n-i*w1)/w2*h2);

2.w1较小时:
分别枚举w1,w2个数,
ans=max(ans,h1*i+(n-i*w1)/w2*h2);
ans=max(ans,h2*i+(n-i*w2)/w1*h1);

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

#define F(i,a,b) for(int i=(a);i<=(b);++i)
int n,w1,h1,w2,h2;

LL solve()
{
LL ans=0;
if(w1<w2){ //保证w1最大
swap(w1,w2);
swap(h1,h2);
}
if(n/w1<65536) //w1较大
for(LL i=0;i*w1<=n;++i){
ans=max(ans,h1*i+(n-i*w1)/w2*h2);
}
else{ //w1较小
for(LL i=0;i<=w1;++i){
ans=max(ans,h2*i+(n-i*w2)/w1*h1);
}
for(LL i=0;i<=w2;++i){
ans=max(ans,h1*i+(n-i*w1)/w2*h2);
}
}
return ans;
}

int main()
{
//freopen("test","r",stdin);
scanf("%d%d%d%d%d",&n,&h1,&h2,&w1,&w2);
cout<<solve()<<endl;
}

D

KMP

E

滑动区间
先找到一个最短区间(其实任意区间都可以,这么做是降低复杂度)长度为n,
然后枚举起点(n+1种情况,即隔板),易知所有情况都包含在内;

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
#include<cstdio>
#include<iostream>
using namespace std;

typedef long long ll;

const int N = 2000010;

int a[N], to[N];
ll p[N];

int main()
{
//freopen("test","r",stdin);
int n,q;
ll sum=0;
scanf("%d %d",&n,&q);
for(int i=0;i<n;++i){
scanf("%d",a+i);
a[i+n]=a[i];
sum+=a[i];
}
int j=0;
while(q--){
ll t,cur=0;
scanf("%lld",&t);
if(t>=sum){
puts("1");
continue;
}
int j=0,len=n,st=0,cnt=0;
for(int i=0;i<n;++i){ //找到一个最短区间
while(j<2*n && a[j]+cur<=t) cur+=a[j++];
to[i]=j;
cur-=a[i];
if(to[i]-i<len) len=to[i]-i,st=i;
++cnt;
}
for(int i=0;i<n;++i){ if(to[i]>=n){
to[i]-=n;
}
//cout<<i<<" "<<to[i]<<endl;
}
int ans=cnt;
for(int i=st;i<=st+len;++i){
if(i>=n) i-=n;
int j=i;
cnt=0;
bool flag=false;
while(1){
j=to[j];
++cnt;
//cout<<j<<endl;
if(flag && j>=i) break;
if(to[j]<j) flag=true; //说明跳到开头
}
ans=min(ans,cnt);
}
printf("%d\n",ans);
}
return 0;
}