Ftt2333's Nest

基于公招的龙门币清空计算程序

创建于2024-02-17

代码

#include <bits/stdc++.h>
using namespace std;

constexpr int maxv = 1e5 + 10, maxn = 40;

int n = 36, a[] = {0, 140, 210, 280, 350, 161, 231, 301, 371, 182, 252, 322, 392, 203, 273, 343, 413, 280, 350, 420, 490, 322, 392, 462, 532, 364, 434, 504, 574, 518, 588, 658, 728, 602, 672, 742, 812};
int f[maxv], pre[maxv];

int main() {
  f[0] = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = a[i]; j < maxv; ++j) {
      if (f[j - a[i]]) f[j] = 1, pre[j] = i;
    }
  }
  cout << "Please input your current resource quantity: ";
  int cur; cin >> cur;
  vector<int> ans;
  if (f[cur]) ans.emplace_back(cur);
  for (int i = cur + 1000; i <= min(maxv - 1, cur + 10000); i += 500) {
    if (f[i]) ans.emplace_back(i);
  }
  cout << "Possible amount(s):";
  for (auto e : ans) cout << ' ' << e;
  cout << "...\n";
  cout << "Please choose on of these numbers: ";
  cin >> cur;
  while (cur) {
    int id = pre[cur], h = (id - 1) / 4 + 1, tags = id - h * 4 + 4;
    cout << '#' << id << ": " << h << " hour(s) with " << tags << " tag(s), cost " << a[id] << ".\n";
    cur -= a[pre[cur]];
  }
}

NOIP游记

创建于2023-11-20

MORE...

Day -1

打隔膜（上午和 cxy，5ab，lzytag 打泰拉，下午玩德扑）。

Day 0

场上：T1 shaber 题，T2 shaber 题，T3T4 看了一眼不太会果断打暴力，然后有点困，直接开摆，估分 $280$ 。

Day $\mathbb{N}^+$

云斗估分 $100+100+35+36=271$ 。
队线估计 $400pts$ ，果断退役。

后继：退役机会被我妈截胡了，强制拖延到省选。

鲜花4

创建于2023-11-06

MORE...

讲个故事：

男人去砍柴，在卧石山遭到一只狗袭击，那狗生得膀大腰圆，面目可憎，而且力大如牛。
男人腿被咬伤，费了好大劲才逃下山。小镇的大夫帮他包扎好伤口，他十分感激，对大夫道谢“万言胜万德”
一旁众人看他伤得这么重，忍不住问他被什么东西咬了，男人回答道“卧石山里灵活的狗。”说罢，他管村民借了打狗棒，就要去找狗算账。
有村民拦住他，问他那狗长什么样。
男人回忆着描述:“圆身，憎模，牛力……”
“哎呀，这就对了，我就说什么狗能把人咬成这样。”那老者恍然大悟，他知道那狗也是仗着人势，赶紧劝男人绕着它走“这是倭门元稹的狗，下次记得别明出路。”
其他人也跟着劝:“蜿蜒山弯的，远甚，弃动！”
但男人不为所动，他摇摇头“怨深，岂懂？”
其他人见拦不住，纷纷叹道:“枉怨生太多导致的，怨来逆言挽怨深！”

鲜花3

创建于2023-11-06

MORE...

以下内容可能引起不适

科学知识源于对客观真实的了解，自然规律的认识；
所以说，只有符合自然规律和客观真实的观念和理论，才能算是科学知识。

违反了科学规律和客观真实的观念和理论，都不能算是科学知识，只能算是错误的理论；
一，相对论是唯心主义的产品，它严重的违反了自然规律和客观真实。所以，它不能算是科学知识，只能算是唯心主义的理论；
二，大爆炸理论也是唯心主义产品，它也严重的违反了自然规律和客观真实。所以，它也不能算是科学知识，只能算是唯心主义的产品；
三，《群论》在三等分角上的论点是错误的，是脱离了几何规律和几何的客观实际，主观的采用代数形式和代数公式，来进行左偏的间接证明，这种左偏的间接证明带有很强的主观性。所以，它只能是错误的理论；
四，调和级数发散理论，也是违反了数学规律和客观真实的错误理论。因为它采用的是违反数学规律和逻辑规律的间接类比似的证明，这样的证明带有很强的主观性，所以，它只能是错误的理论；
五，美国对费马猜想的百页证明，也是错误的，因为它违反了费马的精简、美妙、大半页纸的证明要求。他采用的也是间接的一环扣一环的复杂证明，它里面的一些新理论本身就没有确定性的，本身就需要用数学规律来证明，用一些不确定和没有得到数学规律证明的理论，来证明费马猜想，本身就是有问题的。
......
所以说，它们都不能算是科学知识，只能算是错误的理论和唯心主义的理论。

