ABBA d[i][j] 表示 放 i 个A j 个 B的方案数 d[i][j] 可以由d[i-1][j] 和d[i][j-1] 得到 当 i <= n ,那么A可以随意放； 当 j <= m，那么B可以随意放； 当 i > n，如果放A，AB的数量要小于等于n，i - j 是至少有多少个AB ，i - j <=n； 当 j > m，如果放B，BA的数量要小于等于m，j - i 是至少有多少个BA ，j - i <=n； #include<bits/stdc++.h>...

Equivalent Prefixes 题意：给你两个数组a，b，大小为n，让你寻找一个数p (1<= p <= n) ，使之在 1~p 任意一个区间中a,b数组的最小值下标相同。 笛卡尔树： 概念 笛卡尔树的树根是这一子树中键值最小（或最大）的元素；且对于某个序列的笛卡尔树，其任一子树的中序遍历恰好是对应了原序列中的一段连续区间。 性质 我们会发现笛卡尔树同时满足二叉树搜索和堆的性质： 中序遍历即为原数组序列 父节点的键值均小于（或大于）其左右子节点的键值 我们可以将问题转化为 1~p内，a和b的笛卡尔树是否相...

P1020 导弹拦截 第一问，相当于求一个最长不上升子序列。 第二问，相当于求一个最长上升子序列 证明如下： 假设打导弹的方法是这样的：取任意一个导弹，从这个导弹开始将能打的导弹全部打完。而这些导弹全部记为为同一组，再在没打下来的导弹中任选一个重复上述步骤，直到打完所有导弹。 假设我们得到了最小划分的K组导弹，从第a(1<=a<=K)组导弹中任取一个导弹，必定可以从a+1组中找到一个导弹的高度比这个导弹高（因为假如找不到，那么它就是比a+1组中任意一个导更高，在打第a组时应该会把a+1组所有导弹一起打下而不是另归为第a+1组），同样从a+1组到a+2组也是...

Design Tutorial: Inverse the Problem 题意：给你一个距离矩阵，让你证明该矩阵是不是一颗加权树的距离矩阵。 对于一个点u，与它距离最近的点一定是与它直接相连的，所以对矩阵求一次最短路，可以得到这颗树。然后只需要求出树上任意两点之间的距离是否与矩阵的距离相同就可以了。 求树上任意两点距离，可以使用LCA+树上前缀和，两点间距离等于两点到公共祖先距离之和。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e3+100; int n;...

小雨坐地铁 官方题解： 考虑分层图最短路。 很容易想到建 m 层图，如果多条地铁线都经过同一个点，则在这些点之间暴力两两连边，这样连边是 O(n) 的，可能会超时。 我们可以多建一层虚点，所有点到它对应的虚点不需要代价，从虚点到它对应的点需要对应的代价，这样就可以优化到 O(nm) 建图。最后跑一边最短路就好了。 建m层图， 0 ~ m-1 层表示每条线路。 第m层是虚点，m层的第 i 个点，可以到达任一层的 i 点，需要支付的对应的钱，从任一 i 点到m层 i 点不需要费用。 #include<bits/stdc++.h> using namespace s...

小石的妹子 官方题解： 因为有两维的限制，所以我们先按 ai 从大到小排一下序， 对于排序后的第 i 个妹子，她的排名就是 max{rk[j]}+1 (bj>bi)， 那么我们把排名 bi 当成下标，把 rki 当成值，用线段树维护一下区间  max 即可。 将bi排序，将每个妹子对应的bi变成排序后bi的编号，，对ai进行从大到小排序。 i 从 0 到 n 遍历，对于每个妹子，将她插入线段树中，妹子的重要程度为区间（bi，n）的最大值 + 1，然后将妹子的重要程度更新到bi位置。 模拟： 妹子0，查询线段树中区间（bi，n）的最大值，此时线段树中每个节点都...

小阳买水果 从大佬处学习的 求出ai的前缀和，用线段树维护前缀和最大值， 从 0 遍历到 n ，在线段树中找到大于sum[i]的最远的一个编号，每次先往右找，保证找到的值是最远。然后取最远距离 - i 的最大值。 #include<bits/stdc++.h> using namespace std; #define Mid ((l+r)>>1) #define Left rt<<1,l,Mid #define Right rt<<1|1,Mid+1,r typedef long long ll; const int N=2e6+10;...

