算法竞赛

一年过去了。 现在看到小可，内心却依然无法平静… 强装镇定得打个招呼已经是我的极限了orz 其实还是觉得很可惜…曾经的好朋友变得形同陌路总是令人伤感的…

。。。 醒来，发现，四面都是山。。。 每座山上都写着“线段树”三个字…. 不把线段树的lazy标记搞掉根本没法继续搞数据结构啊喂… 像莫队这种没有前置技能点的东西毕竟是少数吧==

本打算和队友一起买一个。。。 # 结果站长看到id填的学校是华科的。。然后买一送一，感动到cry…

* 《程序员的自我修养—链接、装载与库》 * 了解多线程编程的通用做法，包括如何结束一个while(true)的循环等（tbb.abort()或者发送一个特殊值等） * Kafka分布式消息队列 # * 调研分布式存储系统，以及levelDB * <del>学习gRPC</del> * <del>levelDB笔记，以及protobuff笔记</del> * cuda编程相关 * 阅读facebook开源库**faiss 源码(github)** * <del>tensorRT</del> * 补工程知识 * **阅读caffe代码（重要）** * 补C++(cpp11)知识 * <del>了解tf record 的机制...</del> * 突然MPI.... * <del>在inception-v3上加fine-tune</del> * [cs 231n 2017 sp<del>ring课程</del>](https://www.youtube.com/watch?v=OoUX-nOEjG0&index=2&list=PL3FW7Lu3i5JvHM8ljYj-zLfQRF3EO8sYv) * <del>搞清楚tensorflow checkpoint的四个文件都是什么</del> * <del>补完tensorflow variable 的笔记</del> * tensorflow异步训练 * <del>光流法是什么。。</del> * LSTM->RNN->CNN+RNN处理视频 * <del>TF-slim</del> * <del>cs231n，先把slide啃完(15%)</del> * <del>coursera ML (3/11)</del> * <del>leetcode 102/200</del> * 树上莫队。。。 * <del>分块题目遇到不少lazy标记->线段树</del> * <del>普通型母函数</del> * <del>最大曼哈顿距离</del>（拆点法） * 最小曼哈顿距离 * <del>指数型母函数（基本的做了一点...还需要一些题目训练...然而智商欠费了，回来再看）</del> * <del>数位dp(20160602，基础以及中等题目a得差不多了）</del> * <del>容斥原理（才做了个位数的题目。。还需要训练。。。）</del> * <del>图的连通性问题.. (并查集。。？ 二分+bfs验证？)</del> * <del>spfa->BZOJ 1614 BZOJ 1631</del> * <del>BZOJ 1628 poj 2796 ->单调栈</del> * <del>bzoj 1636 ->rmq（顺便学了rmq+dfs求LCA)</del> * <del>bzoj 1638->图的存储方式...(链式前向星大法好）</del> * bzoj 1654 ->tarjan求强联通分量 * <del>bzoj 1656 ->奇怪姿势的bfs,求绕过某一封闭图形的最短路径，射线法。</del> * cf 449B -> 带点dp思想（类似于之前做过的bfs记录最短路径的条数的题目）的不会做的spfa的题 * <del>匈牙利</del> * <del>km算法</del> * <del>校赛被虐->树形dp,</del> * <del>模拟退火</del> * poj2584->二分图多重最大匹配 * <del>知乎OI爷开专栏讲算法。。？->后缀数组。</del> * <del>后缀数组->cf 123D...不会啊orz</del> * <del>树的直径，次小生成树（）</del> * <del>最小生成树（拒绝划水，推一波难题）</del> * <del>单调栈？单调栈？单调栈单调栈！ （一堆题卡在这里了。。。）</del> 单调队列也来一发 kmp?kmp? kmp!kmp! 扩展kmp trie->ac自动机 线段树线段树？ 线段树线段树！ mutli 2016 %5 1006 -> 回文树 字符串的最小表示法。。。是啥。。。同构什么的orz 复习数论同余->高斯消元 bitset？！ hdu 5313 ->二分图的黑白染色？ 交叉染色法判断二分图？ ->http://blog.csdn.net/yujuan_mao/article/details/8221091 * poj3422-> 三分 * 扫描线（2015暑假：zk：这道题的正解是扫描线blablabla…众：扫描线是啥？23333） * bzoj 2428,cf beta round 2 C ->模拟退火进阶 * hdu 5313 ,poj 1112 ->二分图+dp… * hdu 5222->判断混合图的环 * codeforces 19 D->线段树，不会。 * 快速沃尔什变换(fwt),快速傅里叶变换（fft) (还有fft的数论版本ntt) * 线段树与染色问题http://acm.hust.edu.cn/vjudge/contest/45620#overview * hong kong 网络赛1001 A+b->fft? * 青岛网络赛 1011 ->网络流。。。？？？？？一脸蒙蔽。。。。 * spoj DQUERY ->主席树 * cf 455 E ->dp的单调性优化。。。（学会dp再来看吧orz * 二次剩余 * 离散对数（bsgs算法） * exgcd的三个作用你可晓得？ * crtcrt?crtcrt! * 广义斐波那契循环节 * 指数循环节 * 矩阵都能做什么… * 树上差分。。。？？？ * codeforces 735 E ->树形dp * top k的一堆问题。。。经常被考啊。。。 * 大数据算法。。。（从蓄水池抽样开始。。。） * 理论角度复习hash…以及一些经典算法。。。。 * simhash。。以及推广到其他局部敏感hash算法。。。 * 文本处理工具-> awk awk_维基百科 * levelDB源码… * openssl ，带gui的des,,c/cpp,qt * 浮点数离散化 * 矩形面积并，面积交，周长并 * trie上SA,15年多校，金牌爷含泪推荐 * 二维线段树（四叉树|树套树) * 线段树标记永久化。。是啥 。。李超线段树。。。又是啥 * 扫描线扫描线？扫描线扫描线！ * hdu 3255 体积并 * hdu 5986 * kd tree? kd tree! （静态，动态） * 多个圆并，交 * 主席树？主席树！ * 置换群，循环节 * hdu 5558 | 2015 ICPC HeFei onsite G -> SA?SAM! * 拓扑+dp

