BearChild's Blog

数字表格 Time Limit: 50 Sec Memory Limit: 128 MB Description Doris刚刚学习了fibonacci数列。用f[i]表示数列的第i项，那么 f[0]=0 f[1]=1 f[n]=f[n-1]+f[n-2],n>=2 Doris用老师的超级计算机生成了一个n×m的表格，第i行第j列的格子中的数是f[gcd(i,j)]，其中gcd(i,j)表示i,j的最大公约数。Doris的表格中共有n×m个数，她想知道这些数的乘积是多少。答案对10^9+7取模。 Input 第一个一个数T，表示数据组数。 接下来T行，每行两个数n,m Output 输出T行，第i行的数是第i组数据的结果 Sample Input 3 　2 3 　4 5 　6 7 Sample Output 1 　6 　960 HINT T<=1000,1<=n,m<=10^6 Solution 运用莫比乌斯反演，得到式子： 这样我们对于内外分块即可，复杂度为O(n^(0.75)*T)。 Code 1234567891011121314151617181920 ...

序列 Time Limit: 20 Sec Memory Limit: 512 MB Description 给定长度为n的序列：a1,a2,…,an，记为a[1:n]。 　　类似地，a[l:r]（1≤l≤r≤N）是指序列：al,al+1,…,ar-1,ar。 　　若1≤l≤s≤t≤r≤n，则称a[s:t]是a[l:r]的子序列。 　　现在有q个询问，每个询问给定两个数l和r，1≤l≤r≤n，求a[l:r]的不同子序列的最小值之和。 例如，给定序列5,2,4,1,3，询问给定的两个数为1和3， 　　那么a[1:3]有6个子序列a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3]， 　　这6个子序列的最小值之和为5+2+4+2+2+2=17。 Input 输入文件的第一行包含两个整数n和q，分别代表序列长度和询问数。 　　接下来一行，包含n个整数，以空格隔开,第i个整数为ai，即序列第i个元素的值。接下来q行，每行包含两个整数l和r，代表一次询问。 Output 对于每次询问，输出一行，代表询问的答案。 Sample Input 5 5 　5 2 4 1 3 ...

Gty的二逼妹子序列 Time Limit: 80 Sec Memory Limit: 28 MB Description Autumn和Bakser又在研究Gty的妹子序列了！但他们遇到了一个难题。 对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。 为了方便，我们规定妹子们的美丽度全都在[1,n]中。 给定一个长度为n的正整数序列s(1<=si<=n)，对于m次询问“l,r,a,b”，每次输出sl…sr中，权值∈[a,b]的权值的种类数。 Input 第一行包括两个整数n,m,表示数列s中的元素数和询问数。 第二行包括n个整数s1…sn(1<=si<=n)。 接下来m行,每行包括4个整数l,r,a,b(1<=l<=r<=n,1<=a<=b<=n),意义见题目描述。 保证涉及的所有数在C++的int内。 保证输入合法。 Output 对每个询问，单独输出一行，表示sl…sr中权值∈[a,b]的权值的种类数。 Sample Input 10 10 　4 4 5 1 4 1 5 1 2 1 　5 ...

