Believe it

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial nameDZY Loves Fibonacci Numbers discriptiontime limit per test:4 secondsmemory limit per test:256 megabytesIn mathematical terms, the sequence $F_n$ of Fibonacci numbers is defined by the recurrence relation $F_1 = 1; F_2 = 1; F_n = F_{n - 1} + F_{n - 2} (n > 2)$.DZY loves Fibonacci numbers very much. Today DZY gives you an array consisting of n integers: $a_1, a_2, …, a_n$. Moreov ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###nameNonsense Time ###descriptionYou a given a permutation $p_1,p_2,…,p_n$ of size n. Initially, all elements in p are frozen. There will be n stages that these elements will become available one by one. On stage i, the element $p_{k_i}$ will become available. For each i, find the longest increasing subsequence among available elements after the first i stages. ###inputThe first line of the inpu ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###namePair ###descirptionGiven three integers A, B, C. Count the number of pairs <x,y> (with1≤x≤A and 1≤y≤B)such that at least one of the following is true: (x and y) > C (x xor y) < C(“and”, “xor” are bit operators) ###inputThe first line of the input gives the number of test cases, T (T≤100). T test cases follow. For each test case, the only line contains three integers A, B and ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###nameFind the median ###descirptionLet median of some array be the number which would stand in the middle of this array if it was sorted beforehand. If the array has even length let median be smallest of of two middle elements. For example, median of the array [10,3,2,3,2] is 3 Median of the array [1,5,8,1] is 1 At first, you’re given an empty sequence. There are N operations. The i-th operation c ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 给你两个分数,让你找一个分数在他们俩之间,要求分母最小, 这个问题很显然，我们应该转移到Stern Brocot Tree上面去做,对于给定的两个分数，我们把他们在树上标记出来，可能他们不在树的同一层，但是我们可以找到一个合适的层数，并且把他们标记在这一层，可能标记后，他们之间没有其他分数，那我们就选择更深的一层，直到他们在同一层，且中间有其他数字。 这时我们来分析答案在哪，首先很容易证明答案就在他们俩之间的那些分数之间，因为这些分数已经满足了值在他们俩之间，对于另一个要求-分母最小，这就要求我们在这些分数中取出一个分母最小的。 有一个很简单的做法可以帮助我们找到答案，那就是，把这些可能的答案全部标记为红色，真正的答案就是这些标记的lca。 当我们发现答案是lca的时候，我们也发现了另一个现象，分子分母具有轮换对称性当分母取到最小值的时候，分子可能有多个解，如果我们选择了最小的分子，我们将得到 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###namefraction ###descirptionMany problems require printing the probability of something. Moreover, it is common that if the answer is $\frac{a}{b}$, you should output $a×b^{−1}(modp)$ (p is a prime number). In these problems, you cannot know the exact value of the probability. It’s so confusing!!! Now, we want to reverse engineer the exact probability from such calculated output value x. We do so ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###name病毒 ###descirption二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。 示例：例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。 任务：请写一个程序：1.在文本文件WIR.IN中读入病毒代码；2.判断是否存在一个无限长的安全代码；3.将结果输出到文件WIR.OUT中。 ###input在文本文件WIR.IN的第一行包括一个整数n(n≤2000)，表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ###namethree arrays ###descirptionThere are three integer arrays a,b,c. The lengths of them are all N. You are given the full contents of a and b. And the elements in c is produced by following equation: c[i]=a[i] XOR b[i] where XOR is the bitwise exclusive or operation. Now you can rearrange the order of elements in arrays a and b independently before generating the array c. We ask you to prod ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog 51NOD1009 链接 https://www.51nod.com/Challenge/Problem.html#!#problemId=1009 题意         题意就是求1-n之内出现过多少个1，比如11出现两次，112出现两次。 题解         模版题。

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog 51NOD1055 链接 https://www.51nod.com/Challenge/Problem.html#!#problemId=1055 题意         N个不同的正整数A[i]，找出由这些数组成的最长的等差数列。N<=1e4,A[i]<=1e9 题解         dp[i][j]代表最后两项的下标为i和j,i<j, dp[i][j]&nb ...