11D_Beyonder's Blog

A. Erasing Zeroes You are given a string s. Each character is either 0 or 1. You want all 1’s in the string to form a contiguous subsegment. For example, if the string is 0, 1, 00111 or 01111100, then all 1’s form a contiguous subsegment, and if the string is 0101, 100001 or 11111111111101, then this condition is not met. You may erase some (possibly none) 0’s from the string. What is the minimum number of 0’s that you have to erase? Input The first line contains one integer t (1≤t≤100) — th ...

A-配对 题目描述 现在有正整数集合AAA和BBB，每个集合里有NNN个数，你要建立他们间的一一映射。 将每对配对的数字相加可以得到N个和，你要做的就是最大化第K大的和。 1≤K≤N≤1000001≤K≤N≤1000001≤K≤N≤100000输入的所有数字不超过108{10^8}108。 输入描述 第一行2个数字N,KN,KN,K 接下来两行，每行NNN个正整数，分别表示AAA和BBB中的元素。 输出描述 一行，表示第 K 大的和的最大值。 示例1 输入 3 2 1 2 3 1 2 3 输出 5 思路 首先，组成这K对数字的显然是A中最大的K个数字和B中最大的K个数字。 问题转化为，有K对数字，怎样配对使得最小的和最大。 经过玄学分析可以得到，倒序配对是最优的。 代码 1234567891011121314151617181920212223242526272829#include<iostream>#include<algorithm>using namespace std;typedef long long ll;bool cmp(int x,int ...

A-模板 题目描述 牛牛，牛可乐和牛能组成了一只队伍参加ACM系列赛事，他们起了一个优雅的队名叫~“牛牛战队”。 牛牛战队在没有比赛的时候，会把各种板子放在密码柜里，防止弄丢。这一个密码由整个队伍掌管。其中牛牛和牛能有两个密钥，各自有一个仅由大写字母构成的字符串。牛可乐则掌握着解密方法。一天，你用一瓶可乐贿赂牛可乐，得到了解密的办法。 牛可乐将试图通过以下操作用尽可能少的步骤把一个密钥转换为另一个： ①将其中任意一个字母替换为另一个 ②把最后一个字母删除 ③在尾部添加一个字母 ④得到的转化步数就是最后的密码。 一天，你和他们队员一起聚餐，你用可乐把他们灌倒了，从牛牛和牛能口中套出了两个密钥。你要趁他们醒之前拿到模板并复印一份再放回去。你能尽快的算出密码吗？ 输入描述 输入数据共33行，第一行包括两个整数$n,m{\text{(1}} \leqslant n,m \leqslant {10^5})$，表示两个密钥的长度。 第二行包含一个长度为n的字符串s1{s_1}s1​，表示第一个密钥。 第三行包含一个长度为m的字符串s2{s_2}s2​，表示第二个密钥。 输出描述 在一行内输出一 ...

