In mathematics you don't understand things, you just get used to them.

分类 笔记 下的文章

定义

中心场问题中一个守恒量。定义:$\mathbf{A}=\mathbf{p}\times\mathbf{L}-mk\hat{\mathbf r}$,其中 $\mathbf p$ 是动量, $\mathbf L$ 是角动量,$m$ 是物体质量,$k$ 是平方反比中心场的一个参量,比如对于万有引力问题,$k = GMm$,$\hat{\mathbf r}$ 是位矢的单位。下面证明其守恒性:

守恒性

我们想要证明 $\dot{\mathbf A} = \mathbf 0$,也就是 $\dot{\mathbf A} = \dot{\mathbf p}\times \mathbf L - mk\dot{\hat{\mathbf r}} = \mathbf 0$。

  • $\dot{\mathbf p}$:$\dot{\mathbf p} = \mathbf F = -\frac k{r^2}\hat{\mathbf r}$;
  • $\dot{\hat{\mathbf r}} = \dot{\hat\theta}\hat{\mathbf\theta}$;
  • $\mathbf L = \mathbf r \times m\mathbf v = m(r\hat{\mathrm r})\times(\dot r\hat{\mathbf r}+r\dot\theta\hat{\mathbf\theta})=mr^2\dot\theta\hat{\mathbf n}$.

因此

$$ \begin{align} \dot{\mathbf A} & = (-\frac k{r^2}\hat{\mathbf r})\times \mathbf F - mk\hat{\dot\theta}\hat\theta \\ & = -\frac k{r^2}\hat{\mathbf r}\times(mr^2\dot\theta\hat{\mathbf n})-mk\dot{\hat{\mathbf\theta}}\hat{\mathbf\theta} \\ & = -mk\dot\theta(\hat{\mathbf r}\times\hat{\mathbf n}+\hat{\mathbf\theta}) \\ & = \mathbf 0 \end{align} $$

Q.E.D.

应用

目前只见过用于证明开普勒第一定律,即天体运动的相对运动轨迹为圆锥曲线,或者数学地 $r=\frac p{1+\varepsilon\cos\theta}$。具体证明考虑 $\mathbf A \cdot\mathbf r$ 即可。

Hasty Generalisation

A.k.a. the over-generalisation fallacy. An informal fallacy wherein a conclusion is drawn about all or many instances of a phenomenon on the basis of one of a few instances of that phenomenon.

E.g. Stereotype.

ad hominem

Latin for 'to the person', short for argumentum ad hominem. In accordance with Whately, ad hominem arguments are "addressed to the peculiar circumstances, character, avowed opinions, or past conduct of the individual".

Some voices, however, argue that ad hominem arguments are not necessarily fallacy, that in some instances, questions of personal conduct, character, motives, etc., are legitimate and relevant to the issue, as when it directly involves hypocrisy, or actions contradicting the subject's words, according to Walton (Who the hell is this dude).

E.g. Fuck you wronglie ass.

Bandwagon Appeal

In Latin argumentum ad populum, meaning 'appeal to the people'. A fallacious argument which is based on claiming a truth or affirming something is good or correct because many people think so.

Some voices, however, argue that argumentum ad populum arguments are not necessarily fallacy, such as in political dialogue within a democracy, according to Walton (Yes the same dude. He must be good at critical thinking).

Red Herring

A red herring is something that misleads or distracts from a relevant or important question.

E.g. tI think we should make the academic requirements stricter for students. I recommend you support this because we are in a budget crisis, and we do not want our salaries affected.

Straw Man

A straw man fallacy (sometimes written as strawman) is the informal fallacy of refuting an argument different from the one actually under discussion, while not recognizing or acknowledging the distinction.[1] One who engages in this fallacy is said to be "attacking a straw man".

Slippery Slope

Post hoc ergo propter hoc

Begging the Question

False Dichotomy

Association fallacy

我最近从 Windows 转到了 Linux 环境,主要是为了一些方便的工具,主要是 Vim 啦。我当然知道 Windows 下可以使用 Vim,但我发现 Windows 和 Linux 下这货的配置竟然不一定相通。举个例子,我习惯将 { 映射成行内补全和换行补全,再通过 O 来进行自动缩进。Windows 下这个配置失效了,应该是 Bram 老头子生前留下的 bug 吧。于是为了更加原生的 Vim 体验,抱着学习下新系统的目的,我给这台我初二时买的惠普笔记本装上了 Windows 和 Linux 双系统。

Linux 的头一等大事无非是命令行配置了!我本来比较喜欢 Mac 的 Fig 终端(主要是通过 AI 将自然语言转为命令行脚本的功能让人垂涎呐),可惜 Linux 下想要使用还得加入内测名单,实在麻烦。于是我就开始使用 fish 作为主要的终端。不得不说,用了这类 Shell 环境,再叫我用回原生 UNIX 命令行可就难了!

首先有两个前置技巧:1) 两点间的最短距离就是直接连接两点的边的长度;2) 遍历一个子图的最小花费是最小生成树的边权之和乘二。原问题让我们找出一条最短且必经过钦定边的 $( s, i )$ 路径,那么我们先将 $\lang s , i \rang$ 连上,问题就变成了找出一条最短且必经过钦定边 $( s, i)$ 的回路。虽然每条边不一定恰好经过一次,但是对于正确性的判断,每个点的度数为偶数依然是一个必要条件,再加上连通性的限制,一条回路的正确性就可以由这两条必要条件充要表示。

其次来考虑如何修复每个点度数的奇偶性,一个贪心策略是把一条 $(s, i)$ 拆成 $(s, s+1), (s+1, s+2) \dots (i-1, i)$,由于边权的性质,可以发现这样拆分一定不劣;又考虑连通性修复,类似以上。

