ACM-collection
March 9, 2018
汇总做过的题目：来源、类别、题意概括、难度等。使用<Ctrl> + F 的方式检索。 Title Link Tags Description Picking Strings CF 923-D 字典树 还没看
ACM
Codeforces 855-C 树形DP
September 26, 2017
题意 # 给一颗树， 每个结点可以标记一个type。 一共有m种type，分别是1-m。 其中有一种特殊的type，编号为k，要求： 在这棵树中，最多出现x个type为k的点。 每个type为k的点，其相邻的点type必须小于k。 问，给定以上数据，求树的标记种类数有多少。 数据范围： n <= 1e5, x <=10, m <=1e9 分析 # 这是一个典型的树形DP，DP的维度应该至少是3维。 Dp[i][j][z] 表示： 以i为根的子树，用掉z个k时的种类数。 其中对于根结点的type选取，分三种情况， 0：type < k (type >=1 ) 1：type = k 2：type > k (type <= m) Dp表示内容确定以后，就要来找转移方程了。 这种组合种类的问题，只要分清楚哪些量之间是相乘的关系，哪些量是相加的关系就好办了。 思考一种普遍的情况，对于一个根节点和其儿子节点之间的关系，以及儿子之间的关系。 可以确定的是，各个儿子之间的关系是相乘的关系。因为儿子之间是没有约束的，不直接相连就没有type < k的约束。所以每个子树内的排列种类是直接乘到贡献中的。 然后就是儿子与父亲节点的关系。 讨论一下，如果父亲的取值是0类型，也就是type < k。 对于任何一个儿子都可以任意选择type，并且这些选择之间是相加的关系。选择之和与父亲的选择种类之间是相乘关系。 总上，父亲与儿子、儿子与儿子之间都是相乘的关系，儿子内部是相加关系。 这个时候我们可以选择将父亲先放在一边，先合并各个儿子。最后把合并后的儿子与父亲合并。 为什么不能直接把儿子合并到父亲上呢？ 因为对于一个固定的z来说，其对应的情况是z个k在所有子树中的全排列种情况。这些排列又是相加的关系，很显然我们不能去求这个排列，复杂度太大。 我们要在处理每个儿子的时候，将其对不同的z的贡献都存起来，这个我们可以做到。 以下的代码以根为0时举例，其他两个情况一样。 for(int j=0; j<=x ;j++){ for(int z = 0; z <= x; z++){ if(l+z > x) continue; Dp[u][0][j+z] += ta[0][j] * (Dp[v][0][z] + Dp[v][1][z] + Dp[v][2][z]); } } ta[0][j] 记录的是在当前儿子之前的所有儿子中，使用了j个k时，所有的种类数。 其中，Dp[u][0][j+z] 记录的是对于当前儿子结点v，使用了j+z 个k时，所有的种类数。 ...
FFT 快速傅立叶变换
July 29, 2017
快速傅立叶变换是离散傅立叶变换的加速版。 傅立叶的一个用途是用来计算多项式乘法。先讲一下多项式乘法。 多项式乘法 # 多项式有两种表示方法： 系数表示法 # $$A = a0 + a1x^1 + a2x^2 + … + anx^n$$ 点值表示法 # A ={ (x1, y1), (x2, y2),...,(x3, y3) } 点值表示法相当与用点值来求得各项的系数，所以要准确表示一个多项式就必须至少与多项式未知数的数量一致才可以。 传统的系数表示法求多项式乘法的方式复杂度是O(n^2)。 如果使用点值来计算多项式乘法，就会有一些可优化的地方。首先两个n次多项式相乘得到的结果多项式有2n项，这个是确定的，也就是说要用点值表示法就要有2n个点。如何用点值表示法求多项式相乘呢？我们取点的时候就取x相同的点值，这样对应的y值相乘的结果就是结果多项式的y。所以我们在取两个多项是的点的时候就要取2n个点，然后得到2n个结果点。然后剩余的任务就是将这个点值表示法转换成系数表示法得到了我们要的多项式。这个由点值转换为系数的方式称之为插值。 但是这样的算法，在第一步的时候就崩溃了，因为求一个点的值就要至少O(n)， 我们要求2n×2个点复杂度就O(n^2)了。然后就需要一些数学手段。 秦九韶算法 # 这个算法的中心思想是通过选取特殊的点来简化计算，什么点是特殊的呢，用复数点。 介绍这个之前需要先复习一下复数。 高中数学的基础还是比大学的更有用。 复数的基本表示方法：z = x + yi。在复平面上的从原点到点(x,y)的向量是其对应的几何解释。 利用直角坐标与极坐标之间关系，复数还有一种三角表示：z = r(cosθ + isinθ)，θ代表极角，r是复数向量的模|z|=sqrt(x^2+y^2)。 另一种表示法是指数表示法，见下图. 然后有一个棣莫弗公式能够将两个复数相乘简化： 设两个复数（用三角形式表示）: z1 = r1(cosθ1 + isinθ1) z2 = r2(cosθ2 + isinθ2) 那么相乘的结果就是： z1*z2 = r1*r2[cos(θ1+θ2) + isin(θ1+θ2)] 这个过程很好证明，三角函数就可以了。 这个公式可以进行推广，数学归纳法，得到： z1*z2*...*zn = r1*r2*. ...
VIM 在ACM/ICPC中的非最佳实践
July 23, 2017
5月份在看今年的Final直播，看到了ITMO队的屏幕的时候，看到一些骚操作，感觉自己是拿着冲锋枪当鸟枪使了。 Vim确实十分强大，其强大是有原因的。最主要的原因是他本是依托终端存在的，他与终端有着非常强的联通。终端的强大一定程度上让vim变的很牛逼。不需要插件就可以在内置命令行。 打比赛两年了，现在也算是个退役狗了，才发现自己并没有好好用vim这个神器，不仅仅是装逼。 第一年的时候简单会用vim来写代码，会简单的配置，会用一点点的快捷键。 第二年的时候会用更多的快捷键，并没有什么本质上的突破，除了会用一点bash脚本来加快测试等。 本文将以ACM比赛场景作为线索，介绍一下Vim应该怎么用，以及，你为什么不要用IDE。 比赛开始 # 按照我们队的分工，我在前2分钟负责配置vim环境和代码环境。这里推荐一个简明配置清单： vim ~/.vimrc set nu " 行号 set mouse=a " 鼠标可用 set shiftwidth=4 " 与tab宽度相关的 set tabstop=4 " tab宽度 set cindent " c语言风格缩进 set autoindent " 自动缩进 set cul " 高亮当前行 colorscheme desert " 配色，选用你平时用的最好 syntax on " 开启语法高亮 " 以下配置自己酌情 set noswapfile " 不产生交换文件，在意外退出没有保存的情况下刚写的代码就没有了。 " 好处就是不会在打开文件的时候提醒你交换文件，下面会讲怎么处理这种请况。 在配置完vim后，我会写一个头文件和主函数的模板，然后命令行给每一题都复制一份。 模板会写：所有会用到的头文件、主函数、输入格式、输出Case、常用的#define、typedef、const等。 用一个四行的脚本来复制： #!/bin/bash for name in {A..M}; do cp a.cpp $name.cpp done # 我写的模板文件是a.cpp # 脚本名为copy. ...
比赛题解-2017苏大暑假集训个人赛(13)
July 14, 2017
比赛现场传送门。此次比赛共8道题目如下： A. HDU 5777 签到题 B. Poj 3581 后缀数组 + 细节处理 C. Poj 2228 DP+循环情况处理 D. Poj 2155 二维树状数组/二维线段树(区域修改，单点查询) E. UVA 11853 DFS乱搞 F. HDU 4609 FFT基础题 G. HDU 5676 DFS + 二分 H. Poj 2728 最优比例生成树(0-1分数规划)/二分 题目整体偏难，除签到题外应该都是银牌及以上题目，基本上要掌握到这个程度才算可以。 A. HDU 5777 签到题 # 某一场BestCoder的B题，很简单的思维小题目。 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; int n,k; int a[100006]; ll sum=0; bool cmp(int a,int b) { return a>b; } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d%d", &n,&k); for(int i=0;i<n-1;i++) scanf("%d", &a[i]); sort(a,a+n-1,cmp); sum=n; for(int i=k-1;i<n-1;i++) sum+=a[i]; printf("%lld\n",sum); } return 0; } B. ...
ACMRoad
May 28, 2017
作为ACM的老队员，最经常被问的不是XXX算法的问题，而是“学长我要玩ACM，我该从哪开始？”。这个问题嘛，有超过3个人问就有必要写成文字来回答，正如但凡一个操作需要两条以上命令就可以写成脚本来做一样。 就不回首往事了，尽管一路走来感慨良多啊。 新人，也有区别。你是没有程序编写基础的还是有一定代码基础的？有Py基础还是C的基础？有没有算法基础？ 如果你是一个大一新生，且没有学过程序设计，或正在学，那么我建议你花最多2周，把C语言关于文件操作之前的部分学完(文件操作非必要)。不要说2周太短了，如果你打算在ACM竞赛中获得不凡的成绩，就2周。你可能天赋异秉可以花很少的时间学会C语言，这很好，说明你有个好脑子，且可以在搞好ACM的同时兼顾上课。如果你的脑子不是很棒，但是也喜欢，2周时间就必要的做些调整，课该怎么上就要考虑一下了（事实上就算是脑子很好，也要考虑一下）。 然后你可能要检测一下自己的C语言水平，尤其是在做ACM题目上的水平。此时我建议你去用2周的时间刷掉HDU平台上的第11页的题目，这上面的题目涉及到的算法比较简单，算法对应的C语言程序也比较简单，只是使用到了字符串的处理、数组的使用、结构体的使用等基本语法知识，但是会让你对这些基本知识有翻天覆地的改观，他们很简单，但是可以做出很神奇的动作。这些题目可以让你对C语言的语法更加熟练，甚至到了4岁小朋友说母语的水平一样自然而流畅，同时，当然你因为不会使用高级语法来加快代码编写速度和质量，就像4岁小朋友不会写作文一样。但是仅仅语法熟练只是一方面，同时你会学习到一些更加快速方便的函数，如使用sort()函数来排序而不是自己编写冒泡排序等傻逼的排序函数；你还会接触到强类型语言中变量的数值边界问题、数值精度问题；字符串处理的常见bug；如何编写递归代码等。你还会知道你的电脑一秒钟只能运行大约1e8次的简单数学运算，你会慢慢的学会用计算机的思维方式思考问题的解决办法。同时你还会接触到一些算法，如动态规划等。（此页中有很少的几个题目非常困难，没关系，不要管他们，但你需要完成至少90道题目） 然后你可以小声的对自己说：“我已经看到了ACM-ICPC的影子了！”。 然后你需要入门一下。这个阶段你可能会比较痛苦，因为你要做的就是不断的离开你熟悉的几行代码，转而去学习新的算法，写新的代码。而这一切，应该都没有人会仔细的教你。 到现在为止，你可能都没有学过一个完整的算法。之前做的那些水题都只是思维的开胃菜而已。那么现在你要清楚你必须去认真的、系统的学习一些算法。要能清晰的理出算法的逻辑，快速的编写出高质量且准确的代码，要能眼动查找BUG。不用担心，有人的地方都有路，已经有无数人做过这件事，所以你有章可循。 在介绍下一站之前，我必须告诉你，ACM比赛使用Linux操作系统编写代码。所以，按照我们的一致希望，我们希望你能从现在开始使用Linux并逐步使用Linux来工作，windows只是个好东西，但不是程序员的玩具，你的玩具是Linux操作系统，比赛统一使用Ubuntu操作系统作为平台，如果你对Linux一无所知，你需要去百度一下了。 至于如何安装Ubuntu操作系统和如何使用，请见其他博文或直接来实验室寻找学长的帮助（文章目前还没有整合）。 你需要去Vjudge申请一个帐号，并且开始学习[简单搜索专题]传送门。我们一致建议从这个算法专题开始，因为这里要用到的技能你学习起来会比较快速，因为你的前期技术铺垫已经做好了。其次这里的内容将会在其他的算法中使用到，所以你要从这里开始。这里的学习并没有学习资料，一切资料都在网络上，这里有的只是十几道检验你学习成果的题目，但是，这些题目与你今后比赛中遇到的题目在外形上长的已经很相似了。你大概需要一周多一点的时间来攻克这个专题。当你结束这个专题的时候你应该具备以下几条但不限于此的能力： 快速编写递归程序。 看到搜索类问题可以快速反应出解决方式并编写代码解决。 快速估算自己方案的时间空间复杂度并决定是否可行。 尝试使用高级一些的语法来编写代码，如C++中的部分内容，包括重载运算符等。 手动调试代码修改BUG而不需要依靠调试工具。 初步熟练使用Vim编写代码，并初步熟悉Linux-Ubuntu操作系统，使用简单命令来操作计算机。 熟练的从网络上寻找资源解决自己的疑问，同时可以快速的看懂别人的相关代码。 了解一些题库。 接下来你或许就不再需要这篇文章的指导了，但是，你离入门还差的远。 之后的一段时间内，算法还是要继续学习，依旧用这样的专题的形式。同时你也要去接触一下真正的比赛是什么样子，以及，真的强是什么样子。 以下平台会不定期有比赛，可视个人情况参加： # Codeforces(cf) HihoCoder 以下算法方向需要你在未来两年内有所涉及，但是掌握这些算法并不是保障： # 搜索 图论(最短路、生成树、二分图、连通图、网络流…) 动态规划(树形DP、数位DP、区间DP、斜率DP、概率DP…) 数论 数据结构(线段树、搜索树、平衡二叉树、KD树、树堆…) 字符串(KMP、Hash、AC自动机、后缀数组、字典树) 等… 推荐的书： 刘汝佳竞赛入门经典两本：紫书、大白书，链接不放了。 # 有些问题，可以先尝试自己回答一下，自己实在回答不了或无法找到答案回答，再提出来。