Aigrl

2.3万

AcWing2AK

tuffynibbles
Xuan_Wei
2010

ALS
yunyun117
hncsxzx
OI

Confidentinvincible

Abel51

Aigrl
8小时前

# 笔记汇总

## 广义二项式定理

Aigrl
10小时前

Aigrl
13小时前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 50;

int n;
int w[N];
unsigned f[N][N];
int root[N][N];

void dfs(int l, int r)
{
if (l > r) return;

int k = root[l][r];
printf("%d ", k);
dfs(l, k - 1);
dfs(k + 1, r);
}

int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
for (int len = 1; len <= n; len ++ )
for (int l = 1; l + len - 1 <= n; l ++ )
{
int r = l + len - 1;

for (int k = l; k <= r; k ++ )
{
int left = k == l ? 1 : f[l][k - 1];
int right = k == r ? 1 : f[k + 1][r];
int score = left * right + w[k];
if (l == r) score = w[k];
if (f[l][r] < score)
{
f[l][r] = score;
root[l][r] = k;
}
}
}

printf("%d\n", f[1][n]);
dfs(1, n);
puts("");

return 0;
}


Aigrl
13小时前

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 50;

int n;
int w[N];
unsigned f[N][N];
int root[N][N];

void dfs(int l, int r)
{
if (l > r) return;

int k = root[l][r];
printf("%d ", k);
dfs(l, k - 1);
dfs(k + 1, r);
}

int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
for (int len = 1; len <= n; len ++ )
for (int l = 1; l + len - 1 <= n; l ++ )
{
int r = l + len - 1;

for (int k = l; k <= r; k ++ )
{
int left = k == l ? 1 : f[l][k - 1];
int right = k == r ? 1 : f[k + 1][r];
int score = left * right + w[k];
if (l == r) score = w[k];
if (f[l][r] < score)
{
f[l][r] = score;
root[l][r] = k;
}
}
}

printf("%d\n", f[1][n]);
dfs(1, n);
puts("");

return 0;
}


Aigrl
13小时前

double get_dist(PII a, PII b)
{
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}

double get_hash()
{
double sum = 0;
for (int i = 0; i < top; i ++ )
for (int j = i + 1; j < top; j ++ )
sum += get_dist(q[i], q[j]);    // hash 贡献值
return sum;
}

// 可用最小表示法替换


static ：静态全局变量，清空数组用

typedef unsigned long long ULL;

P = 131;

dfs，参量：坐标，由上往下（递推式）记得判重。

bfs，参量：坐标，如上。

int get_min(char a[N], int n)
{
static char b[N * 2];
for(int i = 0; i < n; i ++)  b[i] = b[i + n] = a[i];    // 拆链法

int i = 0, j = 1, k = 0;
while(i < n and j < n)  // 枚举起点
{
for(k = 0; k < n and b[i + k] == b[j + k]; k ++);   // 找不同
if(k == n)  break;          // 换一波起点
if(b[i + k] > b[j + k]) {   // j 更优
i += k + 1;             // i 后 p = [1,k] 位都不够优秀，因为j+p起在同构处之后，有更优字符
if(i == j)  i ++;       // 错位法
}
else {
j += k + 1;
if(i == j)  j ++;
}
}
k = min(i, j);                  // i >= n ? j : i
for(int i = 0; i < n; i ++)  a[i] = b[k + i];
a[i + n] = 0;

return k;
}



Aigrl
13小时前

double get_dist(PII a, PII b)
{
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}

double get_hash()
{
double sum = 0;
for (int i = 0; i < top; i ++ )
for (int j = i + 1; j < top; j ++ )
sum += get_dist(q[i], q[j]);    // hash 贡献值
return sum;
}

// 可用最小表示法替换


static ：静态全局变量，清空数组用

typedef unsigned long long ULL;

P = 131;

dfs，参量：坐标，由上往下（递推式）记得判重。

bfs，参量：坐标，如上。

int get_min(char a[N], int n)
{
static char b[N * 2];
for(int i = 0; i < n; i ++)  b[i] = b[i + n] = a[i];    // 拆链法

int i = 0, j = 1, k = 0;
while(i < n and j < n)  // 枚举起点
{
for(k = 0; k < n and b[i + k] == b[j + k]; k ++);   // 找不同
if(k == n)  break;          // 换一波起点
if(b[i + k] > b[j + k]) {   // j 更优
i += k + 1;             // i 后 p = [1,k] 位都不够优秀，因为j+p起在同构处之后，有更优字符
if(i == j)  i ++;       // 错位法
}
else {
j += k + 1;
if(i == j)  j ++;
}
}
k = min(i, j);                  // i >= n ? j : i
for(int i = 0; i < n; i ++)  a[i] = b[k + i];
a[i + n] = 0;

return k;
}



Aigrl
1天前

# 笔记汇总

$AC$ 自动机是 以 Trie 的结构为基础，结合 KMP 的思想 建立的。

1. 基础的 Trie 结构：将所有的模式串构成一棵 Trie。
2. KMP 的思想：对 Trie 树上所有的结点构造失配指针。

