顺序大致按照luogu模板题排列
spfa判负环
#include<cstdio>
#include<queue>
using namespace std;
const int N = 2000+99;
const int M = 3000+99;
const int INF = 2147000047;
int n, m, T;
struct edge{
int y, nxt, val;
}e[M<<1];
int head[N], cnt;
void add_edge(int x, int y, int val) {
e[++cnt].y = y;
e[cnt].val = val;
e[cnt].nxt = head[x];
head[x] = cnt;
}
int vis[N], dis[N], num[N];
queue<int> q;
int spfa() {
for(int i = 1; i <= n; i++) vis[i] = num[i] = 0, dis[i] = INF;
dis[1] = 0;
q.push(1);
vis[1] = 1;
while(!q.empty()) {
int now = q.front(); q.pop();
vis[now] = 0;
for(int i = head[now]; i; i = e[i].nxt) if(dis[e[i].y] > dis[now]+e[i].val){
dis[e[i].y] = dis[now] + e[i].val;
if(!vis[e[i].y]) {
q.push(e[i].y); vis[e[i].y] = 1;
if(++num[e[i].y] > n) return false;
}
}
}
return true;
}
void init() {
cnt = 0;
for(int i = 1; i <= n; i++) head[i] = 0;
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
int x, y, val;
for(int i = 1; i <= m; i++) {
scanf("%d%d%d", &x, &y, &val);
add_edge(x, y, val);
if(val >= 0) add_edge(y, x, val);
}
if(!spfa()) printf("YE5\n");
else printf("N0\n");
init();
}
}st
#include<bits/stdc++.h>
using namespace std;
int n,m;
int st[100000+99][17];
int RMQ(int l, int r) {
int k = 0;
while(1<<(k+1) <= r-l+1) k++;
return max(st[l][k], st[r -(1<<k)+1][k]);
}
int main() {
scanf("%d%d",&n, &m);
for(int i = 1; i <= n; i++) scanf("%d",&st[i][0]);
for(int k = 1; (1<<k) <= n; k++)
for(int i = 1; i + (1<<k) - 1 <= n; i++)
st[i][k] = max(st[i][k-1], st[i+(1<<(k-1) )][k-1]);
int l,r;
for(int i = 1; i <= m; i++) {
scanf("%d%d", &l, &r);
printf("%d\n",RMQ(l,r));
}
}并查集
写太丑了，不发了
乘法逆元:线性求[1,n]的逆
#include<cstdio>
using namespace std;
int n, p;
int inv[3000000+9];
int main() {
scanf("%d%d",&n, &p);
inv[1] = 1; printf("1\n");
for(int i = 2; i <= n; i++) {
inv[i] = (long long)(p - p/i)*inv[p%i]%p;
printf("%d\n", inv[i]);
}
return 0;
}裴蜀定理
#include<cstdio>
#include<algorithm>
using namespace std;
int gcd(int x, int y) {
return !y ? x : gcd(y, x%y);
}
int n, ans;
int tmp;
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &tmp);
if(tmp < 0) tmp = -tmp;
ans = gcd(ans, tmp);
}
printf("%d", ans);
}欧拉定理:$ a^b\bmod m$
#include<cstdio>
#include <iostream>
#include<cmath>
using namespace std;
//#define int long long
int a, b, p;
int read(int m) {
char ch = getchar(); int x = 0;
int tag = 0;
while(ch<'0' || ch>'9') {ch = getchar();}
while(ch>='0' && ch<= '9') {
x = (x<<1)+(x<<3)+(ch^48);
if(x >= m) {
x %= m;//只需要最后加上phi(p)即可
tag = 1;
}
ch = getchar();
}
if(tag) x += m;//只有x>=phi时才x+=phi
return x;
}
int ksm(int a, int b, int p) {
int ans = 1;
while(b) {
if(b&1) ans = (long long)ans*a%p;
b >>= 1;
a = (long long)a*a%p;
}
return ans;//?
}
int el_phi(int x) {
int m = sqrt(x+0.5), ans = x;
for(int i = 2; i <= m; i++) if(x%i == 0) {
ans = ans/i*(i-1);
while(x%i == 0) x /= i;
}
if(x > 1) ans = ans/x*(x-1);
return ans;
}
signed main() {
// freopen("testdata (4).in", "r", stdin);
// freopen("testdata (4).out", "w", stdout);
scanf("%d%d", &a, &p);
a %= p;
b = read(el_phi(p));
printf("%d\n", ksm(a, b, p));
}线段树
//出错了请告知，感谢！
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100000+99;
struct tree{
long long add, sum, mx, set;
}tr[N<<2];
long long a[N];
void pushup(int o) {
tr[o].mx = max(tr[o<<1].mx, tr[o<<1|1].mx);
tr[o].sum = tr[o<<1].sum + tr[o<<1|1].sum;
}
void build(int o, int l, int r) {
tr[o].add = 0; tr[o].set = -1;
if(l == r) {
tr[o].sum = tr[o].mx = a[l];
return ;
}
int mid = (l+r)>>1;
build(o<<1, l, mid);
build(o<<1|1, mid+1, r);
pushup(o);
}
void pushdown(int o, int l, int r) {
int mid = (l+r)>>1;
if(tr[o].set != -1) {
tr[o<<1].set = tr[o<<1|1].set = tr[o<<1].mx = tr[o<<1|1].mx = tr[o].set;
tr[o<<1].add = tr[o<<1|1].add = 0;
tr[o<<1].sum = tr[o].set*(mid-l+1); tr[o<<1|1].sum = tr[o].set*(r-mid);
tr[o].set = -1;
}
if(tr[o].add) {
tr[o<<1].add += tr[o].add; tr[o<<1|1].add += tr[o].add;
tr[o<<1].sum += tr[o].add*(mid-l+1); tr[o<<1|1].sum += tr[o].add*(r-mid);
tr[o<<1].mx += tr[o].add; tr[o<<1|1].mx += tr[o].add;
tr[o].add = 0;
}
}
void optadd(int o, int l, int r, int ql, int qr, long long k) {
if(ql <= l && r <= qr) {
tr[o].sum += k*(r-l+1);
tr[o].add += k;
tr[o].mx += k;
return ;
}
int mid = (l+r)>>1;
pushdown(o, l, r);
if(ql <= mid) optadd(o<<1, l, mid, ql, qr, k);
if(mid < qr) optadd(o<<1|1, mid+1, r, ql, qr, k);
pushup(o);
}
void optset(int o, int l, int r, int ql, int qr, long long k) {
if(ql <= l && r <= qr) {
tr[o].set = tr[o].mx = k;
tr[o].add = 0;
tr[o].sum = k*(r-l+1);
return ;
}
int mid = (l+r)>>1;
pushdown(o, l, r);
if(ql <= mid) optset(o<<1, l, mid, ql, qr, k);
if(mid < qr) optset(o<<1|1, mid+1, r, ql, qr, k);
pushup(o);
}
long long query_sum(int o, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) return tr[o].sum;
int mid = (l+r)>>1;
pushdown(o, l, r);
long long ans = 0;
if(ql <= mid) ans += query_sum(o<<1, l, mid, ql, qr);
if(mid < qr) ans += query_sum(o<<1|1, mid+1, r, ql, qr);
return ans;
}
long long query_mx(int o, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) return tr[o].mx;
int mid = (l+r)>>1;
pushdown(o, l, r);
long long mx = -2147000047;
if(ql <= mid) mx = max(mx, query_mx(o<<1, l, mid, ql, qr));
if(mid < qr) mx = max(mx, query_mx(o<<1|1, mid+1, r, ql, qr));
return mx;
}
int n, m;
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
build(1, 1, n);
int cmd, x, y;
long long k;
for(int i = 1; i <= m; i++) {
scanf("%d", &cmd);
if(cmd == 1) {
scanf("%d%d%lld", &x, &y, &k);
optadd(1, 1, n, x, y, k);
}else {
scanf("%d%d", &x, &y);
printf("%lld\n", query_sum(1, 1, n, x, y));
}
}
}模板二不想打了2333...
树链剖分
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100000+99;
int n, m, s, p;
struct node{
int dep, size, fa, son, tp, in, out;
}a[N];
struct edge{
int y, nxt;
}e[N<<1];
int head[N], cnt;
void add_edge(int x, int y) {
e[++cnt].y = y;
e[cnt].nxt = head[x];
head[x] = cnt;
}
void dfs1(int x, int fa) {
a[x].dep = a[fa].dep + 1;
a[x].size = 1;
a[x].fa = fa;
for(int i = head[x]; i; i = e[i].nxt) if(e[i].y != fa) {
dfs1(e[i].y, x);
a[x].size += a[e[i].y].size;
a[x].son = a[a[x].son].size > a[e[i].y].size ? a[x].son : e[i].y;
}
}
int _clock, pos[N], b[N];
void dfs2(int x, int tp) {
a[x].tp = tp;
a[x].in = ++_clock;
pos[_clock] = b[x];
if(a[x].son) dfs2(a[x].son, tp);
for(int i = head[x]; i; i = e[i].nxt) if(e[i].y != a[x].fa && e[i].y != a[x].son)
dfs2(e[i].y, e[i].y);
a[x].out = _clock;
}
struct tree{
int sum, add;
}tr[N<<2];
void pushup(int o) {tr[o].sum = (tr[o<<1].sum + tr[o<<1|1].sum)%p;}
void build(int o, int l, int r) {
tr[o].add = 0;
if(l == r) {
tr[o].sum = pos[l]%p;
return ;
}
int mid = (l+r)>>1;
build(o<<1, l, mid);
build(o<<1|1, mid+1, r);
pushup(o);
}
void pushdown(int o, int l, int r) {
if(!tr[o].add) return ;
tr[o<<1].add = (tr[o<<1].add + tr[o].add)%p;
tr[o<<1|1].add = (tr[o<<1|1].add + tr[o].add)%p;
int mid = (l+r)>>1;
tr[o<<1].sum = (tr[o<<1].sum + tr[o].add*(mid-l+1) )%p;
tr[o<<1|1].sum = (tr[o<<1|1].sum + tr[o].add*(r-mid) )%p;
tr[o].add = 0;
}
void optadd(int o, int l, int r, int ql, int qr, int k) {
if(ql <= l && r <= qr) {
tr[o].add = (tr[o].add + k)%p;
tr[o].sum = (tr[o].sum + k*(r-l+1))%p;
return ;
}
int mid = (l+r)>>1;
pushdown(o, l, r);
if(ql <= mid) optadd(o<<1, l, mid, ql, qr, k);
if(mid < qr) optadd(o<<1|1, mid+1, r, ql, qr, k);
pushup(o);
}
int query(int o, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) return tr[o].sum;
int mid = (l+r)>>1;
pushdown(o, l, r);
int ans = 0;
if(ql <= mid) ans = (ans + query(o<<1, l, mid, ql, qr))%p;
if(mid < qr) ans = (ans + query(o<<1|1, mid+1, r, ql, qr))%p;
return ans;
}
void ttt_optadd(int x, int y, int k) {
while(a[x].tp != a[y].tp) {
if(a[a[x].tp].dep < a[a[y].tp].dep) swap(x, y);
optadd(1, 1, _clock, a[a[x].tp].in, a[x].in, k);
x = a[a[x].tp].fa;
}
if(a[x].dep > a[y].dep) swap(x, y);
optadd(1, 1, _clock, a[x].in, a[y].in, k);
}
int ttt_query(int x, int y) {
int ans = 0;
while(a[x].tp != a[y].tp) {
if(a[a[x].tp].dep < a[a[y].tp].dep) swap(x, y);
ans = (ans + query(1, 1, _clock, a[a[x].tp].in, a[x].in))%p;
x = a[a[x].tp].fa;
}
if(a[x].dep > a[y].dep) swap(x, y);
ans = (ans + query(1, 1, _clock, a[x].in, a[y].in))%p;
return ans;
}
int main() {
// freopen("testdata.in", "r", stdin);
scanf("%d%d%d%d", &n, &m, &s, &p);
for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
int x, y;
for(int i = 1; i < n; i++) {
scanf("%d%d", &x, &y);
add_edge(x, y);
add_edge(y, x);
}
dfs1(s, 0);
dfs2(s, s);
build(1, 1, _clock);
int cmd, z;
for(int i = 1; i <= m; i++) {
scanf("%d", &cmd);
if(cmd == 1) {
scanf("%d%d%d",&x, &y, &z);
ttt_optadd(x, y, z);
}else if(cmd == 2) {
scanf("%d%d",&x, &y);
printf("%d\n", ttt_query(x, y));
}else if(cmd == 3) {
scanf("%d%d",&x, &z);
optadd(1, 1, _clock, a[x].in, a[x].out, z);
}else {
scanf("%d", &x);
printf("%d\n", query(1, 1, _clock, a[x].in, a[x].out));
}
}
}树状数组
复制代码 1 #include<cstdio>
#define lowbit(x) (x & -x)
#define MAX 11111
int n,m;
int t[MAX],a[MAX];//t为树状数组
void add(int x, int k) {//单点修改（向树上走）
for(int i = x; i <= n; i += lowbit(i)) {
t[i] += k;
}
}
int query(int x) {//区间查询（在树下向前推进）//求的是前缀和
int sum = 0;
for(int i = x; i; i -= lowbit(i)) {
sum += t[i];
}
return sum;
}
void lineplus(const int & l , const int &r, const int &k) {
add(l , k);
add(r + 1 , -k);
} //区间修改 & 单点查询 //将区间l~~r的值加k , 要在差分数组中做 ，此时a为差分数组
int main() {
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) {
scanf("%d",&a[i]);
add(i , a[i]);
//add(i, a[i] - a[i-1]) //差分
}
int x,y;
for(int i = 1; i <= m; i++) {
scanf("%d%d",&x,&y);
printf("%d\n",query(y) - query(x - 1));//求的是区间和（x~~y)
}
/* int k;
scanf("%d%d%d",&x,&y,&k);
lineplus(x,y,k);//x~~y区间加k
scanf("%d"，&x)
printf("%d",queue(x) );//查询单点x //差分得出的t的前缀和
*/
}luogu乘法逆元2(应该不算模板)
#include<cstdio>
using namespace std;//5000009
#pragma GCC optimize(3,"Ofast","inline")
inline int read() {
char ch = getchar(); int x = 0;
while(ch<'0' || ch>'9') {ch = getchar();}
while(ch>='0' && ch<='9') {x = (x<<1)+(x<<3)+(ch^48); ch = getchar();}
return x;
}
int n, p, k;
int qzj[5000009], hzj[5000009], a[5000009];
void exgcd(int a, int b, int& x, int& y) {
if(!b) {
x = 1;
y = 0;
}
else exgcd(b, a%b, y, x), y -= (a/b)*x;
}
int main() {
// freopen("testdata (4).in", "r", stdin);
// freopen("testdata (4).out", "w", stdout);
n = read(), p = read(), k = read();
qzj[0] = 1;//27行，34行有用
for(int i = 1; i <= n; i++) {
a[i] = read();
qzj[i] = 1ll*qzj[i-1]*a[i]%p;
}
int y;
exgcd(qzj[n], p, hzj[n+1], y);
for(int i = n; i >= 1; i--) hzj[i] = 1ll*hzj[i+1]*a[i]%p;//hzj[n] = a_{1}^{-1}*...*a_{n-1}^{-1}
int ans = 0, tk = k;//tk累乘
for(int i = 1; i <= n; i++) {
ans = (ans+(qzj[i-1]*1ll*hzj[i+1]%p)*tk)%p;//里面的会溢出！！
tk = tk*1ll*k%p;
}
if(ans < 0) ans = (ans+p)%p;//ans已经是p以内的了
printf("%d\n", ans);
return 0;
}线性筛素数
欧拉筛：
#include<cstdio>
using namespace std;
const int N = 10000000+9;
int not_prime[N] = {1, 1};
int prime[N], tot;
int n, m;
void L_S(){
for(int i = 2; i <= n; i++) {
if(!not_prime[i])
prime[++tot] = i;
for(int j = 1; j <= tot && i*prime[j] <= n; j++) {
not_prime[i*prime[j]] = 1;
if(!( i%prime[j]) ) break;
}
}
}
int main() {
scanf("%d%d", &n, &m);
L_S();
int x;
for(int i = 1; i <= m; i++) {
scanf("%d", &x);
if(not_prime[x]) printf("No\n");
else printf("Yes\n");
}
}埃筛：
#include<cstdio>
#include<cmath>
using namespace std;
#define MAXN 10000000+99
int n,m;
int isp[MAXN];
int main() {
scanf("%d%d",&n,&m);
// for(int i = 2; i <= n; i++)
// for(int j = i*i; j <= n; j+=i) isp[j] = 1;
int tmp = sqrt(n+0.5);//说是解决精度问题，不懂...
for(int i = 2; i <= tmp; i++) if(!isp[i]) //i*i<n //1看题目考虑
for(int j = i*i; j <= n; j+=i) {//没有必要从j*2, 因为在i=2的时候已经被筛掉了
isp[j] = 1;
}
int x;
for(int i = 1; i <= m; i++) {
scanf("%d",&x);
if(x == 1) {
printf("No\n");
continue;
}
if(isp[x] == 0) printf("Yes\n");
else printf("No\n");
}
}求欧拉函数
分解质因数做法
int euler_phi(int n) {
int m = (int)sqrt(n+0.5);//（还是说解决精度问题//这里都行吧
int ans = n;
for(int i = 2; i <= m; i++) if(n%i == 0) {
ans = ans / i * (i-1);
while(n%i == 0) n /= i;
}
if(n > 1) ans = ans / n * (n-1);//还要看n有没有大于sqrt(n)的质因数
}线性筛法
int not_prime[N] = {1, 1};
int prime[N], tot;
int n, m;
int phi[N];
void L_S(){
for(int i = 2; i <= n; i++) {
if(!not_prime[i]) {
prime[++tot] = i;
phi[i] = i - 1;//基本性质2：费马小定理
}
for(int j = 1; j <= tot && i*prime[j] <= n; j++) {
not_prime[i*prime[j]] = 1;
if(i % prime[j] == 0) {//如果i是prime的倍数->i与prime[j]不互质
phi[i*prime[j]] = phi[i]*prime[j];
break;
}
phi[i*prime[j]] = phi[i]*(prime[j]-1);//互质的时候，左边=phi[i]*phi[prime[j]],即=右边的
}
}
}最小生成树
不会prim.....
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXM = 200000+9;
const int MAXN = 5000+9;
int n,m,ans;
struct node{
int x,y,val;
}e[MAXM];
bool cmp(node x, node xx) {
return x.val < xx.val ;
}
int fa[MAXN];
int dad(int x) {
if(x == fa[x] ) return fa[x];
else return fa[x] = dad(fa[x] );
}
int main() {
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 1; i <= m; i++) {
scanf("%d%d%d",&e[i].x ,&e[i].y ,&e[i].val ) ;
}
sort(e+1, e+1+m, cmp);
int x,y;
for(int i = 1; i <= m; i++) {
x = dad(e[i].x) , y = dad(e[i].y) ;
if(x != y) {
fa[x] = fa[y];
ans += e[i].val ;
}
}
printf("%d",ans);
}有理数取余: 快读中加取模
//也可以用exgcd之类的
#include<cstdio>
#include<algorithm>
using namespace std;
const int MOD = 19260817;
int read() {
char ch = getchar(); int x = 0, f = 1;
while(ch<'0' || ch>'9') {if(ch=='-') f = -1; ch = getchar();}
while(ch>='0' && ch<='9') {x = ((x<<1)+(x<<3)+(ch^48))%MOD; ch = getchar();}
return x*f;
}
int a, b;
int qsm(int a, int b, int p) {
int ans = 1;
while(b) {
if(b & 1) ans = (long long)ans*a%p;
b >>= 1;
a = (long long)a*a%p;
}
return ans%p;
}
int main() {
a = read(), b = read();
if(b == 0) {
printf("Angry!\n");
return 0;
}
printf("%lld\n", (long long)a*qsm(b, MOD-2, MOD)%MOD);
}快速幂||取余运算
#include<cstdio>
using namespace std;
#define ll long long
ll a, b, p;
ll ksm(ll a, ll b, ll p) {
if(a == 0) return 0;
ll res = 1;
while(b) {
if(b&1) res = (res*a)%p;
b >>= 1;
a = (a*a)%p;
}
return res%p;
}
int main() {
scanf("%lld%lld%lld", &a, &b, &p);
printf("%lld^%lld mod %lld=%lld\n", a, b, p, ksm(a, b, p));
return 0;
} 建议用上面那个....
下面是刘汝佳书里的
#include<cstdio>
using namespace std;
long long pow_mod(long long a, long long b, long long p) {
if(!b) return 1;
long long x = pow_mod(a, b/2, p);
long long ans = (x%p)*(x%p)%p;
if(b%2) ans = ans*a%p;
return ans;
}
long long a, b, p;
int main() {
scanf("%lld%lld%lld",&a, &b,&p);
long long ans = pow_mod(a, b, p);
if(b == 0 && p == 1) ans = 0;
printf("%lld^%lld mod %lld=%lld\n",a, b, p, ans);
}最长公共子序列
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100000+9;
const int MAX = N;
int a[N], b[N], map[MAX];
int n;
int f[N];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]), map[a[i]] = i;
for(int j = 1; j <= n; j++) scanf("%d", &b[j]), a[j] = map[b[j]], f[j] = MAX;
int len = 1;
f[1] = a[1];
for(int i = 2; i <= n; i++) {
if(a[i] > f[len]) f[++len] = a[i];
else {
int l = 1, r = len, mid;
while(l < r) {
mid = (l+r)>>1;
if(f[mid] >= a[i]) r = mid;
else l = mid + 1;
}
f[l] = min(f[l], a[i]);
}
}
printf("%d", len);
return 0;
}单源最短路
dijkstra
#include<cstdio>
#include<queue>
using namespace std;
const int N = 100000+9;
const int M = 200000+9;
const int INF = 2147000047;
int n, m, S;
int dis[N], vis[N];
struct node{
int id, dis;
node(int id, int dis) : id(id), dis(dis) {}
bool operator < (const node& xxx) const {
return dis > xxx.dis;
}
};
priority_queue <node> q;
struct edge{
int y, nxt, val;
}e[M];
int head[N], cnt;
void add_edge(int x, int y, int val) {
e[++cnt].y = y;
e[cnt].val = val;
e[cnt].nxt = head[x];
head[x] = cnt;
}
void dijkstra() {
for(int i = 1; i <= n; i++) dis[i] = INF;
dis[S] = 0;
q.push(node(S, dis[S]));
while(!q.empty()) {
node tmp = q.top(); q.pop();
int now = tmp.id;
if(vis[now]) continue;
vis[now] = 1;
for(int i = head[now]; i; i = e[i].nxt) {
if(dis[e[i].y] > tmp.dis + e[i].val) {
dis[e[i].y] = tmp.dis + e[i].val;
q.push(node(e[i].y, dis[e[i].y]));
}
}
}
}
int main() {
scanf("%d%d%d",&n, &m, &S);
int x, y, val;
for(int i = 1; i <= m; i++) {
scanf("%d%d%d",&x,&y,&val);
add_edge(x, y, val);
}
dijkstra();
for(int i = 1; i <= n; i++) printf("%d ", dis[i]);
}spfa
高精度
#include<cstdio>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 100000;
int a[N], b[N], c[N], lena, lenb, lenc;
string x, y;
void jinwei() {
for(int i = 1; i <= lenc; i++) if(c[i] >= 10) {
c[i+1] += c[i]/10;
c[i] %= 10;
if(i == lenc) lenc++;
}
while(lenc && c[lenc] == 0) lenc--;//保证lenc不为负
}
int main() {
cin>>x>>y;
lena = x.length(), lenb = y.length();
/*if(lena < lenb || (lena==lenb && x < y)) {//减法时使用
swap(x, y);
swap(lena, lenb);//保证a>=b
printf("-");
}*/
for(int i = 0; i < lena; i++) a[lena-i] = x[i]-'0';
for(int i = 0; i < lenb; i++) b[lenb-i] = y[i]-'0';
// for(int i = lena; i >= 1; i--) printf("%d", a[i]);
// printf("\n");
// for(int i = lenb; i >= 1; i--) printf("%d", b[i]);
// printf("\n");
//高精加: 非负数相加
/* lenc = max(lena, lenb);
for(int i = 1; i <= lenc; i++) c[i] = a[i]+b[i];
jinwei();*/
//高精减
/* for(int i = 1, j = 1; i <= lena || j <= lenb; i++, j++) {
if(a[i] < b[i]) {a[i] += 10; --a[i+1];}
c[i] = a[i] - b[i];
}
lenc = lena;
while(c[lenc] == 0 && lenc) lenc--;//注意使lenc不为负 */
//高精乘
/* for(int i = 1; i <= lena; i++)
for(int j = 1; j <= lenb; j++)
c[i+j-1] += a[i]*b[j];
lenc = lena+lenb-1;
jinwei();*/
if(lenc == 0) printf("0");
else for(int i = lenc; i > 0; i--) printf("%d", c[i]);
return 0;
}//高精除低精
/* for(int i = lena; i >= 1; i--) {
a[i-1] += (a[i]%k)*10;
a[i] = a[i]/k;
}
while(a[lena] == 0 && lena) lena--;
if(lena == 0) printf("0");
else for(int i = lena; i >= 1; i--) printf("%d", a[i]);*/
//高精%低精
/* int yushu = 0;
for(int i = lena; i >= 1; i--) {
yushu = yushu*10+a[i];
yushu %= k;
}
printf("%d", yushu);*/LCA
树链剖分做法
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 500000+99;
const int MAXM = MAXN<<1;
int n,m,s;
int cnt, head[MAXN];
struct node{
int tp, size, fa, son, deep, in/*, out*/;
//top， size，它爸， 重儿子 , 深度 , dfs序
}a[MAXN];
int clock;
struct seg{
int y,next;
}e[MAXM];
void add_edge(int x, int y) {
e[++cnt].y = y;
e[cnt].next = head[x];
head[x] = cnt;
}
void dfs1(int x, int fa) {//先找到重儿子
a[x].deep = a[fa].deep + 1;
a[x].size = 1;//包括自己
a[x].fa = fa;
for(int i = head[x]; i; i=e[i].next )
if(e[i].y != fa) {
dfs1(e[i].y , x);
a[x].size += a[e[i].y ].size ;
a[x].son = a[a[x].son ].size > a[e[i].y].size ? a[x].son : e[i].y ;
}
}
void dfs2(int x, int tp) {//再找top
// a[x].in = ++clock;
a[x].tp = tp;
if(a[x].son ) dfs2(a[x].son , tp);//如果有重儿子要先dfs重儿子（叶子节点木有？？
for(int i = head[x]; i; i = e[i].next )
if(e[i].y != a[x].son && e[i].y != a[x].fa ) //注意判断是不是重儿子（没必要dfs）和祖先（不能dfs）
dfs2(e[i].y , e[i].y );
}
int lca(int l, int r) {
while(a[l].tp != a[r].tp ) {
if(a[a[l].tp].deep < a[a[r].tp ].deep ) swap(l, r);
l = a[a[l].tp].fa ;
}
return a[l].deep < a[r].deep ? l : r;
}
int main() {
scanf("%d%d%d",&n,&m,&s);
int x,y;
for(int i = 1; i < n; i++) {
scanf("%d%d",&x, &y);
add_edge(x, y);
add_edge(y, x);
}
dfs1(s, s);
dfs2(s, s);
for(int i = 1; i <= m; i++) {
scanf("%d%d",&x, &y);
printf("%d\n",lca(x, y));
}
}背包
网上有很多，麻烦同学们自己找