A题.小红的环形字符串
题意：小红拿到了一个环形字符串\(s\)。所谓环形字符串，指首尾相接的字符串。
小红想顺时针截取其中一段连续子串正好等于\(t\)，一共有多少种截法？
分析：记\(s,t\) 的长度分别为\(n,m\) ，环形字符串可以被选取的子串等于\(s+s[n-1,n+m-1]\) ，然后得到了个新的字符串，等价问\(s'\) 能截取多少个\(t\) ，按\(m\) 分组统计即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false),cin.tie(0);
string s,t;
cin>>s>>t;
int n=s.size();
for(int i=0;i<t.size()-1;i++)s+=s[(n+i)%n];
int cnt=0;
int i=0;
while(i<s.size()){
string k=s.substr(i,t.size());
if(k==t)cnt++;
i++;
}
cout<<cnt<<"\n";
return 0;
}
|
时间复杂度：\(O(nm)\)
空间复杂度：\(O(1)\)
B题.相邻不同数字的标记
**题意：**小红拿到了一个数组，每个数字被染成了红色或蓝色。小红有很多次操作，每次操作可以选择两个相邻的不同颜色的数字标记，并获得它们数字之和的得分。已经被标记的数字无法再次标记。小红想知道，自己最多能获得多少分。
**分析：**背包思想，令\(f(i,0)\) 为不选取\(a[i],a[i-1]\) 的最优解，\(f(i,1)\) 为选取了\(a[i],a[i-1]\) 的最优解，答案为\(max(f[n][1],f[n][0])\)
考虑\(f(i,0)\) 的最优解状态转移，不选这个的最优解可能是上一个也不选\(f(i-1,0)\) ，也有可能上一个也选了\(f(i-1,1)\)
考虑\(f(i,1)\) 的最优解状态转移，选这个的最优解就等于上一个没选的最优解加上\((a[i]+a[i-1])\) ，但注意如果\(color_i≠color_{i-1}\) 的话，\(f[i][1]=f[i-1][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
|
#include <iostream>
using namespace std;
typedef long long ll;
const int N=1e5+7;
int a[N];
string c;
ll f[N][2];//第i个 选了前面那个为1 不选为0
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
cin>>c;
c=c[0]+c;//为了防止越界。
for(int i=1;i<=n;i++){
f[i][0]=max(f[i-1][1],f[i-1][0]);
//不选前面那个，这个废弃掉
if(c[i]!=c[i-1])f[i][1]=f[i-1][0]+a[i]+a[i-1];
//选这个，就是前面没选的最优解+这次合并
else f[i][1]=f[i-1][1];
}
cout<<max(f[n][0],f[n][1]);
return 0;
}
|
C题.小红的俄罗斯方块
题意：见原题描述
**分析：**画下图模拟下就可以了，分别统计下不同的方块的不同触点会导致每列的高度怎么样的变化。
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
|
#include <iostream>
using namespace std;
typedef long long ll;
const int N=1e5+7;
int col[10];
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int tt;
cin>>tt;
while(tt--){
int d,l;
cin>>d>>l;
if(d==0){
int maxv=max(col[l],col[l+1]);
col[l]=maxv+3;
col[l+1]=maxv+1;
}
else if(d==90){
int maxv=max(col[l]+1,max(col[l+1],col[l+2]));
col[l]=maxv+1;
col[l+1]=maxv+1;
col[l+2]=maxv+1;
}
else if(d==180){
int maxv=max(col[l],col[l+1]+2);
col[l]=maxv+1;
col[l+1]=maxv+1;
}
else{
int maxv=max(col[l],max(col[l+1],col[l+2]));
col[l]=maxv+1;
col[l+1]=maxv+1;
col[l+2]=maxv+2;
}
}
for(int i=1;i<=8;i++)cout<<col[i]<<" ";
return 0;
}
|
D题.小红打怪
题意：见原题描述
分析：求最优解问题，容易发现如果小红能杀\(k\) 只怪物，自然也能杀\(k-1,k-2,..\) 只怪物，如果他杀不了\(k\) 只，自然也杀不了\(k+1,k+2,..\) ，\(q=10^5\) ，单次回答的次数不能超过\(10^3\) ，但怪物数量就已经有\(10^5\) 了，所以不可能是\(O(n)\) 的做法，所以自然而然是二分答案了。
先对怪物的血量和攻击力排序，然后二分到一个中点\(mid\) ，然后不断与每个怪物进行决策，但这样时间复杂度仍然是\(O(qnlogn)\)，考虑将决策的时间复杂度降低至\(O(1)\) ，不难发现一个怪物的血量如果固定了，那打他需要的次数也固定了，随之扣的血量也固定了，因此定义\(a[i]\) 为前\(i\) 个怪物消灭他们的受伤值，这样只需要二分最大一个小于\(h+xk\) 的即可（注意不是等于号！因为如果恰好等于的话说明最后一次已经阵亡了）
一个怪物血量为\(h\) ，攻击力为\(p\) 时，我们最优的攻击序列是\([2,1,1,2,1,1,..]\) ，令\(t=4\) ，则怪物可以经历完整的\(3*(\frac{t}{4})\) 次攻击，剩余可能是\(1,2,3\) ，分别有\([1,1,2]\) 次，然后观察可以发现受伤值=攻击次数\(-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
|
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+7;
ll a[N];//前i个怪物的伤害
ll n,h,k,x;
int ag[4]={0,1,1,2};
void solve(){
int l=0,r=n;
ll heal=h+x*k;
while(l<r){
int mid=(l+r+1)>>1;
if(a[mid]<heal)l=mid;//满足条件的mid 往大了找
else r=mid-1;
}
cout<<l<<" ";
return;
}
int main(){
ios::sync_with_stdio(false),cin.tie(0);
cin>>n>>h>>k;
for(int i=1;i<=n;i++){
ll h,p;
cin>>h>>p;
ll d=h/4*3;//这里记得开long long
ll d1=h%4;//这里记得开long long
d+=ag[d1];
d--;
a[i]=d*p;
}
sort(a+1,a+1+n);//排序
for(int i=1;i<=n;i++)a[i]+=a[i-1];
int tt;
cin>>tt;
while(tt--){
cin>>x;
solve();
}
return 0;
}
|
时间复杂度：\(O(nlong+qlogn)\)
空间复杂度：\(O(n)\)