## 失配指针

1. 共同点：两者同样是在失配的时候用于跳转的指针。
2. 不同点：next 指针求的是最长 Border（即最长的相同前后缀），而 fail 指针指向所有模式串的前缀中匹配当前状态的最长后缀。

## 实现

### 建字典树

void insert(char *s) {
int u = 0;
for (int i = 1; s[i]; i++) {
if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot;  // 如果没有则插入新节点
u = tr[u][s[i] - 'a'];                              // 搜索下一个节点
}
e[u]++;  // 尾为节点 u 的串的个数
}


### 建失配指针

tr[u][c] 从u往后加一个字符c到达的结点

void build() {
for (int i = 0; i < 26; i++)
if (tr[0][i]) q.push(tr[0][i]);
while (q.size()) {    // bfs 更新确保前面阶段求出
int u = q.front();
q.pop();
for (int i = 0; i < 26; i++) {
if (tr[u][i])
fail[tr[u][i]] = tr[fail[u]][i];
// tr[u][i] 的失配指针等于其父节点的失配指针下沿（若有的话）的节点编号
q.push(tr[u][i]);
else
tr[u][i] = tr[fail[u]][i];
// 没有时快速返回，减少时间复杂度
}
}
}


### 多模式匹配

int query(char *t) {    // 搜索模式串的字符数组
int u = 0, res = 0;
for (int i = 1; t[i]; i++) {  // 非空搜索
u = tr[u][t[i] - 'a'];      // 往后走
for (int j = u; j && e[j] != -1; j = fail[j]) { // 未走完且未重复走则统计出现过的模式串数量
res += e[j], e[j] = -1;
}
}
return res;
}


## 扩展

### T1

int query(char *t) {    // 搜索模式串的字符数组
int u = 0, res = 0;
for (int i = 1; t[i]; i++) {  // 非空搜索
u = tr[u][t[i] - 'a'];      // 往后走
for (int j = u; j && e[j] != -1; j = fail[j]) { // 未走完且未重复走则统计出现过的模式串数量
res += e[j], e[j] = -1;
}
}
return res;
}

// 以 u 为结尾的字符串编号为 idx[u]

int query(char *t) {  // 返回最大的出现次数
int u = 0, res = 0;
for (int i = 1; t[i]; i++) {
u = tr[u][t[i] - 'a'];
for (int j = u; j; j = fail[j]) val[j]++;
// 可以重复走，不用 e 数组
}
for (int i = 0; i <= tot; i++)    // 搜索所有节点, 但只用看字符串的末尾结点（的编号）
if (idx[i]) res = max(res, val[i]), cnt[idx[i]] = val[i]; // 最优化更新, 维护 cnt 以便于输出出现次数相同的字符串
return res;   // 出现次数
}


Aigrl
1天前

Aigrl
1天前

KMP 是可以在文本串$s$中快速查找模式串$p$的一种算法。

## 部分匹配表

$pmt[i]$ 就是，从 $p[0]$ 往后数、同时从 $p[i]$ 往前数相同的位数，在保证前后缀相同的情况下，最多能数多少位。（但要 小于 $p$的长度）

## 匹配

Aigrl
1天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
struct Data
{
int a, b, c, s, res;    // s 是单点的贡献(即所有重复数据)

bool operator< (const Data& t) const
{
if (a != t.a) return a < t.a;
if (b != t.b) return b < t.b;
return c < t.c;
}
bool operator== (const Data& t) const
{
return a == t.a && b == t.b && c == t.c;
}
}q[N], w[N];
int tr[M], ans[N];  // 可以用权值线段树替换

int lowbit(int x)
{
return x & -x;
}

{
for (int i = x; i < M; i += lowbit(i)) tr[i] += v;
}

int query(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}

// 归并排序
void merge_sort(int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(l, mid), merge_sort(mid + 1, r);

// 双指针统计区间合并时的贡献
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)  // 边界
if (q[i].b <= q[j].b) add(q[i].c, q[i].s), w[k ++ ] = q[i ++ ];
else q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
// q[i].b > q[j].b,仅当 q[i].a < q[j].a,则统计此时贡献
while (i <= mid) add(q[i].c, q[i].s), w[k ++ ] = q[i ++ ];
// i 余下的仍然要加入树,以便于后面清空树状数组
while (j <= r) q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
// 统计贡献,此时都是满足的
for (i = l; i <= mid; i ++ ) add(q[i].c, -q[i].s);  // 清空树状数组
for (i = l, j = 0; j < k; i ++, j ++ ) q[i] = w[j];
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
q[i] = {a, b, c, 1};
}
sort(q, q + n);

int k = 1;
for (int i = 1; i < n; i ++ )
if (q[i] == q[k - 1]) q[k - 1].s ++ ;
else q[k ++ ] = q[i];

merge_sort(0, k - 1);
for (int i = 0; i < k; i ++ )
ans[q[i].res + q[i].s - 1] += q[i].s;

for (int i = 0; i < n; i ++ ) printf("%d\n", ans[i]);

return 0;
}