4_3

5669

acwing_1482

ZXG_DXX
77777777777
Caesar123

cocoonnnp

zufestudy3
C++大蒟蒻

ease
1564269628

AcWing2AK
Catch-22

YuWindSky

4_3
11小时前
class Solution:
def maxChunksToSorted(self, arr: List[int]) -> int:
stk = []
for x in arr:
t = x
while len(stk) and stk[-1] > x:
t = max(t, stk[-1])
stk.pop()
stk.append(t)
return len(stk)

class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
stack<int> stk;
for (int i = 0; i < arr.size(); i ++)
{
int t = arr[i];
while (stk.size() && stk.top() > arr[i])
{
t = max(stk.top(), t);
stk.pop();
}
stk.push(t);
}
return stk.size();
}
};


4_3
12小时前
class Solution:
def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
hash = {}
res = []
for i in range(len(groupSizes)):
if groupSizes[i] not in hash:
hash[groupSizes[i]] = []
hash[groupSizes[i]].append(i)

if len(hash[groupSizes[i]]) == groupSizes[i]:
res.append(hash[groupSizes[i]])
hash[groupSizes[i]] = []
return res

class Solution {
public:
vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
unordered_map<int, vector<int>> hash;
vector<vector<int>> res;
for (int i = 0; i < groupSizes.size(); i ++)
{
hash[groupSizes[i]].push_back(i);
if (hash[groupSizes[i]].size() == groupSizes[i])
{
res.push_back(hash[groupSizes[i]]);
hash[groupSizes[i]].clear();
}
}
return res;
}
};


4_3
5天前

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

using namespace std;

const int N = 1010;

int n, m;
int tr[N][4], cnt[N], idx;
char str[N];
int q[N], ne[N];
int f[N][N];
int a[N << 1];

int get(char c)
{
if (c == 'A') return 0;
if (c == 'G') return 1;
if (c == 'C') return 2;
return 3;
}

void insert()
{
int p = 0;
for (int i = 0; str[i]; i ++)
{
int t = get(str[i]);
if (!tr[p][t]) tr[p][t] = ++ idx;
p = tr[p][t];
}
cnt[p] = 1;
}

void build()
{
int hh = 0, tt = -1;
for (int i = 0; i < 4; i ++)
if (tr[0][i])
q[++ tt] = tr[0][i];

while (hh <= tt)
{
int t = q[hh ++];
for (int i = 0; i < 4; i ++)
{
int p = tr[t][i];
if (!p) tr[t][i] = tr[ne[t]][i];
else
{
ne[p] = tr[ne[t]][i];
q[++ tt] = p;
cnt[p] |= cnt[ne[p]];
}
}
}
}

int main()
{
int T = 1;
while (scanf("%d", &n), n)
{
memset(tr, 0, sizeof tr);
memset(cnt, 0, sizeof cnt);
memset(ne, 0, sizeof ne);
idx = 0;

for (int i = 0; i < n; i ++)
{
scanf("%s", str);
insert();
}

build();

scanf("%s", str + 1);
m = strlen(str + 1);

memset(f, 0x3f, sizeof f);
f[0][0] = 0;

int hh = 0, tt = 0;
a[tt ++] = 0;
int flag = tt;
for (int i = 0; i < m; i ++)
{
while (hh != tt && hh != flag)
{
int j = a[hh ++];
if (hh == N << 1) hh = 0;

for (int k = 0; k < 4; k ++)
{
int t = get(str[i + 1]) != k;
int p = tr[j][k];
/*
f[i + 1][p]初始值0x3f3f3f3f
f[i][j]是合法状态，加上t，小于 f[i + 1][p]的初始值
两者取等时f[i + 1][p]肯定更新过，p已经在队列里了
*/
if (!cnt[p] && f[i][j] + t < f[i + 1][p])
{
f[i + 1][p] = f[i][j] + t;
a[tt ++] = p;
if (tt == N << 1) tt = 0;
}
}
}
flag = tt;
}
int res = 0x3f3f3f3f;
for (int i = 0; i <= idx; i ++) res = min(res, f[m][i]);

if (res == 0x3f3f3f3f) res = -1;
printf("Case %d: %d\n", T ++, res);
}

return 0;
}


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

