征集模板题

2018-12-15 23:29:13 By eeeeeericKKK

你也许已经注意到,最近 nflsoj 出现了一道新的模板题:多项式复合逆。如果你不知道这是啥没关系,你只要知道这是杨主力 @fizzydavid 的题就行啦!

杨主力拥有 $10$ 个模板题位置,现在已经在路上或确定好的 idea 有下面几个:(立个flag不会鸽

Lyndon分解,周期串拆分,回文串拆分,Trie上回文树,基本子串字典(Internal Pattern Matching),多项式复合逆

如果你有什么好的模板题,欢迎在这篇博客下评论或者私戳,可以占这 $10$ 个坑,也可以问OJ管理员 @TRCYX 和 @diamond_duke 要空题(既然要了就自己造吧)。占了空题位之后,造数据和写题面的过程可以找几个人一起分锅,标程最好能自己提供。

为了鼓励大家踊跃造题,每贡献一个被认可的idea并出成题目,将获得多项式板子一个。

当然,模板题有一些要求:

  1. 要符合模板题的身份。
  2. 常见oj( lojuoj洛谷等)上找不到相同的纯模板题,或者对应题目数据范围太小或数据太弱被大部分人用非 std 做法爆过去。(当然如果管理员滋磁且你有数据或愿意自己造可以忽略这条)

不过,如果你希望占杨主力的 $10$ 个坑(并强行让他帮你一起造这个题),请仔细考虑/xyx。

典型事例

A:最近刚刚学了个 *** 算法,能不能加到模板题里去啊/kel。

fizzydavid:不行,太简单了,出出来没有牌面。(说罢丢给你一篇论文)你看你/论文里的做法只能做到 $1000000$ ,我来给你加 $6$ 个零。

评论

avatar
skyline
区间线性基
avatar
skyline
分块随机染色(这个可能是假的
avatar
wawawawa
https://loj.ac/problem/129
avatar
djq_cpp
给你n个已知点P[1...n] 以及m次询问 每次询问给出一个点Q 球线段QP[1], QP[2], ..., QP[n]的斜率的最大值 保证对于每个i有Q.x != P[i].x n, m <= 1e5 允许离线
avatar
fizzydavid
有没有人愿意一起造一个半平面交模板题啊?
avatar
ascchrvalstr
动态凸包 动态半平面交
avatar
djq_cpp
静态区间逆序数 O(n sqrt n) 动态区间逆序数 O(n sqrt n log n) (n表示输入规模
avatar
djq_cpp
各种变种FWT (比如说这种最简单的: rep(i, 1 << n) ans[i] = 0; rep(i, 1 << n) rep(j, 1 << n) if(!(i & j)) ans[i | j] += a[i] * b[j]; 给出a[], b[],球ans[]。0 <= n <= 20)
avatar
ascchrvalstr
某少女附中的体育课
avatar
djq_cpp
来说个我不太会的 输入n, a[], b[] for i = 0 to n-1 for j = 0 to n-1 ans[i * j % n] += a[i] * b[j] 球ans的每一项%998244353 n 1e5
avatar
djq_cpp
*扩展拉格朗日反演:定义[n]的一个划分的权值为a[cnt] * sigma(b[size[i]]), 其中a, b输入给出,cnt为划分出的集合数量、size[]表示划分出的集合大小。球[n]所有划分的权值之和。n <= 1e5 多重背包:n种物品,第i种的质量为ai, 有bi个(这bi个完全一样),球有多少种方案购买质量总和为n的物品。n, ai <= 1e5

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。