hdu 5950 Recursive sequence (构造矩阵,快速幂)

题目链接

题意:

给f[1],f[2],n,f[i] = 2*f[i-2] + f[i-1] + i^4,求f[n]的值。

思路:

很容易想到矩阵,但是i^4不是线性的差评,我们可以拆一下

i^4=(i-1+1)^4,然后二项式展开即可

i^4=(i-1)^4 + 4*(i-1)^3 + 6(i-1)^2 + 4(i-1) + 1

所以为了维护i^4这一项,需要(i-1)^4,(i-1)^3,(i-1)^2,(i-1),1,

再加上f[i-1]和f[i-2]两项,一共7项。

然后构造矩阵为

16沈阳 onsite的题,当时好像写了一个小时,现在看来,果然是个人尽皆知的傻逼题orz

 

UVA – 10518 How Many Calls? (构造矩阵,快速幂)

题目链接

题意:

求f[n] = f[n-1] + f[n-2] + 1,在b(10000)进制下的最后一位数字的十进制表示。

思路:

构造矩阵即可,M矩阵是一个33的矩阵,M1矩阵是一个31的矩阵。。很easy,就不说了。

写题解的目的是,对于这种要求b进制下,最后一位或者最后两位的数字的十进制表示的问题,其实就是在说,取模的数是base或者base^2

1A美滋滋

 

hdu 4686 Arc of Dream (构造矩阵,快速幂)

hdu4686题目链接

题意:

An Arc of Dream is a curve defined by following function:


where
0 = A0
i = a i-1AX+AY
0 = B0
i = b i-1
BX+BY
What is the value of AoD(N) modulo 1,000,000,007?

 

思路:

看n的1E18的范围也知道是矩阵快速幂。。

难点还是构造矩阵。

构造矩阵主要凭借经验,但是还是有一些规律可循:

  1. 对于求和的式子,如 s[n] = sum{F[1]..F[n]}类似的式子,我们只需要考虑如何构造F[n]即可。
  2. 尽量将要构造的表达式展开成,第n项,与前面项(第n-1项等)有关的形式。
  3. 观察2中展开的表达式的系数,每一个系数都亚奥出现在转移矩阵M中。
  4. 观察2中展开的表达式的项,基本每一项都要整体或者以其他形式出现在初始矩阵M1中
  5. 我们并不很关心初始项。
  6. 难点其实在于构造M1矩阵,也就是说哪些项是重要的。一般而言,可能有的项是,s[n],f[n],常数项,以及为了构造出f[n]的辅助项。

对于这道题:

 

然后矩阵快速幂即可。

1A

 

hdu 4990 Reading comprehension (构造矩阵,快速幂)

题目链接

题意:

给出了一段程序,程序实际算的是f[n] = (f[n-1] + n%2)%m的值,其中f[1]=1,给出n,m(1E9),问f[n]

思路:

显然是矩阵快速幂,终点在于构造矩阵。

通过经验可得(这次真的是经验了。。。其实也挺容易的,要点大概在于先把需要的项列在一起,然后增加0或者多个,为了转移需要的辅助项。

根据当前列和下一列,手动构造转移矩阵)

转移矩阵M为

[2, 1,0]

[0,-1,1]

[0,0 ,1]

 

4A..都是一个原因。。矩阵乘法那里。。。就算你%了m..也是两个1E9在相乘。。。然后就炸了23333,改成LL即可。

 

 

 

 

今日头条笔试题_或与加(打表,构造)

给定 x, k ,求满足 x + y = x | y 的第 k 小的正整数 y 。 | 是二进制的或(or)运算,例如 3 | 5 = 7。

比如当 x=5,k=1时返回 2,因为5+1=6 不等于 5|1=5,而 5+2=7 等于 5 | 2 = 7。

 

输入描述:

每组测试用例仅包含一组数据,每组数据为两个正整数 x , k。 满足 0 < x , k ≤ 2,000,000,000。

 

输出描述:

输出一个数y。

 

