山东省第八届acm大学程序设计竞赛山师选拔赛第一场
(声明:标题是自己取的,如果有语法错误的话与他人无关)
—————————————————————–分割线—————————————————————–
Problem_A(大数判定2幂数)
题意:给定一个数,判断它是否是2的n次方(0 < n < $2 ^ {1000}$)
按二进制考虑的话,如果n&(n-1)==0,则这个数就是2的n次方,等于1就不是。
AC代码(JAVA版):
1 | import java.math.BigInteger; |
Problem_B(离散化裸题)
有些数据本身很大,自身无法作为数组的下标保存对应的属性。如果这时只是需要这堆数据的相对属性时,那么就可以对其进行离散化。所谓离散化就是指当数据只与它们之间的相对大小有关,而与具体是多少无关时可以用到的一种方法(?
举个例子来说,假设有4个数:1234567、123456789、12345678、123456排序后是123456<1234567<12345678<123456789(只考虑他们相对大小可以想为1<2<3<4),那么这四个数可以表示成:2、4、3、1。
对数据进行离散化如果用上STL会很棒棒哦(思路:先排序,再去重,然后索引元素离散化后对应的值,详见代码)。
AC代码:
1 |
|
Problem_C(最长回文子串)
题意:给定一序列,输出其最长回文子序列的长度。
思路:没有思路,Manacher模板一套带走。
AC代码:
1 |
|
Problem_D(多重背包)
题意:有n个面值为A1,A2,..An,数量为C1,C2,..Cn的n个硬币,问他们之间互相组合能凑出多少种总面额小于m的面值
(可参照POJ的男人八题之Coins
AC代码:
1 |
|
Problem_E(思维 签到)
题意:给定n个数,从中抽取3个,将它们分成4组,问能否使每组的和相同。能的话输出抽取的三个数的位置,不能就输出I am done.
思路:设置i,j,k三个指针,一开始放在2,4,6这三个位置,然后不断判断分成的四组数据和是否相同,不同就找出其中最小的那一组,让他后面的指针往后移动。还有些小细节,比如k指针到头了,四组的值都相同了等等,自己处理一下就好了。
AC代码:
1 |
|
Problem_F(八进制减法)
题意:八进制减法
AC代码(C++–模拟)
1 | /************* |
AC代码(JAVA):
1 | import java.math.BigInteger; |
Problem_G(模拟)
题意:给你n个数,输出对他们进行第一次快速排序后的结果。不知道快速排序的话,自己去搜(其实不知道也没关系,题目里已经给出了排序的方式了,按照它的来就是了)。
AC代码:
1 |
|
Problem_H(大素数判定)
题意:给你n个数,输出他们中素数的个数。要用到Miller-rabin算法,套个模板就好了。
AC代码:
1 |
|