BearChild's Blog

K优解 Time Limit: 20 Sec Memory Limit: 512 MB Description 给定n个行数，每行m个。在每行中选出一个数来，求出前 k 小的异或和。 Input 第一行 3 个正整数 n，m，k。 接下来 n 行，每行 m 个非负整数，第 i 行第 j 个为权值a[i][j]。 Output 一行一个数表示答案。 Sample Input 3 2 2 　　11 21 　　9 25 　　17 19 Sample Output 2 HINT n*m<=300000，k<=300000，保证m^n>=k，a[i][j]均不超过10^9 Solution 先对于每个 i，将每行的 a[i][1]~a[i][m] 从小到大排序，再将行按照其元素差值为多关键字排序（共m-1个关键字）。 那么我们知道，最小的方案肯定是所有行都取第一个。由于其有一些特殊，我们先抛开这个方案。 　　我们知道，次小的方案是**(2,1,1,1…)，把这个状态加入堆，由较优方案扩展较劣方案**，对于每一个状态，我们记录其扩展到第几行，以及取第几个元素。 在已经得到前 k ...

糖果 Time Limit: 10 Sec Memory Limit: 128 MB Description 幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的，lxhgww想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。 Input 输入的第一行是两个整数N，K。 　　接下来K行，表示这些点需要满足的关系，每行3个数字，X，A，B。 　　如果X=1， 表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多； 　　如果X=2， 表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果； 　　如果X=3， 表示第A个小朋友分到的糖果必须不少于第B个小朋友分到的糖果； 　　如果X=4， 表示第A个小朋友分到的糖果必须多于第B个小朋友分到的糖果； 　　如果X=5， 表示第A个小朋友分到的糖果必须不多于第B个小朋友分到的糖果； Ou ...

Young Maids Time Limit: 50 Sec Memory Limit: 512 MB Description 给定一个排列，每次选出相邻的两个放在队头，要求字典序最小。 Input 第一行一个整数n，第二行n个数表示这个排列。 Output n个数表示答案。 Sample Input 8 　　4 6 3 2 8 5 7 1 Sample Output 3 1 2 7 4 6 8 5 HINT n%2=0，2 <= n <= 2e5 Solution 倒着考虑。 　　我们维护一个小根堆，堆里面存**[l, r, val]，表示在区间[l, r]中选择两个元素，第一个元素A的权值为val**（保证合法），以val为第一关键字。 那么显然，我们每次选出堆顶进行操作。 显然，若我们取走了A,B（pos[A] < pos[B]），[l,r]就被拆成了 [l,A-1], [A+1,B-1], [B+1,r]，我们要保证每一个区间长度都是偶数。 　　那么只要有，pos[A]%2 == pos[l]%2，pos[B]%2 == pos[r]%2。 　　又由于我们每次 ...

哈密顿回路 Time Limit: 15 Sec Memory Limit: 256 MB Description 给定一张 n个点的边带权的无向完全图，求图中是否存在一条长为L的哈密顿回路。 哈密顿回路：从起点出发经过所有点恰好一次并最终回到起点(起点头尾经过两次)的路径。 Input Output Sample Input 4 10 　　0 3 2 1 　　3 0 1 3 　　2 1 0 2 　　1 3 2 0 Sample Output possible HINT Main idea 判断能否找到一条长度为L的哈密顿回路。 Solution 我们直接使用Meet in middle，记录M[t][opt]表示以 t 结尾，到的点为 opt 的长度集合。然后暴力合并即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787 ...

Akai的数学作业 Time Limit: 10 Sec Memory Limit: 128 MB Description 这里是广袤无垠的宇宙这里是一泻千里的银河，这里是独一无二的太阳系，这里是蔚蓝色的地球 　　这里，就是这里，是富饶的中国大陆！ 　　这里是神奇的河北大地，这里是美丽的唐山，这里是神话般的唐山一中，这里是Akai曾经的教室 　　黑板上还留有当年Akai做过的数学作业，其实也并不是什么很困难的题目: 　　“ 　　　　给出一个一元n次方程： 　　　　a0 + a1x + a 2 x2 +…+ anxn= 0 　　　　求此方程的所有有理数解。 　　” 　　Akai至今还深刻记得当年熬夜奋战求解的时光，他甚至还能记得浪费了多少草稿纸。 　　但是却怎么也想不起来最后的答案是多少了，你能帮助他么？ Input 第一行一个整数n。第二行n+1个整数，分别代表a0 到 an Output 第一行输出一个整数t，表示有理数解的个数 接下来t行，每行表示一个解 解以分数的形式输出，要求分子和分母互质，且分母必须是正整数特殊的，如果这个解是一个整数，那么直接把这个数输出 等价的解 ...