输入例子:

 

输出例子:

一看就是数学题…?
打表观察…

 

发现如果x的二进制表示中,如果某位为1,那么对应的y的位置上一定为0.

如果某位为0,那么对应的y的位置上可以为0也可以为1…

就是说…x的二进制表示中,为1的的那些位置是能改变的.

影响当前第几大的就是那些为0的位置…

所以我们可以把k转化成二进制表示,按顺序填充到x中为0的那些位置(主要可以填充到x最大权值的1之后的0的位置),然后得到的数就是x+y的答案,最后再减去x即可

因为数组开小了..第一次只过了90%….

果然是个废k了呜呜呜,数组开小这种错误我也是服了…

 

codeforces #381 div 2 C. Alyona and mex (构造)

题目链接

题意:

m个区间,要求构造一个长度为n的数组,满足m个区间中,每个区间的mex值中的最小值最大。

s思路:很容易想到的是…这个最大的mex 不可能超过每一组区间长度,假设最小的区间长度为mn

那么是否一定可以构造出mex为mn的数组呢?

是的。

只需要按照

0,1,2…mn-1,0,1….的方式构造即可。

 

codeforces 496 C Removing Columns (构造)

题目链接

题意:给一个n*m的由小写字母组成的table.要求从上往下每一行字典序不严格递增。问最少删除几列才能满足。

思路:一开始想的是用一个left数组维护每次删除后某一列左边是哪一列,目的是为了下次的判断。

再想了下,发现没必要。我们只需要知道,两行之间的关系是否确定就好了。over[i][j]为真表示第i行和第j行的胜负已分,对于胜负已分的行,大小无所谓。

对于胜负未分的行,如果table[i][j]>table[i+1][j],就必须要删掉这一列了。。。。

需要注意的是,某一列最多删一次,记得打上标记。

以及ove标记的时候,要在最后确定这一列没有被删以后再标记。。。用一个set存下可能的胜负已分的行的下标即可。

1A

 

codeforces 509 B. Painting Pebbles (构造)

题目链接

题意:n堆石子,每堆a[i]个,k种颜色。给每个石子涂色,要求对于每种颜色,任意两堆中该颜色石子的个数最多差一个。问是否有解,有解输出一组方案。

思路:我们发现有解与否只和最大值最小值有关。

设mn为最小值,mx为最大值。

当mx>mn+k时无解,否则有解。

如果有解。。。输出方案就好了。。。

 

codeforces 468 A. 24 Game (构造)

题目链接

题意:给出n,有1..n n个数,可以选择两个数进行加,减,乘,三种操作,操做完得到一个数放回。 n-1次操作后只剩下一个数。现在要求剩下的数为24.问方法。

思路:我们发现。。。两个数相减可以为1.。那么只要找到4个数的方案和5个数的方案就好了。。。

4个数:1*2*3*4

5个数:4*5+3+2-1

 

然而窝一开始以为必须前面减后面。。。

所以是按照4K,4K+1,4K+2,4K+3分的类。。。每4个数得到两个-1,再相乘。。。。麻烦了一点。。代码写了一半的时候意识到了按2K,2K+1分类就行。

 

codeforces 679A A. Bear and Prime 100 (交互题,构造)

题目链接

题意:存在一个[2..100]之间的数,每次可以询问一个数是否是该数的因子,返回yes或者no,最多询问20次。每次要输出询问的数,以及最后要输出这个数是否是质数。

思路:第一次做交互题。。。发现完全不能按照以前的思路。。。

更像是相反的。。。把output看做某种输入。。。input里是某种结果。。。我要根据input里的东西来确定一些东西。

就是先有output,再有input。。。output是选手的输入(最后一个除外),input是返回结果(不是你写的代码的返回结果)

 

对于这道题。。我们要尽可能少得猜一个数的因子,以确定该数是否为质数。

一个数不是质数的话,就有至少两个大于1的因子。。。

很容易想到。。。判素因子。。。

