杂项 | 高性能架构探索

高精度计算

在NOIP里，一般只涉及大整数的运算

int：\(-2^{31}\sim2^{31}-1\)

long long：\(-2^{63}\sim2^{63}-1\)

如何表示更大范围的整数？\(A=\overline{a_{l-1}a_{l-2}\dots a_0}=a\cdot10^0+a_1\cdot10^1+...+a_{l-1}\cdot10^{l-1}\)

字符串输入，倒序转换（毒瘤题需要压位，如每 \(4\) 位放进一个 int。但一般一位一个 int 足矣）

加法&减法

模拟竖式计算过程即可，注意：

进退位为\(\pm1\)

注意处理最高位以及进位

高精度乘法

大数乘大数

同理，\(XY=\sum_{i=0}^{l_x-1}\sum_{j=0}^{l_y-1}x_iy_j10^{i+j}\)

乘完的长度不超过 \(X\)和\(Y\)的长度之和
大数乘小数

个位一次性乘完再处理进位即可

二分

注意事项：

二分是对有关有序数列的操作
区间的更新方式与终止条件 经常犯错 要考虑完善，

二分查找

int BinarySearch(int l,int r,int t,int x[]) {
    while(l<=r) {
        int mid=(l+r)>>1;
        if(x[mid]==t) {
            return mid;
        } else if(x[mid]<t) {
            l=mid+1;
        } else {
            r=mid-1;
        }
    }
    if(l>r) {
        return -1;
    }
}

函数复杂度 \(O(\log n)\)

二分答案

判断条件：

问题的答案满足单调性
题目要求最大最小等

解决套路：

把可能的答案序列排序
枚举当前可能的答案区间中间值mid
验证这个答案是不是一个可行解
缩小区间，重复2
缩小到不能二分时，判断是无解还是找到了最优可行解

字符串

字符串术语

子序列（不破坏相对顺序）、子串（连续的字符的集合，个数 \(=\frac{n(n+1)}{2}\)），回文串
前缀，后缀
字符串匹配

在文本串 \(T\)（或集合）中，找到所有与模式串 \(P\) 匹配的个数

Trie树

解决：

字符串匹配
前缀匹配

基本性质：

储存了字符串的前缀信息
除了根节点，其他节点有且仅有一个字符
从根节点开始到某一个节点连接起来就是该节点对应的前缀
Trie 树可以在线构建
插入一个新的字符串
- 时间复杂度 \(O(len)\)
- 空间复杂度 \(O(\sum len)\)

用法：

字符串查找
前缀相同的字符串
自动排序
两两计算最长公共前缀
扩展：建二进制Trie树，存二进制数

存储实现：

struct Node {
    int cnt;
    Node *ch[30]= {0};
    //或者
    int nxt[30]= {0};//转指针为数组
};

字符串Hash

字符串 \(\rightarrow\) 数字：

hash=0;
p=19260817LL,q=1e9+7LL;
for(int i=0; i<len; i++) {
    hash=(hash*p%q+s[i]-'a'+1)%q;
}

KMP算法

加速单模板串，多个文本串或长文本串的匹配
失配数组\(nxt[i]=j\)表示当第\(i\)位失配时可以快速移动到\(j\)
\(nxt\)数组代可以通过自己配对自己得到

  void getnext(char *s,int len,int *nxt) {
      int x=0;
      nxt[0]=-1;
      for(int i=1; i<len; i++) {
          while(x!=-1&&s[x]^s[x-1]) {
              x=nxt[x];
          }
          nxt[i+1]=++x;
      }
  }
  //kmp函数同理

马拉车

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
char s[maxn * 2], str[maxn * 2];
int Len[maxn * 2], len;
void getstr() {//重定义字符串
    int k = 0;
    str[k++] = '@';//开头加个特殊字符防止越界
    for (int i = 0; i < len; i++) {
        str[k++] = '#';
        str[k++] = s[i];
    }
    str[k++] = '#';
    len = k;
    str[k] = 0;//字符串尾设置为0，防止越界
}
int manacher() {
    int mx = 0, id;//mx为最右边，id为中心点
    int maxx = 0;
    for (int i = 1; i < len; i++) {
        if (mx > i) Len[i] = min(mx - i, Len[2 * id - i]);//判断当前点超没超过mx
        else Len[i] = 1;//超过了就让他等于1，之后再进行查找
        while (str[i + Len[i]] == str[i - Len[i]]) Len[i]++;//判断当前点是不是最长回文子串，不断的向右扩展
        if (Len[i] + i > mx) {//更新mx
            mx = Len[i] + i;
            id = i;//更新中间点
            maxx = max(maxx, Len[i]);//最长回文字串长度
        }
    }
    return (maxx - 1);
}
int main() {
    scanf("%s", s);
    len = strlen(s);
    getstr();
    printf("%d\n",manacher());
    return 0;
}

题目

例题

CF1181B

从中间开始向两边找，找到第一个划分即为所求
CF900B

模拟（e.g \(\frac{24}{7}:(24,0)\rightarrow(3,3)\rightarrow(30,3)...\)）
AT2827

贪心+二分查找优化时间复杂度
P2678

二分选手的最小跳跃距离，如果距离小于选手的最小跳跃距离则把这块石头移走，移走数目大于\(m\)时不满足题意，反之亦然。

杂项