请教会编程的大侠，给点提示也行。一共三题。谢谢
Problem1
Overview: Among all substrings longer than a given length, and among all the anagrams of these
substrings, find the most common one.
Description: Yay! Thanks to the most recent scuffle with evil, Hulk has been able to do what he likes:
smash. Unfortunately, in his great enthusiasm, he’s smashed a warehouse (represented
by a string) containing important items that S.H.I.E.L.D owns. Okay, maybe he was forcibly
ejected off a plane and didn’t actually choose to smash into the warehouse, but details,
details.
Anyhow, the items are probably beyond repair, but S.H.I.E.L.D. would like to figure out
an approximation of what the most well-stocked item in the warehouse was. Items are
represented as substrings of length n or more, and each substring has been smashed into
an anagram. A substring is a contiguous sequence of characters inside of a given string.
For example, the string “abc” has substrings “a”, “b”, “c”, “ab”, “bc”, and “abc”. An anagram
of a string is some rearrangement of the letters. For example, the anagrams of “abc” are
“abc”, “acb”, “bac”, “bca”, “cab”, and “cba”.
Given a warehouse (a string) and a length n, consider all substrings of the string with length
greater than or equal to n. These are all the currently smashed items in the warehouse.
And for all these substrings, consider all of their anagrams - these are all the un-smashed
items that a smashed item could once have been. Output the substring anagram (i.e. item)
that occurs the most frequently; if there are multiple, output the lexicographically smallest
one (i.e. the one that would come first when sorted alphabetically).
Filename: nov91.{java, cpp, c, cc, py}
Input: The input file will consist of exactly two lines. The first line will contain the given string. The
second line will give the length n - the minimum length of substrings to consider.
Output: The most common anagram among all substrings with length greater than or equal to n,
choosing the lexicographically smallest among ties.
Assumptions: The given string will be no longer than 1000 characters.
n will be less than or equal to the length of the string.
Sample bbbabbbaaabaaabbb
Input #1: 4
Sample aaab
Output #1:
Sample abcdefghijklmnopqrstuvwxyz
Input #2: 25
Sample abcdefghijklmnopqrstuvwxy
Output #2:
Problem2
Overview: Determine whether there exists a contiguous sum in an array that is equal to K.
Description: Hey look, someone just made a reference around Captain America, aka Steve Rogers!
Steve would like to figure out if he understands that reference. Steve has an array of N
integers in his head, representing facts that he knows. The reference has value K, so if
there is a contiguous subarray of facts whose sum is equal to K, then Steve has enough
knowledge to have understood that reference.
To illustrate what is contiguous sum, here is an example: a sample array is {1, 4, -8}.
Then all possible contiguous sums are (note that an empty array is also a subarray):
0: {}
1: {1}
4: {4}
-8: {-8}
5: {1, 4}
-4: {4, -8}
-3: {1, 4, -8}
Since computer science didn’t become popularized until well after Steve was frozen in time,
he doesn’t know how to determine whether he understands that reference. Fortunately, as
an adept programmer, you might be able to do so! Can you figure it out?
Filename: nov92.{java, cpp, c, cc, py}
Input: The first line is K and the second line is N. The rest of the lines are the integers in the array;
one number per line.
Output: YES if such contigous subarray exisits, or NO if it does not exist. (Note, both YES and NO are
capitalized.)
Assumptions: Integers can be positive, negative or zero. The array is NOT sorted.
1 < N < 200,000
-1,000,000 < K < 1,000,000
All calculations you are expected to perform fits within a 32-bit integer.
Sample 0
Input #1: 3
1
4
-8
Sample YES
Output #1:
Sample 6
Input #2: 3
1
4
-8
Sample NO
Output #2:
PROBLEM3
Overview: Which number is missing?
Description: Whoops! Agent Maria Hill is trying to break into Loki’s computer system, which is not-very-
intelligently protected by a number between 0 and n-1. Furthermore, one of Loki’s minions
foolishly left a file containing the other n-1 numbers available on a different machine.
Unfortunately, Maria is unable to directly access the other n-1 numbers directly, because if
she does so, Loki might discover her plots and change his password.
Instead, imagine that the n-1 numbers between 0 and n-1 are arranged randomly in an
array; Maria is are allowed to ask what the jth bit of the ith number in the array is. Using
no more than 2500 of these queries, can she figure out which number is missing (and
therefore Loki’s password)?
Filename: nov94.{java, cpp, c, cc, py}
Input/Output: This is an interactive problem. This means that your program will receive input based on
the output your program produces. When your program starts, you will be provided an
integer n as specified above. Your program must then do one of the following:
1. Output two space separated integers i and j, which denote a query for the jth bit (0 ≤
j < 32) of the ith number (0 ≤ i < n-1), after which your program will be provided the
jth bit of the ith number (either 0 or 1). This counts as 1 query.
2. Output a single integer k, indicating that the missing number is k
You MUST output a new line character and flush the output stream after each output:
In C, use printf("n"); fflush(stdout);
In C++, use cout << endl << flush;
In Java, use System.out.println(); System.out.flush();
In Python, use sys.stdout.write("n"); sys.stdout.flush();
Assumptions: n is a power of 2
2 <= n <= 1024
bit indices are numbered from the right, i.e. the ith bit corresponds to 2^i
Sample Hidden numbers: 3 1 2
Sequence #1:
COMPUTER
YOU
COMPUTER
YOU
COMPUTER
YOU
COMPUTER
YOU
COMPUTER
YOU
COMPUTER
YOU
COMPUTER
YOU
4
0
1
0
1
1
1
1
0
2
0
2
1
0
0
1
0
1
0
1Stanford ProCo 2013
Nov 9.4
Sample
Sequence #2:
A Bit of a Problem
Hidden numbers: 2 0 1
COMPUTER
YOU
COMPUTER
YOU
COMPUTER
YOU
COMPUTER
YOU
COMPUTER
YOU
COMPUTER
YOU
COMPUTER
YOU
4
0
0
0
1
1
0
1
0
2
1
2
0
3