由于至少有2个非1的因子才不是素数。。。最小为2,因此另一个因子不会大于50.。。

此外。。。有可能有两个相同质因数组成的因子。。。。

因此还要判一下2*2,3*5,5*5,7*7

 

 

codeforces 623 A. Graph and String (构造)

题目链接:题目链接

题意:给出一个无向图,该图是通过仅包含‘a’ ‘b’ ‘c’三个字母,以规则“i,j之间有边,当且仅当s[i]和s[j]相同,或者s[i]和s[j]在字母表中相邻”(也就是只有’a’和’c’是没有边相连的)得到的,现在问能否还原这个字符串,如果能,输出任意一个解。

思路:其实就是简单构造。。。

构造的一个技巧是。。把能确定的地方先确定了。。。。

我们发现’b’比较特殊。。因为b和任意点都相连。。。

于是可以统计一下度。。。然后确定字符串中的b

然后对于某个没有确定的位置,我放置一个a,并且把所有和这个位置相连的都放成a

字符串中剩下的没有确定的位置就一定是c了。

这个时候我再判断是否满足题中图的条件。

 

 

codeforces #368 div 2 C. Pythagorean Triples (构造,数学)

题目链接

题意:给出一个数,问包含这个数三个数组成的勾股数,输出另外两个数。

思路:

所谓勾股数,就是当组成一个直角三角形的三边长都为正整数时,我们就称这一组数为勾股数.
那么,组成一组勾股数的三个正整数之间,是否具有一定的规律可寻呢?下面我们一起来观察几组勾股数:
规律一:在勾股数(3,4,5)、(5,12,13)、(7,24,25)(9,40,41)中,我们发现
由(3,4,5)有:32=9=4+5
由(5,12,13)有:52=25=12+13
由(7,24,25)有:72=49=24+25
由(9,40,41)有:92=81=40+41.
即在一组勾股数中,当最小边为奇数时,它的平方刚好等于另外两个连续的正整数之和.因此,我们把它推广到一般,从而可得出以下公式:
∵(2n+1)²=4n²+4n+1=(2n²+2n)+(2n²+2n+1)
∴(2n+1)²+(2n²+2n)²=(2n²+2n+1)²(n为正整数)
证明(略)
勾股数公式一:(2n+1,2n²+2n,2n²+2n+1)(n为正整数)
规律二:在勾股数(6,8,10)、(8,15,17)、(10,24,26)中,我们发现
由(6,8,10)有:62=36+2×(8+10)
由(8,15,17)有:82=64=2×(15+17)
由(10,24,26)有:102=100=2×(24+26)
即在一组勾股数中,当最小边为偶数时,它的平方刚好等于两个连续整数之和的二倍,推广到一般,从而可得出另一公式:
∵(2n)2=4n2=2[(n2-1)+(n2+1)]
∴(2n)2+(n2-1)2=(n2+1)2(n≥2且n为正整数)
证明(略)
勾股数公式二:(2n,n²-1,n²+1)(n≥2且n为正整数)
利用以上两个公式,我们可以快速写出各组勾股数.

结论是:  n<=2无解。

n为奇数用公式1构造。

n为偶数用公式2构造。

 

 

 

 

codeforces 652 B. z-sort (简单构造)

题目链接
题意:给出n个元素的序列,问能否得到一个新的序列,使得奇数位置非递减排列,偶数位数非递增排列。
思路:感觉一定可以啊。。。排序以后直接构造。。。

codeforces #342 div 2 D. Finals in arithmetic

http://codeforces.com/contest/625/problem/D
题意:问能否找到一个s,满足s+s的反转=k
思路:如果是回文数。。。那么显然满足。除以2就可以得到答案。
如果不是回文数。。那么考虑进位的情况。
要么从后一位进1,要么从前一位退10回来。
需要特殊考虑1开头的。

codeforces #342 div 2 C. K-special Tables

http://codeforces.com/contest/625/problem/C
题意:构造一个矩阵。。满足三个条件。。。
思路:简单构造。。。看代码把。。。。