这场考试完美的展示了lqz高超的智力水平
竟然能够直逼noip胎教组！
应得：100 + 100 + 100
实得：40 + 100 + 100
T1简直zz，一开始一看题，woc，这么裸！？于是就tarjan，缩点，拓扑balabala
突然一想，这直接dfs不就好了吗？然后就丢掉了刚才的代码，转去写dfs
写完一边过了样例就丢到一边不管了。。。。然后就40分
突然意识到。。。mdzz，应该是建反向边，我建的正向边。。。智商感人。
T1
/* zz的dfs
40分 */ #include <cstdio> #include <iostream> #define rg register inline void read (int &n) { rg char c = getchar (); bool temp = false; for (n = 0; !isdigit (c); c = getchar ()) if (c == '-') temp = true; for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); if (temp) n = -n; } #define Max 300009 bool is[Max]; struct E { E *n; int v; } *list[Max], pool[Max], *Ta = pool; inline void In (int u, int v) { ++ Ta, Ta->v = v, Ta->n = list[u], list[u] = Ta; } int f[Max]; inline void cmax (int &a, int b) { if (b > a) a = b; } inline int max (int a, int b) { return a > b ? a : b; } void Dfs (int n) { cmax (f[n], n); rg int v; for (E *e = list[n]; e; e = e->n) { if (!is[v = e->v]) is[v] = true, Dfs (v); cmax (f[n], max (f[v], v)); } } std :: string Name = "graph", _I = ".in", _O = ".out"; int main (int argc, char *argv[]) { freopen ((Name + _I).c_str (), "r", stdin); freopen ((Name + _O).c_str (), "w", stdout); int x, y, N, M; read (N), read (M); rg int i; for (i = 1; i <= M; ++ i) read (x), read (y), In (x, y); for (i = 1; i <= N; ++ i) if (!is[i]) Dfs (i); for (i = 1; i <= N; ++ i) printf ("%d ", f[i]); return 0; }
/* zz的tajan
90分 */ #include <cstdio> #include <iostream> #include <stack> #include <queue> #define rg register inline void read (int &n) { rg char c = getchar (); for (n = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); } std :: string Name = "graph", _I = ".in", _O = ".out"; #define Max 200005 struct Graph { int l[Max], v[Max], n[Max], EC; Graph () { EC = 0; } inline void In (int x, int y) { v[++ EC] = y, n[EC] = l[x], l[x] = EC; } } g1, g2; std :: stack <int> S; int dfn[Max], low[Max], scc[Max], SC; int key[Max], N, DC; inline void cmin (int &a, int b) { if (b < a) a = b; } inline void cmax (int &a, int b) { if (b > a) a = b; } void Dfs (int n) { S.push (n), dfn[n] = low[n] = ++ DC; rg int i, v; for (i = g1.l[n]; i; i = g1.n[i]) if (!dfn[v = g1.v[i]]) Dfs (v), cmin (low[n], low[v]); else if (!scc[v]) cmin (low[n], dfn[v]); if (dfn[n] == low[n]) for (v = n + 1, ++ SC; !S.empty () && v != n; S.pop ()) v = S.top (), scc[v] = SC, cmax (key[SC], v); } int in[Max]; int Find (int x, int y) { for (rg int i = g2.l[x]; i; i = g2.n[i]) if (g2.v[i] == y) return true; return false; } void Tarjan () { rg int i; for (i = 1; i <= N; ++ i) if (!dfn[i]) Dfs (i); for (int n = 1; n <= N; ++ n) for (i = g1.l[n]; i; i = g1.n[i]) if (scc[n] != scc[g1.v[i]] && !Find (scc[n], scc[g1.v[i]])) g2.In (scc[n], scc[g1.v[i]]), ++ in[scc[g1.v[i]]]; } int f[Max]; inline int max (int a, int b) { return a > b ? a : b; } void Get (int n) { cmax (f[n], key[n]); for (rg int i = g2.l[n]; i; i = g2.n[i]) { Get (g2.v[i]); cmax (f[n], max (f[g2.v[i]], key[g2.v[i]])); } } void GetAnswer () { rg int i; for (i = 1; i <= SC; ++ i) if (!in[i]) Get (i); for (i = 1; i <= N; ++ i) printf ("%d ", f[scc[i]]); } int main (int argc, char *argv[]) { freopen ((Name + _I).c_str (), "r", stdin); freopen ((Name + _O).c_str (), "w", stdout); int M, x, y; read (N), read (M); rg int i; for (i = 1; i <= M; ++ i) read (x), read (y), g1.In (x, y); Tarjan (); GetAnswer (); return 0; }
/* 反向边dfs 100分 */ #include <cstdio> #include <iostream> #define rg register inline void read (int &n) { rg char c = getchar (); bool temp = false; for (n = 0; !isdigit (c); c = getchar ()) if (c == '-') temp = true; for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); if (temp) n = -n; } #define Max 300009 bool is[Max]; struct E { E *n; int v; } *list[Max], pool[Max], *Ta = pool; inline void In (int u, int v) { ++ Ta, Ta->v = v, Ta->n = list[u], list[u] = Ta; } int f[Max]; inline void cmax (int &a, int b) { if (b > a) a = b; } inline int max (int a, int b) { return a > b ? a : b; } void Dfs (int n) { rg int v; for (E *e = list[n]; e; e = e->n) if (!is[v = e->v]) cmax (f[v], f[n]), is[v] = true, Dfs (v); } std :: string Name = "graph", _I = ".in", _O = ".out"; int main (int argc, char *argv[]) { freopen ((Name + _I).c_str (), "r", stdin); freopen ((Name + _O).c_str (), "w", stdout); int x, y, N, M; read (N), read (M); rg int i; for (i = 1; i <= M; ++ i) read (x), read (y), In (y, x); for (i = 1; i <= N; ++ i) f[i] = i; for (i = N; i >= 1; -- i) if (!is[i]) Dfs (i); for (i = 1; i <= N; ++ i) printf ("%d ", f[i]); return 0; }
T2
/* nlogn的最长严格上升子序列 */ #include <cstdio> #include <iostream> #include <algorithm> #define rg register inline void read (int &n) { rg char c = getchar (); bool temp = false; for (n = 0; !isdigit (c); c = getchar ()) if (c == '-') temp = true; for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); if (temp) n = -n; } #define INF 1e9 #define Max 100009 int a[Max], f[Max]; std :: string Name = "incr", _I = ".in", _O = ".out"; inline void cmax (int &a, int b) { if (b > a) a = b; } int main (int argc, char *argv[]) { freopen ((Name + _I).c_str (), "r", stdin); freopen ((Name + _O).c_str (), "w", stdout); int N, t = 1, p; read (N); rg int i; f[0] = -INF; for (i = 1; i <= N; ++ i) read (a[i]); f[t] = -- a[t]; for (i = 2; i <= N; ++ i) { p = std :: upper_bound (f + 1, f + 1 + t, a[i] - i) - f; f[p] = a[i] - i, cmax (t, p); } printf ("%d", N - t); return 0; }
T3
/* 高精+dp */ #include <iostream> #include <cstdio> #include <vector> #include <iomanip> #define rg register inline void read (int &n) { rg char c = getchar (); bool temp = false; for (n = 0; !isdigit (c); c = getchar ()) if (c == '-') temp = true; for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); if (temp) n = -n; } #define Max 200 const int BB = 1000000000, BL = 9; struct Int { inline int max (int a, int b) { return a > b ? a : b; } std :: vector <int> c; Int () {} typedef long long LL; Int (int x) { for (; x > 0; c.push_back (x % BB), x /= BB); } inline void CrZ () { for (; !c.empty () && c.back () == 0; c.pop_back ()); } inline Int &operator += (const Int &rhs) { c.resize (max (c.size (), rhs.c.size ())); rg int i, t = 0, S; for (i = 0, S = rhs.c.size (); i < S; ++ i) c[i] += rhs.c[i] + t, t = c[i] >= BB, c[i] -= BB & (-t); for (i = rhs.c.size (), S = c.size (); t && i < S; ++ i) c[i] += t, t = c[i] >= BB, c[i] -= BB & (-t); if (t) c.push_back (t); return *this; } inline Int &operator *= (const Int &rhs) { rg int na = c.size (), i, j, S, ai; c.resize (na + rhs.c.size ()); LL t; for (i = na - 1; i >= 0; -- i) { ai = c[i], t = 0, c[i] = 0; for (j = 0, S = rhs.c.size (); j < S; ++ j) t += c[i + j] + (LL) ai * rhs.c[j], c[i + j] = t % BB, t /= BB; for (j = rhs.c.size (), S = c.size (); t != 0 && i + j < S; ++ j) t += c[i + j], c[i + j] = t % BB, t /= BB; } CrZ (); return *this; } friend inline Int operator + (const Int &lhs, const Int &rhs) { Int res = lhs; return res += rhs; } friend inline Int operator * (const Int &lhs, const Int &rhs) { Int res = lhs; return res *= rhs; } friend inline std :: ostream &operator << (std :: ostream &out, const Int &rhs) { if (rhs.c.size () == 0) out << "0"; else { out << rhs.c.back (); for (rg int i = rhs.c.size () - 2; i >= 0; -- i) out << std :: setfill ('0') << std :: setw (BL) << rhs.c[i]; } return out; } }; Int f[Max][Max]; std :: string Name = "permutation", _I = ".in", _O = ".out"; int main (int argc, char *argv[]) { freopen ((Name + _I).c_str (), "r", stdin); freopen ((Name + _O).c_str (), "w", stdout); int N, K; read (N), read (K); rg int i, j; if (K >= N) return puts ("0"), 0; for (i = 1; i <= N; ++ i) f[i][0] = 1; for (i = 2; i <= N; ++ i) for (j = 1; j <= K; ++ j) if (j < i) f[i][j] += f[i - 1][j - 1] * (i - j) + (j + 1) * f[i - 1][j]; std :: cout << f[N][K]; return 0; }