我的个人记载
  • About Me
不知名小站
Never Give Up
  1. 首页
  2. 多校训练
  3. 正文

2020年牛客多校-第一场

2020年07月12日 154点热度 2人点赞 0条评论

前言:
不会网络流的菜鸡就做出来了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;
}

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2020年07月15日

框框

喜欢算法,喜欢编程。

打赏 点赞
下一篇 >

文章评论

取消回复

框框

喜欢算法,喜欢编程。

文章归档
  • 2020年10月
  • 2020年8月
  • 2020年7月
  • 2020年1月
  • 2019年11月
  • 2019年8月
  • 2019年7月
分类目录
  • 2008年哈尔滨区域赛
  • 2018焦作网络赛
  • Greater New York Region 2014
  • kuangbin并查集专题
  • Kuangbin数论专题
  • NZPC 2017
  • upc个人训练赛
  • 位运算
  • 博弈论
  • 多校训练
  • 搜索
  • 数据结构
  • 数论
  • 杭电多校训练第五场
  • 深入理解计算机基础/CSAPP
  • 算法模板
  • 线段树

COPYRIGHT © 2020 我的个人记载. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

苏ICP备19034952号-1