开始记录杭电多校补题了！
EASY
1004 Distinct Sub-palindromes
Distinct Sub-palindromes
题意
用x个字母来构建一个字符串，使得整个字符中回文子串最小，求构建数目
思路
当x为1、2、3时，将字符串构造成a，aa，aaa所成的回文子串数量最小，即为pow(26,n);
当x大于3时，字符串构造成abcabcabc……所成的回文子串即为3，即构造为262524种
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n;
scanf("%d", &n);
while(n--){
int t;
cin >> t;
if(t==1)
cout << 26 << endl;
else if(t == 2)
cout << 676 << endl;
else if(t==3)
cout << 17576 << endl;
else
cout << 15600 << endl;
}
return 0;
}
|
1009 Leading Robots
Leading Robots
题意
给定n个机器人的初始位置和加速度，求有多少个机器人曾当过第一（并列第一不算第一）
思路
将数据的加速度按从小到大的顺序排序，若加速度相同则对初始位置的从小到大排序来处理，我们将数据进行记录，并记录位置和加速度的出现的个数，方便排除同一位置和加速度的机器人，如果后面的位置在前面位置的前面，则前面位置的机器人无法成为第一，若存在三个机器人的比较，则机器人B赶上A的时间大于等于C赶上B的则机器人B也无法成为第一，最后再处理可能存在的并列第一的
AC代码
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
| #include<stdio.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<stack>
using namespace std;
typedef long long ll;
#define maxn 50010
struct Node{
ll x,a;
}ro[maxn];
bool Judge(Node A,Node B,Node C){
return (B.x-C.x)*(B.a-A.a)-(C.a-B.a)*(A.x-B.x)<=0;//判断三者关系，如果B超过A的时间大于等于C 超过B的时间，则B无法担任第一
}
bool cmp(Node A,Node B){//排序
if(A.a!=B.a)return A.a<B.a;
else return A.x<B.x;
}
map<pair<ll,ll>,ll> mp;
ll n,top,Stack[maxn];
int main(){
ll t;
scanf("%lld",&t);
while(t--){
mp.clear();
scanf("%lld",&n);
for(ll i=0;i<n;i++){
scanf("%lld %lld",&ro[i].x,&ro[i].a);
pair<ll,ll> p;
p.first=ro[i].a;
p.second=ro[i].x;
mp[p]++;//如果同一位置同一加速度的机器人有多个，则这类机器人无法当第一
}
sort(ro,ro+n,cmp);
ll top=0;
for(ll i=0;i<n;i++){
while((top>0&&ro[i].x>=ro[Stack[top]].x)||(top>1&&Judge(ro[Stack[top-1]],ro[Stack[top]],ro[i]))){//后面位置在top前面，top无法当第一
top--;
}
Stack[++top]=i;
}
ll ans=top;
for(ll i=1;i<=top;i++){
pair<ll,ll> p;
p.first=ro[Stack[i]].a;
p.second=ro[Stack[i]].x;
if(mp[p]>1)ans--;
}
printf("%lld\n",ans);
}
return 0;
}
|
1011 Minimum Index
Minimum Index
题意
求每个前缀的字典序的最小后缀的位置，再求和
思路
Lyndon分解(对于字符串s，如果s的字典序严格小于s的所有后缀字符串，我们称s是简单串或Lyndon串，即分解出来的串si>=si+1)
对字符串s(d[i]表示前缀i的最小后缀的位置)分三种情况(s=s1s2s3使用i,j,k依次表示s2的起始位置，j表示s3的起始位置即新加入的字符，k表示j位字符在s2上一个循环节对应的字符)：
1.当s[j]==s[k]时，意味着j对应的s2某个循环节的一个字符拼在s2
的末尾仍满足
2.s[j]>s[k],新的字符直接拼到s2末尾使之s2是一个Lyndon串
3.s[j] < s[k],可以继续在这个前缀后面增加s[k];
AC代码
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
| #include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int d[1000010];
char s[1000010];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s",s+1);
int ls=strlen(s+1);
long long cnt=0;
int i=1;
d[1]=1;
while(i<=ls)
{
int j=i;
int k=i+1;
while(k<=ls&&s[j]<=s[k])
{
if(s[j]<s[k])
{
d[k]=i;
j=i;
}
else
{
d[k]=d[j]+(k-j);
j++;
}
k++;
}
d[k]=k;
while(i<=j)
{
i+=k-j;
}
}
for(i=ls;i>=1;i--)
{
cnt=cnt*1112+d[i];
cnt%=1000000007;
}
printf("%lld\n",cnt);
}
return 0;
}
|
1012 Mow
题意
思路
AC代码