的确比较奇妙。 有一个奇妙的玩意是fib[gcd(i, j)] == gcd(fib[i], fib[j])。(fib[1] = fib[2] = 1) 然后就比较可搞了。 线性筛处理每个数的因子个数和因子和。开一点变量然后推一下就出来了。 然后要注意fib[2]也可以整除所有奇数，包括1。表示在这上面坑了2次提交。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define _l (long long int) const int maxn = 10000009; const int mod = 1000000007; int tp, pn[maxn], sa[maxn], sb[maxn], b[maxn], c[maxn]; bool pr[maxn]; void pre(int n) { memset(pr, 0, sizeof(pr)); tp = 0; sa[1] = 1; sb[1] = 1; b[1] = 1; c[1] = 0; for (int i = 2; i <= n; ++ i) { if (!...

水水的dp。拿pascal玩玩边表。然后莫名其妙地发现在main上先是ce然后全wa。下到数据一测就过了，交bzoj还是过了。不开心。 必定是一个中间点然后连三条出去。所以直接枚举中间点然后bfs就好了。相当于每条边被转移了两次所以还是O(n^2)的。最初想错了想成三方了把自己吓了一跳。 pascal啊。 type edge = ^edger; edger = record t: longint; next: edge; end; const maxn = 5009; //ONLINE_JUDGE = false; ONLINE_JUDGE = true; var n, i, j, u, v: longint; ans: int64; d, cd, sd, td: array [0 .. maxn] of longint; head: array [0 .. maxn] of edge; ei: edge; procedure addEdge(u, v: longint); var ep: edge; begin new(ep); ep^. t := v; ep^. next := head[u]; head[u] := ep; end;...

题号是3851，题目名称是2048。 比较厉害的DP。最初没有想到怎么表示状态。其实就是一个≤2048的自然数就可以表示状态了。 然后转移不能一个一个来，每个值要一起来， 然后拿组合数来算。然后就行了。 虽然hdu上还是过不到。好慢的说。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define _l (long long int) const int maxn = 100009; const int mod = 998244353; int n, f[2][2051], c[2051]; int fac[maxn], finv[maxn], p2[maxn]; 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;...

全局二分+树状数组，其实还是比较水。 比较坑的一点是直接求和会暴long long。如果≥Pi了要直接break掉。好坑啊。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std;  int _d_; #define readInt(_x_) { \ int& _s_ = (_x_ = 0); \ while (!isdigit(_d_ = getchar())); \ while (_s_ = (_s_ << 3) + (_s_ << 1) + _d_ - 48, isdigit(_d_ = getchar())); \ } typedef long long dint; const int maxn = 300009; struct node { int v; node *next; }; struct rain { int l, r, a; }; struct bintree { dint t[maxn]; int n; bintree() {...

水一发。 本来可以直接拿主席树找中位数的，但是因为main上只有32MB，所以只好写了个splay。感觉现在是爱上指针了。然后kth的时候少打个等号又wa又re好爽。 #include <cstdio> #include <cstring> #include <algorithm> 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 = 100009; #define nsz(p) ((p)?(p->sz):0) #define sof(p) ((p)?(p->s):0) struct splay_node {    int v, sz;    dint s;    splay_node *ls, *rs, *pt;    inline void init(int v0) {    v = v0;    sz = 1;    s = v0;    pt = ls = rs = 0;...

比较简单易懂的状压。 最初想懒一下把起点和终点也压进来然后发现刚好会超一点空间。然后不压进来的话就是100MB左右，很好奇MAIN上面64MB的内存应该怎么做。拿MAP么？ 代码各种难看啊郁闷。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t, v; edge *next; }; #define pow2(x) (1<<(x)) typedef pair <int, int> dspr; const int maxn = 20009; const int maxe = 400009; const int maxk = 20; const int maxz = pow2(20) + 3; int n, m, k, d[maxn]; int f[maxz][maxk], ds[maxk], dt[maxk], dk[maxk][maxk], ans; int g, pr[maxk]; edge *ep, *head[maxn]; dspr hp[maxe]; inline void addEdge(int u, int v, int w) {...

yy了一个sqrt的玩意，不过因为n在变所以没有保障啊。 肯定不是正解了。 1s的题跑了1.3s居然AC，好厉害。 #include <cstdio> typedef long long dint; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif dint calc(dint n, dint k) { if (n <= 1) return k; for (dint i = 1, j; i <= k; i = j + 1) { if (n <= i) return k; j = (n - 1) / ((n - 1) / i); if (j > k) j = k; n = ((n - 1) / i + 1) * j; } return n;...

最初觉得挺麻烦的一道题没思路。有点像并查集直接搞但是不好维护直径。 然后发现树上到任意一点的最远点一定是直径的两个端点之一。于是直接把直径是哪俩点记下来就好了。然后按点权从大到小往树里插。 然后莫名其妙地抢到了第二快。这么老的题也是蛮欣慰的。大概是读入优化2333 #include <bits/stdc++.h> using namespace std; void setRand() { FILE* pf = fopen(".rs", "r"); int hsv; if (pf) { fscanf(pf, "%d", &hsv); fclose(pf); } srand(hsv); printf("Seed = %d\n", hsv); pf = fopen(".rs", "w"); fprintf(pf, "%d", (hsv << 1) | (rand() & 1)); fclose(pf); } #define readArg(a,b) { if (argc > a) sscanf(args[a], "%d", &b); } void mklr(int m, char s) { int l, r; do l = rand() % m + 1, r = rand() % m + 1; while (l > r); printf("%d %d%c", l, r, s); }...

orz jason_yu提醒了我一句“最简单的优化”，才想起来。 如果d合法的话那么b/d-(a-1)/d>0。然后用整除优化到sqrt就可过。虽然比较慢。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int main() { int t, a, b, c, d, s, e; scanf("%d", &t); while (t --) { scanf("%d%d%d%d", &a, &b, &c, &d); -- a; -- c; s = 1; e = min(b, d); for (int i = 1, j; i <= e; i = j + 1) { j = min(b / (b / i), d / (d / i)); if (a / i) j = min(j, a / (a / i)); if (c / i)...

树型贪心orz 写丑了。调了半个晚上，然后发现是起点最耗时的时候的情况搞错了，只用走n-1条路而不是n条。晕。 对于每个节点贪心按f[p]-2*sz[p]排序或者用原式也行。不过巨慢。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; int _d_;  #define readInt(_x_) { \ int& _s_ = (_x_ = 0); \ while (!isdigit(_d_ = getchar())); \ while (_s_ = _s_ * 10 + _d_ - 48, isdigit(_d_ = getchar())); \ } struct edge { int t; edge *next; }; const int maxn = 500009; int n, v[maxn], t, f[maxn], sz[maxn], dfo[maxn], st[maxn]; edge *ep, *head[maxn]; inline void addEdge(int u, int v) { ep-> t = v;...