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美滋滋

 

uva 10655 – Contemplation! Algebra (构造矩阵,快速幂)

uva10655题目链接

题意:

给出a+b和ab的值,问a^n+b^n

思路:

构造矩阵,手写一下很显然…

转移矩阵M=[0 , 1]

[-q,p ]

初始矩阵M1=[p           ]

[p^2-2*q]

快速幂即可。

有个坑点在于..读入的结束是p=0&q=0,并且只有这两个输入。

如果用p=0&&q=0作为终止条件,那么就会将三个输入,但p==0&&q==0的情况错误得终止…

正确的做法是 while (~scanf(“%lld%lld%lld”,&p,&q,&n)==3)

 

 

 

[dp专题000]uva 10328 Coin Toss (java 大数+dp)(Unsolved)

题目链接

题意:问长度为n,每个位置由且仅有‘H’和’T’组成的序列中,至少有连续k个‘H’出现的方案数。

思路:不会做,参考了题解 不过没有完全搞懂。

根据题解,正面考虑比较麻烦,所以反面考虑。[j]

dp[i][j]表示长度为i,前面最后连续的‘H’的个数不超过j个的方案数。

考虑转移方程为:

总的情况为:dp[i][j] = dp[i-1][j] * 2;

但是其中有多考虑的情况,就是第i位是’H’,且i位之前的最后j个位置都是’H’(即从i-j位到第i-1位都是‘H’,此时第i-j-1位必然是’T’)

有i个硬币时,如果i < j+1,那么它对于i-1的情况来说,最后一个硬币的位置就可以随便放了。

如果i > j + 1,dp[ i ] [ j ]  = dp [ i – 1 ] [ j ] * 2 – x(不满足条件的部分)

然后我们来考虑这个x怎么求,既然是不满足条件,那么肯定是第i的位置放了H,前面的都是H,从而这些连续的H大于j。那么就考虑dp[ i – 1 – j – 1 ](中间这 j – 1 个(kk:疑似作者笔误。应该位j个)全为H,加上第i个H,就不满足条件了),所以:

dp [ i ] [ j ] = dp [ i – 1 ] [ j ] * 2 – dp [ i – j – 2 ] [ j ](kk:仍然不是很懂这个式子…)

那么我们就差最后一个了:i == j + 1的情况了。(因为 i – j – 2 就等于 -1 了,用递推公式会RE的)

这种情况只有一种,即是全是H。

那么它就为:dp [ i ] [ j ] = dp [ i – 1 ] [ j ] * 2 – 1

 

 

 

最后,要用到高精度,干脆写了java

 

 

 

 

 

 

uva 10692 Huge Mods (欧拉函数,指数循环节)

题目链接

题意:求一个楼梯数%m的大小。

思路:指数循环节。

需要注意的是,模数只有最外层是m,每往里一层,模数都变成m=phi(m)

所以可以写个dfs或者先预处理出每一层m存一下。

记得考虑n=1的特殊情况。

 

 

uva 10004 Bicoloring (交叉染色法判断二分图模板题)

uva10004题目链接

题意:给出一个无向图,问是否可以组成二分图。

思路:交叉染色法。

首先任意取出一个顶点进行染色,和该节点相邻的点有三种情况:

          1.未染色    那么继续染色此节点(染色为另一种颜色)

          2.已染色但和当前节点颜色不同      跳过该点

          3.已染色并且和当前节点颜色相同       返回失败(该图不是二分图)

 

学习链接

 

upd:更正dfs中的一个错误。

把dfs(v,1-x)改成了 if (!dfs(v,1-x)) return false;

之前的写法中,当前层之后的层的没有起到任何作用。。。

而实际上应该是后面只要某一层不满足,整体就该为false.

写成这样这题还能过我也是醉了。。。。

ural 1314 Hidden Password (字符串的最小表示法模板题)

uva 1314 题目链接

题意:给定一个循环字符串,问字典序最小的串的开始位置。最小表示法裸题。

 

uva 10986 Sending email (spfa)

uva10986题目链接
题意:裸的spfa.

思路:模板,1A.

 

uva 10916 Factstone Benchmark

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1857
题意:计算最大的n,满足n!

