【HDU-3746】Cyclic Nacklace【KMP找序列循环节】

【HDU-3746】Cyclic Nacklace【KMP找序列循环节】

代码:

#include <iostream>
#include <string>

using namespace std;

const int LIM = 1e5 + 10;
int kmp[LIM];
string str;
void build() {
  int k = 0;
  kmp[0] = 0;
  for (int i = 1; i < str.size(); i++) {
    while (k > 0 && str[k] != str[i]) k = kmp[k - 1];
    if (str[k] == str[i]) k++;
    kmp[i] = k;
  }
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
    cin >> n;
  while (n--) {
    cin >> str;
    build();
        int len = str.size();
        int l = len - kmp[str.size() - 1];
        if (l != len && !(len % l)) {
            cout << 0 << "\n";
        } else {
            cout << l - kmp[str.size() - 1] % l << "\n";
        }
    }
  return 0;
}

相关问题:【HDU-1358】Period【KMP的理解】

【HDU-1358】Period【KMP的理解】

【HDU-1358】Period【KMP的理解】

问题链接:https://vjudge.net/problem/HDU-1358

Solution:

#include <iostream>
#include <string>

using namespace std;
// abcabcabc
// | | | | |
// v v v v v
// abcabc
//    abcabc
// 可以绘制每个字符的匹配线
// 如果长度与最大匹配差值小于最大匹配长度,则说明
// 前缀的一部分后缀已经成为了后缀的一部分前缀
// 如果此差值可以整除长度,则说明这个串是由这个差值串
// 多次拼接而成
const int LIM = 1e6 + 10;
int kmp[LIM];
string str;
void build() {
  int k = 0;
  kmp[0] = 0;
  for (int i = 1; i < str.size(); i++) {
    while (k > 0 && str[k] != str[i]) k = kmp[k - 1];
    if (str[k] == str[i]) k++;
    kmp[i] = k;
  }
}

void solution() {
  build();
  for (int i = 1; i < str.size(); i++) {
    int len = i + 1 - kmp[i];
    if (len != i + 1 && !((i + 1) % len))
      cout << i + 1 << ' ' << (i + 1) / len << "\n";
  }
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  for (int k = 1; cin >> n && n; k++) {
    cout << "Test case #" << k << "\n";
    cin >> str;
    solution();
    cout << "\n";
  }
  return 0;
}

 

【HDU-5976】Detachment【二分+模逆元(费马小定理+同余式解法)】

【HDU-5976】Detachment【二分+模逆元(费马小定理+同余式解法)】

代码:

#include <iostream>

using namespace std;

typedef long long LL;
const int SIZE = 5e4;
const int LIM = 1e5;
const LL MOD = 1e9 + 7;
const LL MOD2 = 1e9 + 5;
LL pre[SIZE];
LL fractorial[SIZE];
// modula reverse identity element
LL mr[SIZE];

LL fastPow(LL base, LL p) {
    LL ret = 1;
    while (p) {
        if (p & 1) ret = ret * base % MOD;
        p >>= 1;
        if (p) base = base * base % MOD;
    }
    return ret;
}

int main(void) {
    // init
    // the index is the number of answer's segments
    pre[2] = 0;
    pre[3] = 4;
    int maxn;
    for (LL i = 4; pre[i - 1] <= 1e9; i++) {
        pre[i] = pre[i - 1] + i + 1;
        // cout << i << " : " << pre[i] << "\n";
        maxn = i;
    }
    // build the fractorial numbers' array
    fractorial[0] = fractorial[1] = 1;
    for (LL i = 2; i < SIZE; i++) {
        fractorial[i] = fractorial[i - 1] * i % MOD;
    }
    // build the modulo reverse identity elements' array
    for (LL i = 1; i < SIZE; i++) {
        mr[i] = fastPow(i, MOD2);
    }
    int t;
    LL x;
    // start to deal with input
    scanf("%d", &t);
    while (t--) {
        scanf("%lld", &x);
        if (x < 5) {
            printf("%lld\n", x);
            continue;
        }
        // offset is 5
        x -= 5;
        int l = 2, r = maxn;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (pre[mid] > x) r = mid;
            else l = mid + 1;
        }
        if (pre[l] > x) l--;
        x += 5;
        LL diff = x - (l * (l + 3) / 2);
        // printf("cnt : %d\n", l);
        // printf("fractorial[%d]: %lld\n", l + 2, fractorial[l + 2]);
        // printf("pre[%d]: %lld\n", l, pre[l]);
        // printf("diff: %lld\n", diff);
        if (diff > l) {
            printf("%lld\n", fractorial[l + 3] * mr[2] % MOD * mr[2 * l + 3 - diff] % MOD);
        } else {
            printf("%lld\n", fractorial[l + 2] * mr[l + 2 - diff] % MOD);
        }
    }
}

