前言:
不会网络流的菜鸡就做出来了F和J(Worlfram + oeis),还是太菜,好好学习,早日刷完网络流24题。
F. Infinite String Comparision
题意:
For a string x, Bobo defines x^{\infty}=xxx_{\cdot \cdot \cdot} which is x repeats for infinite times, resulting in a string of infinite length.
Bobo has two strings a and b. Find out the result comparing a^{\infty} and b^{\infty}in lexicographical order.
输入描述:
The input consists of several test cases terminated by end-of-file.
The first line of each test case contains a string a, and the second line contains a string b.
- $1 \leqslant \left| a \right|,\left| b \right|\leqslant 10^5$
- a, b consists of lower case letters.
- The total length of input strings does not exceed 2 * 10^6
输出描述:
For each test case, print "=
" (without quotes) if a^{\infty}=b^{\infty}. Otherwise, print "<
" if a^{\infty}<b^{\infty}, or ">
" if a^{\infty}>b^{\infty}
输入:
aa
b
zzz
zz
aba
abaa
输出:
<
=
>
题解:
比较两个字符串可以一直迭代自身的字典序大小,只需每个字符串扩大2倍,再补成一样长度大小比较即可。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define mem(a, b) memset(a, b, sizeof(a))
#define Fast_IO ios::sync_with_stdio(false);
#define inf 0x3f3f3f3f
const int maxn = 3e6 + 10;
const int maxm = 5e5 + 10;
const ll mod = 998244353;
const double pi = acos(-1.0);
const double eps = 1e-8;
void solve(string s,string t){
s += s;
t += t;
int len1 = s.size();
int len2 = t.size();
if(len1 > len2){
int k = len1 - len2;
for(int i = len2; i < len2 + k; i ++)
t += t[(i - len2) % len2];
// cout <<"---"<< s << " " << t << endl;
if(s == t) puts("=");
else if(s > t) puts(">");
else puts("<");
}
else if(len1 < len2){
int k = len2 - len1;
for(int i = len1; i < len1 + k; i ++)
s += s[(i - len1) % len1];
// cout <<"--"<< s << " " << t << endl;
if(s == t) puts("=");
else if(s > t) puts(">");
else puts("<");
}
else{
if(s == t) puts("=");
else if(s > t) puts(">");
else puts("<");
}
}
int main(){
//srand((unsigned)time(0));
//freopen("out.txt","w",stdout);
//freopen("in.txt","r",stdin);
string s,t;
while(cin >> s >> t){
solve(s,t);
}
return 0;
}
J. Easy Integration
题意:
Given n, find the value of \int_0^1{\left( x-x^2 \right) ^ndx} It can be proved that the value is a rational number \frac{p}{q} Print the result as \left( p\cdot q^{-1} \right) \ mod \ 998244353
输入描述:
The input consists of several test cases and is terminated by end-of-file.
Each test case contains an integer n.
- $1\leqslant n\leqslant 10^6$
- The number of test cases does not exceed 10^5
输出描述:
For each test case, print an integer which denotes the result.
输入:
1
2
3
输出:
166374059
432572553
591816295
题解:
不正经解法:Wolfram + Oeis 查表得公式:
$$
\frac{n!^2}{\left( 2n+1 \right) !}
$$
预处理阶乘+快速幂求逆元。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rlld(a) scanf("%lld", &a)
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define mem(a, b) memset(a, b, sizeof(a))
#define Fast_IO ios::sync_with_stdio(false);
#define inf 0x3f3f3f3f
const int maxn = 3e6 + 10;
const int maxm = 5e5 + 10;
const ll mod = 998244353;
const double pi = acos(-1.0);
const double eps = 1e-8;
ll n, k;
ll fact[maxn];
ll inv[maxn];
ll quickpow(ll a, ll b, ll mod)
{
ll ans = 1 % mod;
while(b)
{
if(b & 1)
ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
void init(){
fact[0] = 1;
for(int i = 1;i < maxn ;i ++)
fact[i] = fact[i - 1] * i % mod;
inv[maxn - 1] = quickpow(fact[maxn - 1], mod - 2, mod);
for(int i = maxn - 2; i >= 0; i --)
inv[i] = inv[i + 1] * (i + 1) % mod;
}
int main(){
ll n;
init();
while(~rlld(n)){
ll ans = quickpow(fact[n], 2ll, mod) % mod;
printf("%lld\n", ans * quickpow(fact[2 * n + 1], mod - 2, mod) % mod);
}
return 0;
}
A. B-Suffix Array
题目链接:https://ac.nowcoder.com/acm/contest/5666/A
题意:给一个长度为n的字符串,通过给定的函数变成一个b序列,求b的所有后缀子串升序排列。
大佬题解:https://blog.csdn.net/weixin_43965698/article/details/107304525
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define mem(a, b) memset(a, b, sizeof(a))
#define rd(a) scanf("%d", &a)
#define rs(a) scanf("%s", a)
#define al(x) x + 1, x + 1 + n
#define inf 0x3f3f3f3f
const int maxn = 2e5 + 10;
const int maxm = 5e5 + 10;
const ll mod = 1e9 + 7;
const double pi = acos(-1.0);
const double eps = 1e-8;
int n, m;
char s[maxn];
int t[maxn], sa[maxn], rk[maxn], c[maxn], y[maxn];
struct node{
int x, y;
bool operator<(const node &rhs)const{
if(y - x == rhs.y - rhs.x)
return rk[y + 1] < rk[rhs.y + 1];
return y - x < rhs.y - rhs.x;
}
}seg[maxn];
void get_sa()
{
for(int i = 1; i <= m; i ++) c[i] = 0;
for(int i = 1; i <= n; i ++) ++ c[rk[i] = t[i]];
for(int i = 2; i <= m; i ++) c[i] += c[i - 1];
for(int i = n; i >= 1; i --) sa[c[rk[i]] --] = i;
for(int k = 1; k <= n; k <<= 1){
int num = 0;
for(int i = n - k + 1; i <= n; i ++) y[++ num] = i;
for(int i = 1; i <= n; i ++)
if(sa[i] > k) y[++ num] = sa[i] - k;
for(int i = 1; i <= m; i ++) c[i] = 0;
for(int i = 1; i <= n; i ++) ++ c[rk[i]];
for(int i = 2; i <= m; i ++) c[i] += c[i - 1];
for(int i = n; i >= 1; i --)
sa[c[rk[y[i]]] --] = y[i], y[i] = 0;
rap(i, 1, n) y[i] = rk[i];
rk[sa[1]] = 1;
num = 1;
for(int i = 2; i <= n; i ++)
rk[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
if(num == n) break;
m = num;
}
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
while(~rd(n)){
rs(s + 1);
int pa = - 1, pb = -1;
mem(t, 0);
rap(i, 1, n){
t[i] = 0;
sa[i] = 0;
if(s[i] == 'a'){
if(pa != -1) t[i] = i - pa;
pa = i;
}
else{
if(pb != -1) t[i] = i - pb;
pb = i;
}
}
rap(i, 1, n) t[i] ++;
m = n;
get_sa();
pa = pb = n + 1;
for(int i = n; i >= 1; i --){
if(s[i] == 'a'){
seg[i] = {i, pb};
pa = i;
}
else{
seg[i] = {i, pa};
pb = i;
}
}
rk[n + 1] = -1;
rk[n + 2] = -2;
sort(al(seg));
rap(i, 1, n){
printf("%d ", seg[i].x);
}
puts("");
}
return 0;
}
这题有个结论,答案等价于对f\left[ i \right] =\min _{j>i,s\left[ j \right] =s\left[ i \right]}\left( j-i \right)求后缀排序,如果对应的后面没有出现s\left[ i \right]则f\left[ i \right]=inf,把后缀排序翻转就是答案。
如abaab=231\infty \infty这个后缀排序为31245,翻转及为答案。
有兴趣可以搜索论文Parameterized\ Suffix\ Arrays\ for\ Binary\ Strings
反正我比赛时是想不到这么牛逼的结论(
代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define lap(i, n, a) for(int i=n; i>=a; i--)
#define mem(a, b) memset(a, b, sizeof(a))
#define rd(a) scanf("%d", &a)
#define rs(a) scanf("%s", a)
#define al(x) x + 1, x + 1 + n
#define inf 0x3f3f3f3f
const int maxn = 2e5 + 10;
const int maxm = 5e5 + 10;
const ll mod = 1e9 + 7;
const double pi = acos(-1.0);
const double eps = 1e-8;
int n, m;
char s[maxn];
int t[maxn], sa[maxn], rk[maxn], c[maxn], y[maxn];
void get_sa()
{
for(int i = 1; i <= m; i ++) c[i] = 0;
for(int i = 1; i <= n; i ++) ++ c[rk[i] = t[i]];
for(int i = 2; i <= m; i ++) c[i] += c[i - 1];
for(int i = n; i >= 1; i --) sa[c[rk[i]] --] = i;
for(int k = 1; k <= n; k <<= 1){
int num = 0;
for(int i = n - k + 1; i <= n; i ++) y[++ num] = i;
for(int i = 1; i <= n; i ++)
if(sa[i] > k) y[++ num] = sa[i] - k;
for(int i = 1; i <= m; i ++) c[i] = 0;
for(int i = 1; i <= n; i ++) ++ c[rk[i]];
for(int i = 2; i <= m; i ++) c[i] += c[i - 1];
for(int i = n; i >= 1; i --)
sa[c[rk[y[i]]] --] = y[i], y[i] = 0;
rap(i, 1, n) y[i] = rk[i];
rk[sa[1]] = 1;
num = 1;
for(int i = 2; i <= n; i ++)
rk[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
if(num == n) break;
m = num;
}
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
while(~rd(n)){
rs(s + 1);
int pa = - 1, pb = -1;
mem(t, 0);
lap(i, n, 1){
t[i] = 0; sa[i] = 0; y[i] = 0;
if(s[i] == 'a'){
if(pa != -1) t[i] = pa - i;
else t[i] = n;
pa = i;
}
else{
if(pb != -1) t[i] = pb - i;
else t[i] = n;
pb = i;
}
}
n ++;
t[n] = n;
m = n;
get_sa();
lap(i, n - 1, 1){
printf("%d ", sa[i]);
}
puts("");
}
return 0;
}
文章评论