- 科技
- 马拉车算法例题 -- P3805 【模板】manacher算法、P1659 [国家集训队]拉拉队排练
马拉车模板
看这个
P3805 【模板】manacher算法
code
#include <iostream>
#include <algorithm>
#include <string>
using namespace std
;
class Solution {
public:
static int longestPalindrome(const string
&s
) {
int len
= s
.length();
if (len
<= 1) {
return len
;
}
string t
= addBoundaries(s
);
len
= t
.length();
int P
[len
];
int center
= 0, maxRight
= 0;
int maxLen
= 1;
for (int i
= 0; i
< len
; ++i
) {
if (i
< maxRight
) {
int mirror
= 2 * center
- i
;
P
[i
] = min(maxRight
- i
, P
[mirror
]);
} else {
P
[i
] = 0;
}
int left
= i
- (P
[i
] + 1);
int right
= i
+ P
[i
] + 1;
while (left
>= 0 && right
< len
&& t
[left
] == t
[right
]) {
P
[i
]++;
left
--;
right
++;
}
if (i
+ P
[i
] > maxRight
) {
maxRight
= i
+ P
[i
];
center
= i
;
}
if (P
[i
] > maxLen
) {
maxLen
= P
[i
];
}
}
return maxLen
;
}
static string
addBoundaries(const string
&s
) {
if (s
.empty()) {
return "";
}
int len
= s
.length();
string t
;
for (int i
= 0; i
< len
; ++i
) {
t
+= '#';
t
+= s
[i
];
}
return t
+ '#';
}
};
int main() {
string s
;
cin
>> s
;
cout
<< Solution
::longestPalindrome(s
) << endl
;
return 0;
}
P1659 [国家集训队]拉拉队排练
code
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std
;
using ll
= long long;
using pii
= pair
<int, int>;
const int MOD
= 19930726;
class Solution {
public:
int n
{};
ll k
{};
string s
;
vector
<int> P
;
int solve() {
cin
>> n
>> k
>> s
;
int len
= s
.length();
if (len
<= 1) {
return len
;
}
string t
= addBoundaries();
int tLen
= t
.length();
P
.resize(tLen
);
vector
<int> cnt(n
+ 1);
int center
= 0, maxRight
= 0;
for (int i
= 0; i
< tLen
; ++i
) {
if (i
< maxRight
) {
int mirror
= 2 * center
- i
;
P
[i
] = min(maxRight
- i
, P
[mirror
]);
} else {
P
[i
] = 0;
}
int left
= i
- (P
[i
] + 1);
int right
= i
+ P
[i
] + 1;
while (left
>= 0 && right
< tLen
&& t
[left
] == t
[right
]) {
P
[i
]++;
left
--;
right
++;
}
if (i
+ P
[i
] > maxRight
) {
maxRight
= i
+ P
[i
];
center
= i
;
}
if (t
[i
] != '#') {
cnt
[P
[i
]]++;
}
}
ll sum
= 0, ans
= 1;
if ((n
& 1) == 0) n
--;
for (int i
= n
; i
>= 1; i
-= 2) {
sum
+= cnt
[i
];
if (sum
< k
) {
ans
= ans
* qPow(i
, sum
, MOD
) % MOD
;
k
-= sum
;
} else {
ans
= ans
* qPow(i
, k
, MOD
) % MOD
;
k
-= sum
;
break;
}
}
if (k
> 0) {
return -1;
} else {
return ans
;
}
}
static ll
qPow(ll a
, ll b
, ll mod
) {
ll res
= 1;
while (b
) {
if (b
& 1) res
= res
* a
% mod
;
a
= a
* a
% mod
;
b
>>= 1;
}
return res
% mod
;
}
string
addBoundaries() {
if (s
.empty()) {
return "";
}
int len
= s
.length();
string t
;
for (int i
= 0; i
< len
; ++i
) {
t
+= '#';
t
+= s
[i
];
}
return t
+ '#';
}
};
int main() {
Solution S
;
cout
<< S
.solve() << endl
;
return 0;
}
Processed:
0.024, SQL:
8
