這次隻要做出第一題和後兩題的小資料集就可以去谷歌面試啦。後兩題大資料集有點超過我的能力範圍了，跳過跳過。
Problem: No Nine (7pts, 13pts)
No Nine is a counting game that you can try when you are bored. In this game, you are only allowed to say numbers that are legal. A number is legal if and only if all of the following are true:
- it is a natural number (i.e. in the set {1, 2, 3...})
- it does not contain the digit 9 anywhere in its base 10 representation
- it is not divisible by 9
For example, the numbers 16 and 17 are legal. The numbers 18, 19, 17.2, and -17 are not legal.
On the first turn of the game, you choose and say a legal number F. On each subsequent turn, you say the next legal number. For example, if you played a game with F = 16, you would say 16, 17, 20, 21, and so on.
Alice is very good at this game and never makes mistakes. She remembers that she played a game in which the first number was F and the last number was L (when she got tired of the game and stopped), and she wonders how many turns were in the game in total (that is, how many numbers she said).
Input
The input starts with one line containing one integer T; T test cases follow. Each test case consists of a single line containing two integers F and L: the first and last numbers from the game, as described above.
Output
For each test case, output one line containing
Case #x: y
, where
x
is the test case number (starting from 1), and
y
is the number of the turns played in the game.
Limits
1 ≤ T ≤ 100.
Time limit: 60 seconds per test set.
Memory limit: 1 GB.
F does not contain a
9
digit.
F is not divisible by 9.
L does not contain a
9
digit.
L is not divisible by 9.
Small dataset (Test set 1 - Visible)
1 ≤ F < L ≤ 106.
Large dataset (Test set 2 - Hidden)
1 ≤ F < L ≤ 1018.
Sample
| Input | Output |
| |
In Sample Case #1, the game lasted for 9 turns, and the numbers Alice said were: 16, 17, 20, 21, 22, 23, 24, 25, 26.
In Sample Case #2, the game lasted for 4 turns, and the numbers Alice said were: 88, 100, 101, 102.
- 思路：
- 重點是題目說明了給的數字 L 和 R 都是合法的。是以就可以找到 [0, L] 和 [0, R] 這兩個區間共有幾個符合預期的數字，然後相減再加一就可以得到 [L, R] 這個區間合法數字的個數。
- 對于數組 L ，周遊每一位 L[i]（i < len(L) - 1）, 第 i 位是 L[i], 從 0 至 i-1 位是可以随便選擇的。也就是 L[i] * 9^(i-2) * 8。這個地方最後乘以8是為了不讓這個數被 9 整除。也就是說，最後一位數字，在0-8這9個數字裡一定會有一位數字，組成的數字是可以被9整除的（這是為什麼？嘗試了幾個數字還真的是這樣）。
- 後來想了想是這樣的，前面的數字為 n，最後一位數字位 m。則（n+m）% 9 = 0。設 r = n % 9。則隻要 m = 9 - n。（n+m）就一定可以被9整除。
- 對于L的最後一位數字 x，下一定是可以加上的。還有如果最後一位是0，也需要加一。
- 注意：
- 資料是longlong int，有一個循環沒注意，寫成了int。是以溢出了。
- 還有一個坑，就是我使用了pow函數，這個函數傳回double類型，也溢出了。
- 可見谷歌的題目，就是corner cases比較多，還看不到測試集。是以看清資料規模。。
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli cnt(lli n) {
lli store = n;
lli ret = 0;
vector<lli> digits;
while(n) {
digits.push_back(n % 10);
n = n / 10;
}
reverse(digits.begin(), digits.end());
int len = digits.size();
for(int i = 0; i < len; i++) {
if(i < len - 1) {
lli tmp = digits[i] * 8;
for(int j = 0; j < len - i - 2; j++) {
tmp *= 9;
}
ret += tmp;
}
else {
for(lli i = store - store % 10; i < store + 1; i++) {
if(i % 9 > 0)
ret++;
}
}
}
return ret;
}
lli solve(lli l, lli r) {
return cnt(r) - cnt(l) + 1;
}
int main()
{
int t;
cin >> t;
for(int i = 1; i <= t; i++) {
lli l, r;
cin >> l >> r;
cout << "Case #" << i << ": " << solve(l, r) << endl;
}
return 0;
}
Problem: Sherlock and the Bit Strings (11pts, 26pts)
Sherlock and Watson are playing a game involving bit strings, i.e., strings consisting only of the digits
and
1
. Watson has challenged Sherlock to generate a bit string S of N characters S1, S2, ..., SN. The string must obey each of K different constraints; each of these constraints is specified via three integers Ai, Bi, and Ci. The number of
1
s in the substring SAi, SAi + 1, ..., SBi must be equal to Ci.
Watson chooses the constraints in a way that guarantees that there is at least one string of the right length that obeys all of the constraints. However, since there could be multiple such strings, Watson wants Sherlock to choose the string from this set that is Pth in lexicographic order, with P counted starting from 1.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with one line containing three integers N, K, and P, as described above. Then, there are K more lines; the i-th of these contains three integers Ai, Bi and Ci, representing the parameters of the i-th constraint, as described above.
Output
For each test case, output one line containing
Case #x: y
, where
x
is the test case number (starting from 1) and
y
is the Pth lexicographically smallest bit string among all possible strings following the K specified constraints.
Limits
1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
1 ≤ N ≤ 100.
1 ≤ K ≤ 100.
1 ≤ P ≤ min(1018, the number of bit strings that obey all of the constraints).
1 ≤ Ai ≤ Bi ≤ N for all 1 ≤ i ≤ K.
0 ≤ Ci ≤ N, for all 1 ≤ i ≤ K.
(Ai, Bi) ≠ (Aj, Bj), for all 1 ≤ i < j ≤ K.
Small dataset (Test set 1 - Visible)
Ai = Bi for all 1 ≤ i ≤ K.
Large dataset (Test set 2 - hidden)
Bi - Ai ≤ 15 for all 1 ≤ i ≤ K.
Sample
| Input | Output |
| |
Note that the last sample case would not appear in Small dataset.
In Sample Case #1, the bit strings that obey the only constraint in lexicographically increasing order are [010, 011, 110, 111].
In Sample Case #2, the bit strings that obey the given constraints in lexicographically increasing order are [0101, 1010].
- 思路：
- 小資料集合Ai和B都是給定的。是以Ci也就是0或1兩個值。K個條件可以唯一确定一個數字~.
- 題目要第p分位數。取這個數就好。
- 注意：
- 我發現刷題也需要debug。下一個visual studio再戰。。
- 要維護兩個bit數組，然後剛開始就把坐标搞混了。這個要仔細一點。
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
int main() {
int t;
cin >> t;
for (int i = 1; i <= t; i++) {
int n, k, p;
cin >> n >> k >> p;
vector<int> bits(n, 0);
for (int j = 0; j < k; j++) {
int a, b, c;
cin >> a >> b >> c;
bits[a - 1] = c > 0 ? 1 : 0;
}
cout << "Case #" << i << ": ";
vector<int> pBits;
p--;
while (p > 0) {
pBits.push_back(p % 2);
p /= 2;
}
for (int n = 0, m = bits.size(); n < pBits.size() && m > 0;) {
if (bits[m] == 0) {
bits[m--] = pBits[n++];
}
else {
m--;
}
}
for (int& bit : bits)
cout << bit;
cout << endl;
}
return 0;
}
Problem: King's Circle (16pts, 27pts)
For the first time in as long as anyone can remember, the kingdom of Kickstartia is alive with celebration: it is the coronation day for the new King. As is customary for the coronation, a Royal Parade will march its way through the streets of the capital.
The capital can be thought of as an infinite 2D plane, with infinitely many, infinitely long, streets spaced one meter apart, running horizontally and vertically throughout. The horizontal streets are labelled from negative infinity to infinity from top to bottom, while the vertical streets are labelled from negative infinity to infinity from left to right.
There are N cafes in the capital, and the i-th one is located at the intersection of vertical street Vi and horizontal street Hi. No two cafes lie on the same intersection. In order to keep the parade technicians happy and well-fed, you will pick exactly three of these cafes for them to stop at along the way.
To introduce some order to the chaos, you have additionally decided that a parade should end where it starts, and that its path through the streets must make the shape of a square (with straight sides, all of equal length). Each cafe can be anywhere along the square (on the sides or at a corner).
This immediately presents a problem: depending on which three cafes you pick, it may not be possible to make a square parade that goes through those three cafes. So, your task is to find out: how many different sets of three cafes are there such that there exists at least one square parade that includes all three cafes in the set? (Two sets are different if and only if there is a cafe in one that is not present in the other.)
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of one line containing ten integers N, V1, H1, A, B, C, D, E, F and M.
N is the number of cafes. The first cafe lies at the intersection of vertical street V1 and horizontal street H1.
The locations of the remaining cafes Vi, Hi, can be generated for i = 2 to N as follows:
- Vi = (A × Vi-1 + B × Hi-1 + C) modulo M
- Hi = (D × Vi-1 + E × Hi-1 + F) modulo M
Output
For each test case, output one line containing
Case #x: y
, where
x
is the test case number (starting from 1) and
y
is the number of sets of cafes satisfying the conditions explained above.
Limits
1 ≤ T ≤ 100.
Time limit: 100 seconds per test set.
Memory limit: 1 GB.
0 ≤ A < M.
0 ≤ B < M.
0 ≤ C < M.
0 ≤ D < M.
0 ≤ E < M.
0 ≤ F < M.
0 ≤ V1 < M.
0 ≤ H1 < M.
For all i ≠ j, (Vi, Hi) ≠ (Vj, Hj).
Small dataset (Test set 1 - Visible)
3 ≤ N ≤ 1000.
2 ≤ M ≤ 1000.
Large dataset (Test set 2 - Hidden)
3 ≤ N ≤ 5 × 105.
2 ≤ M ≤ 106.
Sample
| Input | Output |
| |
In Sample Case #1, there are four cafes and they are at (1, 1), (1, 0), (0, 3) and (4, 0). It would be possible for a square parade to go through the set of cafes (1, 1), (1, 0), (0, 3), or the set (1, 1), (1, 0), (4, 0) or the set (1, 0), (0, 3) (4, 0) as shown in the diagram below. There is no possible square parade that goes through the set of cafes (1, 1), (0, 3), (4, 0).
In Sample Case #2, there are 6 cafes and they are at (3, 1), (4, 1), (5, 1), (6, 1), (7, 1) and (8, 1). Since they are all on the same vertical street, every triplet of cafes has a square parade going through it. So the answer is 6 choose 3 = 20.
In Sample Case #3, there are 3 cafes and they are at (7, 24), (19, 17), (0, 34). There is no square parade that goes through these cafes, so the answer is 0.
Note: We do not recommend using interpreted/slower languages for the Large dataset of this problem.
- 思路：沒有太好的思路。就算是小規模資料集也想不出很好的解決方法。這次确實有點難。。
![P1147 連續自然數和（數論，洛谷，java）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)