《2023年福建省第三届大学生程序设计竞赛题目.doc》由会员分享，可在线阅读，更多相关《2023年福建省第三届大学生程序设计竞赛题目.doc（23页珍藏版）》请在金锄头文库上搜索。
1、Problem A Solve equationAccept: 111Submit: 229Time Limit: 1000 mSecMemory Limit : 32768 KBProblem DescriptionYou are given two positive integers A and B in Base C. For the equation:A=k*B+dWe know there always existing many non-negative pairs (k, d) that satisfy the equation above. Now in this proble
2、m, we want to maximize k.For example, A=123 and B=100, C=10. So both A and B are in Base 10. Then we have:(1) A=0*B+123(2) A=1*B+23As we want to maximize k, we finally get one solution: (1, 23)The range of C is between 2 and 16, and we use a, b, c, d, e, f to represent 10, 11, 12, 13, 14, 15, respec
3、tively.InputThe first line of the input contains an integer T (T10), indicating the number of test cases.Then T cases, for any case, only 3 positive integers A, B and C (2C16) in a single line. You can assume that in Base 10, both A and B is less than 231.OutputFor each test case, output the solutio
4、n “(k,d)” to the equation in Base 10.Sample Input32bc 33f 16123 100 101 1 2 Sample Output(0,700)(1,23)(1,0)Problem B Bin & Jing in wonderlandAccept: 4Submit: 28Time Limit: 1000 mSecMemory Limit : 32768 KBProblem DescriptionBin has a dream that he and Jing are both in a wonderland full of beautiful g
5、ifts. Bin wants to choose some gifts for Jing to get in her good graces.There are N different gifts in the wonderland, with ID from 1 to N, and all kinds of these gifts have infinite duplicates. Each time, Bin shouts loudly, “I love Jing”, and then the wonderland random drop a gift in front of Bin.
6、The dropping probability for gift i (1iN) is P(i). Of cause, P(1)+P(2)+P(N)=1. Bin finds that the gifts with the higher ID are better. Bin shouts k times and selects r best gifts finally.That is, firstly Bin gets k gifts, then sorts all these gifts according to their ID, and picks up the largest r g
7、ifts at last. Now, if given the final list of the r largest gifts, can you help Bin find out the probability of the list?InputThe first line of the input contains an integer T (T2,000), indicating number of test cases. For each test cast, the first line contains 3 integers N, k and r (1N20, 1k52, 1r
8、min(k,25) as the description above. In the second line, there are N positive float numbers indicates the probability of each gift. There are at most 3 digits after the decimal point. The third line has r integers ranging from 1 to N indicates the finally list of the r best gifts ID. OutputFor each c
9、ase, output a float number with 6 digits after the decimal points, which indicates the probability of the final list.Sample Input42 3 30.3 0.71 1 12 3 30.3 0.71 1 22 3 30.3 0.71 2 22 3 30.3 0.72 2 2 Sample Output0.0270000.1890000.4410000.343000Problem C Floor problemAccept: 133Submit: 150Time Limit:
10、 1000 mSecMemory Limit : 32768 KBProblem DescriptionIn this problem, we have f(n,x)=Floorn/x. Here Floorx is the biggest integer such that no larger than x. For example, Floor1.1=Floor1.9=1, Floor2.0=2.You are given 3 positive integers n, L and R. Print the result of f(n,L)+f(n,L+1)+.+f(n,R), please
11、.InputThe first line of the input contains an integer T (T100), indicating the number of test cases.Then T cases, for any case, only 3 integers n, L and R (1n, L, R10,000, LR).OutputFor each test case, print the result of f(n,L)+f(n,L+1)+.+f(n,R) in a single line.Sample Input31 2 3100 2 100100 3 100
12、 Sample Output0382332Problem D Digits CountAccept: 11Submit: 64Time Limit: 10000 mSecMemory Limit : 262144 KBProblem DescriptionGiven N integers A=A0,A1,.,AN-1. Here we have some operations:Operation 1: AND opn L RHere opn, L and R are integers.For LiR, we do Ai=Ai AND opn (here AND is bitwise opera
13、tion).Operation 2: OR opn L RHere opn, L and R are integers.For LiR, we do Ai=Ai OR opn (here OR is bitwise operation).Operation 3: XOR opn L RHere opn, L and R are integers.For LiR, we do Ai=Ai XOR opn (here XOR is bitwise operation).Operation 4: SUM L RWe want to know the result of AL+AL+1+.+AR.No
14、w can you solve this easy problem?InputThe first line of the input contains an integer T, indicating the number of test cases. (T100)Then T cases, for any case, the first line has two integers n and m (1n1,000,000, 1m100,000), indicating the number of elements in A and the number of operations.Then
15、one line follows n integers A0, A1, ., An-1 (0Ai16,0in).Then m lines, each line must be one of the 4 operations above. (0opn15)OutputFor each test case and for each SUM operation, please output the result with a single line.Sample Input14 41 2 4 7SUM 0 2XOR 5 0 0OR 6 0 3SUM 0 2 Sample Output718 HintA = 1 2 4 7SUM 0 2, result=1+2+4=7;XOR 5 0 0, A=4 2 4 7;OR 6 0 3, A=6 6 6 7;SUM 0 2, res
