前天深夜，数据结构课程再次留下了小作业。本着在DDL面前愉悦身心的态度，我用两天的时间水完了它们。这里来挂一下十分迷惑的思路和奇奇怪怪的代码。
注意：本篇博文主要面对本班同学，所以我不会在此提供题面、数据范围等信息。如果你没有相关内容说明你不是本篇博客的对象，请自行将鼠标移到页面选单点击图标「x」。
抄代码的就无所谓了，反正我猜我写的像...一样的代码也没有人愿意抄。
3020：
哈夫曼树板题，实现二叉堆即可。
注意每次减少m - 1个元素，所以要补充元素个数到(n - 1) mod (m - 1) = 1，特判m = 2的情况，此时不用补。
代码：
（二叉堆都写炸了，丢～人！）
+ Show Code
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 2e5 + 1e2;
struct Heap {
long long dat[maxn];
int n;
void fixHeapDown() {
int pos = 1;
while(pos <= n) {
const int ls = pos << 1, rs = pos << 1 | 1;
if(ls > n) return;
if(rs > n) {
if(dat[pos] < dat[ls]) return;
swap(dat[pos], dat[ls]), pos = ls;
} else {
if(dat[pos] <= min(dat[ls], dat[rs])) return;
if(dat[ls] <= dat[rs]) swap(dat[pos], dat[ls]), pos = ls;
else swap(dat[pos], dat[rs]), pos = rs;
}
}
}
void fixHeapUp() {
int pos = n;
while(pos != 1) if(dat[pos] < dat[pos >> 1]) swap(dat[pos], dat[pos >> 1]), pos >>= 1; else break;
}
void push(long long x) {
dat[++n] = x;
fixHeapUp();
}
long long pop() {
int ret = dat[1];
dat[1] = dat[n--];
fixHeapDown();
return ret;
}
int size() {
return n;
}
}hp;
int main() {
static int n, m;
long long ans = 0, su;
scanf("%d%d", &n, &m);
for(int i = 1, x; i <= n; i++) scanf("%d", &x), hp.push(x);
while(m != 2 && hp.size() % (m - 1) != 1) hp.push(0);
while(hp.size() != 1) {
su = 0;
for(int i = 1; i <= m; i++) su += hp.pop();
ans += su, hp.push(su);
}
printf("%lld\n", ans);
return 0;
}
1358：
类似找点分治中找重心的操作，只不过要你找出所有分割后子块大小小于一半的点。
搜索一遍算出大小，最大的块大小就是max(子树最大大小, n - 该点子树大小)。
代码：
+ Show Code
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 2e5 + 1e2;
int s[maxn], t[maxn << 1], nxt[maxn << 1], siz[maxn], mxs[maxn], n, cnt;
inline void coredge(int from, int to) { t[++cnt] = to, nxt[cnt] = s[from], s[from] = cnt; }
inline void addedge(int a, int b) { coredge(a, b), coredge(b, a); }
inline void dfs(int pos, int fa) { siz[pos] = 1; for(int at = s[pos]; at; at = nxt[at]) if(t[at] != fa) dfs(t[at], pos), siz[pos] += siz[t[at]], mxs[pos] = max(mxs[pos], siz[t[at]]); mxs[pos] = max(mxs[pos], n - siz[pos]); }
int main() {
scanf("%d", &n);
for(int i = 1, a, b; i < n; i++) scanf("%d%d", &a, &b), addedge(a, b);
dfs(1, -1);
for(int i = 1; i <= n; i++) if(mxs[i] <= n / 2) printf("%d\n", i);
return 0;
}
1056：
并查集维护糖与盒子的关系，二叉堆维护盒子中的糖数。（因为p很小，所以可以暴力～）
如果一个堆中一个盒子被取出时发现其所在并查集的根不是自己，则说明它已经被合并掉了，直接丢弃即可。
代码：
+ Show Code
#include <iostream>
#include <cstdio>
#define debug cerr
using namespace std;
const int maxn = 1e6 + 1e2;
struct Node {
int v, p;
friend bool operator < (const Node &a, const Node &b) {
return a.v > b.v;
}
friend bool operator <= (const Node &a, const Node &b) {
return a.v >= b.v;
}
};
struct Heap {
Node dat[maxn];
int n;
void fixHeapDown() {
int pos = 1;
while(pos <= n) {
const int ls = pos << 1, rs = pos << 1 | 1;
if(ls > n) return;
if(rs > n) {
if(dat[pos] < dat[ls]) return;
swap(dat[pos], dat[ls]), pos = ls;
} else {
if(dat[pos] <= min(dat[ls], dat[rs])) return;
if(dat[ls] <= dat[rs]) swap(dat[pos], dat[ls]), pos = ls;
else swap(dat[pos], dat[rs]), pos = rs;
}
}
}
void fixHeapUp() {
int pos = n;
while(pos != 1) if(dat[pos] < dat[pos >> 1]) swap(dat[pos], dat[pos >> 1]), pos >>= 1; else break;
}
void push(Node x) {
dat[++n] = x;
fixHeapUp();
}
Node pop() {
Node ret = dat[1];
dat[1] = dat[n--];
fixHeapDown();
return ret;
}
int size() {
return n;
}
}hp;
struct UnionFindSet {
int fa[maxn];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
}ufs;
int siz[maxn];
int main() {
static int n, m;
static char o[1010];
static Node temp[1010];
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) ufs.fa[i] = i, hp.push((Node){siz[i] = 1, i});
for(int i = 1, x, y; i <= m; i++) {
scanf("%s%d", o, &x);
if(*o == 'C') {
scanf("%d", &y), x = ufs.find(x), y = ufs.find(y);
if(x == 0 || y == 0 || x == y) continue;
ufs.fa[x] = ufs.fa[y] = ++n, ufs.fa[n] = n, hp.push((Node){siz[n] = siz[x] + siz[y], n});
} else if(*o == 'D') {
x = ufs.find(x);
ufs.fa[x] = 0;
} else {
int top = 0;
while(hp.size() && top < x) {
Node x = hp.pop();
// debug << "v = " << x.v << " p = " << x.p << endl;
if(ufs.find(x.p) == x.p) temp[++top] = x;
}
if(top < x) puts("0");
else printf("%d\n", temp[top].v);
for(int i = 1; i <= top; i++) hp.push(temp[i]);
}
}
return 0;
}
4118：
树的不同形态是由c(m, 子树个数)产生的。
前序遍历、后序遍历中，相同字母所控制的一段连续区间一定为同一子树，例如：(a{...}，{...}a)，所以直接递归即可。
+ Show Code
#include <cstdio>
#include <cstring>
typedef long long int lli;
constexpr int maxn = 50;
char sa[maxn], sb[maxn];
int ia[maxn][maxn], ib[maxn][maxn], rf[maxn], m, n;
inline lli fac(int x) { lli ret = 1; while(x) ret *= x--; return ret; }
inline lli c(int n, int m) { return fac(n) / (fac(m) * fac(n - m)); }
lli dfs(int l, int r, int ll, int rr) {
if(ia[l][r] != ib[ll][rr] || sa[l] != sb[rr]) return 0; // no solution.
++l, --rr;
lli ret = 1;
int su = 0;
while(l <= r && ll <= rr) {
int rangeRR = rf[l], rangeR = rangeRR - ll + l;
++su, ret *= dfs(l, rangeR, ll, rangeRR);
l = rangeR + 1, ll = rangeRR + 1;
}
ret *= c(m, su);
return ret;
}
int main() {
scanf("%d%s%s", &m, sa + 1, sb + 1), n = strlen(sa + 1);
for(int i = 1; i <= n; i++) for(int j = i; j <= n; j++) for(int k = i; k <= j; k++) {
ia[i][j] |= (1 << (sa[k] - 'a'));
ib[i][j] |= (1 << (sb[k] - 'a'));
}
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(sa[i] == sb[j]) rf[i] = j;
printf("%lld\n", dfs(1, n, 1, n));
return 0;
}
4119：
枚举集合点，树剖lca求距离加和即可。
代码：
+ Show Code
#include <cstdio>
const int maxn = 2e4 + 1e2;
int s[maxn], t[maxn << 1], nxt[maxn << 1], l[maxn << 1], fa[maxn], dep[maxn], dis[maxn], siz[maxn], son[maxn], top[maxn], cnt, n, ans = -1, ass = 0x3f3f3f3f, p[3];
inline void coredge(int from, int to, int len) { t[++cnt] = to, l[cnt] = len, nxt[cnt] = s[from], s[from] = cnt; }
inline void addedge(int a, int b, int l) { coredge(a, b, l), coredge(b, a, l); }
inline void dfs1(int pos) { dep[pos] = dep[fa[pos]] + (siz[pos] = 1); for(int at = s[pos]; at; at = nxt[at]) if(t[at] != fa[pos]) fa[t[at]] = pos, dis[t[at]] = dis[pos] + l[at], dfs1(t[at]), siz[pos] += siz[t[at]], son[pos] = siz[t[at]] > siz[son[pos]] ? t[at] : son[pos]; }
inline void dfs2(int pos) { top[pos] = pos == son[fa[pos]] ? top[fa[pos]] : pos; for(int at = s[pos]; at; at = nxt[at]) if(t[at] != fa[pos]) dfs2(t[at]); }
inline int lca(int x, int y) { while(top[x] != top[y]) dep[top[x]] > dep[top[y]] ? x = fa[top[x]] : y = fa[top[y]]; return dep[x] < dep[y] ? x : y; }
inline int gdis(int x, int y) { return dis[x] + dis[y] - (dis[lca(x, y)] << 1); }
int main() {scanf("%d", &n); for(int i = 0; i < 3; i++) scanf("%d", p + i); for(int i = 1, u, v, w; i < n; i++) scanf("%d%d%d", &u, &v, &w), addedge(u, v, w); dfs1(1), dfs2(1); for(int i = 1; i <= n; i++) {int s2 = 0; for(int j = 0; j < 3; j++) s2 += gdis(i, p[j]); if(s2 < ass) ans = i, ass = s2;} return printf("%d\n%d\n", ans, ass), 0; }
4120：
先缩点，考虑所有没有入度的块，它们一定要各问一次，设其数量为x，则答案就是1 - x / n。
注意如果存在一个块，它没有入度，大小为1，且连向的所有块都能被其他块指向，则这个块能用排除法解决。
实际上我不缩点也过了2333
代码：
+ Show Code
#include <cstdio>
const int maxn = 1e5 + 1e2, maxe = 3e5 + 1e2;
int s[maxn], t[maxe], nxt[maxe], ind[maxn], cnt, siz;
bool vis[maxn];
inline void addedge(int from, int to) { t[++cnt] = to, nxt[cnt] = s[from], s[from] = cnt; }
inline void dfs(int pos) { if(vis[pos]) return; siz += (vis[pos] = 1); for(int at = s[pos]; at; at = nxt[at]) dfs(t[at]); }
int main() {
static int n, m, ans, flag;
scanf("%d%d", &n, &m);
for(int i = 1, a, b; i <= m; i++) scanf("%d%d", &a, &b), addedge(a, b), ++ind[b];
for(int i = 1; i <= n; i++) if(!ind[i]) siz = 0, dfs(i), flag += (siz == 1), ++ans;
for(int i = 1; i <= n; i++) if(!vis[i]) siz = 0, dfs(i), flag += (siz == 1), ++ans;
if(n != 1 && flag) --ans;
printf("%0.6Lf\n", 1 - (long double)ans / n);
return 0;
}
4180：
有解说明给出的有向边一定构成DAG。拓扑排序，拓扑序小的点指向拓扑序大的点即可。正确性显然。（因为其他边起码不会反着指回来）
+ Show Code
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1e5 + 1e2;
int s[maxn], t[maxn], nxt[maxn], deg[maxn], cnt;
int u[maxn], v[maxn], id[maxn];
inline void addedge(int from, int to) { t[++cnt] = to, nxt[cnt] = s[from], s[from] = cnt; }
struct Queue { int dat[maxn], st, ed; Queue() {st = 1, ed = 0;} void push(int x) {dat[++ed] = x;} int pop() {return dat[st++];} int size() {return ed - st + 1;} }que;
int main() {
static int n, p1, p2, iid;
scanf("%d%d%d", &n, &p1, &p2);
for(int i = 1, u, v; i <= p1; i++) scanf("%d%d", &u, &v), addedge(u, v), ++deg[v];
for(int i = 1; i <= p2; i++) scanf("%d%d", u + i, v + i);
for(int i = 1; i <= n; i++) if(!deg[i]) que.push(i);
while(que.size()) {
const int pos = que.pop(); id[pos] = ++iid;
for(int at = s[pos]; at; at = nxt[at]) if(!--deg[t[at]]) que.push(t[at]);
}
for(int i = 1; i <= p2; i++) printf("%d %d\n", id[u[i]] < id[v[i]] ? u[i] : v[i], id[u[i]] < id[v[i]] ? v[i] : u[i]);
return 0;
}
4122：
Tire树匹配下单词，然后二分答案，求包含所有可能出现元素的最小区间即可。
滑动窗口，维护计数，基础操作了。
注意n个单词中重复的只算一次。
代码：
（因为没有判0还WA了几发，丢～人！）
+ Show Code
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 1e2, maxe = 1e4 + 1e2;
struct Tire {
int ch[maxe][257], isEnd[maxe], cnt, root;
Tire() {root = cnt = 1;};
void insert(char* s, int len, int id) {
int cur = root;
for(int i = 1; i <= len; i++) {
if(!ch[cur][s[i]]) ch[cur][s[i]] = ++cnt;
cur = ch[cur][s[i]];
}
isEnd[cur] = id;
}
int find(char* s, int len) {
int cur = root;
for(int i = 1; i <= len; i++) cur = ch[cur][s[i]];
return isEnd[cur];
}
}tr;
int id[maxn], vis[maxe], fs, n;
inline bool check(int len) {
memset(vis, 0, sizeof vis);
int siz = 0;
for(int i = 1; i <= len; i++) if(id[i] && ++vis[id[i]] == 1) ++siz;
if(siz == fs) return 1;
for(int i = len + 1; i <= n; i++) {
if(id[i] && ++vis[id[i]] == 1) ++siz;
if(id[i - len] && !--vis[id[i - len]]) --siz;
if(siz == fs) return 1;
}
return 0;
}
inline int bin() {
int l = 0, r = n, mid;
while(r > l + 1) {
mid = (l + r) >> 1;
check(mid) ? r = mid : l = mid;
}
return r;
}
int main() {
static int m;
static char s[1010];
scanf("%d", &m); for(int i = 1; i <= m; i++) scanf("%s", s + 1), tr.insert(s, strlen(s + 1), i);
scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%s", s + 1), ++vis[id[i] = tr.find(s, strlen(s + 1))];
for(int i = 1; i <= m; i++) fs += (bool) vis[i];
if(!fs) return puts("0\n0"), 0;
printf("%d\n%d\n", fs, bin());
return 0;
}
4123：
类似「HEOI2016：排序」的线段树解法，枚举答案字符，按照相对大小转为0、1，将区间排序转为区间赋值、区间求和。
代码：
+ Show Code
#include <iostream>
#include <cstdio>
#include <cstring>
#define debug cerr
using namespace std;
const int maxn = 1e5 + 1e2;
char in[maxn], ans[maxn];
int lst[maxn], v[maxn], o[maxn], l[maxn], r[maxn];
struct SegmentTree {
int sum[maxn << 2], tag[maxn << 2];
#define lson(pos) (pos << 1)
#define rson(pos) (pos << 1 | 1)
inline void maintain(int pos) {
sum[pos] = sum[lson(pos)] + sum[rson(pos)];
}
inline void build(int pos, int l, int r) {
tag[pos] = -1;
if(l == r) return void(sum[pos] = v[l]);
const int mid = (l + r) >> 1;
build(lson(pos), l, mid), build(rson(pos), mid + 1, r), maintain(pos);
}
inline void apply(int pos, int l, int r, int v) {
sum[pos] = (r - l + 1) * (tag[pos] = v);
}
inline void push(int pos, int l, int r, int mid) {
if(!~tag[pos]) return;
apply(lson(pos), l, mid, tag[pos]), apply(rson(pos), mid + 1, r, tag[pos]), tag[pos] = -1;
}
inline void update(int pos, int l, int r, int ll, int rr, int v) {
if(ll > rr) return;
if(ll <= l && r <= rr) return apply(pos, l, r, v);
const int mid = (l + r) >> 1; push(pos, l, r, mid);
if(ll <= mid) update(lson(pos), l, mid, ll, rr, v);
if(mid < rr) update(rson(pos), mid + 1, r, ll, rr, v);
maintain(pos);
}
inline int query(int pos, int l, int r, int ll, int rr) {
if(ll <= l && r <= rr) return sum[pos];
const int mid = (l + r) >> 1; push(pos, l, r, mid);
int ret = 0;
if(ll <= mid) ret += query(lson(pos), l, mid, ll, rr);
if(mid < rr) ret += query(rson(pos), mid + 1, r, ll, rr);
return ret;
}
inline void dfs(int pos, int l, int r) {
if(l == r) return void(v[l] = sum[pos]);
const int mid = (l + r) >> 1; push(pos, l, r, mid);
dfs(lson(pos), l, mid), dfs(rson(pos), mid + 1, r);
}
}sgt;
int main() {
static int n, m;
scanf("%d%d%s", &n, &m, in + 1);
for(int i = 1; i <= m; i++) scanf("%d%d%d", l + i, r + i, o + i);
for(int al ='a'; al <= 'z'; al++) {
memcpy(lst, v, sizeof lst);
for(int i = 1; i <= n; i++) v[i] = in[i] <= al;
sgt.build(1, 1, n);
for(int i = 1; i <= m; i++) {
int s1 = sgt.query(1, 1, n, l[i], r[i]), s0 = r[i] - l[i] + 1 - s1;
if(!o[i]) sgt.update(1, 1, n, l[i], l[i] + s0 - 1, 0), sgt.update(1, 1, n, l[i] + s0, r[i], 1);
else sgt.update(1, 1, n, l[i], l[i] + s1 - 1, 1), sgt.update(1, 1, n, l[i] + s1, r[i], 0);
}
sgt.dfs(1, 1, n);
for(int i = 1; i <= n; i++) if(v[i] && !lst[i]) ans[i] = al;
}
puts(ans + 1);
return 0;
}
1402：
非旋Treap维护两个标记：赋值、加等差。
注意标记合并顺序为先赋值，后等差。应用赋值时候清除原有一切标记。
代码：
（size * size没转long long挂了一发，丢～人！）
+ Show Code
#include <iostream>
#include <cstdio>
#define debug cerr
typedef long long ll;
using namespace std;
struct Treap {
struct Node {
ll v, sum, fill_v, add_fir, add_d;
bool tag_fill, tag_add;
Node *ls, *rs;
int siz, hv;
Node(ll x): v(x), sum(x), siz(1), hv(rand()) { cleanTags(); }
void cleanTags() { tag_fill = tag_add = fill_v = add_fir = add_d = 0; }
void apply_fill(ll nv) { cleanTags(), tag_fill = 1, sum = siz * (v = fill_v = nv); }
void apply_add(ll fir, ll d) {
const int lsiz = ls ? ls->siz : 0;
tag_add = 1, add_fir += fir, add_d += d;
v += fir + d * lsiz, sum += (ll(siz) * (siz - 1) >> 1) * d + siz * fir;
}
void push() {
if(tag_fill) {
if(ls) ls->apply_fill(fill_v);
if(rs) rs->apply_fill(fill_v);
} if(tag_add) {
const int lsiz = ls ? ls->siz : 0;
if(ls) ls->apply_add(add_fir, add_d);
if(rs) rs->apply_add(add_fir + add_d * (lsiz + 1), add_d);
} cleanTags();
}
void maintain() {
sum = v, siz = 1;
if(ls) sum += ls->sum, siz += ls->siz;
if(rs) sum += rs->sum, siz += rs->siz;
}
}*root;
pair<Node*, Node*> split(Node* pos, int tar) {
if(!tar) return make_pair(nullptr, pos);
const int lsiz = pos->ls ? pos->ls->siz : 0;
pos->push();
if(tar <= lsiz) {
auto ret = split(pos->ls, tar);
pos->ls = ret.second, pos->maintain();
return make_pair(ret.first, pos);
} else {
auto ret = split(pos->rs, tar - lsiz - 1);
pos->rs = ret.first, pos->maintain();
return make_pair(pos, ret.second);
}
}
Node* merge(Node* l, Node* r) {
if(l == nullptr || r == nullptr) return l == nullptr ? r : l;
if(l->hv > r->hv) return l->push(), l->rs = merge(l->rs, r), l->maintain(), l;
else return r->push(), r->ls = merge(l, r->ls), r->maintain(), r;
}
Treap() { root = nullptr; }
~Treap() { delete_All(root); }
void delete_All(Node* pos) {
if(pos == nullptr) return;
if(pos->ls) delete_All(pos->ls);
if(pos->rs) delete_All(pos->rs);
delete pos;
}
void fill_v(int l, int r, ll v) {
auto sp1 = split(root, l - 1), sp2 = split(sp1.second, r - l + 1);
sp2.first->apply_fill(v);
root = merge(sp1.first, merge(sp2.first, sp2.second));
}
void add_v(int l, int r, ll fir, ll d) {
auto sp1 = split(root, l - 1), sp2 = split(sp1.second, r - l + 1);
sp2.first->apply_add(fir, d);
root = merge(sp1.first, merge(sp2.first, sp2.second));
}
void push(int pos, ll v) {
Node* np = new Node(v);
auto sp = split(root, pos - 1);
root = merge(sp.first, merge(np, sp.second));
}
ll query(int l, int r) {
auto sp1 = split(root, l - 1), sp2 = split(sp1.second, r - l + 1);
const ll ret = sp2.first->sum;
root = merge(sp1.first, merge(sp2.first, sp2.second));
return ret;
}
}tp;
int main() {
static int n, q;
scanf("%d%d", &n, &q);
for(int i = 1, x; i <= n; i++) scanf("%d", &x), tp.push(i, x);
for(int i = 1, o, l, r, x; i <= q; i++) {
scanf("%d%d%d", &o, &l, &r);
switch(o) {
case 1: scanf("%d", &x), tp.fill_v(l, r, x); break;
case 2: scanf("%d", &x), tp.add_v(l, r, x, x); break;
case 3: tp.push(l, r); break;
case 4: printf("%lld\n", tp.query(l, r));
}
}
return 0;
}
好了，就酱。一堆水题还要发什么题解～还不是要填博客嘛qwq
我也是很难的啦～
对了，zoom课堂用这种头像是不是会被...啊
原图ID：Pixiv 80315592
（什么？没有梯子？这我可不能负责）
评论～ NOTHING