Codes

#include #include #include #include #include using namespace std; #ifdef WIN32 #define randInt ((rand()«16)|rand()) #else #define randInt (rand()) #endif const double eps = 1e-11; const double pi = acos(-1); inline double sqr(const double& x) { return x * x; } inline int sgn(const double& x) { return (x > eps) - (x < -eps); } typedef struct triobj { double x, y, z; triobj() {} triobj(const double& xo, const double& yo, const double& zo) { x = xo, y = yo, z = zo; } inline void read() { scanf("%lf%lf%lf", &x, &y, &z); } } point, vect; inline triobj operator +(const triobj& a, const triobj& b) { return triobj(a....

#include #include #include using namespace std; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) const int maxn = 50009; dint n, s; int tp, pn[maxn], u[maxn], fc[maxn], tf; bool pr[maxn]; void pre() { memset(pr, 0, sizeof(pr)); u[1] = 1; tp = 0; for (int i = 2; i < maxn; ++ i) { if (!pr[i]) { pn[tp ++] = i; u[i] = -1; } for (int j = 0, v; j < tp && i * pn[j] < maxn; ++ j) { pr[v = i * pn[j]] = 1; if (i % pn[j] == 0) { u[v] = 0; break; } else u[v] = -u[i]; } } }...

#include #include #include using namespace std; #define mInc(x,y) { x += y; if (x >= mod) x -= mod; } #define _l (long long int) const int maxn = 20009; const int mod = 1004535809; const int wo = 3; int n, m, mz, l, x, a[maxn], g[maxn], ss; int wm, wp[maxn]; int modPow(int a, int x, int tmod = mod) { int s(1); for (; x; x »= 1, a = _l a * a % tmod) if (x & 1) s = _l s * a % tmod; return s; }...

#include #include #include using namespace std; struct edge { int t; edge *next; }; const int maxn = 109; const int inf = 0x3f3f3f3f; edge *head[maxn], ebuf_arr[maxn « 1], ebuf; int n, f[maxn][2][2]; / f[node][if u is light][if u is chosen] */ inline void addEdge(int u, int v) { ebuf-> t = v; ebuf-> next = head[u]; head[u] = ebuf ++; } #define protect(x) { if (x > inf) x = inf; }...

#include #include #include using namespace std; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) struct node { int v; dint phi, mu; node *next; }; const int maxv = 3000009; const int hmod = 4432457; int n, tp, pn[maxv], phi[maxv], mu[maxv]; dint sp[maxv], smu[maxv]; bool pr[maxv]; node *head[hmod]; void pre() { memset(pr, 0, sizeof(pr)); memset(head, 0, sizeof(head)); tp = 0; phi[1] = mu[1] = 1; for (int i = 2; i < maxv; ++ i) { if (!...

#include #include #include using namespace std; #define _l (long long int) const int maxn = 2000009; const int mod = (1 « 23) * 7 * 17 + 1; int n, a[maxn], b[maxn], c[maxn]; int readInt(int* a) { static char g[maxn]; scanf("%s", g); int l(strlen(g)); for (int i = 0; i < l; ++ i) a[l - i - 1] = g[i] - 48; return l; } int modPow(int a, int x) { int s(1); for (; x; x »= 1, a = _l a * a % mod) if (x & 1) s = _l s * a % mod; return s; }...

#include #include #include using namespace std; const int maxn = 100009; int n, a[maxn], sm[maxn], ans; int f[maxn], g[maxn], q[maxn], hd, tl; int main() { #ifndef ONLINE_JUDGE //freopen(".in", “r”, stdin); #endif scanf("%d", &n); sm[0] = 0; for (int i = 0; i < n; ++ i) { scanf("%d", a + i); sm[i + 1] = sm[i] + a[i]; } hd = 0, tl = 1, q[hd] = n; f[n] = 0, g[n] = 0; for (int i = n - 1; i >= 0; -- i) { while (hd + 1 < tl && sm[q[hd + 1]] - f[q[hd + 1]] >= sm[i]) ++ hd; f[i] = sm[q[hd]] - sm[i]; g[i] = g[q[hd]] + 1; while (hd < tl && sm[i] - f[i] >= sm[q[tl - 1]] - f[q[tl - 1]]) -- tl; q[tl ++] = i; } printf("%d\n", g[0]); }

#include #include #include using namespace std; const int maxn = 200009; int n, tn, tr[maxn][26], ed[maxn], fl[maxn]; int m, pi[maxn], dl[maxn], r[maxn]; char a[maxn], g[maxn]; void trieIns(char* i) { int p(1), l(0); for (; *i; ++ i, ++ l) { int t(*i - 97); if (!tr[p][t]) { tr[p][t] = ++ tn; ed[tn] = 0; memset(tr[tn], 0, sizeof(tr[tn])); } p = tr[p][t]; } ed[p] = l; } void acaBuild() { static int q[maxn]; int hd(0), tl(1); q[0] = 1; while (hd < tl) { int u(q[hd ++]); for (int i = 0; i < 26; ++ i) if (tr[u][i]) { int v(tr[u][i]), w; for (w = fl[u]; w && !...

#include #include #include #include using namespace std; const int maxn = 500009; int n, a[maxn], z[maxn], ans, sa[maxn], sr[maxn]; double sqa[maxn]; void pre(int n) { for (int i = 0, j = 0; j <= n; ++ i) for (; j <= i * i && j <= n; ++ j) z[j] = i; for (int i = 0; i <= n; ++ i) sqa[i] = sqrt(i); } inline double fi(int j, int i) { return a[j] + sqa[i - j]; } inline int fii(int j, int i) { return a[j] + z[i - j]; }...

#include #include #include using namespace std; struct edge { int t; edge *next; }; const int maxn = 200009; const int maxe = 300009; int n, m, vis[maxn], tscc, fs[maxn], cs[maxn], f[2][maxn]; int tpo[maxn], ind[maxn]; edge ebuf_arr[maxe], *ebuf(ebuf_arr), *head[maxn], *hg[maxn]; inline void addEdge(edge** head, int u, int v) { ebuf-> t = v; ebuf-> next = head[u]; head[u] = ebuf ++; } void tarjanDFS(int po) { static int stc[maxn], stv[maxn], stj[maxn], fr[maxn], d[maxn]; static int dfb[maxn], low[maxn]; int tst(1), dfn(0), tsv(0), tsj(0); vis[stc[tst] = po] = 1; fr[po] = 0; d[po] = 1; while (tst) { int p(stc[tst –]); if (dfb[p]) continue; for (; tsv && d[stv[tsv]] >= d[p]; – tsv) { int q(stv[tsv]); low[fr[q]] = min(low[fr[q]], low[q]); if (dfb[q] == low[q]) { cs[++ tscc] = 0; do { ++ cs[tscc]; fs[stj[tsj]] = tscc; vis[stj[tsj]] = 2; } while (stj[tsj –] !...