伪科学在科学规律和客观真实的面前，是不堪一击的。
符合科学规律和客观真实的理论，是没有办法否定的。

错误的理论和唯心主义的理论，是不能算科学知识的，只能算是伪科学。

你们要认为它们是科学知识，就必须要用科学规律和客观真实来证明它们是科学知识；
如果你们没有丝毫的科学能力，证明它们是科学知识，就只能老老实实的承认，它们就是伪科学！

——转载自《民科吧》

csp游记

创建于2023-11-04

MORE...

Day -1

打隔膜（Track mania，CS2）。

Day 0

上午：打隔膜，水 B 站。
场上：T1 shaber 题，T2 模拟赛我拉过，T3 shaber 题，T4 shaber 题。

Day $\mathbb{N}^+$

luogu 估分 $100+100+100+80=380$ 。
正式出分： $100+100+100+100=400$ 。
进入 AK 者联盟，喜提 200RMB，约 $3$ 桶球。

水题乱做-2

创建于2023-11-04

MORE...

Here's something encrypted, password is required to continue reading.

洛谷-P5538

创建于2023-10-07

MORE...

提供一个模拟赛场上的思路。

题目大意

给你一颗树，点有点权，你需要求出下列式子模 $786433$ 的值（ $786433$ 是质数且有原根 $10$ ）：
$\sum_{1\leq u\leq v\leq n}f(u,v)^{f(u,v)}$
其中 $f(u,v)$ 表示 $u$ 到 $v$ 的最短路径上所有点的点权按位与在一起之后的值。
保证 $n\cdot d\le 2\times10^6$ ，其中 $d$ 是叶子个数。

解题思路

首先考虑一个比较暴力的想法，枚举路径的起点 $u$ ，显然，任意一条路径都是 $u$ 到叶子的路径一个前缀，所以以 $u$ 为起点不同权值的路径最多只有 $d\log V$ 种。
如果能快速找到这些终点就可以做到 $O(nd\log V)$ 的时间复杂度。
我们考虑把度数 $\neq2$ 的点作为关键点建虚树，显然虚树上的边就是原树上的一条路径，把边内部的单独算掉，剩下的就是要经过至少一个关键点的路径。
显然是由一条边的前缀再拓展出去，那么本质不同的起点就是 $\min(d\log V,n)$ 个，然后本质不同的终点也只有 $\min(d\log V,n)$ ，直接枚举即可。
可以预处理线性对数做到 $O(1)$ 求幂。

代码实现

Code

constexpr int maxn = 2e5 + 10, maxm = 510, mod = 786433;
constexpr int base = 1 << 30;

int a[maxn], pw[mod], dlog[mod];
int n, m, id[maxn], rnk[maxn];
vector<int> g[maxn];
struct E {
  int v;
  vector<int> a;
  vector<pair<int, int>> pre;
};
vector<E> ed[maxn]; 

vector<int> cur;
void dfs(int x, int fa, int rt) {
  if (g[x].size() != 2 && rt != x) {
    ed[id[rt]].emplace_back(E{id[x], cur});
    return;
  }
  if (x != rt) cur.emplace_back(a[x]);
  for (int y : g[x]) if (y != fa) dfs(y, x, rt); 
  if (x != rt) cur.pop_back();
}

void init() {
  pw[0] = 1; for (int i = 1; i < mod - 1; ++i) pw[i] = 10 * pw[i - 1] % mod;
  for (int i = 0; i < mod - 1; ++i) dlog[pw[i]] = i;
}

int qpow(int a, int b) {
  a %= mod; if (!a) return 0;
  b %= mod - 1; b = 1ll * b * dlog[a] % (mod - 1);
  return pw[b];
}

int calc(int x) {
  int A = base - 1 - x % base;
  int O = x / base;
  if (!A) return 0;
  return qpow(A, A);
}

int case1(vector<int> a) {
  ll ans = 0;
  vector<pair<int, int>> cur;
  for (int x : a) {
    for (auto &e : cur) e.first |= x;
    cur.emplace_back(x, 1);
    vector<pair<int, int>> nxt;
    for (auto e : cur) {
      if (nxt.empty() || nxt.back().first != e.first) nxt.emplace_back(e);
      else nxt.back().second += e.second;
    }
    cur = nxt;
    for (auto e : cur) ans += 1ll * calc(e.first) * e.second % mod;
  }
  return ans % mod;
}

vector<pair<int, int>> res;

void findres(int x, int fa, int cur) {
  if (base - 1 - cur % base == 0) return;
  cur |= a[rnk[x]];
  res.emplace_back(cur, 1);
  for (auto &e : ed[x]) if (e.v != fa) {
    int tmp = cur;
    for (auto &p : e.pre) tmp |= p.first, res.emplace_back(tmp, p.second);
    findres(e.v, x, tmp);
  }
}

