题号是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;...
一血yeah yeah。 第一眼觉得是比较麻烦的单调队列。 然后发现转移的时候只会加1或者不加。 那么取的时候只用取队首，队里首先fi单不降然后hi单减。那么一定没有方案比取队首差。 #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())); \ } const int maxn = 1000009; int n, m, a[maxn], f[maxn], q[maxn]; int getTrans(int l, int r) { int v0 = f[q[l]]; while (l < r) { int mid = (l + r + 1) >> 1;...
签到题。表示今天虽然废了一天但是还是坚持写了题的。 单调栈搞定。 因为打球把小指头打残了所以不想敲include所以写了pascal，然后发现include不用小指。 const maxn = 100009; var n, i, t: longint; a, st, ans: array[0 .. maxn] of longint; begin readln(n); for i := 1 to n do readln(a[i]); t := 0; for i := n downto 1 do begin while (t > 0) and (a[i] >= a[st[t]]) do dec(t); if t = 0 then ans[i] := 0 else ans[i] := st[t]; inc(t); st[t] := i; end; for i := 1 to n do...