using namespace std;

const int N = 1010;

int n, m;
int tr[N][4], cnt[N], idx;
char str[N];
int q[N], ne[N];
int f[N][N];

int get(char c)
{
if (c == 'A') return 0;
if (c == 'G') return 1;
if (c == 'C') return 2;
return 3;
}

void insert()
{
int p = 0;
for (int i = 0; str[i]; i ++)
{
int t = get(str[i]);
if (!tr[p][t]) tr[p][t] = ++ idx;
p = tr[p][t];
}
cnt[p] = 1;
}

void build()
{
int hh = 0, tt = -1;
for (int i = 0; i < 4; i ++)
if (tr[0][i])
q[++ tt] = tr[0][i];

while (hh <= tt)
{
int t = q[hh ++];
for (int i = 0; i < 4; i ++)
{
int p = tr[t][i];
if (!p) tr[t][i] = tr[ne[t]][i];
else
{
ne[p] = tr[ne[t]][i];
q[++ tt] = p;
cnt[p] |= cnt[ne[p]];
}
}
}
}

int main()
{
int T = 1;
while (scanf("%d", &n), n)
{
memset(tr, 0, sizeof tr);
memset(cnt, 0, sizeof cnt);
memset(ne, 0, sizeof ne);
idx = 0;

for (int i = 0; i < n; i ++)
{
scanf("%s", str);
insert();
}

build();

scanf("%s", str + 1);
m = strlen(str + 1);

memset(f, 0x3f, sizeof f);
f[0][0] = 0;

for (int i = 0; i < m; i ++)
for (int j = 0; j <= idx; j ++)
{
if (f[i][j] == 0x3f3f3f3f || cnt[j]) continue;
for (int k = 0; k < 4; k ++)
{
int t = get(str[i + 1]) != k;
int p = tr[j][k];
if (!cnt[p]) f[i + 1][p] = min(f[i + 1][p], f[i][j] + t);
}
}

int res = 0x3f3f3f3f;
for (int i = 0; i <= idx; i ++) res = min(res, f[m][i]);

if (res == 0x3f3f3f3f) res = -1;
printf("Case %d: %d\n", T ++, res);
}

return 0;
}


4_3
6天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, M = 1000010;

int n;
int tr[M][26], cnt[M], idx;
int q[M], ne[M];
char str[M];
int id[N];

void insert(int x)
{
int p = 0;
for (int i = 0; str[i]; i ++)
{
int t = str[i] - 'a';
if (!tr[p][t]) tr[p][t] = ++ idx;
p = tr[p][t];
cnt[p] ++;
}
id[x] = p;
}

void build()
{
int hh = 0, tt = -1;
for (int i = 0; i < 26; i ++)
if (tr[0][i])
q[++ tt] = tr[0][i];

while (hh <= tt)
{
int t = q[hh ++];
for (int i = 0; i < 26; i ++)
{
int p = tr[t][i];
if (!p) tr[t][i] = tr[ne[t]][i];
else
{
ne[p] = tr[ne[t]][i];
q[++ tt] = p;
}
}
}
}

int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++)
{
scanf("%s", str);
insert(i);
}

build();

for (int i = idx - 1; ~i; i --) cnt[ne[q[i]]] += cnt[q[i]];

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

return 0;
}


4_3
7天前

trie图中有父节点的空节点，直接存其可以在树上回跳的节点编号

kmp只匹配一个单词，trie图匹配多个，可能有以i结尾的子单词匹配成功,所以要跳

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

using namespace std;

const int N = 550010, M = 1000010;

