原题：The Problem to Make You Happy 原题大意　　Bob和Alice在有向图内玩游戏，n个顶点，m条边。　　每人一颗棋子，初始位置分别是x，y。　　Bob先手，轮流操作，每次只能走一条有向边。　　结束条件: 1.不能操作的人输 2.两个棋子重合Bob输 3.游戏没有尽头Alice输　　问 Bob 能不能赢？　　2 <= n <= 100. 1 <= m <= n <= n*(n-1) 1 <= x , y <= n, x != y. 算法分析 状态设计：两颗棋子的位置，下一步棋是谁走。因子我们可以用dp[x][y] [0/1]表示两枚棋子的状态,Alice在x，Bob在y处，0是下一步Alice走，1是下一步Bob走。 思路：通过BFS，进行状态之间的转移。 初始状态：两颗棋子重叠为必败状态，先令这些状态在dp数组中的值为0，其它的为1 状态转移：a) 若是选手A打算行动，那么在他之前行动的是B，要让B能GG必须B能到达的所有状态均为必败。b) 若是选手B打算行动，那么在他之前行动的是A，时光倒流，A行动时的那个状态 ...

原题：Anton and School - 2 原题大意给出一组由“（”和“)”组成的字符串，问有多少种方法使得删除其中一些括号后，字符串会成为RSBS串，RSBS串是一种左右完全对称的串，如“（（（）））”，有一些则不是，如“（（（））”，“（（）（））”。 算法分析删除几个，其实也就是算有几种成立。看了网上的代码，知道了如何通过逆元来算组合数，博客如下，本题中求1/(k!) 是通过 k^(MOD - 2) % MOD (MOD为素数); 组合数学公式推导 含MOD求逆元 程序代码#include <cstdio> #include <memory.h> #include <cstring> using namespace std; typedef long long LL; const int maxn = 2e5+5; const LL mod = 1e9 + 7; int n; char s[maxn]; int l[maxn], r[maxn]; LL fac[maxn], inv[maxn];//fac[i] 保存阶乘，inv[i] ...

区间价值 原题大意给定n个数A1…An，小Ho想了解AL..AR中有多少对元素值相同。小Ho把这个数目定义为区间[L,R]的价值，用v[L,R]表示。 例如1 1 1 2 2这五个数所组成的区间的价值为4。 现在小Ho想知道在所有的的v[L,R] (1 <= L <= R <= n)中，第k小的值是多少。 输入： 2 4 7 1 1 2 3 3 6 100 100 100 输出： 03 算法分析因为比较数字之间是否相同，所以与数字大小没有关系，先通过离散化将数据规模压缩，然后又因为最大的价值为 n*(n+1)/2，最小价值为 0，所以通过二分枚举价值，看是否有k个区间满足，然后通过区间的移动（尺取法），找到满足的解。 程序代码#include <iostream> #include <cstdio> #include <map> #include <algorithm> #define ll long long using namespace std; const int maxn = 200000+5; ll n, ...

出勤记录Ⅱ 原题大意小Hi的算法课老师每次上课都会统计小Hi的出勤记录。迟到会被记录一个L，缺席会被记录一个A，按时上课会被记录一个O。 一学期结束，小Hi的出勤记录可以看成是一个只包含LAO的字符串，例如”OOOOLOOOLALLO……”。 如果小Hi整学期缺席不超过1次，并且没有连续3次迟到，小Hi的出勤记录就算合格。 现在给出字符串的长度N，小Hi想知道长度为N的出勤记录中，合格的记录总共有多少种。 例如长度为3的合格出勤记录有19种：OOO OOL OOA OLO OAO LOO AOO OLL OLA OAL LOL LOA AOL LLO LAO ALO LLA LAL ALL。 算法分析状态dp[i][j][k]表示长度为i的组合中合格的个数，i表示长度，j表示A出现的个数，k表示连续L出现的个数。 程序代码#include <cstdio> using namespace std; const int mod = 1e9 + 7; int dp[100005][2][3]; int up(int &a, int b){ a += ...

原题:Chosing Recipes 原题大意有r种菜谱，有p种原料，每种原料都有相应的价格，已经有了m种原料，需要你做出n道菜，问最少需要花多少钱，注意：只要买了一种原料，下面如果还用到无需再买。输入的菜谱中，1表示需要这种原料，0表示不需要。 算法分析刚开始，我想通过暴力+回溯，可是p的最大值可以取到13，结果，就超时了。后来看了网上的题解，算法应该这样设计：1.将菜谱当成2进制，然后用数组保存，因为最多有2^13种可能，数组开到9000就够了。2.用动态规划，每种菜谱要么选，要么不选，选了之后会对下面的选择造成影响，可以用记忆化搜索完成。 程序代码#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <vector> using namespace std; const int INFI = (1 << 20) - 1; int r;// 菜谱数 int p;// 配料数 int m;//已 ...