lqz已经什么题也写不对了。
期望得分：100 + 100 + 100
实际得分：95 + 70 + 60
T1本来写的矩阵快速幂，可是怎么也调不出来（初始矩阵建错），于是就去打了个找循环节的做法，自己手算了一下貌似循环节的长度大部分都很短，于是就去写了，但是被卡掉一个点。
T2打了个表，一下子发现是个等差数列，于是就写了正解，但是自己智障，特判了一下n==m的情况，这本来不用特判，正常跑就能跑出来，但是自己莫名其妙就认为当n==m的时候答案是固定的，于是挂了30分，去掉后就可以AC。
T3本来打的是标算，但是打错了一个字母，哭死。ev[i] -> _v[i]
T1
/* 因为是mod7 所以可以找一下从哪里开始循环之前的值 找到就退出 */ #include <cstdio> #include <iostream> #define rg register typedef long long LL; #define Max 55000000 short f[Max]; std :: string Name = "attack", _I = ".in", _O = ".out"; int main (int argc, char *argv[]) { freopen ((Name + _I).c_str (), "r", stdin); freopen ((Name + _O).c_str (), "w", stdout); f[1] = 1, f[2] = 1; LL A, B, N; std :: cin >> A >> B >> N; rg int i; for (i = 3; i <= N; ++ i) { f[i] = (A * f[i - 1] + B * f[i - 2]) % 7; if (f[i] == 1 && f[i - 1] == 1) break; } if (i == 3) return puts ("1"), 0; std :: cout << ((i == N + 1) ? f[N] : f[((N % (i - 2)) == 0 ? (i - 2) : (N % (i - 2)))]); return 0; }
/* 矩阵快速幂 */ #include <cstdio> #include <iostream> #define rg register typedef long long LL; struct Matrix { int c[2][2]; #define L 2 Matrix operator * (const Matrix &rhs) { Matrix res; for (rg int i = 0, j, k; i < L; ++ i) for (j = 0; j < L; ++ j) { res.c[i][j] = 0; for (k = 0; k < L; ++ k) (res.c[i][j] += c[i][k] * rhs.c[k][j]) %= 7; } res.c[0][0] %= 7; return res; } } Answer, P; std :: string Name = "attack", _I = ".in", _O = ".out"; int main (int argc, char *argv[]) { freopen ((Name + _I).c_str (), "r", stdin); freopen ((Name + _O).c_str (), "w", stdout); LL A, B, N; std :: cin >> A >> B >> N; rg int i; Answer.c[0][0] = Answer.c[0][1] = 1; Answer.c[1][1] = Answer.c[1][0] = 0; P.c[0][0] = A % 7, P.c[1][0] = B % 7, P.c[0][1] = 1, P.c[1][1] = 0; if (N <= 2) return puts ("1"), 0; for (N -= 2; N; P = P * P, N >>= 1) if (N & 1) Answer = Answer * P; std :: cout << Answer.c[0][0] % 7; return 0; }
T2
/* 求出公差即可 */ #include <cstdio> #include <iostream> #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 ()); } typedef double flo; std :: string Name = "fseq", _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 T; flo x, y, d; read (T); for (; T; -- T) { scanf ("%lf%lf", &x, &y); if (y == 0) { puts ("1.000000"); continue; } if (x == 0) { puts ("0.000000"); continue; } if (y > x) { puts ("0.000000"); continue; } d = 1.0 / (x + 1.0); printf ("%.6lf ", 1.0 - y * d); } return 0; }
T3
/* 套路题，没营养 Tarjan缩点 求出缩完点后树的直径 对于每个点，若在最长链上就直接对两个端点取max 否则就一直往上跳，累加边权，直到跳到最长链上 然后做上一种情况的操作就好了 */ #include <cstdio> #include <iostream> #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 = "prize", _I = ".in", _O = ".out"; #define Max 40008 int _v[Max * 20], _n[Max * 20], list[Max * 20], EC = 1, _d[Max * 20]; int N; inline void In (int u, int v, int d) { _v[++ EC] = v, _n[EC] = list[u], list[u] = EC, _d[EC] = d; } int t, sk[Max], DC, SC; int dfn[Max], low[Max], scc[Max]; inline void cmin (int &a, int b) { if (b < a) a = b; } void Dfs (int n, int l) { sk[++ t] = n; dfn[n] = low[n] = ++ DC; for (rg int i = list[n], v; i; i = _n[i]) if (i != l && i != (l ^ 1)) { if (!dfn[v = _v[i]]) Dfs (v, i), cmin (low[n], low[v]); else if (!scc[v]) cmin (low[n], dfn[v]); } if (low[n] == dfn[n]) { ++ SC; for (int r = n + 1; t && r != n; -- t) r = sk[t], scc[r] = SC; } } int ev[Max * 20], en[Max * 20], el[Max * 10], ec, ed[Max * 20]; inline void _In (int u, int v, int d) { ev[++ ec] = v, en[ec] = el[u], el[u] = ec, ed[ec] = d; ev[++ ec] = u, en[ec] = el[v], el[v] = ec, ed[ec] = d; } bool Find (int x, int y) { for (rg int i = el[x]; i; i = en[i]) if (ev[i] == y) return true; return false; } void Tarjan () { rg int i; for (i = 1; i <= N; ++ i) if (!dfn[i]) Dfs (i, 0); for (int n = 1; n <= N; ++ n) for (i = list[n]; i; i = _n[i]) if (scc[n] != scc[_v[i]]) if (!Find (scc[n], scc[_v[i]])) { _In (scc[n], scc[_v[i]], _d[i]); } } int Answer[Max]; int dis1[Max], dis2[Max], pos1, pos2, Max1, Max2, pre[Max]; void Gc1 (int n, int F) { for (rg int i = el[n], v; i; i = en[i]) if ((v = ev[i]) != F) dis1[v] = dis1[n] + ed[i], Gc1 (v, n); if (dis1[n] > Max1) Max1 = dis1[n], pos1 = n; } int f[Max]; void Gc2 (int n, int F) { f[n] = F; for (rg int i = el[n], v; i; i = en[i]) if ((v = ev[i]) != F) dis2[v] = dis2[n] + ed[i], Gc2 (v, n), pre[v] = n; if (dis2[n] > Max2) Max2 = dis2[n], pos2 = n; } bool isc[Max]; inline int max (int a, int b) { return a > b ? a : b; } void GetAnswer () { Gc1 (1, 0), Gc2 (pos1, 0); rg int i; for (i = pos2; i; i = pre[i]) isc[i] = true; rg int n; int res = 0, j; for (i = 1; i <= SC; ++ i) { res = 0; for (n = i; !isc[n] && n; n = f[n]) { for (j = el[n]; j; j = en[j]) if (ev[j] == f[n]) { res += ed[j]; break; } } res += max (dis2[n], Max2 - dis2[n]); Answer[i] = res; } for (i = 1; i <= N; ++ i) printf ("%d ", Answer[scc[i]]); } int main (int argc, char *argv[]) { freopen ((Name + _I).c_str (), "r", stdin); freopen ((Name + _O).c_str (), "w", stdout); int x, y, M, z; read (N), read (M); for (rg int i = 1; i <= M; ++ i) read (x), read (y), read (z), In (x, y, z), In (y, x, z); Tarjan (); GetAnswer (); return 0; }