https://ac.2333.moe/Problem/view.xhtml?id=1457 题意：求一段区间内数字个数的立方和。 思路：由于一共才1E5,而数字1E9,所以先离散化，再莫队，类似小z的袜子。 注意 ：%lld会WA,要用%I64d

http://acm.hdu.edu.cn/showproblem.php?pid=5610 题意：有重量为a,b两种铁圈每种无限多个…能能否组成一个重量为c且平衡杠铃（中间的杆的重量忽略不计） a,b,c都是整数。 思路：平衡的话。。就是两边重量一样。。那么c为奇数的时候显然不行。 由于有多组答案的时候输出铁圈数之和小的。。。那么我们枚举的话。应该把里面那层枚举的变量放置成重量较大的。。。。

http://poj.org/problem?id=1350 题意：6174问题。。。一个四位数。。四个数字重排。。。最大的减去最小的得到新的数字。最后一定能得到6174或者0.除非这个四位数的四个数字都一样。写出变化的过程。

一般有两个 1static int a; 2int b; 3void func(void) 4{ 5 static int c=0; 6 int d; 7} 在这里，a与b都是全局变量，二者的区别是，b可以被别的文件使用，a只能在本文件中使用，这是static对全局变量的作用。 ** c和d的区别是，d是一个自动变量，func函数执行完后，d会自动被释放。但c却不会被释放，下一次调用func函数时，c的值会保留上次的值继续使用(而不是初始值0，初始化只会在函数第一次被调用的时候执行)**

