字符串
Trie
const int maxn = 1e6+10;
char str[15];
int trie[maxn][26], rec[maxn], num;
void insert() {
int len = strlen(str), p = 0;
for (int i = 0; i<len; ++i) {
int n = str[i]-'a';
if (!trie[p][n]) trie[p][n] = ++num; //给新结点分配编号
p = trie[p][n];
}
++rec[p]; //字符串的结尾
}
int find() { //在trie上遍历当前字符串，看是否存在当前字符串的子串
int len = strlen(str), p = 0;
for (int i = 0; i<len; ++i) {
if (!trie[p][str[i]-'a']) return 0;
p = trie[p][str[i]-'a'];
}
return 1;
}
acwing 143 01trie
const int maxn = 1e5+10;
const int maxm = 3e6+10;
int a[maxn], trie[maxm][2], tot, n;
void insert(int num) {
int p = 0;
for (int i = 30; i>=0; --i) {
int t = num>>i&1;
if (!trie[p][t]) trie[p][t] = ++tot;
p = trie[p][t];
}
}
ll solve(int x) {
ll res = 0, p = 0;
for (int i = 30; i>=0; --i) {
res <<= 1;
int t = x>>i&1;
if (trie[p][t^1]) {
res |= 1;
p = trie[p][t^1];
}
else p = trie[p][t];
}
return res;
}
int main() {
scanf("%d",&n);
for (int i = 0; i<n; ++i) {
scanf("%d",&a[i]);
insert(a[i]);
}
ll res = 0;
for (int i = 0; i<n; ++i) res = max(res,solve(a[i]));
printf("%lld
",res);
return 0;
}
kmp
const int maxn = 1e6+10;
char str[maxn], sstr[maxn];
int len, slen, ans, nxt[maxn];
void get_next() {
int i = 0, j = -1;
nxt[i] = j;
while(i < len){
while( j != -1 && sstr[i] != sstr[j]) j = nxt[j];
nxt[++i] = ++j;
}
}
void kmp() {
get_next();
int i =0, j = 0;
while(i < len){
while(j != -1 && str[i] != sstr[j]) j = nxt[j];
++i, ++j;
if(j == slen) {
++ans;
//j = 0; 不允许重叠
}
}
}
HDU 1358
KMP求前缀的最小循环节以及循环次数
const int maxn = 2e6+10;
char str[maxn];
int n, nxt[maxn];
void get_next() {
int i = 0, j = -1;
nxt[i] = j;
while(i<n) {
while(~j && str[i]!=str[j]) j = nxt[j];
nxt[++i] = ++j;
}
}
int main(void) {
int kase = 1;
while(~scanf("%d", &n) && n) {
scanf("%s", str);
get_next();
printf("Test case #%d
", kase++);
for (int i = 2; i<=n; ++i) {
int tmp = i-nxt[i];
if (nxt[i]>=1 && !(i%tmp)) printf("%d %d
", i, i/tmp);
nxt[i] = 0;
}
putchar(endl);
}
return 0;
}
exkmp
在KMP算法的流程中, 我们可以很方便的求出来一个量: 在T[j]移动之前, 说明发生了匹配失败, 而这个时候, 已经匹配的长度就是T[j]了.记录下这个长度, 就得到了串s的每一个后缀与串t的最长公共前缀这个就是扩展KMP算法所求的, 我们只需要在T[j]移动前记录下它就好
const int maxn = 1e6+10;
char s[maxn], str[maxn];
int m, n;
ll nxt[maxn], ext[maxn];
void exkmp(char *s, char *t, ll *f, ll *extend) {
int lens = strlen(s), lent = strlen(t), i, j;
for(i = 0; i < lens; i++) extend[i] = 0;// extend与s等长, 并且需要初始化为0
f[1] = 0;
for(i = 1, j = 0; i < lent; f[++i]=j) {
while(j && t[i] != t[j]) j = f[j];
if(t[i] == t[j]) ++j;
}
for(i = 0, j = 0; i < lens; ++i) {
while(j && s[i] != t[j]) {
extend[i-j] = j; // T[j]发生变化前
j = f[j];
}
if(s[i] == t[j]) ++j;
if(j == lent) {
extend[i+1-j] = j; j = f[j];
} //T[j]发生变化前
}
while(i-j < lens) extend[i-j] = j, j = f[j];
//最后, 需要求完剩余的部分, 因为匹配的结束是 Si 到结尾, 这时 i-j 还未到末尾
}
exkmp模板2
const int maxn = 1e6+10;
char s[maxn], str[maxn];
int m, n;
ll nxt[maxn], ext[maxn];
void egn() {
nxt[0] = m;
int j = 0;
while(j+1 < m && s[j]==s[j+1]) ++j;
nxt[1] = j;
int k = 1;
for (int i = 2; i<m; ++i) {
int p = nxt[k]+k-1, l = nxt[i-k];
if (i+l < p+1) nxt[i] = l;
else {
j = max(0, p-i+1);
while(i+j < m && s[i+j]==s[j]) ++j;
nxt[i] = j;
k = i;
}
}
}
void ekmp() {
egn();
int j = 0;
while(j<n && j<m && s[j]==str[j]) ++j;
ext[0] = j;
int k = 0;
for (int i = 1; i<n; ++i) {
int p = ext[k]+k-1;
int l = nxt[i-k];
if (i+l < p+1) ext[i] = l;
else {
j = max(0, p-i+1);
while(i+j<n && j<m && str[i+j]==s[j]) ++j;
ext[i] = j;
k = i;
}
}
}
HDU 6153
求一个串以i为终点和另一个串以末尾为终点的公共后缀(颠倒一下就是公共前缀)
const int maxn = 1e6+10;
char s[maxn], str[maxn];
int m, n;
ll nxt[maxn], ext[maxn];
void egn() {
nxt[0] = m;
int j = 0;
while(j+1 < m && s[j]==s[j+1]) ++j;
nxt[1] = j;
int k = 1;
for (int i = 2; i<m; ++i) {
int p = nxt[k]+k-1, l = nxt[i-k];
if (i+l < p+1) nxt[i] = l;
else {
j = max(0, p-i+1);
while(i+j < m && s[i+j]==s[j]) ++j;
nxt[i] = j;
k = i;
}
}
}
void ekmp() {
egn();
int j = 0;
while(j<n && j<m && s[j]==str[j]) ++j;
ext[0] = j;
int k = 0;
for (int i = 1; i<n; ++i) {
int p = ext[k]+k-1;
int l = nxt[i-k];
if (i+l < p+1) ext[i] = l;
else {
j = max(0, p-i+1);
while(i+j<n && j<m && str[i+j]==s[j]) ++j;
ext[i] = j;
k = i;
}
}
}
int main(){
int t; scanf("%d", &t);
while(t--) {
scanf("%s%s", str, s);
m = strlen(s), n = strlen(str);
reverse(s, s+m); reverse(str, str+n);
ekmp();
ll ans = 0;
for (int i = 0; i<n; ++i)
ans = (ans+(1LL+ext[i])*ext[i]/2%MOD)%MOD;
printf("%lld
", ans);
}
return 0;
}
manacher
char ma[maxn], str[maxn];
int ans, len, mp[maxn];
void manacher() {
int l = 0;
ma[l++] = '$', ma[l++] = '#';
for (int i = 0; i<len; ++i) {
ma[l++] = str[i];
ma[l++] = '#';
}
ma[l] = -1;
int id = 0, mx = 0;
for (int i = 0; i<l; ++i) {
mp[i] = mx>i ? min(mp[id*2-i], mx-i) : 1;
while(ma[i+mp[i]]==ma[i-mp[i]]) ++mp[i];
if (mx<i+mp[i]) {
mx = i+mp[i];
id = i;
}
}
}
HDU 5340
求是否能用三个回文串组成一个字符串
const int maxn = 1e5+10;
char ma[maxn], str[maxn];
int ans, len, mp[maxn], pre[maxn], post[maxn];
bool manacher() {
int l = 0;
ma[l++] = '$', ma[l++] = '#';
for (int i = 0; i<len; ++i) {
ma[l++] = str[i];
ma[l++] = '#';
}
ma[l] = '1';
int id = 0, mx = 0, k1 = 0, k2 = 0;
for (int i = 0; i<l; ++i) {
mp[i] = mx>i ? min(mp[id*2-i], mx-i) : 1;
while(ma[i+mp[i]]==ma[i-mp[i]]) ++mp[i];
if (mx<i+mp[i]) {
mx = i+mp[i];
id = i;
}
if (mp[i]>1 && i-mp[i]==0) pre[k1++] = i;
if (mp[i]>1 && i+mp[i]==l) post[k2++] = i;
}
for (int i = 0; i<k1; ++i)
for (int j = k2-1; j>=0; --j) {
int L = pre[i]+mp[pre[i]]-1, R = post[j]-mp[post[j]]+1;
if (L>=R) break;
int mid = (L+R)/2;
if (mp[mid]>1 && mid+mp[mid]-1>=R) return true;
}
return false;
}
int main(void) {
int t; scanf("%d", &t);
while(t--) {
scanf("%s", str);
len = strlen(str);
printf("%s
", manacher()? "Yes":"No");
}
return 0;
}
数据结构
分块
const int maxn = 5e4+10;
int n,sz,num,a[maxn],ls[maxn],rs[maxn],belong[maxn],lazy[maxn];
void build() {
sz = sqrt(n);
num = (n+sz-1)/sz;
for (int i = 1; i<=num; ++i) {
ls[i] = (i-1)*sz+1, rs[i] = i*sz;
}
rs[num] = n;
for (int i = 1; i<=n; ++i) belong[i] = (i-1)/sz+1;
}
void update(int l, int r, int c) {
if (belong[l]==belong[r]) {
//左右同一块处理
return;
}
for (int i = belong[l]+1; i<belong[r]; ++i) //处理左边不完整的块
for (int i = l; i<=rs[belong[l]]; ++i) //用lazy处理中间完整的块
for (int i = ls[belong[r]]; i<=r; ++i) //处理右边不完整的块
}
LibreOJ 6279
给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内比x小的最大元素.
const int maxn = 1e5+10;
struct INFO {
int num, i;
INFO(int a=0, int b=0): num(a), i(b) {}
bool operator < (const INFO &a) const {
return num < a.num;
}
} arr[maxn];
int n,sz,num,l[maxn],r[maxn],bl[maxn],lazy[maxn];
void build() {
num = (n+sz-1)/sz;
for (int i = 1; i<=num; ++i) {
l[i] = (i-1)*sz+1, r[i] = i*sz;
}
r[num] = n;
for (int i = 1; i<=n; ++i) bl[i] = (i-1)/sz+1;
for (int i = 1; i<=num; ++i) sort(arr+l[i],arr+r[i]+1);
}
void update(int a, int b, int c) {
if (bl[a]==bl[b]) {
for (int i = l[bl[a]]; i<=r[bl[a]]; ++i)
if (arr[i].i>=a && arr[i].i<=b) arr[i].num += c;
sort(arr+l[bl[a]], arr+r[bl[a]]+1);
return;
}
for (int i = bl[a]+1; i<bl[b]; ++i) lazy[i] += c;
for (int i = l[bl[a]]; i<=r[bl[a]]; ++i)
if (arr[i].i>=a) arr[i].num += c;
for (int i = l[bl[b]]; i<=r[bl[b]]; ++i)
if (arr[i].i<=b) arr[i].num += c;
sort(arr+l[bl[a]], arr+r[bl[a]]+1);
sort(arr+l[bl[b]], arr+r[bl[b]]+1);
}
int find(int a, int b, int c) {
ll ans = LLONG_MIN;
if (bl[a]==bl[b]) {
for (int i = l[bl[a]]; i<=r[bl[a]]; ++i)
if (arr[i].i>=a && arr[i].i<=b && arr[i].num+lazy[bl[i]]<c) ans = max(ans, (ll)arr[i].num+lazy[bl[i]]);
return ans==LLONG_MIN?-1:ans;
}
for (int i = bl[a]+1; i<bl[b]; ++i) {
if (arr[r[i]].num+lazy[i]<c) ans = max(ans,(ll)(arr[r[i]].num+lazy[i]));
else if (arr[l[i]].num+lazy[i]<c) {
int p = lower_bound(arr+l[i],arr+r[i]+1,INFO(c-lazy[i],0))-arr;
ans = max(ans,(ll)arr[p-1].num+lazy[i]);
}
}
for (int i = l[bl[a]]; i<=r[bl[a]]; ++i)
if (arr[i].i>=a && arr[i].num+lazy[bl[i]]<c) ans = max(ans,(ll)arr[i].num+lazy[bl[i]]);
for (int i = l[bl[b]]; i<=r[bl[b]]; ++i)
if (arr[i].i<=b && arr[i].num+lazy[bl[i]]<c) ans = max(ans,(ll)arr[i].num+lazy[bl[i]]);
return ans==LLONG_MIN?-1:ans;
}
int main() {
scanf("%d",&n);
for (int i = 1; i<=n; ++i) {
scanf("%d",&arr[i].num);
arr[i].i = i;
}
sz = sqrt(n); build();
for (int i = 1,op,l,r,c; i<=n; ++i) {
scanf("%d%d%d%d",&op,&l,&r,&c);
if (!op) update(l,r,c);
else printf("%d
",find(l,r,c));
}
return 0;
}
莫队
const int maxn = 2e5+10;
ll ans[maxn], res;
int arr[maxn], cnt[maxn*5], sz;
struct Q {
int l, r, i;
} q[maxn];
inline void add(int p) {
}
inline void sub(int p) {
}
int main(void) {
int n, m; scanf("%d%d", &n, &m);
sz = sqrt(n)+eps;
for (int i = 1; i<=n; ++i) scanf("%lld", &arr[i]);
for (int i = 0; i<m; ++i) scanf("%d%d", &q[i].l, &q[i].r), q[i].i = i;
sort(q, q+m, [](Q x, Q y) {return (x.l/sz^y.l/sz) ? x.l/sz < y.l/sz : ( ((x.l/sz)&1) ? x.r<y.r : x.r>y.r);});
//return x.l/sz == y.l/sz ? x.r < y.r : x.l/sz < y.l/sz; 普通排序，换成上面的奇偶排序一般快一些
int l = 1, r = 0;
for (int i = 0; i<m; ++i) {
while(q[i].r > r) add(++r);
while(q[i].l > l) sub(l++);
while(q[i].r < r) sub(r--);
while(q[i].l < l) add(--l);
ans[q[i].i] = res;
}
for (int i = 0; i<m; ++i) printf("%lld
", ans[i]);
return 0;
}
CodeForces 617E
已知一个长度为 n 的整数数列 a[1],a[2],…,a[n] ，给定查询参数 l、r ，问在 [l,r] 区间内，有多少连续子段满足异或和等于 k 。也就是说，对于所有的 x，y (l≤x≤y≤r)，能够满足a[x]a[x+1]…^a[y]=k的x，y有多少组。
const int maxn = 1e5+10;
ll cnt[maxn*100], ans[maxn], sz;
ll arr[maxn], res, k;
struct Q {
int l, r, i;
} q[maxn];
inline void add(int p) {
res += cnt[arr[p]^k];
++cnt[arr[p]];
}
inline void sub(int p) {
--cnt[arr[p]];
res -= cnt[arr[p]^k];
}
int main(void) {
int n, m;
scanf("%d%d%lld", &n, &m, &k);
for (int i = 1; i<=n; ++i) scanf("%lld", &arr[i]), arr[i] ^= arr[i-1];
for (int i = 0; i<m; ++i) scanf("%d%d", &q[i].l, &q[i].r), q[i].i = i;
sz = sqrt(n)+eps;
sort(q, q+m, [](Q x, Q y) {return (x.l/sz^y.l/sz) ? x.l/sz < y.l/sz : ( ((x.l/sz)&1) ? x.r<y.r : x.r>y.r);});
cnt[0] = 1; int l = 1, r = 0;
for (int i = 0; i<m; ++i) {
while(q[i].l < l) add(--l-1);
while(q[i].r > r) add(++r);
while(q[i].l > l) sub(l++-1);
while(q[i].r < r) sub(r--);
//因为用的前缀和，判断消去k能否到前缀异或和arr[l-1]所以要记得-1
ans[q[i].i] = res;
}
for (int i = 0; i<m; ++i) printf("%lld
", ans[i]);
return 0;
}
CodeForces 86D
给定一个长度N的数组a, 询问区间1<=L<=R<=N中，每个数字出现次数的平方与当前数字的乘积和
const int maxn = 2e5+10;
ll ans[maxn], res;
int arr[maxn], cnt[maxn*5], sz;
struct Q {
int l, r, k;
} q[maxn];
inline void add(int p) {
++cnt[arr[p]];
res += 1LL * cnt[arr[p]]*cnt[arr[p]]*arr[p];
res -= 1LL * (cnt[arr[p]]-1)*(cnt[arr[p]]-1)*arr[p];
}
inline void sub(int p) {
res -= 1LL * cnt[arr[p]] * cnt[arr[p]] * arr[p];
res += 1LL * (cnt[arr[p]]-1)*(cnt[arr[p]]-1)*arr[p];
--cnt[arr[p]];
}
int main(void) {
int n, m; scanf("%d%d", &n, &m);
sz = sqrt(n)+eps;
for (int i = 1; i<=n; ++i) scanf("%lld", &arr[i]);
for (int i = 0; i<m; ++i) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].k = i;
}
sort(q, q+m, [](Q x, Q y) {return (x.l/sz^y.l/sz) ? x.l/sz < y.l/sz : ( ((x.l/sz)&1) ? x.r<y.r : x.r>y.r);});
//return x.l/sz == y.l/sz ? x.r < y.r : x.l/sz < y.l/sz;
int l = 1, r = 0;
for (int i = 0; i<m; ++i) {
while(q[i].r > r) add(++r);
while(q[i].l > l) sub(l++);
while(q[i].r < r) sub(r--);
while(q[i].l < l) add(--l);
ans[q[i].k] = res;
}
for (int i = 0; i<m; ++i) printf("%lld
", ans[i]);
return 0;
}
线段树
普通操作
bzoj 1230 区间异或
const int maxn = 1e5+10;
int n, m;
struct Tree {
int l, r, sum, lz;
} tree[maxn<<2];
inline void push_up(int rt) {
tree[rt].sum = tree[rt<<1].sum+tree[rt<<1|1].sum;
}
inline void push_down(int rt) {
if (tree[rt].lz==1) {
int len = tree[rt].r-tree[rt].l+1;
tree[rt<<1].sum = (len-(len>>1))-tree[rt<<1].sum;
tree[rt<<1|1].sum = (len>>1)-tree[rt<<1|1].sum;
if (tree[rt<<1].lz==-1) tree[rt<<1].lz = 1;
else tree[rt<<1].lz ^= 1;
if (tree[rt<<1|1].lz==-1) tree[rt<<1|1].lz = 1;
else tree[rt<<1|1].lz ^= 1;
}
tree[rt].lz = -1;
}
void build(int rt, int l, int r) {
tree[rt].l = l, tree[rt].r = r; tree[rt].lz = -1; tree[rt].sum = 0;
if (l==r) return;
int mid = (l+r)>>1;
build(rt<<1, l, mid);
build(rt<<1|1, mid+1, r);
}
void update(int rt, int l, int r) {
if (tree[rt].l>=l && tree[rt].r<=r) {
int len = tree[rt].r-tree[rt].l+1;
tree[rt].sum = len-tree[rt].sum;
if (tree[rt].lz==-1) tree[rt].lz = 1;
else tree[rt].lz ^= 1;
return;
}
push_down(rt);
int mid = (tree[rt].l+tree[rt].r)>>1;
if (l<=mid) update(rt<<1, l, r);
if (r>mid) update(rt<<1|1, l, r);
push_up(rt);
}
int ask(int rt, int l, int r) {
if (tree[rt].l>=l && tree[rt].r<=r) return tree[rt].sum;
int sum = 0;
int mid = (tree[rt].l+tree[rt].r)>>1;
push_down(rt);
if (l<=mid) sum += ask(rt<<1, l, r);
if (r>mid) sum += ask(rt<<1|1, l, r);
push_up(rt);
return sum;
}
int main() {
cin >> n >> m;
build(1, 1, n);
for (int i = 0, a, b, c; i<m; ++i) {
scanf("%d%d%d", &a, &b, &c);
if (a) printf("%d
", ask(1, b, c));
else update(1, b, c);
}
return 0;
}
区间合并
HDU 1540 环形最大子段和
const int maxn = 1e5+10;
struct Tree {
int l, r, len, pre, post;
} tree[maxn<<2];
int n, m;
inline void push_down(int rt) {
tree[rt].pre = tree[rt<<1].pre;
tree[rt].post = tree[rt<<1|1].post;
if (tree[rt<<1].pre==tree[rt<<1].len) tree[rt].pre = tree[rt<<1].pre+tree[rt<<1|1].pre;
if (tree[rt<<1|1].post==tree[rt<<1|1].len) tree[rt].post = tree[rt<<1|1].post+tree[rt<<1].post;
}
void build(int rt, int l, int r) {
tree[rt].l = l, tree[rt].r = r, tree[rt].len = r-l+1;
if (l==r) {
tree[rt].pre = tree[rt].post = 1;
return;
}
int mid = (l+r)>>1;
build(rt<<1, l, mid);
build(rt<<1|1, mid+1, r);
push_down(rt);
}
void update(int rt, int pos, int val) {
if (tree[rt].l==tree[rt].r) {
tree[rt].post = tree[rt].pre = val;
return;
}
int mid = (tree[rt].l+tree[rt].r)>>1;
if (mid>=pos) update(rt<<1, pos, val);
else update(rt<<1|1, pos, val);
push_down(rt);
}
int quary(int rt, int pos) {
if (tree[rt].l==tree[rt].r) return tree[rt].pre;
int mid = (tree[rt].l+tree[rt].r)>>1;
if (mid>=pos) {
if (tree[rt<<1].post+pos>mid) return tree[rt<<1].post+tree[rt<<1|1].pre;
else return quary(rt<<1, pos);
}
else {
if (tree[rt<<1|1].pre+mid>=pos) return tree[rt<<1|1].pre+tree[rt<<1].post;
else return quary(rt<<1|1, pos);
}
}
int main() {
while(cin >> n >> m) {
stack<int> sk;
build(1, 1, n);
for (int i = 1; i<=m; ++i) {
char ch[5]; scanf("%s", ch);
if (ch[0]=='D') {
int num; scanf("%d", &num);
update(1, num, 0); sk.push(num);
}
else if (ch[0]=='Q') {
int num; scanf("%d", &num);
printf("%d
", quary(1, num));
}
else if (!sk.empty()) update(1, sk.top(), 1), sk.pop();
}
}
return 0;
}
dfs序建树
HDU 3974 把以某点为根的子树都染成一个颜色，问某点颜色
const int maxn = 2e5+10;
int n, m, in[maxn], last[maxn], num[maxn], tot;
vector<int> e[maxn];
int dfs(int u, int p) {
num[u] = ++tot;
last[u] = u;
for (auto v : e[u])
if (v!=p) last[u] = dfs(v, u);
return last[u];
}
struct Tree {
int l, r, col, lz;
} tree[maxn<<2];
void build(int rt, int l, int r) {
tree[rt].l = l, tree[rt].r = r; tree[rt].col = -1, tree[rt].lz = 0;
if (l==r) return;
int mid = (l+r)>>1;
build(rt<<1, l, mid);
build(rt<<1|1, mid+1, r);
}
inline void push_down(int rt) {
if (tree[rt].lz) {
tree[rt<<1].lz = tree[rt<<1|1].lz = tree[rt].lz;
tree[rt<<1].col = tree[rt<<1|1].col = tree[rt].lz;
tree[rt].lz = 0;
}
}
void update(int rt, int l, int r, int col) {
if (tree[rt].l>=l && tree[rt].r<=r) {
tree[rt].col = tree[rt].lz = col;
return;
}
push_down(rt);
int mid = (tree[rt].l+tree[rt].r)>>1;
if (l<=mid) update(rt<<1, l, r, col);
if (r>mid) update(rt<<1|1, l, r, col);
}
int ask(int rt, int pos) {
if (tree[rt].l==tree[rt].r) return tree[rt].col;
push_down(rt);
int mid = (tree[rt].l+tree[rt].r)>>1;
if (pos<=mid) return ask(rt<<1, pos);
else return ask(rt<<1|1, pos);
}
int k;
int main(void) {
int T; cin >> T;
while(T--) {
cin >> n;
printf("Case #%d:
", ++k);
build(1, 1, n);
for (int i = 0, a, b; i<n-1; ++i) {
scanf("%d%d", &a, &b);
e[b].push_back(a); ++in[a];
}
int rt;
for (int i = 1; i<=n; ++i)
if (!in[i]) rt = i;
tot = 0; dfs(rt, -1);
cin >> m;
while(m--) {
char ch[3]; scanf("%s", ch);
if (ch[0]=='C') {
int pos; scanf("%d", &pos);
printf("%d
", ask(1, num[pos]));
}
else {
int x, y; scanf("%d%d", &x, &y);
update(1, num[x], num[last[x]], y);
}
}
for (int i = 1; i<=n; ++i) e[i].clear(), in[i] = 0;
}
return 0;
}
树状数组
HDU 5869 区间GCD
const int maxn = 1e5+10;
int n, m, arr[maxn], pre[maxn], last[maxn*10];
ll c[maxn], ans[maxn];
void add(int x, int y) {
while(x<=n) c[x] += y, x += x&-x;
}
ll ask(int x) {
ll sum = 0;
while(x) sum += c[x], x -= x&-x;
return sum;
}
vector<P> q[maxn];
int main(void) {
while(cin >> n >> m) {
for (int i = 1; i<=n; ++i) {
scanf("%d", &arr[i]);
pre[i] = arr[i]==arr[i-1] ? pre[i-1]:i-1;
}
for (int i = 1, l, r; i<=m; ++i) {
scanf("%d%d", &l, &r);
q[r].push_back({i, l});
}
for (int i = 1; i<=n; ++i) {
for (int j = i, x = arr[j]; j; j = pre[j], x = __gcd(x, arr[j])) {
if (j>last[x]) {
if (last[x]) add(last[x], -1);
add(j, 1);
last[x] = j;
}
if (x==1) break;
}
for (auto v : q[i]) ans[v.first] = ask(i)-ask(v.second-1);
}
for (int i = 1; i<=m; ++i) printf("%lld
", ans[i]);
for (int i = 1; i<=n; ++i) q[i].clear();
clr(last, 0); clr(c, 0);
}
return 0;
}
区间翻转 POJ 2155
const int maxn = 1e3+10;
int n, m, flag, c[maxn][maxn];
void add(int x, int y) {
for (int i = x; i<=n; i+=i&-i)
for (int j = y; j<=n; j+=j&-j)
c[i][j] += 1;
}
int ask(int x, int y) {
int sum = 0;
for (int i = x; i; i-=i&-i)
for (int j = y; j; j-=j&-j)
sum += c[i][j];
return sum;
}
int main(void) {
int T; cin >> T;
while(T--) {
clr(c, 0);
if (flag) putchar(endl);
cin >> n >> m;
int a, b, c, d;
while(m--) {
char ch[10];
scanf("%s", ch);
if (ch[0]=='C') {
scanf("%d%d%d%d", &a, &b, &c, &d);
add(a, b); add(a, d+1); add(c+1, b); add(c+1, d+1);
}
else {
scanf("%d%d", &a, &b);
printf("%d
", ask(a, b)%2);
}
}
flag = 1;
}
return 0;
}
数论
exgcd
ll x, y;
void exgcd(ll a, ll b) {
if (!b) {
x = 1, y= 0;
return;
}
exgcd(b, a%b);
ll t = x; x = y;
y = t - a/b*y;
}
excrt
ll exgcd(ll a, ll b, ll &x, ll &y){
if(!b){
x = 1, y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
ll excrt() {
ll lcm = m[0], ans = a[0];
for(int i = 1; i<n; ++i) {
ll lcm_a = ((a[i]-ans)%m[i]+m[i])%m[i], x, y, k = lcm;
ll gcd = exgcd(lcm, m[i], x, y), t = m[i]/gcd;
if ((a[i]-ans) % gcd) return -1;
x = (x*lcm_a/gcd%t+t)%t;
lcm = lcm*t,ans = (ans + k*x)%lcm;
}
ans = (ans%lcm+lcm)%lcm;
return ans ? ans:lcm;
}
线性求逆元
Inv[1] = 1;
for(int i = 2; i <= n; ++i)
Inv[i] = (p - p / i)*Inv[p % i]%p;
卢卡斯定理
ll C(ll n, ll m){
if(m>n) return 0;
return fac[n]*qp(fac[m],mod-2)%mod*qp(fac[n-m],mod-2,id)%mod;
}
ll lucas(ll n,ll m){
if(!m) return 1;
return lucas(n/mod,m/mod)*C(n%mod,m%mod,id)%mod;
}
矩阵快速幂
int n, ans[2][2], res[2][2], tmp[2][2];
void mul(int a[][2], int b[][2]) {
zero(tmp);
for (int i = 0; i<2; ++i)
for (int j = 0; j<2; ++j)
for (int k = 0; k<2; ++k)
tmp[i][j] = (1LL*tmp[i][j]+1LL*a[i][k]*b[k][j]%MOD)%MOD;
memcpy(a, tmp, sizeof(tmp));
}
void mxqp(ll y) {
ans[0][0] = ans[1][1] = 1; ans[0][1] = ans[1][0] = 0; //单位矩阵
res[0][0] = res[0][1] = res[1][0] = 1; res[1][1] = 0; //用来算斐波那契数列
while(y) {
if (y&1) mul(ans, res);
mul(res, res);
y >>= 1;
}
}
图论
最短路
spfa
Acwing 340 可以有k条免费的最短路
const int maxn = 1e3+10;
const int maxm = 1e6+10;
struct E {
int to, w, nxt;
} e[maxm]; int h[maxn], tot;
void add(int u, int v, int w) {
e[++tot] = {v, w, h[u]}; h[u] = tot;
}
int n, m, k, vis[maxn], d[maxn][maxn];
void spfa() {
clr(d, 0x3f); clr(vis, 0);
queue<int> q; q.push(1); d[1][0] = 0;
while(!q.empty()) {
int u = q.front(); q.pop(); vis[u] = 0;
for (int i = h[u]; i; i=e[i].nxt) {
int v = e[i].to;
for (int j = 0; j<=k; ++j) {
int w = max(d[u][j], e[i].w);
if (j) w = min(d[u][j-1], w);
if (d[v][j]>w) {
d[v][j] = w;
if (!vis[v]) vis[v] = 1, q.push(v);
}
}
}
}
}
int main() {
cin >> n >> m >> k; tot = 0;
for (int i = 0; i<=n; ++i) h[i] = 0;
for (int i = 0,u,v,w; i<m; ++i) {
scanf("%d%d%d", &u, &v, &w);
add(u, v, w), add(v, u, w);
}
spfa();
int ans = INF;
for (int i = 0; i<=n; ++i) ans = min(ans, d[n][i]);
if (ans==INF) ans = -1;
cout << ans << endl;
return 0;
}
AcWing 341 枚举同一条路上权值最小的点和最大的点
const int maxn = 1e5+10;
const int maxm = 1e6+10;
vector<int> e[maxn], re[maxn];
int pri[maxn], d1[maxn], d2[maxn], vis[maxn], n, m;
void spfa() {
clr(d1, 0x3f); d1[1] = pri[1];
queue<int> q, clears; q.push(1);
while(!q.empty()) {
int u = q.front(); q.pop();
vis[u] = 0;
for (auto v : e[u])
if (d1[v]>min(d1[u], pri[v])) {
d1[v] = min(d1[u], pri[v]);
if (!vis[v]) q.push(v), vis[v] = 1;
}
}
clr(vis, 0);
q = clears; q.push(n);
while(!q.empty()) {
int u = q.front(); q.pop();
vis[u] = 0;
for (auto v : re[u])
if (d2[v]<max(d2[u], pri[v])) {
d2[v] = max(d2[u], pri[v]);
if (!vis[v]) q.push(v), vis[v] = 1;
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i<=n; ++i) scanf("%d", &pri[i]);
for (int i = 0, a, b, c; i<m; ++i) {
scanf("%d%d%d", &a, &b, &c);
e[a].push_back(b), re[b].push_back(a);
if (~c&1) e[b].push_back(a), re[b].push_back(a);
}
spfa();
int ans = -1;
for (int i = 1; i<=n; ++i) ans = max(ans, d2[i]-d1[i]);
cout << ans << endl;
return 0;
}
dijkstra
AcWing 342含有正的双向边和负的单向边的单源最短路(卡spfa)
const int maxn = 1e5+10;
const int maxm = 1e6+10;
int in[maxn], vis[maxn];
int n, r, p, s, tot, num[maxn], d[maxn];
vector<P> e[maxn]; vector<int> tmp[maxn], e2[maxn];
queue<int> q;
void dfs(int u) {
num[u] = tot;
tmp[tot].push_back(u);
for (auto v : e[u])
if (!num[v.second]) {
num[v.second] = tot; dfs(v.second);
}
}
void dij(int x) {
priority_queue<P, vector<P>, greater<P> > pq;
for (auto v : tmp[x]) pq.push({d[v], v});
while(!pq.empty()) {
int u = pq.top().second, w = pq.top().first; pq.pop();
if (vis[u]) continue; vis[u] = 1;
for (auto v : e[u]) {
if (vis[v.second]) continue;
if (w!=INF && d[v.second] > w+v.first) {
d[v.second]=w+v.first;
if (num[v.second]==num[u]) pq.push({d[v.second], v.second});
}
if (num[v.second]!=num[u])
if (--in[num[v.second]]==0) q.push(num[v.second]);
}
}
}
void topo() {
q.push(num[s]);
for (int i = 1; i<=tot; ++i)
if (!in[i]) q.push(i);
while(!q.empty()) {
int u = q.front(); q.pop();
dij(u);
}
}
int main() {
cin >> n >> r >> p >> s;
for (int i = 0, a, b, c; i<r; ++i) {
scanf("%d%d%d", &a, &b, &c);
e[a].push_back({c, b});
e[b].push_back({c, a});
}
for (int i = 1; i<=n; ++i)
if (!num[i]) ++tot, dfs(i);
for (int i = 0, a, b, c; i<p; ++i) {
scanf("%d%d%d", &a, &b, &c);
e[a].push_back({c, b});
}
clr(d, 0x3f); d[s] = 0;
for (int i = 1; i<=n; ++i)
for (auto v : e[i])
if (num[v.second]!=num[i]) {
++in[num[v.second]];
e2[num[i]].push_back(num[v.second]);
}
topo();
for (int i = 1; i<=n; ++i) {
if (d[i]==INF) printf("NO PATH
");
else printf("%d
", d[i]);
}
return 0;
}
floyed
AcWing344 最少包含三个边的最短路，且输出路径
const int maxn = 3e2+10;
const int maxm = 1e4+10;
int res[maxn][maxn], g[maxn][maxn];
int n, m, p[maxn][maxn];
vector<int> path;
void solve(int u, int v) {
if (!p[u][v]) return;
solve(u, p[u][v]);
path.push_back(p[u][v]);
solve(p[u][v], v);
}
int main(void) {
clr(g, 0x3f);
cin >> n >> m;
for (int i = 0, a, b, c; i<m; ++i) {
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);
}
memcpy(res, g, sizeof(g));
ll ans = LLONG_MAX;
for (int k = 1; k<=n; ++k) {
for (int i = 1; i<=n; ++i)
for (int j = i+1; j<=n; ++j)
if (i!=j && i!=k && j!=k && ans>(ll)res[i][j]+g[j][k]+g[k][i]) {
ans = (ll)res[i][j]+g[j][k]+g[k][i];
path.clear();
path.push_back(i);
solve(i, j);
path.push_back(j);
path.push_back(k);
}
for (int i = 1; i<=n; ++i)
for (int j = 1; j<=n; ++j)
if (res[i][j]>res[i][k]+res[k][j]) p[i][j] = k, res[i][j] = res[i][k]+res[k][j];
}
if (ans>=INF) cout << "No solution." << endl;
else {
int sz = path.size();
for (int i = 0; i<sz; ++i) printf(i==sz-1?"%d
":"%d ", path[i]);
}
return 0;
}
AcWing 345恰好k条边，可以重复的最短路
const int maxn = 2e2+10;
const int maxm = 1e6+10;
int n, t, s, e, tot;
map<int, int> mp;
ll g[maxn][maxn], ans[maxn][maxn], tmp[maxn][maxn];
void mul(ll a[maxn][maxn], ll b[maxn][maxn]) {
clr(tmp, 0x3f);
for (int i = 1; i<=tot; ++i)
for (int j = 1; j<=tot; ++j)
for (int k = 1; k<=tot; ++k)
if (tmp[j][k]>a[j][i]+b[i][k]) tmp[j][k]=a[j][i]+b[i][k];
memcpy(a, tmp, sizeof(tmp));
}
int main() {
cin >> n >> t >> s >> e;
clr(g, 0x3f);
for (int i = 1, a, b, c; i<=t; ++i) {
cin >> c >> a >> b;
if (!mp[a]) mp[a] = ++tot;
if (!mp[b]) mp[b] = ++tot;
g[mp[a]][mp[b]] = g[mp[b]][mp[a]] = min(g[mp[a]][mp[b]], (ll)c);
}
clr(ans, 0x3f);
for (int i = 1; i<=tot; ++i) ans[i][i] = 0;
while(n) {
if (n&1) mul(ans, g);
mul(g, g);
n >>= 1;
}
cout << ans[mp[s]][mp[e]] << endl;
return 0;
}
最小生成树
prim
kruskal
LCA
倍增
const int maxn = 1e5+10;
const int maxm = 2e6+10;
struct E {int to, nxt, w;} e[maxm]; int h[maxn], tot;
void add(int u, int v, int w) {e[++tot] = {v, h[u], w}, h[u] = tot;}
int n, m, f[maxn][21], d[maxn]; ll dis[maxn];
void bfs(int x) {
d[x] = 1, dis[x] = 0;
queue<int> q; q.push(x);
while(!q.empty()) {
int u = q.front(); q.pop();
for (int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (d[v]) continue;
d[v] = d[u]+1;
dis[v] = dis[u]+e[i].w;
q.push(v);
f[v][0] = u;
for (int j = 1; j<=20; ++j) f[v][j] = f[f[v][j-1]][j-1];
}
}
}
int lca(int x, int y) {
if (d[x]>d[y]) swap(x, y);
for (int i = 20; i>=0; --i)
if (d[f[y][i]]>=d[x]) y = f[y][i];
if (x==y) return x;
for (int i = 20; i>=0; --i)
if (f[x][i]!=f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
int main(void) {
int T; cin >> T;
while(T--) {
cin >> n >> m; tot = 0;
clr(h, 0); clr(d, 0); clr(f, 0);
for (int i = 0, a, b, c; i<n-1; ++i) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
bfs(1);
for (int i = 0, a, b; i<m; ++i) {
scanf("%d%d", &a, &b);
printf("%lld
", dis[a]+dis[b]-2*dis[lca(a,b)]);
}
}
return 0;
}
tarjan
const int maxn = 1e5+10;
const int maxm = 2e6+10;
struct E {
int to, nxt, w;
} e[maxm]; int h[maxn], tot;
void add(int u, int v, int w) {
e[++tot] = {v, h[u], w}; h[u] = tot;
}
vector<P> quary[maxn];
int n, m, d[maxn], ans[maxn], state[maxn], p[maxn];
void dfs(int u, int p) {
for (int i = h[u]; i; i=e[i].nxt) {
int v = e[i].to;
if (v!=p) d[v] = d[u]+e[i].w, dfs(v, u);
}
}
int find(int x) {
return p[x]==x ? p[x]:p[x]=find(p[x]);
}
void tarjan(int u, int fa) {
state[u] = 1;
for (int i = h[u]; i; i=e[i].nxt) {
int v = e[i].to;
if (v==fa) continue;
if (!state[v]) tarjan(v, u);
p[v] = u;
}
for (auto t : quary[u]) {
int v = t.second, id = t.first;
if (state[v]==2) ans[id] = d[u]+d[v]-d[find(v)]*2;
}
state[u] = 2;
}
int main(void) {
int t; cin >> t;
while(t--) {
cin >> n >> m; tot = 0;
for (int i = 0, a, b, c; i<n-1; ++i) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
for (int i = 1, a, b; i<=m; ++i) {
scanf("%d%d", &a, &b);
quary[a].push_back({i,b}), quary[b].push_back({i,a});
ans[i] = INF;
}
for (int i = 1; i<=n; ++i) d[i] = INF, p[i] = i;
d[1] = 0; dfs(1, 0);
tarjan(1, -1);
for (int i = 1; i<=m; ++i) printf("%d
", ans[i]), quary[i].clear();
for (int i = 1; i<=n; ++i) state[i] = 0, ans[i] = 0, h[i] = 0;
}
return 0;
}
二分图匹配
匈牙利算法
int n, m, k;
int find(int x) {
for (int i = 1; i<=m; ++i)
if (mp[x][i] && !vis[i]) {
vis[i] = true;
if (!match[i] || find(match[i])) {
match[i] = x; return 1;
}
}
return 0;
}
int solve() {
int ans = 0;
for (int i = 1; i<=n; ++i)
if (find(i)) ++ans;
return ans;
}
km算法
const int maxn = 1e2+10;
const int maxm = 30;
int match[maxn], lx[maxn], ly[maxn], s[maxn];
int visx[maxn], visy[maxn], pre[maxn];
int n, m, g[maxn][maxn];
void find(int k) {
int y = 0, p = 0; clr(pre, 0);
for (int i = 1; i<=m; ++i) s[i] = INF;
match[y] = k;
while(1) {
int x = match[y], d = INF; visy[y] = 1;
for (int i = 1; i<=m; ++i)
if (!visy[i]) {
if (s[i] > lx[x]+ly[i]-g[x][i])
s[i] = lx[x]+ly[i]-g[x][i], pre[i] = y;
if (d > s[i]) d = s[i], p = i;
}
for (int i = 0; i<=m; ++i) {
if (visy[i]) lx[match[i]] -= d, ly[i] += d;
else s[i] -= d;
}
y = p;
if (!match[y]) break;
}
while(y) match[y] = match[pre[y]], y = pre[y];
}
int km() {
clr(lx, 0x3f); clr(ly, 0); clr(match, 0);
for (int i = 1; i<=n; ++i)
clr(visy, 0), find(i);
int ans = 0;
for (int i = 1; i<=m; ++i) ans += g[match[i]][i];
return ans;
}