参考了:https://blog.csdn.net/qq_34374664/article/details/53466435

https://www.cnblogs.com/hsd-/p/5325780.html

感谢大神们的分享。

另外,这个数列十分有趣,附上OEIS相关页面:

https://oeis.org/A034893

相关论文:https://cs.uwaterloo.ca/journals/JIS/VOL8/Doslic/doslic15.pdf

【HDU-5975】Aninteresting game【lowbit数列】

【HDU-5975】Aninteresting game【lowbit数列】

Solution:

对于查询1,我们可以发现,输出的其实就是L到R之间(包含L和R)所有数的lowbit之和,即\(\sum_{i = L}^Rlowbit(i)\)。但是我们不能去枚举这个数,因为枚举的平均复杂度是\(O(n)\),而这道题的n取值为1e18.我们采用前缀和的方法,因为我们可以\(O(logn)\)的时间复杂度求出从1到n之间的所有数lowbit之和,我们先考虑如果对于单个要求的lowbit,如何求出拥有这个lowbit的数在1到x中出现的次数,如果我们用x除以\(lowbit(i) = 2^k\),就可以知道x中有多少个不小于\(2^k\)的数,用它再减去x中有多少个不小于\(2^{k + 1}\)的个数,就得知了拥有lowbit(i)的数的个数,由于我们要求它们lowbit之和,求出每个拥有lowbit(i)的数的个数,再乘上lowbit(i)就可以了,于是我们的策略就是枚举lowbit(i)。【这道题时间卡很紧,这个查询尽量避免多余的移位、乘除、条件判断操作,否则会超时】

对于查询2,直接把平常树状数组更新操作的循环那里加一个计数,即可解决。

#include <iostream>

using namespace std;

typedef long long LL;

LL query1(LL x) {
    LL ret = 0;
    for (LL i = 1; i <= x; i <<= 1) {
        ret += ((x / i) - (x / (i << 1))) * i;
    }
    return ret;
}

LL query2(LL x, LL n) {
    LL ret = 0;
    while (x <= n) {
        x += x & (-x);
        ret++;
    }
    return ret;
}

int main(void) {
    LL n, q, l, r;
    int op;
    while (~scanf("%lld%lld", &n, &q)) {
        while (q--) {
            scanf("%d", &op);
            if (op & 1) {
                scanf("%lld%lld", &l, &r);
                printf("%lld\n", query1(r) - query1(l - 1));
            } else {
                scanf("%lld", &l);
                printf("%lld\n", query2(l, n));
            }
        }
    }
    return 0;
}

相关阅读:

关于这个数列与此数列的前缀和:

lowbit数列:https://oeis.org/A006519

lowbit数列前缀和:https://oeis.org/A006520

【HDU-5973】Game of Taking Stones【威佐夫博弈】

【HDU-5973】Game of Taking Stones【威佐夫博弈】

Solution:

直接根据威佐夫博弈的定理,两堆数量之差乘上黄金分割比等于数量少的那堆的个数,先手必输,反之先手必胜。

求解黄金分割比使用公式\(\frac{\sqrt{5} – 1}{2}\),关于\(\sqrt{5}\)的求解,等价于求解函数\(f(x) = x^2 – 5\)与横坐标轴的正值交点的横坐标,显然\(\sqrt{5}\)就是上面所述问题的解,但是我们现在需要一个浮点数值,也就是一定精度下根号的浮点近似值,可以使用二分法(基于介值定理,我们知道如果在一个区间内有根,这个区间的左右端点函数值之积一定小于零),还可以使用牛顿迭代法,它的收敛速度会比二分法快,但是有时牛顿迭代法比二分法更容易出现不收敛的情况,不过对于当前函数是不存在这个问题的,因为我们确定要找的根在0到5的区间内,并且这个函数显然在这个区间内单调递增,因此选取初始值5可以确保函数值收敛到我们想要的位置上。