int n, T;
int tr[N][26], cnt[N], idx;
int q[N], ne[N];
char str[M];
bool st[N];

void insert()
{
int p = 0;
for (int i = 0; str[i]; i ++)
{
int t = str[i] - 'a';
if (!tr[p][t]) tr[p][t] = ++ idx;
p = tr[p][t];
}
cnt[p] ++;
}

void build()
{
int hh = 0, tt = -1;
for (int i = 0; i < 26; i ++)
if (tr[0][i])
q[++ tt] = tr[0][i];

while (hh <= tt)
{
int t = q[hh ++];
for (int i = 0; i < 26; i ++)
{
int p = tr[t][i];
if (!p) tr[t][i] = tr[ne[t]][i];
else
{
ne[p] = tr[ne[t]][i];
q[++ tt] = p;
}
}
}
}

int main()
{
scanf("%d", &T);
while (T --)
{
memset(tr, 0, sizeof tr);
memset(ne, 0, sizeof ne);
memset(cnt, 0, sizeof cnt);
memset(st, 0, sizeof st);
idx = 0;

scanf("%d", &n);
for (int i = 0; i < n; i ++)
{
scanf("%s", str);
insert();
}

build();

scanf("%s", str);

int res = 0;
for (int i = 0, j = 0; str[i]; i ++)
{
int t = str[i] - 'a';
j = tr[j][t];

int p = j;
while (p && !st[p])
{
res += cnt[p];
cnt[p] = 0;
st[p] = true;
p = ne[p];
}
}
printf("%d\n", res);
}
return 0;
}


4_3
7天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;

int n, m;
int a[N];
vector<int> nums;
struct Node{
int l, r;
int cnt;
}tr[N * 4 + N * 17];

int root[N], idx;

int find(int x)
{
return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

int build(int l, int r)
{
int p = ++ idx;
if (l == r) return p;
int mid = l + r >> 1;
tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
return p;
}

int insert(int p, int l, int r, int v)
{
int q = ++ idx;
tr[q] = tr[p];
if (l == r)
{
tr[q].cnt ++;
return q;
}
int mid = l + r >> 1;
if (v <= mid) tr[q].l = insert(tr[q].l, l, mid, v);
else tr[q].r = insert(tr[q].r, mid + 1, r, v);

tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
return q;
}

int query(int p, int q, int l, int r, int k)
{
if (l == r) return r;
int mid = l + r >> 1;
int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
if (k <= cnt) return query(tr[p].l, tr[q].l,  l, mid, k);
else return query(tr[p].r, tr[q].r, mid + 1, r, k - cnt);
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
{
scanf("%d", &a[i]);
nums.push_back(a[i]);
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());

root[0] = build(0, nums.size() - 1);

for (int i = 1; i <= n; i ++)
root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));

int l, r, k;
while (m --)
{
scanf("%d%d%d", &l, &r, &k);
printf("%d\n", nums[query(root[l - 1], root[r], 0, nums.size() - 1, k)]);
}

return 0;
}


4_3
7天前

## 关于max_id[0] = -1

