https://www.bilibili.com/video/BV19Z4y1Q7iX
第一次用OpenGL开发游戏，虽然之前做Minecraft Mod的时候也接触过一点，但是还是深有感触，因为有了更多的知识储备，所以学到了更多的东西。
其实这本来就是个高程的Project而已啦，只是灵感到了就想认认真真做出一个游戏出来，做完成就感MAXMAX！
期间抠图还学习用python自动化处理，还有解包游戏之类的，虽然很麻烦，但还是很有趣的。
幸好暑假的时候用Unity做了Flappy Paimon，对游戏引擎的大概框架有了一定了解，让我做这个游戏的时候更加得[……]
本文为记录在南京大学转专业到计算机科学与技术系的历程，以及给在南大同样想转专业到计算机科学与技术专业的学弟学妹们分享经验。
本人由于提前批的原因，只能在大二转专业，但转专业考核都是和大一一起的，没什么区别。
计算机科学与技术系可谓十分热门，每年基本都是爆满状态，即使报名人数少于分配名额，也会秉持“宁缺毋滥”的原则进行淘汰。并且，转专业考试的难度可以用困难来形容。
因此，如果想要转专业到计算机科学与技术系，要做好充足的前期准备，才能考好这场转专业考试。
首先，是自身的前提条件。如果是零基础的话，我不建议转专业，计科的课程的难度比较大，零基础学习[……]
初学一周不到的Unity处女作。
暑假想着学者做点游戏吧！于是开始了Unity的学习。
Unity还挺好用的，有一堆轮子，可惜国内网上的资源太少了，真要搜还得Google一下。
灵感来源于原神拜年纪的开场动画，就把它复刻了下来。
素材来源：
https://www.bilibili.com/video/BV15v411e7ne
https://www.bilibili.com/video/BV1F54y1n7KR
下载地址：
https://github.com/BakaSea/FlappyPaimon/releases/tag/0.1[……]
\(对查询的边x，分为两种情况 \)
\(第一种，x为最大边，只需要找离x最近且比x小的两条边判断a+b>x就够了，此处可用multiset \)
\(第二种，x不是最大边，那么需要找到一个b，使得b \geq x，b-a<x \)
\(可用平衡树或线段树进行维护，此处用动态开点线段树来解决 \)
\(区间[l, r]权值为min_{x_i \in [l, r]}\{x_i-x_{i-1}\} \)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
#include <stdio.h> #include <set> #include <algorithm> #define INF 1000000010 #define MAXN 200010 using namespace std; multiset<int> up; multiset<int, greater<int> > down; int Q, cnt, rt; struct Node { int val, lc, rc; } t[50*MAXN]; void modify(int& p, int l, int r, int x, int d) { if (!p) { p = ++cnt; t[p].val = INF; } if (l == r) { t[p].val = d; return; } int mid = ((long long)l + (long long)r) >> 1; if (x <= mid) modify(t[p].lc, l, mid, x, d); if (x > mid) modify(t[p].rc, mid + 1, r, x, d); t[p].val = min(t[t[p].lc].val, t[t[p].rc].val); } int query(int& p, int l, int r, int ll, int rr) { if (!p) { p = ++cnt; t[p].val = INF; } if (ll <= l && r <= rr) { return t[p].val; } int mid = ((long long)l + (long long)r) >> 1, ans = INF; if (ll <= mid) ans = min(ans, query(t[p].lc, l, mid, ll, rr)); if (rr > mid) ans = min(ans, query(t[p].rc, mid + 1, r, ll, rr)); return ans; } int main() { scanf("%d", &Q); up.insert(-INF); up.insert(INF); up.insert(-INF); up.insert(INF); down.insert(-INF); down.insert(INF); down.insert(-INF); down.insert(INF); t[0].val = INF; for (int i = 1, opt, x; i <= Q; ++i) { scanf("%d%d", &opt, &x); if (opt == 1) { int y1 = *up.lower_bound(x), y2 = *down.lower_bound(x); up.insert(x); down.insert(x); modify(rt, 1, INF, x, x - y2); if (down.count(y1) <= 1) modify(rt, 1, INF, y1, y1 - x); } else if (opt == 2) { multiset<int>::iterator iter1 = up.find(x); up.erase(iter1); int y1 = *up.upper_bound(x); multiset<int, greater<int >>::iterator iter2 = down.find(x); down.erase(iter2); int y2 = *down.lower_bound(x), y3; if (down.count(y2) <= 1) y3 = *down.upper_bound(y2); else y3 = *down.lower_bound(y2); modify(rt, 1, INF, x, INF); if (down.count(y1) <= 1) modify(rt, 1, INF, y1, y1 - y2); if (y2 != -INF) modify(rt, 1, INF, y2, y2 - y3); } else { int b = *down.lower_bound(x), cb = down.count(b), a; if (cb > 1) a = b; else a = *down.lower_bound(b - 1); if (a != -INF && a + b > x) { printf("Yes\n"); } else { int d = query(rt, 1, INF, x, INF); if (d != INF && d < x) { printf("Yes\n"); } else { printf("No\n"); } } } } return 0; } |
\(很明显，记叶子节点数为s，则k=\left \lceil \frac{s}{2} \right \rceil \)
\(那么如何匹配呢？首先要选取一个非叶子节点作为根，然后对其进行dfs得到dfs序\)
\(按照dfs序大小排序得到叶子节点u_1, u_2, …, u_s \)
\(于是u_i跟u_{i+\frac{s}{2}}进行匹配，若s为奇数，则最后一个点跟根节点进行匹配 \)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include<stdio.h> #include<string.h> #include<vector> #include<algorithm> #define MAXN 200010 using namespace std; struct Edge { int u, v, next; } e[2*MAXN]; int n, h[MAXN], vis[MAXN], dfn[MAXN], d[MAXN], cnt, rt, rd; vector<int> res; void addEdge(int num, int u, int v) { e[num].u = u; e[num].v = v; e[num].next = h[u]; h[u] = num; } void dfs(int u) { vis[u] = 1; dfn[u] = ++cnt; for (int i = h[u]; i; i = e[i].next) { if (!vis[e[i].v]) { dfs(e[i].v); } } } int cmp(const int &a, const int &b) { return dfn[a] < dfn[b]; } int main() { scanf("%d", &n); for (int i = 1, u, v; i < n; ++i) { scanf("%d%d", &u, &v); d[u]++; d[v]++; addEdge(i, u, v); addEdge(i+n, v, u); } for (int i = 1; i <= n; ++i) { if (d[i] > rd) { rt = i; rd = d[i]; } if (d[i] == 1) { res.push_back(i); } } dfs(rt); sort(res.begin(), res.end(), cmp); printf("%d\n", (res.size()+1)/2); for (int i = 0; i < res.size()/2; ++i) { printf("%d %d\n", res[i], res[i+(res.size()+1)/2]); } if (res.size() & 1) { printf("%d %d\n", rt, res[res.size()/2]); } return 0; } |
\(对每个s_i的前缀s_{i, 1…j}进行与所有后缀比较，相同的次数记为res_{i,j}，此处可以用哈希进行比较 \)
\(因为要取最大前缀，所以要用kmp求出next数组后res_{i,next[j]} -= res_{i, j}，注意一下下标的偏移 \)
\(答案就是\Sigma_{i=1}^n\Sigma_{j=1}^{len_i}j^2res_{i,j} \)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <string> #include <iostream> #include <string.h> #include <unordered_map> #define MOD 998244353 #define MAXN 100010 #define MAXS 1000010 #define LL long long using namespace std; int n, nt[MAXS]; LL ans, res[MAXS]; string s[MAXN]; unordered_map<unsigned long long, LL> cnt; int main() { cin >> n; for (int i = 1; i <= n; ++i) { cin >> s[i]; unsigned long long x = 0, p = 1; for (int j = s[i].size() - 1; j >= 0; --j) { x += (s[i][j] - 'a' + 1) * p; cnt[x]++; p *= 233; } } for (int i = 1; i <= n; ++i) { unsigned long long x = 0, p = 1; for (int j = 0; j < s[i].size(); ++j) { x = x * 233 + s[i][j] - 'a' + 1; res[j + 1] = cnt[x]; p *= 233; } for (int j = 1; j < s[i].size(); ++j) { int k = nt[j - 1]; while (k && s[i][k] != s[i][j]) k = nt[k - 1]; if (s[i][k] == s[i][j]) k++; nt[j] = k; } for (int j = 1; j <= s[i].size(); ++j) { res[nt[j-1]] -= res[j]; } for (int j = 1; j <= s[i].size(); ++j) { ans = (ans + (((1LL * res[j] * j) % MOD) * j) % MOD) % MOD; } } printf("%lld\n", ans); return 0; } |
\(令c_i=min_{1\leq i < j, t_j=t_i}\{j-i\} \)
\(B数组其实就是c_1 c_2 c_3 … c_n的后缀数组 \)
\(要注意若没有t_j=t_i，则c_i = n，同时c_{n+1} = n+1 \)
\(答案就是后缀数组的逆序 \)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<stdio.h> #include<iostream> #include<string.h> #define MAXN 100010 using namespace std; int n, sa[MAXN], rk[MAXN], oldrk[MAXN], id[MAXN], px[MAXN], cnt[MAXN], s[MAXN]; char str[MAXN]; void buildSA() { memset(cnt, 0, sizeof(cnt)); int m = n, *x = rk, *y = oldrk; for (int i = 1; i <= n; ++i) ++cnt[x[i] = s[i]]; for (int i = 1; i <= m; ++i) cnt[i] += cnt[i-1]; for (int i = n; i >= 1; --i) sa[cnt[x[i]]--] = i; for (int w = 1, p; w < n; w <<= 1) { p = 0; for (int i = n; i > n-w; --i) id[++p] = i; for (int i = 1; i <= n; ++i) { if (sa[i] > w) id[++p] = sa[i]-w; } memset(cnt, 0, sizeof(cnt)); for (int i = 1; i <= n; ++i) ++cnt[px[i] = x[id[i]]]; for (int i = 1; i <= m; ++i) cnt[i] += cnt[i-1]; for (int i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i]; swap(x, y); p = 0; for (int i = 1; i <= n; ++i) { x[sa[i]] = y[sa[i]] == y[sa[i-1]] && y[sa[i]+w] == y[sa[i-1]+w] ? p : ++p; } if (p >= n) break; m = p; } } int main() { while (scanf("%d", &n) != EOF) { scanf("%s", str+1); int pa = 0, pb = 0; for (int i = n; i >= 1; --i) { if (str[i] == 'a') { s[i] = !pa ? n : pa-i; pa = i; } else { s[i] = !pb ? n : pb-i; pb = i; } } n++; s[n] = n; buildSA(); for (int i = n-1; i >= 1; --i) printf("%d ", sa[i]); printf("\n"); } return 0; } |
相信不少人轻松灭掉 1,2 两题（蒟蒻无视此句） ，我相信，大家对物理也是很有兴趣的（众人：我们对揍人也是很有兴趣的） ，那么，再奉上 100 分给Physicaler 们。
现给定一个电阻网络，已知其中每条边上的电阻，和若干个点和负极之间的电压（电源电压不变） ，现在求任意两点之间的电压。
第一行三个数n,m,k,q，表示n个节点（可能是几个点用导线相连接，与一个点等价，编号为1-n，0号节点为电源负极），m个定值电阻，每个定值电阻连接两个点，k表示电源正极有k个接口，有q个询问。
以下k行，每行两整数，表[……]
三分法适合求解凸性函数的极值问题
\(设当前求解的区间为[l, r]，令lmid = l+\frac{r-l}{3}，rmid = r-\frac{r-l}{3}，计算f(lmid), f(rmid)\)
将其中函数值更优的点叫做好点，函数值较差的点叫做坏点
最优点与好点会与坏点同侧，据此缩小区间
\(因为a≥0，所以S是开口向上的二次函数，F(x)=\max \{S_{i}(x)\} 也满足单调性，可用三分法求其区间最小值\)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include<stdio.h> #define MAXN 10010 #define eps 1e-8 #define max(a, b) ((a) > (b) ? (a) : (b)) int T, n, a[MAXN], b[MAXN], c[MAXN]; double cal(double x) { double k = -2147483647; for (int i = 1; i <= n; ++i) k = max(k, a[i]*1.0*x*x+b[i]*1.0*x+c[i]*1.0); return k; } int main() { scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d%d%d", &a[i], &b[i], &c[i]); double l = 0, r = 1000; while (r-l > eps) { double lmid = l+(r-l)/3, rmid = r-(r-l)/3; if (cal(lmid) < cal(rmid)) r = rmid; else l = lmid; } printf("%.4lf\n", cal(r)); } return 0; } |
\(二分答案，判断是否存在长度不小于L的字段，平均数不小于二分的值\)
\(如果把数列中每个数都减去二分的值，就转化为判定是否存在一个长度不小于L的子段，子序列和非负\)
\(用前缀和维护数列，就可用O(1)的时间查询平均数\)
\(这题由于精度问题，需要先将读入的数乘上1000再整数二分……乘完之后还要开long long\)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include<stdio.h> #define MAXN 100010 #define INF 2147483647 #define min(a, b) ((a) < (b) ? (a) : (b)) #define max(a, b) ((a) > (b) ? (a) : (b)) int n, L, l, r = -INF, a[MAXN]; long long sum[MAXN], b[MAXN]; int main() { scanf("%d%d", &n, &L); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); a[i] *= 1000; r = max(r, a[i]); } while (l <= r) { int mid = (l+r) >> 1; long long x = -INF, ms = INF; for (int i = 1; i <= n; ++i) b[i] = a[i]-mid; for (int i = 1; i <= n; ++i) sum[i] = sum[i-1]+b[i]; for (int i = L; i <= n; ++i) { ms = min(ms, sum[i-L]); x = max(x, sum[i]-ms); } if (x >= 0) l = mid+1; else r = mid-1; } printf("%d", r); return 0; } |