题目链接：HDU - 1133 讲这道题之前，决定先讲一下卡特兰数； 卡特兰数是组合数学中一个很著名的数列。 它的第n项可以用以下几种公式得出： 递推公式1 f ( x ) = <munderover> ...

数位dp 之所以叫数位dp，是因为它在记数上经行dp操作，但数位dp是很暴力的，但是比一般的纯暴力快的多，因为它有记忆化的操作。 这篇数位dp文章还是很好的：数位dp总结 之 从入门到模板 关于数位dp的题 ，通常会给你一个数，然后给你一些要求，让你求从1~n中符合要求的数有多少个。 比如这道：HDU 2089 不要62 题意就是给你两个数l,r。然后让你求l到r的区间里既没有出现4,也没有出现62（连续62）的数有多少个。 思路： 我们枚举每位上的数的时候，不枚举有4和62的情况就可以了，4很好避免，但是62有两位数，那么我们可以开一个二维的dp数组，用其中一个维度记录前一位是不是6这...

题目传送门 暑假打多校的时候第一次刚遇到这题是一脸懵逼，那场比赛虽然比较惨烈，但是队友强大，还是做出了这道题，当时还给我讲了这道题，当时懵懵懂懂就知道用威尔逊定理，但是最近又做到了这道题. emmmm…还是不会，（生气了，盘它）。 题目大意： T组，每组一个素数P，这个数有点大（1e9到1e14）让你找到一个素数Q，Q<P,并且Q最大。也就是让你找到小于P并且距离P最近的素数。 然后求的是(Q!)mod P(即Q的阶乘取模P)。 思路： 这给Q还算好找，因为我们可以直接从P往前找，（素数相邻差别不大）判断一个数是不是素复杂度sqrt(P）。所以Q不难找。 但是Q肯定和P差不了多...

题目 描述 今年的ACM暑期集训队一共有18人，分为6支队伍。其中有一个叫做YZJ的大佬，在共同的集训生活中，大家建立了深厚的友谊，YZJ准备做点什么来纪念这段激情燃烧的岁月，想了一想，YZJ从家里拿来了一块上等的牛肉干，准备在上面刻下一个长度为n的只由"Y" “Z” "J"三种字符组成的字符串（可以只有其中一种或两种字符，但绝对不能有其他字符）,YZJ学长同时禁止在串中出现ZZ相邻的情况，他认为，"ZZ"看起来就像骂人的话语，影响不好。 你，NEWACMer,YZJ的崇拜者，能帮学长算一下一共有多少种满足要求的不同的字符串吗？ ...

动态规划（DP): 就是把把大问题转化为一个个小问题，然后在众多的小问题中递推得到这个大问题的最佳解（当然，这只是我个人对动态规划的理解，希望有大牛来指导改正），那么区间dp就是在区间之间进行动态规划。 那么区间dp的典型例题就是 nyoj 15 括号配对 nyoj 737 石子合并 做区间dp的题的一般步骤： 1. 首先肯定开一个dp[maxx][maxx]数组，（区间dp一般是二维）dp[i][j]就是表示i到j这个区间的最优解，那么dp[1][n]一般就是我们所要求的答案。 2. dp数组的初始化是很重要的，根据题目要求，是全部赋值成0,还是-1，又或者是无穷大，但是更多的是（以dp[i...

链接：https://ac.nowcoder.com/acm/contest/1106/B 题目 Hanks 博士是BT (Bio-Tech，生物技术) 领域的知名专家。现在，他正在为一个细胞实验做准备工作：培养细胞样本。 Hanks 博士手里现在有N 种细胞，编号从1~N，一个第i 种细胞经过1 秒钟可以分裂为Si 个同种细胞（Si 为正整数）。现在他需要选取某种细胞的一个放进培养皿，让其自由分裂，进行培养。一段时间以后，再把培养皿中的所有细胞平均分入M 个试管，形成M 份样本，用于实验。Hanks 博士的试管数M 很大，普通的计算机的基本数据类型无法存储这样大的M 值，但万幸的是，M 总可...

我们平常求两个数的最大公约数，用到就是欧几里得算法，也就是辗转相除法，也就是递归方法，如果数据大的话，复杂度也不小。 int gcd(int x,int y) { return y==0?x:gcd(y,x%y); } 但是我们是可以对这个进行优化的； 我们用不断除以2来对这个进行一点小优化（可以提高gcd效率）。 我们判断这么几种情况： 1. x=y，那么gcd(x,y）=x; 2. x,y都是偶数，那么gcd(x,y)=2*gcd(x/2,y/2); 3. x为偶数，y为奇数，那么gcd(x,y)=gcd(x/2,y); 4. x为奇数，y为偶数，那么gcd(x,y)=gcd...

链接：https://codeforces.com/problemset/problem/1237/D 题目 Your favorite music streaming platform has formed a perfectly balanced playlist exclusively for you. The playlist consists of n tracks numbered from 1 to n. The playlist is automatic and cyclic: whenever track i finishes playing, track i+1 sta...

题目链接：https://codeforces.com/problemset/problem/1238/D 大致题意： 给你一个数n，然后给你一个长度为n的字符串，这个字符串是只有A，B两个字母，问你这个字符串的子串（当然本身也是自己的子串）中有多少个回文串（单个字符不算回文串）。 思路： 本来我是往dp方向想的，考虑他的子串要想构成回文串，那么最小的回文串就只有这四中情况 1 AA 2 BB 3 ABA 4 BAB 但是我发现这种方法还是有很多情况没有考虑到，比如：AABB有三个回文子串，AABBB有6个回文子串。发现情况还是很复杂。 看了一下大佬们的题解博客，发...

题目： Bobo has a string of length 2(n + m) which consists of characters A and B. The string also has a fascinating property: it can be decomposed into (n + m) subsequences of length 2, and among the (n + m) subsequences n of them are AB while other m of them are BA. Given n and m, find the number of...

题目链接：https://vjudge.net/contest/327529#problem/B A Telephone Line Company (TLC) is establishing a new telephone cable network. They are connectingseveral places numbered by integers from 1 toN. No two places have the same number. The linesare bidirectional and always connect together two places and...

一直想整理一下最短路，好久之前学的（都忘了差不多了），再回顾一下，增加印象 最短路； 1.Floyd最短路算法； （被戏称为五行算法）它可以求出一个图中任意两点之间的最短路距离，即多源最短路算法，但是复杂度为O(n3)很大，所以一般比赛用到的机会很少，1s的时间要求下，最多只能求1000点之间的最短路。优点就是代码短，好理解。 主要思想就是用图中的一个点k来判断能不能优化i到j之间的最短距离。（枚举k点）。 代码： void floyd() { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ...

题目链接：https://vjudge.net/contest/327529#problem/M 题目： ACboy很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗？ 输入： 每个测试实例首先包括2个整数，N,M.(1 <= M <= N <= 200);在接下来的N行里，每行包括2个整数，a,b. 在第 i 行，a 代表要攻克第 i 个城堡必须...

题目链接；https://www.luogu.org/problem/P1983 题目 一条单向的铁路线上，依次有编号为 1,2,…,n1, 2, …, n 1,2,…,n的 nn n个火车站。每个火车站都有一个级别，最低为 111 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 xxx，则始发站、终点站之间所有级别大于等于火车站x xx 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点） 例如，下表是5 5 5趟车次的运行情况。其中，前4 44 趟车次均满足要求，而第 555 趟车次由于停靠了 333 号火车站（222 级）却未停...