牛顿迭代法公式:\(x_n = x_{n – 1} – \frac{f(x_{n – 1})}{f'(x_{n – 1})}\)。

代码:

import java.util.Scanner;
import java.math.BigDecimal;

public class Main {
    private static final BigDecimal EPS = new BigDecimal("0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001");
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        BigDecimal sqrt5 = sqrtNewtownMethod("5");
        BigDecimal goldNum = sqrt5.add(BigDecimal.valueOf(1)).divide(BigDecimal.valueOf(2));
        while (in.hasNext()) {
            BigDecimal a = in.nextBigDecimal();
            BigDecimal b = in.nextBigDecimal();
            if (a.compareTo(b) > 0) {
                BigDecimal t = a;
                a = b;
                b = t;
            }
            BigDecimal c = b.subtract(a).multiply(goldNum);
            if (c.setScale(0, BigDecimal.ROUND_FLOOR).compareTo(a) == 0)
                System.out.println("0");
            else
                System.out.println("1");
        }
    }
    private static BigDecimal sqrtNewtownMethod(String b) {
        BigDecimal two = BigDecimal.valueOf(2);
        BigDecimal num = new BigDecimal(b);
        BigDecimal pre = new BigDecimal(b);
        BigDecimal crt = new BigDecimal("0");
        while (true) {
            // System.out.println(pre.subtract(pre.multiply(pre).subtract(num).divide(two.multiply(pre))));
            crt = pre.subtract(pre.multiply(pre).subtract(num).divide(two.multiply(pre), 102, BigDecimal.ROUND_FLOOR));
            if (crt.subtract(pre).abs().compareTo(EPS) < 0) break;
            pre = crt;
        }
        return crt;
    }
}

 

【HDU-4990】Reading comprehension

【HDU-4990】Reading comprehension

Solution:

看上去是分奇偶的,但是具有统一的递推形式:

记\(a_k\)为第k项的值。

Part 1.当k是偶数时,则\(a_k = a_{k – 1} \times 2 = a_{k – 1} + 2 \times a_{k – 2} + 1\)。

Part 2.当k是奇数时,则\(a_k = a_{k – 1} \times 2 +1 = a_{k – 1} + 2 \times a_{k – 1} + 1\)。

写出变换矩阵就可以解决了。

#include <iostream>

using namespace std;

typedef long long LL;
LL MOD;
struct Matrix {
    LL t[3][3];
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {0};
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    ret.t[i][j] = (ret.t[i][j] + t[i][k] * m.t[k][j]) % MOD;
                }
            }
        }
        return ret;
    }
};

const Matrix BASE = {{1, 2, 1, 1, 0, 0, 0, 0, 1}};