http://codeforces.com/problemset/problem/519/C 题意：两种组队方式，3人一组，1个大牛+2个蒟蒻或者1个蒟蒻+2个大牛。给定大牛和蒟蒻的个数。问最多能组多少队。 思路：线性规划。设两种队分别有x,y个即可。 突然发现这题以前做过。。。比当时的代码简单了一些。还不错。

题意：求1+2+..+n的和。。但是对于是2的整数幂的项数。。符号是-。。

我经常看有人发帖问关于项目点子的事，也看到了很多回帖，我自己也回了一些常见的项目。不过我觉得只列出三两个是远远不够的，因此就收集并这个项目列表，大家要找简单的编程项目学习练手的话，可以收藏并扩散本文。这些项目并不是论文级别的，只是想抛砖引玉让大家能从中受些启发。

题意：给定一个01串。要进行一次变换：选一段连续的非空的字串，将这段串的0和1反转（0变成1,1变成0） 然后问能得到的最长的0,1交替的序列的长度是多少（不一定连续）

应大家的要求，写一篇博客来介绍下vim在ACM中的简单使用。 写本文的目的，只是为了给广大acmer一个入门vim的指导。不喜勿喷！ 不想看到的请远离！

然而不能上传… 插件也是。在线安装也不可以。 google遍了只看到说是权限问题。

欢迎使用WordPress。这是您的第一篇文章。编辑或删除它，然后开始写作吧！

