111qqz的小窝

老年咸鱼冲锋!

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里,最后再输出。

 

 

 

uva 120 Stacks of Flapjacks

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

题意:给出一个长度为n的序列(无重复元素),询问经过多少次flip(i)操作,使得序列升序排列。定义flip(i)为将1到n-i+1的元素反转…
思路:先离散化,然后注意读入….

uva 409 – Excuses, Excuses!

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=350
题意:给出k个key word,e个借口…找出包含key word最多的借口,即为最坏的借口。匹配补区分大小写&&同一个key word算多次。
思路:需要注意的是因为不区分大小写,需要都转化成大写或者小写。。但是输出的时候要输出原始的。。所以要另外存一份。

hdu 5610 ||BC #69 div2 1001 Baby Ming and Weight lifting

http://acm.hdu.edu.cn/showproblem.php?pid=5610
题意:有重量为a,b两种铁圈每种无限多个…能能否组成一个重量为c且平衡杠铃(中间的杆的重量忽略不计)
a,b,c都是整数。
思路:平衡的话。。就是两边重量一样。。那么c为奇数的时候显然不行。
由于有多组答案的时候输出铁圈数之和小的。。。那么我们枚举的话。应该把里面那层枚举的变量放置成重量较大的。。。。

hdu 5611 || BC #69 div2 1002 Baby Ming and phone number

http://acm.hdu.edu.cn/showproblem.php?pid=5611
题意:给出n个电话号码(长度为11的字符串),满足特殊条件的价格为a,否则为b.特殊条件为最后5位数字一样,最后5位严格递增或者严格递减,最后8位是一个1980年1月一日到2016年12月31日的合法日期。问最后的价值。

 

思路:直接搞….结果死在cin了。。。原来3E6的cin就会TLE。。。。。q神说1E5有的也会tle…..

所以方案是,能不用cin就不要用cin…

如果要读string的话。。。一个解决办法是把数据流同步关掉(是叫这个名字吗。。)

std::ios::sync_with_stdio(false); 会快很多。。。

还有一个办法是先用scanf读 char[] 然后再转化? 没试过==
哦哦还要注意要判闰年。
还有要开long long

 

 

 

 

 

 

uva 537 Artificial Intelligence?

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=478
题意:给出一段文字。。其中包含了 P,U,I(功率,电压,电流)中的两个。。求第三个。
思路:字符串处理。。第一次用vim复制整段代码。。命令模式下按v,然后光标扫过的区域都会选中,按y就就复制到剪贴板了。。
所以虽然代码写了300行但只有100行是需要写的。。200行复制改下就好==
WA了两次。。一次是因为I写成了小写。。另一次是因为多组数据记得初始化多次。

uva 10010 – Where’s Waldorf?

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=951
题意:给出一个由大小写字母组成的二维maze…给出k个询问。每个询问一个单词。问能否在maze中找到这个单词。不区分大小写。输出开头字母的坐标(从1开始)。如果有多组输出最上面的。如果还有多组,输出最左边的。数据保证至少有一组。
思路:直接找就好了。。。坑的地方是。。。格式。。数据组数之后会有一个空行。然后每两组读入数据之间会有一个空行。。输出的时候每两组数据之间也有一个空行。

我因为一直多输出了一个空行一直wa QAQ

=

uva 152 Tree’s a Crowd

题意:题意:给你一组三维空间中的点,每个点到其它点都有个距离,其中有个最小距离,如果这个最小距离小于10,就将对应的距离的点个数加1,最后输出距离为0,1,2…8,9的点的个数。(from 百度)
老实说,上面这题意也讲的不明不白,其实这题非常水,就是对每个点进行判断,找出和其他点最短的距离,在下标为该距离的数组上+1,最后输出数组下标0-9的数。
trick:其实最小距离大于9的就不用存放了,只要开个大小10的数组。(不会概括。。。抄的别人的)

好坑啊。。。最后要多一个换行。。不然会WA…题目中又木有说。。。WA到死了好么。。。。