const int MN = 2.5e3;
int n, m, s, fa[MN + 100], deg[MN + 100];
int find(int u) {
    while (u != fa[u]) u = fa[u] = fa[fa[u]];
    return u;
}
bool unite(int u, int v) {
    if (find(u) != find(v)) {fa[find(u)] = find(v);return 1;}
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m >> s; s --;
    iota(fa, fa+n, 0);
    ll res = 0;
    rep(m) {
        int u, v;cin >> u >> v;u--;v--;
        deg[u] ++ , deg[v] ++;
        res += abs(u - v);
        unite(u, v);
    }
    vi tmp(fa, fa+n);
    rep(n) {
        deg[s] ++ , deg[i] ++;
        unite(s, i);
        vi id;
        rep(j,n) if (deg[j]%2) id.pb(j);
        ll sum = 0;
        rep(j,intsz(id)-1) {
            rep(k,id[j],id[j+1]) unite(k, k+1);
            sum += id[j+1]-id[j];
            j++;
        }
        vi from, to; vi().swap(id);
        rep(j,n) if (deg[j] > 0) id.pb(j);
        rep(j,intsz(id)-1) from.pb(id[j]), to.pb(id[j+1]);
        vi(intsz(to)).swap(id);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](int x, int y) {
            return to[x]-from[x]<to[y]-from[y];
        });
        for (int j : id) {
            if (unite(from[j], to[j])) sum += 2*(to[j]-from[j]);
        }
        cout<< res + sum << " \n"[i==n-1];
        deg[s] -- , deg[i] --;
        rep(j,n) fa[j] = tmp[j];
    }
}
/*
急
|
|
速
|
|
地
|
|
下
|
|
坠
|
|
*/

我说怎么 T2 被暴切,原来大家都做过这道题,这下是 🤡 了。

Desc.

Link.

有 $m$ 次事件,和一个初始为空的双端队列,格式如下:

  • IF w v:$\text{PUSH-FRONT}(w, v)$;
  • IG w v:$\text{PUSH-BACK}(w, v)$;
  • DF:$\text{POP-FRONT}$;
  • DG:$\text{POP-BACK}$;
  • QU l r:询问在当前队列中选取若干二元组 $S$,使得 $\sum w \in S \bmod p \in [l, r]$,且 $\sum v \in S$ 最大。

$m \leqslant 5 \times 10^4$,$p \leqslant 500$。

Sol.

朴素 DP 很容易,设 $f_{i, s}$ 表示前 $i$ 个元素中,$w$ 和模 $p$ 的余数为 $s$ 的最大 $v$ 和。关键是如何维护双端队列的操作。

如果维护的数据结构是栈,那么这个题就变得很容易了,恰好,我们有用栈实现双端队列的方法,以下是 tly 的解说:

至少支持:双端插入删除(删除时非空),维护半群运算(只有结合律),做到均摊 $\mathcal O(n)$ 次运算。

比如双端插入删除元素,求矩阵乘或者 min 之类的不可减信息。

……

具体做法是维护两个栈,分别用于前端插入删除/后端插入删除。这个时候就是「插入同端删除,也即可撤回」的情况了。

如果一个栈空了,这个时候就不能直接把另一个栈弄过来。

考虑将另一个栈的元素按中点划分开,分别装入两个栈,这样复杂度是均摊 $\mathcal O(n)$。
39
具体原因考虑势能函数 $\Phi = |size_1 - size_2|$,每次 $\Phi$ 至多增加 $1$,重构则清零(或变成 $1$),因此复杂度均摊下来线性。

(有删改)

代码很简洁。

int __tmp, m, p, w[2][50100], v[2][50100], top[2], q[600];
ll dp[2][50100][600];
string op;
void insert(int a, int b, int f) {
    w[f][++top[f]] = a, v[f][top[f]] = b;
    for (int i=0;i<p;++i)
        dp[f][top[f]][(i+a)%p] = max(dp[f][top[f]-1][i]+b, dp[f][top[f]-1][(i+a)%p]);
}
void remove(int f) {
    if (top[f] == 0) {
        int tmp = top[f^1];
        top[0] = top[1] = 0;
        for (int i=(tmp+1)/2;i>=1;--i) insert(w[f^1][i], v[f^1][i], f);
        for (int i=(tmp+1)/2+1;i<=tmp;++i) insert(w[f^1][i], v[f^1][i], f^1);
    }
    top[f]--;
}
ll ask(int l, int r) {
    ll res = -1, *f = dp[0][top[0]], *g = dp[1][top[1]];
    int h = 1, t = 0;
    for (int i=r;i>=l;--i) {
        while (h <= t && g[i] >= g[q[t]]) t--;
        q[++t] = i;
    }
    for (int i=0;i<p;++i) {
        while (h <= t && ((i+q[h])%p < l || (i+q[h])%p > r)) h++;
        while (h <= t && g[(l+p-i)%p] >= g[q[t]]) t--;
        q[++t] = (l+p-i)%p;
        cmax(res, f[i]+g[q[h]]);
    }
    return res;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    for (int i=0;i<2;++i)
        memset(dp[i][0]+1, 0xcf, sizeof dp[i][0]);
    cin >> __tmp >> m >> p;
    for (int a, b; m--;) {
        cin >> op;
        if (op[0] == 'I' || op[0] == 'Q') cin >> a >> b;
        if (op == "IF") insert(a%p, b, 0);
        else if (op == "IG") insert(a%p, b, 1);
        else if (op == "DF") remove(0);
        else if (op == "DG") remove(1);
        else cout << ask(a, b) << "\n";
    }
}

我既没有愁苦到足以成为诗人,又没有冷漠到像个哲学家。但我清醒到足以成为一个废人。

—— E·M·齐奥朗 - 眼泪与圣徒