mex Time Limit: 20 Sec Memory Limit: 128 MB Description 有一个长度为n的数组{a1,a2,…,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。 Input 第一行n,m。 　第二行为n个数。 　从第三行开始，每行一个询问l,r。 Output 一行一个数，表示每个询问的答案。 Sample Input 5 5 　2 1 0 2 1 　3 3 　2 3 　2 4 　1 2 　3 5 Sample Output 1 　2 　3 　0 　3 HINT 1<=n,m<=200000, 0<=ai<=1e9 Solution 首先，权值>n的显然是没有用的，最多排满1~n。然后我们直接使用莫队，对权值分块，查询的时候看一下这个块里面权值数是否满了，即可做到O(sqrt(n))的查询。 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565 ...

消耗战 Time Limit: 20 Sec Memory Limit: 512 MB Description 在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。 侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到1号岛屿上）。不过侦查部门还发现了这台机器只能够使用m次，所以我们只需要把每次任务完成即可。 Input 第一行一个整数n，代表岛屿数量。 接下来n-1行，每行三个整数u,v,w，代表u号岛屿和v号岛屿由一条代价为c的桥梁直接相连，保证1<=u,v<=n且1<=c<=100 ...

下落的圆盘 Time Limit: 10 Sec Memory Limit: 162 MB Description 有n个圆盘从天而降，后面落下的可以盖住前面的。求最后形成的封闭区域的周长。 看下面这副图, 所有的红色线条的总长度即为所求。 Input 第一行为1个整数n 　接下来n行每行3个实数,ri,xi,yi,表示下落时第i个圆盘的半径和圆心坐标. Output 最后的周长，保留三位小数 Sample Input 2 　1 0 0 　1 1 0 Sample Output 10.472 HINT n <= 1000 Solution 显然是一道计算几何题。 考虑一个圆对于答案的贡献，显然是这个圆的周长 - 后面的圆把它覆盖掉的周长的并。那么我们就考虑怎么求这个并。 先考虑怎样记录下一个答案，显然直接扣掉单个圆对它的覆盖是不可行的，要减去重叠的情况。 既然边不可行，我们就用角度。显然，若我们求出 两圆交点的角度 即可解决这题。 我们考虑求圆A被圆B覆盖的角度：现在我们有两个圆的半径、圆心距。我们就可以得到 圆A与圆B的圆心连线 与 圆A半径 的夹角。 我们也可以知道 圆A与 ...

数矩形 Time Limit: 20 Sec Memory Limit: 128 MB Description 最近某歌手在研究自己的全国巡回演出，他将所有心仪的城市都用平面上一个点来表示，并打算从中挑选出4个城市作为这次巡回演出的地点。 　　为了显示自己与众不同，他要求存在一个矩形使得挑选出的4个点恰好是这个矩形的4个顶点，并且希望这个矩形的面积最大。 　　这可急坏了经纪人，于是他向全球歌迷征集方案，当然你这位歌迷一定不会错过这个机会。 Input 第一行是一个正整数N，表示平面上点的个数（即某歌手心仪的城市数）。 　　接下来N行，每行是两个整数Xi,Yi，表示对应点的坐标。 Output 输出一个数，表示最大矩形面积。 Sample Input 8 　　-2 3 　　-2 -1 　　0 3 　　0 -1 　　1 -1 　　2 1 　　-3 1 　　-2 1 Sample Output 10 HINT 1<=N<=1500 , -10^8<=Xi,Yi<=10^8 Main idea 给出平面上的若干个点，求出可由这些点作为顶点构成的矩形的最大面积。 Solu ...

生日礼物 Time Limit: 10 Sec Memory Limit: 128 MB Description ftiasch 18岁生日的时候，lqp18_31给她看了一个神奇的序列 A1, A2, …, AN. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。 自然地，ftiasch想要知道选择元素之和的最大值。你能帮助她吗？ Input 第1行，两个整数 N 和 M , 序列的长度和可以选择的部分。 第2行， N 个整数 A1, A2, …, AN , 序列。 Output 一个整数，最大的和。 Sample Input 5 2 　2 -3 2 -1 2 Sample Output 5 HINT 1 ≤ N ≤ 105， 0 ≤ M ≤ 105， 0 ≤ |Ai| ≤ 104 Solution 首先，我们可以把权值正负相同的连续的一段合并起来。Ans+=（所有正数），块数++。 然后把每一段的绝对值加入到小根堆里面。每次贪心取出最小的来，块数减去 1 直到满足题目要求为止。 为什么这样可以对呢？我们来讨论一下： 1. 如果删去的段是正数， 那么相当于不取这个。 2. 如 ...

免费道路 Time Limit: 2 Sec Memory Limit: 128 MB Description Input Output Sample Input 5 7 2 　1 3 0 　4 5 1 　3 2 0 　5 3 1 　4 3 0 　1 2 1 　4 2 1 Sample Output 3 2 0 　4 3 0 　5 3 1 　1 2 1 HINT 1<=n<=20000,1<=m<=100000,0<=k<=n-1 Main idea 一种0边，一种1边，求一棵最小生成树并且正好有K条0边，输出其中一种方案。 Solution 显然要搞一棵符合题目的生成树。 每次要加入0边或者1边，直接做肯定不可行，考虑有什么0边是一定要加入的。 只需要输出一种方案，所以我们先加入所有可加的1边，如果图不联通则加入可加入的0边，那么这几条0边在我们所求的方案中是一定需要加入的。 这时候判断一下，如果此时加入的0边数量>K，或者图还是无法联通的话则无解。然后处理完毕前半部分，考虑接下来如何实现。 因为我们要使得图为树并且正好有K条0边，运用 ...

新生舞会 Time Limit: 10 Sec Memory Limit: 128 MB Description 学校组织了一次新生舞会，Cathy作为经验丰富的老学姐，负责为同学们安排舞伴。有n个男生和n个女生参加舞会买一个男生和一个女生一起跳舞，互为舞伴。 Cathy收集了这些同学之间的关系，比如两个人之前认识没计算得出 a[i][j] ，表示第i个男生和第j个女生一起跳舞时他们的喜悦程度。 Cathy还需要考虑两个人一起跳舞是否方便，比如身高体重差别会不会太大，计算得出 b[i][j]，表示第i个男生和第j个女生一起跳舞时的不协调程度。 当然，还需要考虑很多其他问题。Cathy想先用一个程序通过a[i][j]和b[i][j]求出一种方案，再手动对方案进行微调。 Cathy找到你，希望你帮她写那个程序。 一个方案中有n对舞伴，假设没对舞伴的喜悦程度分别是a’1,a’2,…,a’n， 假设每对舞伴的不协调程度分别是b’1,b’2,…,b’n。 令C=(a’1+a’2+…+a’n)/(b’1+b’2+…+b’n),Cathy希望C值最大。 Input 第一行一个整数n。 接下来n行，每 ...