浙江大学acm答案完整版

求余运算 给出 S 和 M 求 0 S M 1 S M 2 S M M 1 S M 能否组成一个集合包含 0 1 M 1 这个是原题意改造而来 算法 判断两个数是否互质 or 暴力解决 其实暴力完全可以解决这个问题 b 只是其中用数学方法更加高效 巧妙 证明如果 S 和 M 互质则满足题意 另 G gcd S M 则 S A G M B G 另 X K S M K S T M T 为整数 满足 X 属于 0 到 M 1 X K A G T B G 因此取余后的整数一定是 G 的倍数 G 只能取 1 才能满足条件 充分性的证明 即当 S 与 M 互质 则 0 到 M 1 的 S 倍对 M 取余一定能遍历 0 到 M 1 只需证明的是 该余数中两两之间互不相等 假设 k S 和 b S 对 M 取余相等 k 和 b 0 M 并且 k 和 b 不等 则 k S q1 M r q2 M r b S k b S M q1 q2 S 与 M 互质 由上式子可得 M k b 与 k 和 b 0 M 并且 k 和 b 不等矛盾 因此得证 另外 偶然看到一个很牛叉的辗转相除法 int gcd int a int b while b b a b a b return a 此代码 很好很强大 把涉及位运算的交换的程序加入 便到得这段简洁高效的代码 注 A 和 B 经过 A B A B 结果就得到 A 和 B 的交换 1000 include int main int a b i scanf d for i 1 i a i int sum 0 sum sum i printf d n sum return 0 1001 include stdio h int main unsigned int64 n unsigned int64 temp while scanf I64u printf I64u n n temp return 0 HDU ACM 1014 Uniform Generator 三月 22nd 这个题目是判断给定的步长和 mod 判断所产生的随机数已经覆盖 0 mod 1 中所有的数 如果是 则说明所选的步长和 mod 是一个 Good choice 否则为 bad choice 需要懂得的基本内容为线性同余产生随机数 链接 http zh wikipedia org zh cn E7 B7 9A E6 80 A7 E5 90 8C E9 A4 98 E6 96 B9 E6 B3 95 Problem Description Computer simulations often require random numbers One way to generate pseudo random numbers is via a function of the form seed x 1 seed x STEP MOD where is the modulus operator Such a function will generate pseudo random numbers seed between 0 and MOD 1 One problem with functions of this form is that they will always generate the same pattern over and over In order to minimize this effect selecting the STEP and MOD values carefully can result in a uniform distribution of all values between and including 0 and MOD 1 For example if STEP 3 and MOD 5 the function will generate the series of pseudo random numbers 0 3 1 4 2 in a repeating cycle In this example all of the numbers between and including 0 and MOD 1 will be generated every MOD iterations of the function Note that by the nature of the function to generate the same seed x 1 every time seed x occurs means that if a function will generate all the numbers between 0 and MOD 1 it will generate pseudo random numbers uniformly with every MOD iterations If STEP 15 and MOD 20 the function generates the series 0 15 10 5 or any other repeating series if the initial seed is other than 0 This is a poor selection of STEP and MOD because no initial seed will generate all of the numbers from 0 and MOD 1 Your program will determine if choices of STEP and MOD will generate a uniform distribution of pseudo random numbers Input Each line of input will contain a pair of integers for STEP and MOD in that order 1 STEP MOD 100000 Output For each line of input your program should print the STEP value right justified in columns 1 through 10 the MOD value right justified in columns 11 through 20 and either Good Choice or Bad Choice left justified starting in column 25 The Good Choice message should be printed when the selection of STEP and MOD will generate all the numbers between and including 0 and MOD 1 when MOD numbers are generated Otherwise your program should print the message Bad Choice After each output test set your program should print exactly one blank line Sample Input 3 5 15 20 63923 99999 Sample Output 3 5 Good Choice 15 20 Bad Choice 63923 99999 Good Choice 线性同余方法 LCG 是个产生伪随机数的方法 它是根据递归公式 其中 A B M 是产生器设定的常数 LCG 的周期最大为 M 但大部分情况都会少于 M 要令 LCG 达到最大周期 应符合以下 条件 B M 互质 M 的所有质因子的积能整除 A 1 若 M 是 4 的倍数 A 1 也是 A B N0 都比 M 小 A B 是正整数 由以上可知 本题的求解方案 代码如下 include int main int a b max min tmp while scanf d d min a b a b while min tmp max min max min min tmp if max 1 printf 10d 10d Good Choice n n a b else printf 10d 10d Bad Choice n n a b return 0 Problem Description OK you are not too bad em But you can never pass the next test feng5166 says I will tell you an odd number N and then N integers There will be a special integer among them you have to tell me which integer is the special one after I tell you all the integers feng5166 says But what is the characteristic of the special integer Ignatius asks The integer will appear at least N 1 2 times If you can t find the right integer I will kill the Princess and you will be my dinner too Hahahaha feng5166 says Can you find the special integer for Ignatius Input The input contains several test cases Each test case contains two lines The first line consists of an odd integer N 1 N 999999 which indicate the number of the integers feng5166 will tell our hero The second line contains the N integers The input is terminated by the end of file Output For each test case you have to output only one line which contains the special number you have found Sample Input 5 1 3 2 3 3 11 1 1 1 1 1 5 5 5 5 5 5 7 1 1 1 1 1 1 1 Sample Output 3 5 1 include include include include using namespace std int main int n i x freopen a txt r stdin while scanf d mapm for i 0 i n i scanf d m x n n 1 2 map iterator it for it m begin it m end it if it second n v push back it first sort v begin v end if v size 1 printf d v 0 for i 1 i v size i printf d v i printf n return 0 1048 用 100 的 AC 热情 挑战 39 的高温 加油 The Hardest Problem Ever Time Limit 2000 1000 MS Java Others Memory Limit 65536 32768 K Java Others Total Submission s 5571 Accepted Submission s 2540 Problem Description Julius Caesar lived in a time of danger and intrigue The hardest situation Caesar ever faced was keeping himself alive In order for him to survive he decided to create one of the first ciphers This cipher was so incredibly sound that no one could figure it out without knowing how it worked You are a sub captain of Caesar s army It is your job to decipher the messages sent by Caesar and provide to your general The code is simple For each letter in a plaintext message you shift it five places to the right to create the secure message i e if the letter is A the cipher text would be F Since you are creating plain text out of Caesar s messages you will do the opposite Cipher text A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Plain text V W X Y Z A B C D E F G H I J K L M N O P Q R S T U Only letters are shifted in this cipher Any non alphabetical character should remain the same and all alphabetical characters will be upper case Input Input to this problem will consist of a non empty series of up to 100 data sets Each data set will be formatted according to the following description and there will be no blank lines separating data sets All characters will be uppercase A single data set has 3 components Start line A single line START Cipher message A single line containing from one to two hundred characters inclusive comprising a single message from Caesar End line A single line END Following the final data set will be a single line ENDOFINPUT Output For each data set there will be exactly one line of output This is the original message by Caesar Sample Input START NS BFW JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX END START N BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJ END START IFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ END ENDOFINPUT Sample Output IN WAR EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES I WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROME DANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE include include int main char a 15 char b 100 char c 15 int j for gets a if strcmp a START gets b gets c if strcmp c END for j 0 b j 0 j if b j F printf s n b else if strcmp a ENDOFINPUT break return 0 1018 Big Number Time Limit 20000 10000 MS Java Others Memory Limit 65536 32768 K Java Others Total Submission s 8372 Accepted Submission s 3701 Problem Description In many applications very large integers numbers are required Some of these applications are using keys for secure transmission of data encryption etc In this problem you are given a number you have to determine the number of digits in the factorial of the number Input Input consists of several lines of integer numbers The first line contains an integer n which is the number of cases to be tested followed by n lines one integer 1 n 107 on each line Output The output contains the number of digits in the factorial of the integers appearing in the input Sample Input 2 10 20 Sample Output 7 19 include include define pi 3 14159265 int num result void JC double t t num log num num 0 5 log 2 num pi log 10 经典的转换技巧 result int t 1 printf d n result int main int i n scanf d for i 0 i n i 求阶 乘共用多少位 经典常用 scanf d JC return 0 1013 Problem Description The digital root of a positive integer is found by summing the digits of the integer If the resulting value is a single digit then that digit is the digital root If the resulting value contains two or more digits those digits are summed and the process is repeated This is continued as long as necessary to obtain a single digit For example consider the positive integer 24 Adding the 2 and the 4 yields a value of 6 Since 6 is a single digit 6 is the digital root of 24 Now consider the positive integer 39 Adding the 3 and the 9 yields 12 Since 12 is not a single digit the process must be repeated Adding the 1 and the 2 yeilds 3 a single digit and also the digital root of 39 Input The input file will contain a list of positive integers one per line The end of the input will be indicated by an integer value of zero Output For each integer in the input output its digital root on a separate line of the output Sample Input 24 39 0 Sample Output 6 3 include include using namespace std int Digit int n int digit 0 while true digit 0 while n digit n 10 这步很经典 常用数字的判断及各位数的存取 如 123 可以得出 百位为 1 十位为 2 等等 n 10 if digit s sum 0 for i 0 i s for i 0 i s size i 还在这里 求和 求各个字符时 用这行也可以 sum s i 0 if sum 0 break digit Digit sum cout digit endl return 0 1032 Problem Description Problems in Computer Science are often classified as belonging to a certain class of problems e g NP Unsolvable Recursive In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs Consider the following algorithm 1 input n 2 print n 3 if n 1 then STOP 4 if n is odd then n 3n 1 5 else n n 2 6 GOTO 2 Given the input 22 the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 It is conjectured that the algorithm above will terminate when a 1 is printed for any integral input value Despite the simplicity of the algorithm it is unknown whether this conjecture is true It has been verified however for all integers n such that 0 n 1 000 000 and in fact for many more numbers than this Given an input n it is possible to determine the number of numbers printed including the 1 For a given n this is called the cycle length of n In the example above the cycle length of 22 is 16 For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j Input The input will consist of a series of pairs of integers i and j one pair of integers per line All integers will be less than 1 000 000 and greater than 0 You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j You can assume that no opperation overflows a 32 bit integer Output For each pair of input integers i and j you should output i j and the maximum cycle length for integers between and including i and j These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length on the same line Sample Input 1 10 100 200 201 210 900 1000 Sample Output 1 10 20 100 200 125 201 210 89 900 1000 174 include using namespace std int main int m n lenm lenn while cin m n int start m end n i max 0 if start end int temp start start end end temp if for i start i end i int count 1 temp i while temp 1 if temp 2 0 temp 3 temp 1 else temp 2 count while if max count max count cout count for cout m n max endl while return 0 1040 必看的 也是 必会的 As Easy As A B Time Limit 2000 1000 MS Java Others Memory Limit 65536 32768 K Java Others Total Submission s 12053 Accepted Submission s 4798 Problem Description These days I am thinking about a question how can I get a problem as easy as A B It is fairly difficulty to do such a thing Of course I got it after many waking nights Give you some integers your task is to sort these number ascending 升序 You should know how easy the problem is now Good luck Input Input contains multiple test cases The first line of the input is a single integer T which is the number of test cases T test cases follow Each test case contains an integer N 1 N 1000 the number of integers to be sorted and then N integers follow in the same line It is guarantied that all integers are in the range of 32 int Output For each case print the sorting result and one line one case Sample Input 2 3 2 1 3 9 1 4 7 2 5 8 3 6 9 Sample Output 1 2 3 1 2 3 4 5 6 7 8 9 include void main int n i m j k t l a 10000 scanf d for i 0 i n i scanf d for j 0 j m j scanf d for k 0 k m k for t 0 ta t 1 l a t a t a t 1 a t 1 l for j 0 j m j printf d a j if j m 1 就这两步要小心谨慎 陷阱 有时不用多加 换行服 printf printf n 1042 N Time Limit 10000 5000 MS Java Others Memory Limit 65536 32768 K Java Others Total Submission s 17235 Accepted Submission s 4385 Problem Description Given an integer N 0 N 10000 your task is to calculate N Input One N in one line process to the end of file Output For each N output N in one line Sample Input 1 2 3 Sample Output 1 2 6 include include int main int n k t p sum j i int s 40000 while scanf d t 0 p 0 sum 0 s 0 1 for j 1 j n j for i 0 i9 s i sum 10 p sum 10 if t i t s t 0 看不明白 else s i sum for i t i 0 i printf d s i printf n return 0 Gridland Time Limit 2000 1000 MS Java Others Memory Limit 65536 32768 K Java Others Total Submission s 981 Accepted Submission s 474 Problem Description For years computer scientists have been trying to find efficient solutions to different computing problems For some of them efficient algorithms are already available these are the easy problems like sorting evaluating a polynomial or finding the shortest path in a graph For the hard ones only exponential time algorithms are known The traveling salesman problem belongs to this latter group Given a set of N towns and roads between these towns the problem is to compute the shortest path allowing a salesman to visit each of the towns once and only once and return to the starting point The president of Gridland has hired you to design a program that calculates the length of the shortest traveling salesman tour for the towns in the country In Gridland there is one town at each of the points of a rectangular grid Roads run from every town in the directions North Northwest West Southwest South Southeast East and Northeast provided that there is a neighbouring town in that direction The distance between neighbouring towns in directions North South or East West is 1 unit The length of the roads is measured by the Euclidean distance For example Figure 7 shows 2 3 Gridland i e a rectangular grid of dimensions 2 by 3 In 2 3 Gridland the shortest tour has length 6 Input The first line contains the number of scenarios For each scenario the grid dimensions m and n will be given as two integer numbers in a single line separated by a single blank satisfying 1 m 50 and 1 n 50 Output The output for each scenario begins with a line containing Scenario i where i is the number of the scenario starting at 1 In the next line print the length of the shortest traveling salesman tour rounded to two decimal digits The output for every scenario ends with a blank line Sample Input 2 2 2 2 3 Sample Output Scenario 1 4 00 Scenario 2 6 00 include include using namespace std int main int i j cas mid k double res root sqrt 2 0 cin cas for k 1 k i j mid i j if mid 2 0 res double mid else res double mid 1 root printf Scenario d n 2lf n n k res return 0 1 095 A B for Input Output Practice VII Time Limit 2000 1000 MS Java Others Memory Limit 65536 32768 K Java Others Total Submission s 11057 Accepted Submission s 7506 Problem DescriptionYour task is to Calculate a b InputThe input will consist of a series of pairs of integers a and b separated by a space one pair of integers per line OutputFor each pair of input integers a and b you should output the sum of a and b and followed by a blank line Sample Input1 5 10 20 Sample Output 6 30 includeusing namespace std int main int a b while cin a b cout a b endl endl 经典在这里 return 0 1096 A B for Input Output Practice VIII Time Limit 2000 1000 MS Java Others Memory Limit 65536 32768 K Java Others Total Submission s 30197 Accepted Submission s 8895 Problem Description Your task is to calculate the sum of some integers Input Input contains an integer N in the first line and then N lines follow Each line starts with a integer M and then M integers follow in the same line Output For each group of input integers you should output their sum in one line and you must note that there is a blank line between outputs Sample Input 3 4 1 2 3 4 5 1 2 3 4 5 3 1 2 3 Sample Output 10 15 6 include n while n sum 0 cin m for i 0 i a i for i 0 i m i sum a i if n 0 cout sum endl else cout sum endl endl return 0 第二个 1097 Problem Description lcy gives a hard puzzle to feng5166 lwg JGShining and Ignatius gave a and b how to know the a b everybody objects to this BT problem so lcy makes the problem easier than begin this puzzle describes that gave a and b how to know the a b s the last digit number But everybody is too lazy to slove this problem so they remit to you who is wise Input There are mutiple test cases Each test cases consists of two numbers a and b 0 a b 2 30 Output For each test case you should output the a b s last digit number Sample Input 7 66 8 800 Sample Output 9 6 b 的值最大有 2 30 一次遍历下来当然会 T 咯 看看我的代码把 include include using namespace std int main int a b int s 10 10 1 0 1 1 4 2 4 8 6 4 3 9 7 1 2 4 6 经典这步 1 5 1 6 4 7 9 3 1 4 8 4 2 6 2 9 1 while