Matrix powMod(int pow, Matrix m) {
    Matrix ret = {{1, 0, 0, 0, 1, 0, 0, 0, 1}};
    while (pow) {
        if (pow & 1) ret = ret * m;
        m = m * m;
        pow >>= 1;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    LL n;
    while (cin >> n >> MOD) {
        if (n == 1) cout << 1 % MOD << "\n";
        else if (n == 2) cout << 2 % MOD << "\n";
        else {
            Matrix trans = powMod(n - 2, BASE);
            LL ans = (trans.t[0][0] * 2 + trans.t[0][1] * 1 + trans.t[0][2]) % MOD;
            cout << ans << "\n";
        }
    }
    return 0;
}

 

 

【HDU-5015】233 Matrix【矩阵快速幂】

【HDU-5015】233 Matrix【矩阵快速幂】

Solution:

看到这道题,最先想说233333…

最先考虑到的方法,当然是直接暴力推,反正每个位置只与它左侧及上侧有关,推到要求的那个位置上就好,但是这样单组数据复杂度是\(O(nm)\),虽然有5000ms,但是一般这种题目数据量会很大,这样暴力绝对会超时,于是考虑到需要更快的迭代方法,第一列依次是\(0, a_1, a_2… a_n\),尝试在纸上把这个矩阵列出来,并且把每个位置上的值都只使用这些已知符号代替,我们发现一个规律,每个位置上的数实际上都把这一列它上方的所有数都加了进来,同理也把它左边的所有数都加了进来,进行简单的整理后,我们发现:每一行可以仅由上一行的值推出,每一列也可以仅由上一列的值推出。由上一行推的时候需要考虑到一个与输入相关的无规律常数,这个常数的存在破坏了递推形式不变性,所以只能够用刚才\(O(nm)\)复杂度的方法推;而由上一列推这一列时,我们需要考虑一个题目中拟定的嘲讽一般的233,它的规律很明显,由上一列到这一列,它的值扩10倍后加3便可完成这次递推,唯一不满足的就是最前面那一列的0。这时,注意到,在整个矩阵中,左上角的0是唯一一个不对结果产生贡献的值(并不是因为它是0,而是因为根据题设递推规则,它没有被加入到\(a_{nm}\)中),这样,它的值可以任意修改,那么我们便修改成23,这时每一列之间的递推形式固定的了下来,可以写出变换矩阵,之后使用矩阵快速幂来求解,复杂度降到\(O(n^3logm)\)。

总结一下,这道题关键是:

1.发现可以通过每一列的值推出下一列的值。

2.注意到0没有贡献于最终结果,是题设故意设计的一个坑。

#include <iostream>

using namespace std;

typedef long long LL;
const LL MOD = 10000007;
const int LIM = 15;
struct Matrix {
    LL t[LIM][LIM];
    int size;
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {{0}, size};
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                for (int k = 0; k < size; k++) {
                    ret.t[i][j] = (ret.t[i][j] + t[i][k] * m.t[k][j]) % MOD;
                }
            }
        }
        return ret;
    }
};

Matrix buildBase(int size) {
    Matrix ret = {{0}, size};
    ret.t[size - 1][size - 1] = 1;
    for (int i = size - 2; i >= 0; i--) {
        ret.t[i][0] = 10;
        ret.t[i][size - 1] = 1;
        for (int j = 1; j <= i; j++)
            ret.t[i][j] = 1;
    }
    return ret;
}

Matrix powMod(int pow, Matrix m) {
    Matrix ret = {{0}, m.size};
    for (int i = 0; i < ret.size; i++)
        ret.t[i][i] = 1;
    while (pow) {
        if (pow & 1) ret = ret * m;
        m = m * m;
        pow >>= 1;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    LL n, m;
    LL ori[LIM];
    while (cin >> n >> m) {
        ori[0] = 23;
        ori[n + 1] = 3;
        for (int i = 1; i <= n; i++) cin >> ori[i];
        if (m == 0) cout << ori[n] << "\n";
        else {
            Matrix trans = powMod(m, buildBase(n + 2));
            LL ans = 0;
            for (int i = 0; i <= n + 1; i++)
                ans = (ans + trans.t[n][i] * ori[i]) % MOD;
            cout << ans << "\n";
        }
    }
    return 0;
}

 

【HDU – 1711】Number Sequence【KMP】

【HDU – 1711】Number Sequence【KMP】

问题链接:https://vjudge.net/problem/HDU-1711

Solutiion:

模式匹配问题。b串是模式串,要在a串里找b。

关于KMP,详见:KMP (Knuth Morris Pratt) Pattern Searching

//
// Created by Undefined on 2018/7/17.
//

#include <iostream>

using namespace std;

const int SIZE = 1e6 + 10;
const int LIM = 1e4 + 10;             /* The maximum length of pattern string */
int kmp[LIM];
int txt[SIZE], pat[LIM];
int n, m;

void build() {
    kmp[0] = 0;
    int k = 0;
    int len = m;
    for (int i = 1; i < len; i++) {
        while (k > 0 && pat[k] != pat[i])
            k = kmp[k - 1];
        if (pat[k] == pat[i]) kmp[i] = ++k;
        else kmp[i] = 0;
    }
}

void kmpSearch() {
    build();
    int k = 0;
    int len = n;
    int pl = m;
    for (int i = 0; i < len; i++) {
        while (k > 0 && pat[k] != txt[i])
            k = kmp[k - 1];
        if (pat[k] == txt[i]) k++;
        else k = 0;
        if (k == pl) {
            printf("%d\n", i - k + 2);
            return;
        }
    }
    printf("-1\n");
}

int main(void) {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) scanf("%d", txt + i);
        for (int j = 0; j < m; j++) scanf("%d", pat + j);
        kmpSearch();
    }
    return 0;
}