uva 107 The Cat in the Hat

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=43
题意:其实就是给了两个式子。。。(N+1)^h=a,N^h=b,a,b已知,然后求关于N的两个式子.。。
思路:数学上这个方程貌似不可解。。? 所以只能枚举一下==。。。注意精度问题把。。。

然后用换底公式求对数的时候要向上取整。

还有b为1的时候是特殊数据。

 

 

 

uva 846 Steps

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=787

题意:从x增加到y,第一步和最后一步步长只能是1,其他步一定可以是上一步减一,和上一步相等,或者上一步步长加一,三种情况,且步长恒为正。问从x到y最少需要的步数。

思路:首先可以知道,走的最快的方法是1+2+3+…+k+…+3+2+1.这个式子的结果是一个完全平方数,为k^2,式子的长度为2*k-1.即为答案。
我们可以知道k肯定不超过 ceil(sqrt(y-x)).但是中间的k是不一定要加的。再判断k^2减去k是否已经达到结果,如果是,就将答案减一。
注意对于这种做法x=y是特殊情况。。需要特判。。。。

还有一种做法是比较好想的非数学方法。
由于对第一步和最后一步的步长有要求,都是1.
很容易想到从两边往中间走。
然后每走两步(两个方向各一步),后增加一次步长。

uva 10025 The ? 1 ? 2 ? … ? n = k problem

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=966
题意:?1?2?3?4…?n=k,把每个?替换成+或者-,找到最小的n使得式子成立。
题意:这道题最关键的一点是。如果s1=1+2+3+.,x+..+n>=k (所有数取正数),那么一定有s2=1+2+3+..-x+..+n=k

非严格证明如下:

s1-s2 = 2x,s1-k=2x

一个数减去偶数,奇偶性不变。x是从1到n中的一个,2*x则包含了s1和s2相差的数所有可能性。

 

具体做法就是找到一个大于等于k的s1,且s1-k是偶数。

 

 

 

 

uva 113 Power of Cryptography

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=49
题意:求p开n次方。保证结果为整数。
思路:p最大10的101次方。。。double最大10的308次方。。因为肯定是整数。。不存在精度问题。。所以可以用douible水过QAQ…

uva 10785 The Mad Numerologist

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1726
题意:给出26个大写字母的权值,要求构造一个长度为n(n不超过210)的字符串。并且满足奇数位置只能放元音字母,偶数位置只能放辅音字母,且每个元音字母最多放21次,每个辅音字母最多放5次,要求构造的字符串的权值之和最小,在权值最小的前提下字典序最小。

思路:贪心。一开始错误得以为不是完整得不能交换(也就是不完整的字母只能放在最后,这是错误的)。但实际上只要每个字母的数量不变,那么就不影响权值。所以做法是,奇数位置偶数位置分别搞,先把构成字符串的字母按次存入,然后排序一下,输出即可。

uva 10194 Football (aka Soccer)

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1135
题意:给出球队的名字和比赛的信息,得出stanging
思路:字符串处理。需要注意的是多组数据记得初始化多次,以及比较字典序的时候team name是大小写补敏感的。

uva 156 – Ananagrams

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=92
题意:给出一段文字,包含若干个单词,以’#’结束。按照字典序输出所有的ananagrams。所谓ananagram,是指经过任意的重排后,不能得到这段文字中的另一个单词(不区分大小写)
思路:首先是字符串的读入…可以整行读入然后用空格分隔单词。由于补区分大小写,所以要都转化成小写…但是输出的时候要输出原始,所以还记得保留一份。而且要能够通过新的找到原始的(我用了一个toori的map<string,string>来实现)
然后最关键的部分是如何判断两个单词经过重排是否能一样…

我的做法是构造一个hash函数…一个单词的hash值等于对应字母的顺序的平方和…效果还不错?

单词和hash值一一对应…最大也就9E5,可以存的下。然后统计每个hash值出现的次数。对于那些只出现一次的,就是我们要的答案。

还要注意的是输出要按照原始单词的字典序,而不是都变成小写以后的字典序。

所以找到之后可以先找到对应的原始单词存到set里,最后再输出。