A-欧几里得 题目描述 欧几里得算法是一种求最大公约数的有效算法，在算法竞赛中很常用。 Python代码实现如下： 1234def gcd(a,b): if b == 0: return a return gcd(b,a%b) 现在，如果已知 gcd(a,b) 共递归了 n次，求所有可能的a,b中满足a>b>=0且a+b最小的一组的a与b之和。 输入描述 第一行一个整数,T。 接下来T行一行一个整数，n。 输出描述 T行，每行一个整数，代表a+b。 示例1 输入 1 0 输出 1 说明 gcd(1,0) 由于 b=0，不会递归，即是递归0次。 示例2 输入 1 1 输出 3 说明 gcd(2,1)会递归一次至gcd(1,0)。 思路 题给的两个样例非常具有启发性。(2,1)递归一次变为(1,0)。那么我们给出的(a,b)最终必定会递归至(2,1)–>(1,0)。(a,b)一步递归后变为(b,a%b)，这是一定的；但是从(b,a%b)反推(a,b)有多种情况，而使a+b最小的情况是(a,b)=(b+a%b,b)。于是有序列(1,0),(2, ...

A-牛牛的DRB迷宫 I 题目描述 牛牛有一个 n×mn\times mn×m 的迷宫，对于迷宫中的每个格子都为 ‘R’,‘D’,‘B’ 三种类型之一，'R’表示处于当前的格子时只能往右边走’D’表示处于当前的格子时只能往下边走，而’B’表示向右向下均可以走。 我们认为迷宫最左上角的坐标为 (1,1)(1,1)(1,1)，迷宫右下角的坐标为 (n,m)(n,m)(n,m)，除了每个格子有向右移动以及向下移动的限制之外，你也不能够走出迷宫的边界。 牛牛现在想要知道从左上角走到右下角不同种类的走法共有多少种，请你告诉牛牛从 (1,1)(1,1)(1,1) 节点移动到 $(n,m) $ 节点共有多少种不同的移动序列，请你输出方案数对 $10^9+7 $ 取余数后的结果。 我们认为两个移动序列是不同的，当且仅当移动序列的长度不同，或者在某一步中采取了不同的移动方式。 输入描述 第一行输入两个正整数n,m(1≤n,m≤50)n,m(1≤n,m≤50)n,m(1≤n,m≤50)表示迷宫的大小是 nnn 行 mmm 列。 接下来n行，每行输入一个长度为m的字符串，字符串中仅包含大写字母’D’,‘ ...

A-做游戏 题目描述 牛牛和 牛可乐在玩石头剪刀布。 众所周知，石头剪刀布的规则是这样的： 在一局游戏中，双方各自出石头、剪刀、布其一。 胜负关系如下： 牛牛和牛可乐进行了多轮游戏，牛牛总共出了A次石头，B次剪刀，C次布；牛可乐总共出了 X次石头，Y次剪刀，Z次布。你需要求出牛牛最多获胜多少局。 输入描述 第一行，三个非负整数 A,B,C 。 第二行，三个非负整数 X,Y,Z 。 保证$ A+B+C=X+Y+Z, 0≤A,B,C,X,Y,Z≤1000000000$。 输出描述 输出一行，一个整数表示答案。 示例1 输入 114514 0 0 0 114514 0 输出 114514 思路 尽可能让牛牛的每次出 剪刀/石头/布 对应到牛可乐出 布/剪刀/石头。 ans=min(A,Y)+min(B,Z)+min(C,X)ans=min(A,Y)+min(B,Z)+min(C,X)ans=min(A,Y)+min(B,Z)+min(C,X)。 时间复杂度 O(1)。 代码 123456789101112131415#include<cstdio>#include<al ...

E .1-Trees and Queries(LCA求树上距离) Gildong was hiking a mountain, walking by millions of trees. Inspired by them, he suddenly came up with an interesting idea for trees in data structures: What if we add another edge in a tree? Then he found that such tree-like graphs are called 1-trees. Since Gildong was bored of solving too many tree problems, he wanted to see if similar techniques in trees can be used in 1-trees as well. Instead of solving it by himself, he’s going to test you by providing ...

定义 在图论和计算机科学中，最近公共祖先是指在一颗树或者一个有向无环图中同时拥有vvv和www作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果vvv是www的后代，那么www就是vvv和www的最近公共祖先。(来源:维基百科) 如图，是一棵树 每两个点的最近公共祖先一目了然。 用树上倍增求两点的LCA 思想 如图，是一棵树 每两个节点的最近公共祖先一目了然。 假设我们要寻找x,yx,yx,y的最近公共祖先（默认xxx的深度比yyy的深度大），只需要做到如下步骤： ①利用倍增算法，将xxx上升至同yyy的相同深度； ②同步上升x,yx,yx,y，直到两节点的父亲节点相同； ③返回此时相同的父亲节点。 father[n][logn]father[n][logn]father[n][logn]和每一个节点的深度depth[n]depth[n]depth[n]可以通过BFS\text{BFS}BFS得到，上升的步骤则利用倍增算法。 用LCA求树上两点的距离 思想 如图，是一棵树 设两点的编号为u,vu,vu,v(默认uuu的深度比vvv的深度大),两点的位置关系会 ...

倍增思想 如图，是一棵树 假设一棵树有nnn个节点，开一个数组father[n][logn]father[n][logn]father[n][logn]，father[i][j]father[i][j]father[i][j]表示第iii个节点的第2j2^j2j个父亲。当寻找父亲节点时，每次跳2p2^p2p层，大大降低时间复杂度，显然有2p−1+2p−1=2p2^{p-1}+2^{p-1}=2^p2p−1+2p−1=2p，于是得到递推式： father[i][j]=father[fahter[i][j−1]][j−1]father[i][j]=father[fahter[i][j-1]][j-1] father[i][j]=father[fahter[i][j−1]][j−1] 其实就是2j2^{j}2j分成两步跳。 由于二进制可以表示任何数字，所以这样的跳跃能到达树上的每一个节点。 寻找父亲节点 我们要寻找iii的第kkk个父亲节点，就需要把kkk拆成二进制，若kkk的第jjj位为111，则需要将iii向上倍增2j2^j2j。 代码如下 1234567int FindFather( ...

快速幂 思想 我们要让计算机很快地计算出aba^bab。 可以利用乘方的性质：axay=ax+ya^xa^y=a^{x+y}axay=ax+y。 我们要求aba^bab，可以将bbb拆成二进制数。比如b=(11)10=(1011)2b=(11)_{10}=(1011)_2b=(11)10​=(1011)2​，从左至右，每一个111，分别代表8,2,18,2,18,2,1，可以计算a11=a8a2a1a^{11}=a^8a^2a^1a11=a8a2a1 。 可以得出，如果bbb在二进制上的第nnn位是111,我们就把答案乘上对应的a2na^{2^n}a2n。 在快速幂中，我们通过aaa的不断自乘，得到a1,a2,a4...a^1,a^2,a^4...a1,a2,a4...，通过bbb的右移(>>)，自右向左取得bbb的二进制位，用按位与运算(&)判断每一位是否为111。 代码 12345678910111213141516171819202122#include<iostream>using namespace std;typedef long long ...