从放暑假前周sir给我讲了一个用polya计数法和burnside定理做的题目（pku2409）后，突然觉得组合数学挺有意思，然后从那时起到现在几乎都在做这类的题目。 做到现在感觉这类题目的一些基本知识点都差不多有所了解了，水题也刷了不少，但还有很多难题自己实在是做不动，所以准备把这类题目先放一放，然后把前段时间做的水题整理一下（供以后的初学者参考，大牛就不要看了哈，都是水题）。剩下的比较难的题目就慢慢来吧，以后做出来再不上，这个小结会不断地更新。也希望大家有好的题目可以推荐一下，分享一下哈。 感谢：周sir，J_factory和福州大学神牛aekdycoin，大连理工大学神牛czyuan。 不扯了，进入主题： 1.burnside定理，polya计数法 这个专题我单独写了个小结，大家可以简单参考一下：polya 计数法，burnside定理小结 2.置换，置换的运算 置换的概念还是比较好理解的，《组合数学》里面有讲。对于置换的幂运算大家可以参考一下潘震皓的那篇《置换群快速幂运算研究与探讨》，写的很好。 *简单题：（应该理解概念就可以了） pku3270 Cow Sorting http://acm.pku.edu.cn/JudgeOnline/problem?id=3270 pku1026 Cipher http://acm.pku.edu.cn/JudgeOnline/problem?id=1026 *置换幂运算： pku1721 CARDS http://162.105.81.212/JudgeOnline/problem?id=1721 pku3128 Leonardo’s Notebook http://162.105.81.212/JudgeOnline/problem?id=3128 *推荐：（不错的应用） pku3590 The shuffle Problem http://162.105.81.212/JudgeOnline/problem?id=3590 3.素数，整数分解，欧拉函数 素数是可能数论里最永恒，最经典的问题了（我们的队名就叫PrimeMusic^-^）。素数的判断，筛法求素数，大素数的判断···还有很多其他问题都会用到素数。 *最水最水的：（心情不爽时用来解闷吧） pku1365 Prime Land pku2034 Anti-prime Sequences pku2739 Sum of Consecutive Prime Numbers pku3518 Prime Gap pku3126 Prime Path pku1595 Prime Cuts pku3641 Pseudoprime numbers pku2191 Mersenne Composite Numbers pku1730 Perfect Pth Powers pku2262 Goldbach’s Conjecture pku2909 Goldbach’s Conjecture *筛法： pku2689 Prime Distance（很好的一个应用） http://162.105.81.212/JudgeOnline/problem?id=2689 *反素数： zoj2562 More Divisors http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2562 *素数判断，整数分解： 这两题都要用到miller_rabin的素数判断和pollard_rho的整数分解，算法书上都会有，应该是属于模板题吧，不过最好看懂自己敲一遍。 pku1811 Prime Test http://acm.pku.edu.cn/JudgeOnline/problem?id=1811 pku2429 GCD & LCM Inverse http://acm.pku.edu.cn/JudgeOnline/problem?id=2429 *欧拉函数： 数论里很多地方都能用到欧拉函数，很重要的。 pku1284 Primitive Roots （很水） http://acm.pku.edu.cn/JudgeOnline/problem?id=1284 pku2407 Relatives （很水） http://acm.pku.edu.cn/JudgeOnline/problem?id=2407 pku2773 Happy 2006 http://162.105.81.212/JudgeOnline/problem?id=2773 pku2478 Farey Sequence （快速求欧拉函数） http://162.105.81.212/JudgeOnline/problem?id=2478 pku3090 Visible Lattice Points （法雷级数） http://acm.pku.edu.cn/JudgeOnline/problem?id=3090 *推荐：（欧拉函数，费马小定理） pku3358 Period of an Infinite Binary Expansion http://acm.pku.edu.cn/JudgeOnline/problem?id=3358 *整数分解 这个也很重要的耶，包括大数的表示方法。 pku2992 Divisors http://acm.pku.edu.cn/JudgeOnline/problem?id=2992 fzu1753 Another Easy Problem http://acm.fzu.edu.cn/problem.php?pid=1753 hit2813 Garden visiting http://acm-hit.sunner.cn/judge/show.php?Proid=2813 pku3101 Astronomy （分数的最小公倍数） http://acm.pku.edu.cn/JudgeOnline/problem?id=3101 4.扩展欧几里得，线性同余，中国剩余定理 这应该是数论里比较重要的一个部分吧，这类的题目也挺多，具体的内容最好先看看数论书，我也整理过一些，可以参考参考： http://hi.baidu.com/shw/blog/item/0676025d56a87d4afbf2c093.html *简单题： pku1006 Biorhythms http://acm.pku.edu.cn/JudgeOnline/problem?id=1006 pku1061 青蛙的约会 http://acm.pku.edu.cn/JudgeOnline/problem?id=1061 pku2891 Strange Way to Express Integers http://acm.pku.edu.cn/JudgeOnline/problem?id=2891 pku2115 C Looooops http://acm.pku.edu.cn/JudgeOnline/problem?id=2115 pku2142 The Balance http://162.105.81.212/JudgeOnline/problem?id=2142 *强烈推荐： sgu106 The equation http://acm.sgu.ru/problem.php?contest=0&problem;=106 pku3708 Recurrent Function （经典） http://acm.pku.edu.cn/JudgeOnline/problem?id=3708 5.约瑟夫环问题 这个问题还是比较有意思的，不是很难。 *简单题： pku3517 And Then There Was One http://acm.pku.edu.cn/JudgeOnline/problem?id=3517 pku1781 In Danger http://acm.pku.edu.cn/JudgeOnline/problem?id=1781 pku1012 Joseph http://162.105.81.212/JudgeOnline/problem?id=1012 pku2244 Eeny Meeny Moo http://162.105.81.212/JudgeOnline/problem?id=2244 *推荐： pku2886 Who Gets the Most Candies? http://162.105.81.212/JudgeOnline/problem?id=2886 6.高斯消元法解方程 其实解方程并不是很难，就是按线性代数中学的那种方法，把系数矩阵化成上三角矩阵或数量矩阵，不过有些题目要判断是否有解，或枚举所有解。不过这类题目我认为比较难的还是怎么去建立这个方程组，这个理解了，就没什么大问题了。 *简单题： pku1222 EXTENDED LIGHTS OUT http://162.105.81.212/JudgeOnline/problem?id=1222 pku1681 Painter’s Problem http://162.105.81.212/JudgeOnline/problem?id=1681 pku1830 开关问题 http://162.105.81.212/JudgeOnline/problem?id=1830 *推荐： pku2947 Widget Factory http://162.105.81.212/JudgeOnline/problem?id=2947 pku2065 SETI http://162.105.81.212/JudgeOnline/problem?id=2065 *强烈推荐： pku1753 Flip Game http://162.105.81.212/JudgeOnline/problem?id=1753 pku3185 The Water Bowls http://162.105.81.212/JudgeOnline/problem?id=3185 *变态题： pku1487 Single-Player Games http://162.105.81.212/JudgeOnline/problem?id=1487 7.矩阵 用矩阵来解决问题确实很常见，但我现在用到还不是很好，很多难题我还不会做。建议大家可以去看Matrix67的那篇关于矩阵的十个问题，确实很经典，但不太好看懂。 *简单： pku3070 Fibonacci http://162.105.81.212/JudgeOnline/problem?id=3070 pku3233 Matrix Power Series http://162.105.81.212/JudgeOnline/problem?id=3233 pku3735 Training little cats http://162.105.81.212/JudgeOnline/problem?id=3735 8.高次同余方程 有关这个问题我应该是没什么发言权了，A^B%C=D，我现在只会求D和B，唉，很想知道A该怎么求。就先推荐几道题目吧，这里涉及到了一个baby-step，giant-step算法。 fzu1759 Super A^B mod C http://acm.fzu.edu.cn/problem.php?pid=1759 pku3243 Clever Y http://162.105.81.212/JudgeOnline/problem?id=3243 pku2417 Discrete Logging http://162.105.81.212/JudgeOnline/problem?id=2417 hdu2815 Mod Tree http://acm.hdu.edu.cn/showproblem.php?pid=2815 9.容斥原理，鸽巢原理 很有用的两个定理，但好像单独考这两个定理的不是很多。 *鸽巢原理： pku2365 Find a multiple http://162.105.81.212/JudgeOnline/problem?id=2356 pku3370 Halloween treats http://162.105.81.212/JudgeOnline/problem?id=3370 *容斥原理： hdu1695 GCD http://acm.hdu.edu.cn/showproblem.php?pid=1695 hdu2461 Rectangles http://acm.hdu.edu.cn/showproblem.php?pid=2461 10.找规律，推公式 这类题目的设计一般都非常巧妙，真的是很难想出来，但只要找到规律或推出公式，就不是很难了。我很多都是在参考别人思路的情况下做的，能自己想出来真的很不容易。 *个人感觉都挺不错的： pku3372 Candy Distribution http://162.105.81.212/JudgeOnline/problem?id=3372 pku3244 Difference between Triplets http://162.105.81.212/JudgeOnline/problem?id=3244 pku1809 Regetni http://162.105.81.212/JudgeOnline/problem?id=1809 pku1831 不定方程组 http://162.105.81.212/JudgeOnline/problem?id=1831 pku1737 Connected Graph http://162.105.81.212/JudgeOnline/problem?id=1737 pku2480 Longge’s problem http://162.105.81.212/JudgeOnline/problem?id=2480 pku1792 Hexagonal Routes http://acm.pku.edu.cn/JudgeOnline/problem?id=1792 11.排列组合，区间计数，计数序列 这些题目可能需要一些组合数学知识，基本上高中的知识就够了。区间计数问题一般不难，但写的时候需要仔细一些，各种情况要考虑到位。至于像卡特兰数，差分序列，斯特灵数···都还挺有意思，可以去看看《组合数学》。 *简单题： pku1850 Code http://162.105.81.212/JudgeOnline/problem?id=1850 pku1150 The Last Non-zero Digit http://162.105.81.212/JudgeOnline/problem?id=1150 pku1715 Hexadecimal Numbers http://162.105.81.212/JudgeOnline/problem?id=1715 pku2282 The Counting Problem http://162.105.81.212/JudgeOnline/problem?id=2282 pku3286 How many 0’s? http://162.105.81.212/JudgeOnline/problem?id=3286 *推荐： pku3252 Round Numbers http://162.105.81.212/JudgeOnline/problem?id=3252 *计数序列： pku1430 Binary Stirling Numbers http://162.105.81.212/JudgeOnline/problem?id=1430 pku2515 Birthday Cake http://acm.pku.edu.cn/JudgeOnline/problem?id=2515 pku1707 Sum of powers http://acm.pku.edu.cn/JudgeOnline/problem?id=1707 12.二分法 二分的思想还是很重要的，这里就简单推荐几个纯粹的二分题。 *简单： pku3273 Monthly Expense http://162.105.81.212/JudgeOnline/problem?id=3273 pku3258 River Hopscotch http://162.105.81.212/JudgeOnline/problem?id=3258 pku1905 Expanding Rods http://162.105.81.212/JudgeOnline/problem?id=1905 pku3122 Pie http://162.105.81.212/JudgeOnline/problem?id=3122 *推荐： pku1845 Sumdiv http://acm.pku.edu.cn/JudgeOnline/problem?id=1845 13.稳定婚姻问题 无意中接触到这个算法，还蛮有意思的，《组合数学》中有详细的介绍。 pku3487 The Stable Marriage Problem http://acm.pku.edu.cn/JudgeOnline/problem?id=3487 zoj1576 Marriage is Stable http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1576 14.数位类统计问题 在航点月赛中第一次接触到这类问题，scau大牛little龙推荐我看了一篇论文，09年刘聪的《浅谈数位类统计问题》，这篇论文相当精彩，也相当详细，每道题都有详细的分析和作者的参考代码。所以我也没什么可说的了，这些题的代码我博客里也就不贴了，大家直接去看论文吧。 简单： ural1057 Amount of degrees http://acm.timus.ru/problem.aspx?space=1#=1057 spoj1182 Sorted bit squence https://www.spoj.pl/problems/SORTBIT/ hdu3271 SNIBB http://acm.hdu.edu.cn/showproblem.php?pid=3271 较难： spoj2319 Sequence https://www.spoj.pl/problems/BIGSEQ/ sgu390 Tickets http://acm.sgu.ru/problem.php?contest=0&problem;=390 以上分类的题目在我的博客里都可以找到详细的解题报告和参考代码，由于比较麻烦就没加链接，需要的可以用我的站内搜索找到。 本小结会不断更新，转载请注明出处。 严重声明：本文只适合ACM初学者，路过的大牛如有相同类型的比较好的题目可以推荐一些啊。 来自: http://hi.baidu.com/shw/blog/item/5305e12c7289973e359bf768.html

