锐客网

  1. 首页 > it技术 > >

ACM模板

1、快速读入

ll read(){ ll ret = 0; bool fl = 0; char ch = getchar(); while(ch < '0' || ch > '9') {if(ch == '-') fl = 1; ch = getchar(); } while(ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = getchar(); return fl ? -ret : ret; }

2、java大整数
import java.util.*; //import com.sun.xml.internal.ws.api.server.AbstractServerAsyncTransport; import java.math.*; public class Main{ public static void main(String args[]){ Scanner cin = new Scanner(System.in); String str1, str2; String a; BigDecimal A, B; double b; while(cin.hasNext()) { str1 = cin.next(); if(str1.charAt(0) == '1') { System.out.println(str1 + " [8] = " + "1" + " [10]"); continue; } str2 = str1.substring(2, str1.length()); //System.out.println(str2); BigInteger c = new BigInteger(str2, 8); a = c.toString(10); A = new BigDecimal(a); for(int i = 0; i < str2.length(); i++) { A = A.divide(BigDecimal.valueOf(8)); } System.out.println(str1 + " [8] = " + A + " [10]"); } } }

3、线性筛
void Prime(){ for(int i = 2; i <= n; i++) isprime[i] = 1; for(int i = 2; i <= n; i++){ if(isprime[i]) prime[++cnt] = i, phi[i] = i - 1; for(int j = 1; j <= cnt && prime[j] * i <= n; j++){ isprime[prime[j] * i] = 0; if(i % prime[j] == 0){ phi[i * prime[j]] = phi[i] * prime[j]; break; } else phi[i * prime[j]] = phi[i] * (prime[j] - 1); } } }

4、扩展欧几里得
void exgcd(ll a, ll b, ll &d, ll &x, ll &y) { if(!b) {d = a; x = 1; y = 0; return; } exgcd(b, a % b, d, y, x); y -= x * (a / b); }

5、中国剩余定理 （普通）
……留坑
（扩展）
ll excrt() { ll M = m[1], R = r[1], d, x, y; for(int i = 2; i <= n; i++) { exgcd(M, m[i], d, x, y); if((R - r[i]) % d) return -1; x = (R - r[i]) / d * x % m[i]; R -= M * x; M = M * m[i] / d; R %= M; } return (R % M + M) % M; }

6、BM算法
#include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i,a,n) for (int i=a; i=a; i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector VI; typedef long long ll; typedef pair PII; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1; a%=mod; for(; b; b>>=1){if(b&1)res=res*a%mod; a=a*a%mod; }return res; } // headint _,n; namespace linear_seq { const int N=100010; ll res[N],base[N],_c[N],_md[N]; vector Md; void mul(ll *a,ll *b,int k) { rep(i,0,k+k) _c[i]=0; rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod; for (int i=k+k-1; i>=k; i--) if (_c[i]) rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod; rep(i,0,k) a[i]=_c[i]; } int solve(ll n,VI a,VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+... //printf("%d\n",SZ(b)); ll ans=0,pnt=0; int k=SZ(a); // assert(SZ(a)==SZ(b)); rep(i,0,k) _md[k-1-i]=-a[i]; _md[k]=1; Md.clear(); rep(i,0,k) if (_md[i]!=0) Md.push_back(i); rep(i,0,k) res[i]=base[i]=0; res[0]=1; while ((1ll<=0; p--) { mul(res,res,k); if ((n>>p)&1) { for (int i=k-1; i>=0; i--) res[i+1]=res[i]; res[0]=0; rep(j,0,SZ(Md)) res[Md[j]]= (res[Md[j]]-res[k]*_md[Md[j]])%mod; } } rep(i,0,k) ans=(ans+res[i]*b[i])%mod; if (ans<0) ans+=mod; return ans; } VI BM(VI s) { VI C(1,1),B(1,1); int L=0,m=1,b=1; rep(n,0,SZ(s)) { ll d=0; rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod; if (d==0) ++m; else if (2*L<=n) { VI T=C; ll c=mod-d*powmod(b,mod-2)%mod; while (SZ(C) num; int p[100] ={ 31, 197, 1255, 7997, 50959, 324725, }; for(int i=0; i<6; i++) num.push_back(p[i]); linear_seq::init(num); int T; scanf("%d",&T); while(T--) { ll n; scanf("%lld",&n); n--; printf("%d\n",linear_seq::gao(num,n-1)); } return 0; }

7、莫比乌斯反演
#include #include #define N 100005 #define ll long long using namespace std; bool p[N]={1,1}; int prime[N],mu[N],sum[N],cnt,t,a,b,c,d,k; void getmu(){ mu[1]=1; cnt=0; for(int i = 2; i < N; i++){ if(!p[i]){ prime[++cnt]=i; mu[i]=-1; } for(int j = 1; j <= cnt && i * prime[j] < N; j++){ p[i * prime[j]] = 1; if(i % prime[j] == 0){ mu[i * prime[j]] = 0; break; } mu[i * prime[j]] = -mu[i]; } } for(int i = 1; i < N; i++) sum[i] = sum[i-1] + mu[i]; //for(int i=1; i<100; i++) printf("%d\n",mu[i]); } ll getans(int n,int m){ ll ret = 0; if(n > m) swap(n, m); for(int i = 1, last; i <= n; i = last + 1){ last = min(n / (n / i), m / (m / i)); ret += (ll)(n / i) * (ll)(m / i)*(ll)(sum[last] - sum[i-1]); } return ret; } int main(){ scanf("%d", &t); getmu(); for(int i = 1; i <= t; i++){ scanf("%d%d%d%d%d", &a, &b, &c, &d, &k); if(k == 0) printf("Case %d: %lld\n", i, 0); else printf("Case %d: %lld\n", i, getans(b / k, d / k)); } return 0; }

8、splay
struct SPLAY{ int val[N], sz[N], fa[N], ch[N][2], cnt[N], root, tot; void update(int x){ sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; } void debug(){ for(int i = 1; i <= 10; i++) printf("%d %d %d %d %d\n", i, ch[i][0], ch[i][1], sz[i], cnt[i]); } void Rotate(int x){ int y = fa[x], z = fa[y]; int k = (ch[y][1] == x); ch[z][ch[z][1] == y] = x; fa[x] = z; ch[y][k] = ch[x][k ^ 1]; fa[ch[y][k]] = y; ch[x][k ^ 1] = y; fa[y] = x; update(y); update(x); } void splay(int x, int pos){ while(fa[x] != pos){ int y = fa[x], z = fa[y]; if(z != pos) ((ch[z][0] == y) ^ (ch[y][0] == x)) ? Rotate(x) : Rotate(y); Rotate(x); } if(pos == 0) root = x; update(x); } void Insert(int x){ int u = root, ff = 0; while(u && val[u] != x){ ff = u; u = ch[u][x > val[u]]; } if(u) {cnt[u]++; splay(u, 0); return; } u = ++tot; if(ff) ch[ff][x > val[ff]] = u; ch[u][0] = ch[u][1] = 0; fa[u] = ff; val[u] = x; cnt[u] = 1; sz[u] = 1; splay(u, 0); } void Find(int x){ int u = root; if(!u) return; while(ch[u][x > val[u]] && x != val[u]) u = ch[u][x > val[u]]; splay(u, 0); //printf("%d\n", u); } int Next(int x, int f){ Find(x); //debug(); int u = root; if(val[u] > x && f) return u; if(val[u] < x && !f) return u; u = ch[u][f]; // printf("%d\n", u); while(ch[u][f ^ 1]) u = ch[u][f ^ 1]; return u; } void Delete(int x){ int last = Next(x, 0); int next = Next(x, 1); splay(last, 0); splay(next, last); //debug(); sz[next]--; sz[last]--; int del = ch[next][0]; if(cnt[del] > 1){ sz[del]--; cnt[del]--; splay(del, 0); } else ch[next][0] = 0; //debug(); } int Rank(int x){ Find(x); return sz[ch[root][0]]; } int kth(int k){ k++; int u = root, now = 0; while(1){ if(ch[u][0] && k <= sz[ch[u][0]]) u=ch[u][0]; else{ int tmp = sz[ch[u][0]] + cnt[u]; if(k <= tmp) return val[u]; k -= tmp; u = ch[u][1]; } } } }; SPLAY Splay;

9、prim 留坑
10、dijkstra
void dijkstra(int s, int o, int k){ for(int i = 1; i <= n; i++) dis[i][k] = 1e18; memset(vis, 0, sizeof(vis)); dis[s][k] = 0; q.push(mp(0, s)); while(!q.empty()){ ll d = q.top().fi; int x = q.top().se; q.pop(); if(vis[x]) continue; vis[x] = 1; for(int t = idx[x]; t; t = edge[t].nxt){ E e = edge[t]; if(d + e.w < dis[e.to][k]){ dis[e.to][k] = d + e.w; q.push(mp(dis[e.to][k], e.to)); } } } }

11、spfa
void SPFA(){ q.push(s); vis[s]=1; memset(dis,127,sizeof(dis)); dis[s]=0; while(!q.empty()){ int x=q.front(); q.pop(); for(int t=idx[x]; t; t=edge[t].nxt){ E e=edge[t]; if(dis[e.to]>dis[x]+e.w){ dis[e.to]=dis[x]+e.w; if(!vis[e.to]){ vis[e.to]=1; q.push(e.to); } } } vis[x]=0; } }

12、线段树
#include #define ll long long #define N 100005 * 4 #define mid ((l + r) >> 1) #define L k << 1, l, mid #define R k << 1 | 1, mid + 1, r #define O k, l, r using namespace std; ll sum[N],tag[N],a[N]; int n,m; ll read(){ char ch; ll x = 0; bool f = 0; for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = 1; for(; '0' <= ch && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; if(f) return -x; return x; } void paint(int k, int l, int r, ll z){ sum[k] += z * (r - l + 1); tag[k] += z; } void pushup(int k){ sum[k] = sum[k << 1] + sum[k << 1 | 1]; } void pushdown(int k, int l, int r){ paint(L, tag[k]); paint(R, tag[k]); tag[k] = 0; } void build(int k, int l, int r){ if(l == r){ sum[k] = a[l]; tag[k] = 0; return; } build(L); build(R); pushup(k); return; } void add(int k, int l, int r, int x, int y, ll z){ if(x <= l && r <= y){ paint(O, z); return; } pushdown(O); if(x <= mid) add(L, x, y, z); if(mid + 1 <= y) add(R, x, y ,z); pushup(k); return; } ll query(int k, int l, int r, int x, int y){ if(x <= l && r <= y) return sum[k]; ll ans = 0; pushdown(O); if(x <= mid) ans += query(L, x, y); if(mid + 1 <= y) ans += query(R, x, y); pushup(k); return ans; } int main(){ while(scanf("%d%d", &n, &m) == 2){ for(int i = 1; i <= n * 4; i++) sum[i] = tag[i] = 0; for(int i = 1; i <= n; i++) a[i] = read(); build(1, 1, n); for(int i = 1, x, y, z; i <= m; i++){ char c = getchar(); if(c == 'C'){ x = read(); y = read(); z = read(); add(1, 1, n, x, y, z); } if(c == 'Q'){ x = read(); y = read(); printf("%lld\n", query(1, 1, n, x, y)); } } } return 0; }

13、kmp
void getnext(){ memset(f, 0, sizeof(f)); f[1] = 0; int j = 0; num[1] = 1; for(int i = 2; i <= la; i++){ while(j && s1[i] != s1[j + 1]) j = f[j]; if(s1[i] == s1[j + 1]) j++; f[i] = j; num[i] = num[f[i]] + 1; } //for(int i = 1; i <= la; i++) printf("%d : %lld ", i, num[i]); puts(""); } void kmp(){int j = 0; for(int i = 2; i <= la; i++){ while(j && s1[i] != s1[j + 1]) j = f[j]; if(s1[i] == s1[j + 1]) j++; while(j * 2 > i) j = f[j]; //printf("%d\n", j); ans = ans * (num[j] + 1) % Mo; }//puts(""); }

14、manacher
void manacher(){ ans = 0; for(int i = 1; i <= l + l + 1; i++) if(i & 1) s[i] = '%'; else s[i] = s1[i / 2]; f[1] = 1; R = 1; pos = 1; l = l + l + 1; for(int i = 1; i <= l; i++){ if(i <= R) f[i] = min(f[pos * 2 - i], R - i); else f[i] = 1; while(i - f[i] >= 1 && i + f[i] <= l && s[i - f[i]] == s[i + f[i]]) f[i]++; if(i + f[i] > R) {pos = i; R = i + f[i]; } } }

15、set
#include #include #include using namespace std; const int N = 200005; const int inf = 0x7fffffff; struct Node{ int id, val; }; bool operator < (const Node a, const Node b){ return a.val < b.val; } set s; int q, x, y; char opt; int main(){ while(scanf("%d", &opt) && opt){ if(opt == 1){ scanf("%d%d", &x, &y); s.insert((Node){x, y}); } if(opt == 2){ if(s.empty()) {printf("0\n"); continue; } printf("%d\n", (*(--s.end())).id); s.erase(--s.end()); } if(opt == 3){ if(s.empty()) {printf("0\n"); continue; } printf("%d\n", (*s.begin()).id); s.erase(s.begin()); } } return 0; }

16、km算法
#include #include #include using namespace std; const int N = 20005; const int M = 100005; struct E {int to, nxt; }edge[M]; bool vis[N]; int left[N], idx[N], tot, n, m, x, y, ans; struct A{int x, y; } a[N]; bool operator < (A l, A r){return l.x < r.x; } void addedge(int from, int to){ from++; to++; //printf("%d %d\n", from, to); edge[++tot].to = to; edge[tot].nxt = idx[from]; idx[from] = tot; } bool dfs(int x){ for(int t = idx[x]; t; t = edge[t].nxt){ E e = edge[t]; if(vis[e.to]) continue; vis[e.to] = 1; if(!left[e.to] || dfs(left[e.to])){ left[e.to] = x; return 1; } }return 0; } int main() { scanf("%d", &n); m = n; for(int i = 0; i < n; i++){ scanf("%d", &x); if(x > n / 2) {printf("No Answer\n"); return 0; } x = n - x; if(i + x < n) addedge(i, i + x + n); x = n - x; if(i + x < n) addedge(i, i + x + n); if(i - x >= 0) addedge(i, i - x + n); x = n - x; if(i - x >= 0) addedge(i, i - x + n); } for(int i = n; i >= 1; i--){ memset(vis, 0, sizeof(vis)); ans += dfs(i); } //printf("%d\n", ans); //for(int i = 1; i <= m; i++) printf("%d %d\n", left[i + n], i); if(ans != n) {printf("No Answer\n"); return 0; } for(int i = 1; i <= m; i++) a[i].x = left[i + n], a[i].y = i; sort(a + 1, a + 1 + m); for(int i = 1; i < m; i++) printf("%d ", a[i].y - 1); printf("%d\n", a[m].y - 1); return 0; }

17、dinic
void init(){ memset(idx, 0, sizeof(idx)); memset(a, 0, sizeof(a)); memset(cur, 0, sizeof(0)); tot = 2; S = 1; T = n; for(int i=1, x, y, w; i <= m; i++) scanf("%d%d%d", &x, &y, &w), addedge(x, y, w, 0), addedge(y, x, 0, 0); } bool BFS(){ memset(vis, 0, sizeof(vis)); memset(dis, 0, sizeof(dis)); Q.push(S); vis[S] = 1; while(!Q.empty()){ int x = Q.front(); Q.pop(); for(int t = idx[x]; t; t = edge[t].nxt){ E& e = edge[t]; if(!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; Q.push(e.to); dis[e.to] = dis[x] + 1; } } } return vis[T]; } int DFS(int x, int a){ int flow=0, f; if(x == T || a == 0) return a; for(int& i = cur[x]; i; i = edge[i].nxt){ E& e = edge[i]; if(dis[x] + 1 == dis[e.to]){ f=DFS(e.to, min(a,e.cap - e.flow)); if(f > 0){ edge[i].flow += f; edge[i ^ 1].flow -= f; flow += f; a -= f; if(!a) break; } } } return flow; } int dinic(){ int flow=0; while(BFS()){ for(int i = 0; i <= n; i++) cur[i] = idx[i]; flow += DFS(S, INF); } return flow; }

18、费用流
bool SPFA(){ Q.push(S); memset(vis, 0, sizeof(vis)); memset(dis, 127, sizeof(dis)); memset(last, 255, sizeof(last)); memset(cnt, 0, sizeof(cnt)); vis[S] = 1; dis[S] = 0; while(!Q.empty()){ int x = Q.front(); Q.pop(); vis[x]=0; for(int t = idx[x]; t; t = edge[t].nxt){ E& e = edge[t]; if(e.cap <= e.flow) continue; if(dis[e.to] > dis[x] + e.cost){ last[e.to] = x; edges[e.to] = t; dis[e.to] = dis[x] + e.cost; if(!vis[e.to]) { vis[e.to] = 1; Q.push(e.to); } } } } return (dis[T] != dis[0]); } void mcmf(){ int flow = 0; int cost = 0; while(SPFA()){ //printf("%d\n", flow); int u = T, f = INF; while(last[u] != -1){ f = min(edge[edges[u]].cap - edge[edges[u]].flow, f); u = last[u]; } u = T; while(last[u] != -1){ edge[edges[u]].flow += f; edge[edges[u] ^ 1].flow -= f; u = last[u]; } //printf("***%d",f); flow += f; cost += dis[T] * f; } printf("%d\n", cost); }

19、tarjan
void tarjan(int x){ dfn[x] = low[x] = ++Time; S.push(x); ins[x] = 1; for(int t = idx[x] ; t; t = edge[t].nxt){ E e = edge[t]; if(!dfn[e.to]){ tarjan(e.to); low[x] = min(low[x], low[e.to]); } else if(ins[e.to]) low[x] = min(low[x], dfn[e.to]); } int now; if(dfn[x] == low[x]){ cnt++; do{ now = S.top(); S.pop(); ins[now] = 0; col[now] = cnt; }while(now != x); } }

20、割点割边双联通
void dfs(int x,int fa){ int child = 0; dfn[x] = low[x] = ++Time; for(int t = idx[x]; t; t = edge[t].nxt){ E e = edge[t]; E ee = (E) {x, e.to}; if(!dfn[e.to]){ S.push(ee); child++; dfs(e.to, x); low[x] = min(low[e.to], low[x]); if(low[e.to] >= dfn[x]){ iscut[x] = 1; bcc_cnt++; bcc[bcc_cnt].clear(); for(; ; ){ E now = S.top(); S.pop(); if(bccno[now.u] != bcc_cnt) { bcc[bcc_cnt].push_back(now.u); bccno[now.u] = bcc_cnt; } if(bccno[now.v] != bcc_cnt) { bcc[bcc_cnt].push_back(now.v); bccno[now.v] = bcc_cnt; } if(now.u == x && now.v == e.to) break; }} //if(low[e.to] > dfn[x]) 割边} else if(dfn[e.to] < dfn[x] && e.to != fa) { S.push(ee); low[x] = min(low[x], dfn[e.to]); } } if(fa == -1 && child == 1) iscut[x] = 0; }

21、欧拉回路方案
void dfs(int x) { a[x] = 1; //printf("%d\n", x); for(int &t = idx[x]; t; t = edge[t].nxt) { E e = edge[t]; if(!vis[t / 2]) { vis[t / 2] = 1; dfs(e.to); ans.push_back(e.id); } } }

22、
struct AC{ queue q; int ch[N][27]; int f[N], last[N], cnt[N]; int ans; int idx(char c){return c - 'a' + 1; } int size, now; void init() { memset(f, 0, sizeof(f)); memset(last, 0, sizeof(last)); memset(cnt, 0, sizeof(cnt)); ans = 0; size = 0; memset(ch, 0, sizeof(ch)); } void insert(char* ss){ now = 0; for(int i=0; ss[i]; i++){ if(!ch[now][idx(ss[i])]) ch[now][idx(ss[i])] = ++size; now = ch[now][idx(ss[i])]; } cnt[now]++; } void getfail(){ for(int i = 1; i <= 26; i++) if(ch[0][i]) q.push(ch[0][i]); while(!q.empty()){ int r = q.front(); q.pop(); for(int i = 1; i <= 26; i++){ int u = ch[r][i]; if(!u) {ch[r][i] = ch[f[r]][i]; continue; } q.push(u); int v = f[r]; while(v && !ch[v][i]) v = f[v]; f[u] = ch[v][i]; last[u] = cnt[f[u]] ? f[u] : last[f[u]]; } } } void calc(int x){ if(x == 0) return; ans += cnt[x]; cnt[x] = 0; calc(last[x]); } void find(char *s){ int j=0; for(int i = 0; s[i]; i++){ int c = idx(s[i]); j = ch[j][c]; if(cnt[j]) calc(j); else calc(last[j]); } } };

23、计算几何
int sgn (double x) { if(fabs(x) < eps) return 0; return x < 0 ? -1 : 1; } double dist (double x, double y) { return sqrt(x *x + y * y); } struct Point { double x, y; Point(){} Point(double _x, double _y) { x = _x; y = _y; } void input() { scanf("%lf%lf", &x, &y); } void output() { printf("%lf %lf\n", x, y); } bool operator == (const Point &b) { return sgn(x - b.x) == 0 && sgn(y - b.y) == 0; } bool operator < (const Point &b) { return sgn(y - b.y) == 0 ? sgn(x - b.x) < 0 : sgn(y - b.y) < 0; } Point operator + (const Point &b) { return Point(x + b.x, y + b.y); } Point operator - (const Point &b) { return Point(x - b.x, y - b.y); } double operator ^ (const Point &b) { return x * b.y - y * b.x; } double operator * (const Point &b) { return x * b.x + y * b.y; } double dis (const Point &b) { return dist(x - b.x, y - b.y); } }p; struct Line { Point s, e; Line(){} Line(Point _s, Point _e) { s = _s; e = _e; } void input() { s.input(); e.input(); } void output() { puts("line:"); s.output(); e.output(); } // 1 left 2 right 3 on int relation (Point p) { int c = sgn((p - s) ^ (e - s)); //printf("c : %d\n", c); if(c < 0) return 1; if(c > 0) return 2; return 3; } void adjust() { if(e < s) swap(e, s); } bool operator < (const Line &b) { return s < b.s || (s == b.s && e < b.e); } }line[N], l;

24、2-sat
bool dfs(int x) { if(mark[x ^ 1]) return 0; if(mark[x]) return 1; mark[x] = 1; s[++c] = x; for(int t = idx[x]; t; t = edge[t].nxt) if(!dfs(edge[t].to)) return 0; return 1; } bool solve() { if (!dfs(1)) return false; for(int i = 2; i <= 2 * n - 1; i += 2) { if(!mark[i] && !mark[i + 1]) { c = 0; if(!dfs(i)) { for(int j = 1; j <= c; j++) mark[s[j]] = 0; c = 0; if(!dfs(i + 1)) return 0; } } } return 1; }

25、后缀数组
//后缀数组倍增算法,假设输入的字符串为s[1..n] //sa[i]表示字典序第i小的后缀在串s中的位置 //Rank[i]表示从位置i开始的后缀在串s的所有后缀中排第几 //height[i]表示字典序第i-1小的后缀与字典序第i小的后缀的最长公共前缀 void buildsa(int m){ int i,*x=t1,*y=t2; for(i = 1; i <= m; i++) c[i] = 0; for(i = 1; i <= n; i++) c[x[i] = s[i]]++; for(i = 1; i <= m; i++) c[i] += c[i - 1]; for(i = n; i >= 1; i--) sa[c[x[i]]--] = i; for(int k = 1; k <= n; k <<= 1){ int p = 0; for(i = n - k + 1; i <= n; i++) y[++p] = i; for(i = 1; i <= n; i++) if(sa[i] > k) y[++p] = sa[i] - k; for(i = 1; i <= m; i++) c[i] = 0; for(i = 1; i <= n; i++) c[x[y[i]]]++; for(i = 1; i <= m; i++) c[i] += c[i - 1]; for(i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i]; swap(x, y); p = 1; x[sa[1]] = 1; for(i = 2; i <= n; i++) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p : ++p; if(p >= n) break; m = p; } } void getheight(){ int i, j, k = 0; for(i = 1; i <= n; i++) Rank[sa[i]] = i; for(i = 1; i <= n; i++){ if(k) k--; j=sa[Rank[i] - 1]; // sa[rank[i]]=i; while(s[j+k] == s[i+k]) k++; height[Rank[i]] = k; } }

26、树链剖分
#include #include #include #include using namespace std; const int M=200010; const int inf=0x7fffffff; struct E {int to,nxt; }edge[M*2]; struct SEG {int l,r,sum,mx; }tree[M*2]; int v[M],fa[M],size[M],son[M],dep[M],top[M],w[M],f[M]; int n,q,tot=1,idx[M],vis[M],cnt,retsum,retmax; void addedge(int from,int to){ edge[tot].to=to; edge[tot].nxt=idx[from]; idx[from]=tot++; } void init(){ scanf("%d",&n); for(int i=1; i1; build_seg(k<<1,a,mid); build_seg(k<<1|1,mid+1,b); tree[k].mx=max(tree[k<<1].mx,tree[k<<1|1].mx); tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; } void change(int k,int a,int x){ if(atree[k].r) return; if(a==tree[k].l && a==tree[k].r) {tree[k].mx=x,tree[k].sum=x; return; } change(k<<1,a,x); change(k<<1|1,a,x); tree[k].mx=max(tree[k<<1].mx,tree[k<<1|1].mx); tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; } int getsum(int k,int a,int b){ if(btree[k].r) return 0; if(a<=tree[k].l && tree[k].r<=b) return tree[k].sum; return getsum(k<<1,a,b)+getsum(k<<1|1,a,b); } int getmax(int k,int a,int b){ if(btree[k].r) return -inf; if(a<=tree[k].l && tree[k].r<=b) return tree[k].mx; return max(getmax(k<<1,a,b),getmax(k<<1|1,a,b)); } void solve(int x,int y,int opt){ int f1=top[x],f2=top[y]; retmax=-inf,retsum=0; while(f1!=f2){ if(dep[f1]

27、莫队算法
所以有一个比较优雅的替代品。那就是先对序列分块。然后对于所有询问按照L所在块的大小 排序。如果一样再按照R排序。然后按照排序后的顺序计算。为什么这样计算就可以降低复杂度呢。 一、i与i+1在同一块内，r单调递增，所以r是O(n)的。由于有n^0.5块,所以这一部 分时间复杂度是n^1.5。 二、i与i+1跨越一块，r最多变化n，由于有n^0.5块，所以这一部分时间复杂度是n^1.5 三、i与i+1在同一块内时变化不超过n^0.5，跨越一块也不会超过2*n^0.5，不 妨看作是n^0.5。由于有n个数，所以时间复杂度是n^1.5 于是就变成了O(n^1.5)了。 而我们知道 莫队算法的O(n^1.5)是基于O(1)得到[l-1,r]结果的 然而这道题 查逆序对 需要O(logn)时间用树状数组完成= = 所以复杂度O(n^1.5*logn)。。

#include #include #include #include #define lowbit(pos) pos&(-pos) using namespace std; const int M=50010; int a[M],disc[M],bl[M],c[M]; int N,Q; struct qu {int l,r,id,ans; }q[M]; bool cmp(qu x,qu y){ if(bl[x.l]==bl[y.l]) return x.rr) {r++; add(a[r],1); now+=r-l+1-query(a[r]); } while(q[i].l>l) {add(a[l],-1); now-=query(a[l]-1); l++; } while(q[i].r

28、点分治
#include #include #include using namespace std; const int inf = 0x7fffffff; const int N = 10005; int n, tot, idx[N], root, ans, sum, sz[N], f[N], d[N], dep[N], p, K; bool can[N]; struct E {int to, nxt, w; }edge[N * 2]; void init() { memset(idx, 0, sizeof(idx)); tot = 1; memset(can, 0, sizeof(can)); sum = n; ans = 0; root = 0; f[root] = inf; for(int i = 0; i < N; i++) can[i] = 1; } void addedge(int from, int to, int w) { edge[++tot].to = to; edge[tot].nxt = idx[from]; idx[from] = tot; edge[tot].w = w; } void getroot(int x, int fa) { sz[x] = 1; f[x] = 0; for(int t = idx[x]; t; t = edge[t].nxt) { E e = edge[t]; if(e.to == fa || !can[e.to]) continue; getroot(e.to, x); sz[x] += sz[e.to]; f[x] = max(sz[e.to], f[x]); } sz[x]++; f[x] = max(sum - sz[x], f[x]); if(f[x] < f[root]) root = x; } void getdeep(int x, int fa) { d[++p] = dep[x]; for(int t = idx[x]; t; t = edge[t].nxt) { E e = edge[t]; if(e.to == fa || can[e.to] == 0) continue; dep[e.to] = dep[x] + e.w; getdeep(e.to, x); } } int calc(int x, int now) { int ret = 0; dep[x] = now; p = 0; getdeep(x, -1); //printf("%d : ", x); //for(int i = 1; i <= p; i++) printf("%d ", d[i]); puts(""); sort(d + 1, d + 1 + p); int l = 1, r = p; for(int l = 1; l <= p; l++) { while(d[l] + d[r] > K && l < r) r--; if(l >= r) break; ret += (r - l); } return ret; } void work(int x) { ans += calc(x, 0); //printf("%d %d\n", can[3], can[4]); can[x] = 0; for(int t = idx[x]; t; t = edge[t].nxt) { E e = edge[t]; if(!can[e.to]) continue; //printf("%d\n", e.to); ans -= calc(e.to, e.w); sum = sz[e.to]; root = 0; getroot(e.to, -1); //printf("%d %d\n", e.to, root); return; work(root); } } int main() { while(scanf("%d%d", &n, &K) && n + K) { init(); for(int i = 1, x, y, z; i < n; i++) scanf("%d%d%d", &x, &y, &z), addedge(x, y, z), addedge(y, x, z); getroot(1, -1); work(root); printf("%d\n", ans); } return 0; }

29、二维rmq
int getmax(int X1, int Y1, int X2, int Y2) { int k1 = LOG[X2 - X1 + 1]; int k2 = LOG[Y2 - Y1 + 1]; X2 = X2 - (1 << k1) + 1; Y2 = Y2 - (1 << k2) + 1; return max(max(maxx[X1][Y1][k1][k2], maxx[X1][Y2][k1][k2]), max(maxx[X2][Y1][k1][k2] ,maxx[X2][Y2][k1][k2])); } int getmin(int X1, int Y1, int X2, int Y2) { int k1 = LOG[X2 - X1 + 1]; int k2 = LOG[Y2 - Y1 + 1]; X2 = X2 - (1 << k1) + 1; Y2 = Y2 - (1 << k2) + 1; return min(min(minn[X1][Y1][k1][k2], minn[X1][Y2][k1][k2]), min(minn[X2][Y1][k1][k2] ,minn[X2][Y2][k1][k2])); } int main() { scanf("%d%d%d", &n, &b, &k); LOG[0] = -1; for(int i = 1; i <= 254; i++) LOG[i] = ((i & (i - 1)) == 0) ? LOG[i - 1] + 1 : LOG[i - 1]; for(int i = 1, x; i <= n; i++) for(int j = 1; j <= n; j++) scanf("%d", &x), minn[i][j][0][0] = maxx[i][j][0][0] = x; for(int ii = 0; ii <= LOG[n]; ii++) for(int jj = 0; jj <= LOG[n]; jj++) if(ii + jj) for(int i = 1; i + (1 << ii) - 1 <= n; i++) for(int j = 1; j + (1 << jj) - 1 <= n; j++) if(ii) minn[i][j][ii][jj] = min(minn[i][j][ii - 1][jj], minn[i + (1 << (ii - 1))][j][ii - 1][jj]), maxx[i][j][ii][jj] = max(maxx[i][j][ii - 1][jj], maxx[i + (1 << (ii - 1))][j][ii - 1][jj]); else minn[i][j][ii][jj] = min(minn[i][j][ii][jj - 1], minn[i][j + (1 << (jj - 1))][ii][jj - 1]), maxx[i][j][ii][jj] = max(maxx[i][j][ii][jj - 1], maxx[i][j + (1 << (jj - 1))][ii][jj - 1]); for(int i = 1, x, y; i <= k; i++) { scanf("%d%d", &x, &y); printf("%d\n", getmax(x, y, x + b - 1, y + b - 1) - getmin(x, y, x + b - 1, y + b - 1)); } return 0; }

30、rmq
int getmax(int l, int r) { int k = LOG[r - l + 1]; r = r - (1 << k) + 1; return max(maxx[l][k], maxx[r][k]); } int getmin(int l, int r) { int k = LOG[r - l + 1]; r = r - (1 << k) + 1; return min(minn[l][k], minn[r][k]); } int main(){ LOG[0] = -1; for(int i = 1; i < N; i++) LOG[i] = ((i & (i - 1)) == 0) ? LOG[i - 1] + 1 : LOG[i - 1]; while(scanf("%d%d", &n, &q) != EOF){ for(int i = 1; i <= n; i++) scanf("%d", &minn[i][0]), maxx[i][0] = minn[i][0]; for(int j = 1; j <= 19; j++) for(int i = 1; i <= n; i++){ int k = i + (1 << j) - 1; if(k > n) break; minn[i][j] = min(minn[i][j - 1], minn[i + (1 << (j - 1))][j - 1]); maxx[i][j] = max(maxx[i][j - 1], maxx[i + (1 << (j - 1))][j - 1]); } for(int i = 1, l, r; i <= q; i++) { scanf("%d%d", &l, &r); printf("%d\n", getmax(l, r) - getmin(l, r)); } } return 0; }

31、树上rmq
void dfs(int x, int f) { vis[x] = 1; for(int t = idx[x]; t; t = edge[t].nxt) { E e = edge[t]; if(e.to == f) continue; if(vis[e.to]) { X = x; Y = e.to; W = e.w; continue; } dep[e.to] = dep[x] + 1; fa[e.to][0] = x; w[e.to][0] = e.w; for(int k = 1; k <= LOG[dep[e.to]]; k++) fa[e.to][k] = fa[fa[e.to][k - 1]][k - 1], w[e.to][k] = w[e.to][k - 1] + w[fa[e.to][k - 1]][k - 1]; dfs(e.to, x); } } ll query(int x, int y) { ll ans = 0; int h = dep[y] - dep[x]; while(h > 0) { ans += w[y][LOG[h]]; y = fa[y][LOG[h]]; h = dep[y] - dep[x]; } h = dep[x] - dep[y]; while(h > 0) { ans += w[x][LOG[h]]; x = fa[x][LOG[h]]; h = dep[x] - dep[y]; } if(x == y) return ans; h = dep[y]; for(int k = LOG[h]; k >= 0; k--) if(fa[x][k] != fa[y][k]) { ans += w[x][k]; ans += w[y][k]; x = fa[x][k]; y = fa[y][k]; } ans += (w[x][0] + w[y][0]); return ans; }

32、fft
#include #include #include #include #include #define N 300000 #define pi acos(-1.0) using namespace std; typedef complex cd; char s1[N],s2[N]; cd f[N],g[N],eps[N],c_eps[N]; int n,m,a[N]; void init(){ for(int i=0; ij) swap(x[i],x[j]); for(int l=n>>1; (j^=l)>=1); } for(int i=2; i<=n; i<<=1){ int m=i>>1; for(int j=0; j=0; i--) printf("%d",a[i]); return 0; }

33、错排 【ACM模板】

34、莫队算法：至少存在k次的数
#include #include #include #include #define N 100005 struct Q{ int l,r,k,ans,id; }q[N]; int n,m,a[N],num[N],cnt[N],block[N],tot[N],End[N],Begin[N]; using namespace std; int read(){ char ch=getchar(); int f=1,x=0; while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar(); } return x*f; } bool cmp(Q x,Q y){ return block[x.l]q[i].r; r--) upd(r,-1); for(; l>q[i].l; l--) upd(l-1,1); for(; l

35、最小表示法
#include #include #include using namespace std; int T; char s[20005]; int MinR(){ int l=strlen(s+1); for(int i=l+1; i<=l+l; i++) s[i]=s[i-l]; int i=1,j=2,k; while(i<=l&&j<=l){ k=0; while(s[i+k]==s[j+k]&&ks[j+k]) if(i+k+1>j) i=i+k+1; else i=j+1; else if(j+k+1>i) j=j+k+1; else j=i+1; } if(i<=l) return i; else return j; } int main(){ freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); scanf("%d",&T); while(T--){ scanf("%s",s+1); printf("%d\n",MinR()); } return 0; }

36、lucas定理
#include #include #include #define Mo 10007 #define ll long long using namespace std; const int N=10010; ll fac[N]; ll n,m; void exgcd(ll a,ll b,ll &x,ll &y){ if(!b){x=1; y=0; return; } else{exgcd(b,a%b,y,x); y-=(a/b)*x; } } ll inv(ll a){ ll x,y; exgcd(a,10007,x,y); return (x%Mo+Mo)%Mo; } ll C(ll n,ll m){ if(m==0) return 1; if(n

    推荐阅读


    上一篇：副业，才不是一个成年人应有的自觉……

    下一篇：柠檬讲故事34——羊驼驼传说