XLkxc Time Limit: 20 Sec Memory Limit: 128 MB Description 给定 k,a,n,d,p 　　f(i)=1^k+2^k+3^k+…+i^k 　　g(x)=f(1)+f(2)+f(3)+…+f(x) 　　求(g(a)+g(a+d)+g(a+2d)+…+g(a+nd))mod p Input 第一行数据组数，(保证小于6) 　　以下每行四个整数 k,a,n,d Output 每行一个结果。 Sample Input 5 　1 1 1 1 　1 1 1 1 　1 1 1 1 　1 1 1 1 　1 1 1 1 Sample Output 5 　5 　5 　5 　5 HINT 1<=k<=123 　　0<=a,n,d<=123456789 　　p==1234567891 Main idea 给定k,a,n,d，求 Solution 我们可以令 然后推一波式子，再令 那么显然有 然后我们通过若干次差分，发现g在差分k+3次时全为0，那么g就是一个k+2次多项式；f在差分k+5次时全为0，那么f就是一个k+4次多项式。 我 ...

ZS and The Birthday Paradox Time Limit: 20 Sec Memory Limit: 512 MB Description Input Output Sample Input 4 3 Sample Output 23 128 HINT Solution Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include<bits/stdc++.h>using namespace std;typedef long long s64;const int ONE = 1000005;const int MOD = 1e6 + 3;s64 n, k;s64 num = 0;s64 Fz = 1, Fm = 1;int get(){ int res;char c; while( (c=getchar())<48 || c ...

Floor it Time Limit: 10 Sec Memory Limit: 256 MB Description 令 x = (sqrt(5) + 1) / 2，求 floor(x^n) % p。 Input 一行两个整数 n, p。 Output 一行表示答案。 Sample Input 5 97 Sample Output 11 HINT n <= 1e18, p <= 998244353。 Solution 首先这必然是一道数学题。我们令 x = (1 + sqrt(5)) / 2, y = (1 - sqrt(5)) / 2 。 那么我们发现， x 和 y 分别是 x^2 - x - 1 = 0 的两个实数根。那么有 x^2 = x + 1。 我们这样操作： x^2 = x + 1 　　　　x^2 * x^(n-2) = x * x^(n-2) + x^(n-2) 　　　　x^n = x^(n-1) + x^(n-2) 令 An 表示 x^n，Bn 表示 y^n。那么显然有 An = An-1 + An-2，Bn = Bn-1 + Bn-2。 这时候 (A ...

tty的方程math Time Limit: 50 Sec Memory Limit: 128 MB Description 给定n、m、k、p。 a+b+c=n, a^2+b^2+c^2=m, a^3+b^3+c^3=k。 求a^p+b^p+c^p。 Input 输入n、m、k、p Output 以A/B形式表示答案。 Sample Input 5 7 11 4 Sample Output 27/1 HINT 0<=n,m,k <=20，0<=p<=10 Solution Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include<bits/stdc++.h>using namespace std;typedef long long s64;const int ONE = 1000005;const int MOD = 1e9 + 7;int get( ...

不等式 Time Limit: 10 Sec Memory Limit: 128 MB Description 小z热衷于数学。 　今天数学课的内容是解不等式：L<=Sx<=R 。小z心想这也太简单了，不禁陷入了深深的思考：假如已知L,R,S,M ，满足L<=(Sx) mod M<=R 的最小正整数x该怎么求呢？ Input 第一行包含一个整数T，表示数据组数，接下来是T行，每行为四个正整数M, S, L, R 。 Output 对于每组数据，输出满足要求的x值，若不存在，输出-1 。 Sample Input 1 　　5 4 2 3 Sample Output 2 HINT 30%的数据中保证有解并且答案小于等于10^6； 　另外20%的数据中保证L=R； 　100%的数据中T<=100，M, S, L, R<=10^9。 Solution Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include&l ...