int main() {
  init(); n = read();
  for (int i = 1; i <= n; ++i) a[i] = base - 1 - read();
  for (int i = 1; i < n; ++i) {
    int u = read(), v = read();
    g[u].emplace_back(v); g[v].emplace_back(u);
  }
  for (int i = 1; i <= n; ++i) if (g[i].size() != 2) id[i] = ++m, rnk[m] = i;
  for (int i = 1; i <= n; ++i) if (g[i].size() != 2) dfs(i, 0, i);
  for (int x = 1; x <= m; ++x) {
    for (auto &e : ed[x]) {
      int cur = 0;
      vector<pair<int, int>> tmp;
      for (auto k : e.a) cur |= k, tmp.emplace_back(cur, 1);
      for (auto p : tmp) {
        if (e.pre.empty() || e.pre.back().first != p.first) e.pre.emplace_back(p);
        else e.pre.back().second += p.second;
      }
    }
  }
  ll ans1 = 0;
  for (int x = 1; x <= m; ++x) {
    for (auto &e : ed[x]) {
      ans1 += case1(e.a);
    }
  }
  ans1 = 1ll * ans1 * (mod + 1 >> 1) % mod;
  ll ans2 = 0;
  for (int i = 1; i <= m; ++i) {
    res.clear();
    findres(i, 0, 0);
    for (auto e : res) ans2 += 1ll * calc(e.first) * e.second % mod;
  }
  for (int x = 1; x <= m; ++x) {
    for (auto &e : ed[x]) {
      res.clear();
      findres(x, e.v, 0);
      for (auto p : e.pre) {
        for (auto q : res) {
          ans2 += 1ll * calc(p.first | q.first) * p.second % mod * q.second % mod;
        }
      }
    }
  }
  for (int i = 1; i <= m; ++i) ans2 += calc(a[rnk[i]]);
  ans2 = 1ll * ans2 * (mod + 1 >> 1) % mod;
  write((ans1 + ans2) % mod), pc(10);
}

鲜花2

创建于2023-10-06

MORE...

太恐怖了，羽毛球打四人南，发了个侧旋，对面一个拔北，然后就十莲宝灯把我飞了。
第二局对面开局小球发大了，差点就达成十三个孤儿，结果对面自摸，又被飞了。

图论相关

创建于2023-09-23

MORE...

生成树

本文不会使用拟阵相关知识。

引理 1

对于一张图 $G$ ，以及她的两颗生成树 $T_1,T_2$ ，对于任意一条边 $e\in(T_1-T_2)$ ，必定存在一条边 $e'\in(T_2-T1)$ ，满足 $T_1-\{e\}+\{e'\}$ 和 $T_2-\{e'\}+\{e\}$ 都是 $G$ 的生成树。
证明：
先考虑第二个条件，显然，把 $e=(u,v)$ 加入 $T_2$ 后会与 $T2$ 中 $u$ 到 $v$ 的路径 $p$ 形成一个环，而 $e'$ 一定属于 $p$ 。
然后考虑第一个条件，将 $e$ 从 $T_1$ 中去掉之后会形成两个连通块，而因为 $p$ 连接了两个连通块，所以 $p$ 至少有一条边会横跨两个连通块，显然这样的边是合法的。

引理 2

对于任意一颗最小生成树 $T$ ，她的第 $i$ 小的边是所有生成树里最小的。
考虑另一颗生成树 $T'$ ，我们找到引理 1 中的 $e$ 和 $e'$ ，由于 $T$ 是最小生成树，所以 $w(e)\le w(e')$ ，然后将 $T'$ 变为 $T'-\{e'\}+\{e\}$ 。
然后不断执行这个操作直到最终 $T'$ 变为 $T$ ，由于操作中只会把大的边变小，所以 $T'$ 里第 $i$ 小的边都大于等 $T$ 中的第 $i$ 小。由此可知，所有最小生成树的边权的集合都相同。

引理 3

对于所有的最小生成树，边权小于 $w$ 的所有边的连通性是一样的，很明显如果连通性不一样，就可以并起来，那么第 $i$ 小的边就不是所有生成树中最小的，与引理 2 矛盾。

最小生成树

根据引理 3，很明显 Kruskal 的做法就是正确的。

严格次小生成树

泰斯特

创建于2023-09-21

MORE...

Here's something encrypted, password is required to continue reading.

基于公招的龙门币清空计算程序

NOIP游记

Day -1

Day 0

Day N+\mathbb{N}^+N+

鲜花4

鲜花3

csp游记

Day -1

Day 0

Day N+\mathbb{N}^+N+

水题乱做-2

洛谷-P5538

题目大意

解题思路

代码实现

鲜花2

图论相关

生成树

引理 1

引理 2

引理 3

最小生成树

严格次小生成树

泰斯特

Day $\mathbb{N}^+$

Day $\mathbb{N}^+$