max_id记录节点及其子树中数据版本号最大是多少
max_id[0] = -1，表示树中所有idx = 0的点版本号为-1，本题查询时，最小查询的是0版本号(l最小为1L = l - 1最小为0），初始化成-1表示用不到它

## 关于insert(0, 23, 0, root[0])

1.初始化其值

2.本题不同的是，要在树中搜索查询的版本号，不插入0版本的S_0 = 0，搜索时查不到

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

using namespace std;

const int N = 600010, M = N * 25;

int n, m, idx;
int s[N];
int tr[M][2], max_id[M];
int root[N];

void insert(int i, int k, int p, int q)
{
if (k < 0)
{
max_id[q] = i;
return;
}

int v = s[i] >> k & 1;
if (tr[p][v ^ 1]) tr[q][v ^ 1] = tr[p][v ^ 1];
tr[q][v] = ++ idx;
insert(i, k - 1, tr[p][v], tr[q][v]);
max_id[q] = max_id[tr[q][v]];
}

int query(int root, int C, int L)
{
int p = root;
for (int i = 23; ~i; i --)
{
int v = C >> i & 1;
if (max_id[tr[p][v ^ 1]] >= L) v ^= 1;
p = tr[p][v];
}

return C ^ s[max_id[p]];
}

int main()
{
scanf("%d%d", &n, &m);

max_id[0] = -1;
root[0] = ++ idx;
insert(0, 23, 0, root[0]);

for (int i = 1; i <= n; i ++)
{
scanf("%d", &s[i]);
s[i] ^= s[i - 1];
root[i] = ++ idx;
insert(i, 23, root[i - 1], root[i]);
}

char op[2];
int l, r, x;
while (m --)
{
scanf("%s", op);
if (*op == 'A')
{
scanf("%d", &x);
root[++ n] = ++ idx;
s[n] = s[n - 1] ^ x;
insert(n, 23, root[n - 1], root[n]);
}
else
{
scanf("%d%d%d", &l, &r, &x);
printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1));
}
}

return 0;
}


4_3
8天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 600010, M = N * 25;

int n, m, idx;
int s[N];
int tr[M][2], max_id[M];
int root[N];

void insert(int i, int k, int p, int q)
{
if (k < 0)
{
max_id[q] = i;
return;
}

int v = s[i] >> k & 1;
if (tr[p][v ^ 1]) tr[q][v ^ 1] = tr[p][v ^ 1];
tr[q][v] = ++ idx;
insert(i, k - 1, tr[p][v], tr[q][v]);
max_id[q] = max_id[tr[q][v]];
}

int query(int root, int C, int L)
{
int p = root;
for (int i = 23; ~i; i --)
{
int v = C >> i & 1;
if (max_id[tr[p][v ^ 1]] >= L) v ^= 1;
p = tr[p][v];
}

return C ^ s[max_id[p]];
}

int main()
{
scanf("%d%d", &n, &m);

max_id[0] = -1;
root[0] = ++ idx;
insert(0, 23, 0, root[0]);

for (int i = 1; i <= n; i ++)
{
scanf("%d", &s[i]);
s[i] ^= s[i - 1];
root[i] = ++ idx;
insert(i, 23, root[i - 1], root[i]);
}

char op[2];
int l, r, x;
while (m --)
{
scanf("%s", op);
if (*op == 'A')
{
scanf("%d", &x);
root[++ n] = ++ idx;
s[n] = s[n - 1] ^ x;
insert(n, 23, root[n - 1], root[n]);
}
else
{
scanf("%d%d%d", &l, &r, &x);
printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1));
}
}

return 0;
}


4_3
8天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 3100010;

int n, idx;
int a[N];
int son[M][2];

void insert(int x)
{
int p = 0;
for (int i = 30; ~i; i --)
{
int &s = son[p][x >> i & 1];
if (!s) s = ++ idx;
p = s;
}
}

int search(int x)
{
int p = 0, res = 0;
for (int i = 30; ~i; i --)
{
int t = x >> i & 1;
if (son[p][!t])
{
res += 1 << i;
t ^= 1;
}
p = son[p][t];
}
return res;
}

int main()
{
cin >> n;
for (int i = 0; i < n; i ++)
{
scanf("%d", &a[i]);
insert(a[i]);
}

int res = 0;
for (int i = 0; i < n; i ++) res = max(res, search(a[i]));
printf("%d\n", res);

return 0;
}


4_3
8天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, idx;
int son[N][26], cnt[N];
char str[N];

void insert(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++)
{
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++;
}

int query(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++)
{
int u = str[i] - 'a';
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}

int main()
{
scanf("%d", &n);
while (n -- )
{
char op[2];
scanf("%s%s", op, str);
if (*op == 'I') insert(str);
else printf("%d\n", query(str));
}
return 0;
}