C. Day at the Beach time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output One day Squidward, Spongebob and Patrick decided to go to the beach. Unfortunately, the weather was bad, so the friends were unable to ride waves. However, they decided to spent their time building sand castles.

B. Spongebob and Joke time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output While Patrick was gone shopping, Spongebob decided to play a little trick on his friend. The naughty Sponge browsed through Patrick’s personal stuff and found a sequence _a_1, _a_2, …, a__m of length m, consisting of integers from 1 to n, not necessarily distinct. Then he picked some sequence _f_1, _f_2, …, f__n of length n and for each number a__i got number b__i = f__a__i. To finish the prank he erased the initial sequence a__i.

1#include <cstdio> 2#include <iostream> 3#include <cmath> 4using namespace std; 5long long d1,d2,d3; 6int main() 7{ 8cin>>d1>>d2>>d3; 9long long ans = 999999999999; 10ans = min(ans,d1+d2+d3); 11ans = min (ans,d1*2+d2*2); 12ans = min (ans,d1*2+2*d3); 13ans = min(ans,d2*2+2*d3); 14cout<<ans<<endl; 15return 0; 16} time limit per test 1 second

热身赛的时候发现没有codeblocks瞬间爆炸…我从暑假开始用的vim还好…不过两个队友平常用codeblocks的。。