J. Thanos Power 题意：给你一个数N，让你求它最少通过多少次操作得到的。 初值为0，每次操作只能增加，x >= 0; 0最少通过多少次操作得到的N，等价于N通过多少次操作得到的0 从高位往低位看，，， 对于每一位上的数x，我有两种方法让它变成0， 一直加 1，加到10后进位，操作数10-x 一直减 1，减到 0， 操作数 x d[i][0] 表示第i位一直执行加 1 ,最后变成0的操作次数。 d[i][1] 表示第i位一直执行减 1 ,最后变成0的操作次数。 d[i][0]=10-x + min ( d[i-1][0]-1 ,  d[i-1][1]...

Bashar and Hamada 给你一个长度为 n 的数组 选k个数，使F=，ai 、aj  k个数，i！= j 。求k=2，3，……n时，F的最大值 首先n=2时，肯定选择数组中的最大值和最小值，这样F2=max-min，F2最大 n=3时，在F2的，然后无论选择哪个，假设选取的数是x，F3=F2 + max - x + x - min = 2 * F2                                                      n=4时，在F3的基础上，随便取一个数 y， F4 =F3 + max - y + y - min +| y -...

Meeting Bahosain 给你一个数组a和一个数组b，你可以让数组a中的数 +/- 数组b中的任一个数。目标使a数组中数相等。 可以将a[n]的值转化为a[n-1]再转化为a[n-2]，……，最后使所有数都等于a[0]，那么就是对于所有a[i] - a[i-1]都能由b表示出来，就输出YES 设对于所有i ，x=a[i] - a[i-1] , 那么x=k1*b1 + k2*b2 +k3*b3 + k4*b4 ……，ki是任意整数（每次只能加减bi），可以发现只要x % gcd(b1 b2....bn) ==0 ,那么该方程一定成立。例如：3=2*k1+4*k2 -->3/2...

D - Tokitsukaze, CSL and Stone Game 给n堆石子，每一堆有a[i] 个 石头，现在二人玩游戏，每一人每一次选择一个非空的石头堆，从中拿出一个石头。如果当一个人操作之后，这n堆石头中有两堆中的石头数量是相同的，那么这个人就输掉。假设二人决定聪明，请判断是先手赢还是后手赢。  通过思考我们可以知道初始情况是以下情况先手必输 空堆的数量 >=2 有三个堆中石头数量相等 或者 有至少两 对 堆中石头数量相等。 有这种情况 x x x-1 如果先手不必输，那么二人的最优操作之后，石子堆一定会到达这个状态 （无顺序） 0,1,2,3,,,n-1...

 D:Two Sets 题意：将n个数分成两个集合。 如果x属于集合A，那么a - x一定属于集合A，如果x属于集合B，那么b - x一定属于集合B 首先很容易想到将，x与a - x同时存在，那么将它们放在A集合，同理B 但是这是错的，举个例子，a=3,b=6,   x: 1 2 4， x = 1 , a - x = 2 ， 所以 1 、2  放入集合A ，x = 4 ， b - 4 = 2  ， 那么2 ， 4在B集合 ， 如果a - x不存在，那么x一定不在A集合。 为什么？？ 因为，在A中没有与之相对应的a - x。 同样。。如果b -  x不存在，那么x一定不在B集合里面。...

Codeforces Round #268 (Div. 2)     题意：初始你手中有n张牌，数字分别是1~n，然后你任选其中两张牌，用“+”，“-”，“*”，来组合出另一张牌(另一个数字)，并把使用过的牌扔掉，问最后能否剩下的最后一张牌为24？如果不能，输出NO；否则，输出YES，并将如何得到24的方法打印出来。 构造，当n<4时，不可能存在， n==4时存在1*2*3*4=24， 当n==5时，存在5-1=4,4-2=1,现在剩下2*3*4=24， n为6时，1*2*3*4=24,6-5=1，1*24=24，n>5时n为偶数时，n-(n-1)=1,将大于4的全部转...

金色传说 参考于：xls tql 若存在a+b，那么一定存在一个a-b，两者求和，2*a，所以对于每个长度为n和合法式子，只需对每个式子第一个 +/- 前面数字求和，所以需要统计 + / - 号前面的a出现多少次。 假设第一个 + / - 前面是一个长度为i的数字，那么 +  / -  号后面有 n - i - 1位，每个长度为i的数字出现次数 = 2(正负两种情况) * 长度为 n - i -1 合法式子的种数。 因为每个长度为 i 的数字出现次数相同，所以先对长度为 i 的数字求和，前导0也算，用等差数列求和公式（1 + (10 ^ i - 1)）*(10 ^ i - 1) / 2 ...