題目1 : Binary Watch
時間限制:10000ms
單點時限:1000ms
記憶體限制:256MB
描述
Consider a binary watch with 5 binary digits to display hours (00 - 23) and 6 binary digits to display minutes (00 - 59).
For example 11:26 is displayed as 01011:011010.
Given a number x, output all times in human-readable format “hh:mm” when exactly x digits are 1.
輸入
An integer x. (0 ≤ x ≤ 9)
輸出
All times in increasing order.
樣例輸入
1
樣例輸出
00:01
00:02
00:04
00:08
00:16
00:32
01:00
02:00
04:00
08:00
16:00
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
int main() {
// freopen("input", "r", stdin);
int x; cin >> x;
for (int i = ; i < ( << ); i++) {
if (__builtin_popcount(i) == x) {
int hour = i >> ;
int minute = i & ;
if (hour < && minute < ) {
cout << setw() << setfill('0') << hour << ":" << setw() << setfill('0') << minute << endl;
}
}
}
return ;
}
— Built-in Function: int __builtin_ffs (unsigned int x)
Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.
傳回右起第一個‘1’的位置。
— Built-in Function: int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
傳回左起第一個‘1’之前0的個數。
— Built-in Function: int __builtin_ctz (unsigned int x)
Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.
傳回右起第一個‘1’之後的0的個數。
— Built-in Function: int __builtin_popcount (unsigned int x)
Returns the number of 1-bits in x.
傳回‘1’的個數。
— Built-in Function: int __builtin_parity (unsigned int x)
Returns the parity of x, i.e. the number of 1-bits in x modulo 2.
傳回‘1’的個數的奇偶性。
題目2 : Popular Products
時間限制:10000ms
單點時限:1000ms
記憶體限制:256MB
描述
Given N lists of customer purchase, your task is to find the products that appear in all of the lists.
A purchase list consists of several lines. Each line contains 3 parts: the product id (format XXXX-XXXX), the purchase date (format mm/dd/yyyy) and the price (with decimal places). Two product are considered equal if both the product id and the price are equal.
輸入
The first line contains an integer N denoting the number of lists. (1 ≤ N ≤ 1000)
Then follow N blocks. Each block describes one list.
The first line of each block contains an integer M denoting the number of products in the list. (1 ≤ M ≤ 50)
M lines follow. Each line contains the product id, the purchase date and the price.
輸出
The products that appear in all of the lists. You should output the product id in increasing order.
If two different product share the same id (with different price) you should output the id twice.
樣例輸入
3
2
1111-1111 07/23/2016 998.00
1111-2222 07/23/2016 888.00
2
1111-2222 07/23/2016 888.00
1111-1111 07/23/2016 998.00
2
1111-2222 07/23/2016 888.00
1111-1111 07/23/2016 999.00
樣例輸出
1111-2222
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
struct Product {
string id, price;
Product(string id_, string price_): id(id_), price(price_) {}
bool operator<(const Product& p) const {
return (id + price) < (p.id + p.price);
}
bool operator==(const Product& p) const {
return id == p.id && price == p.price;
}
};
map<Product, int> cnt;
int main() {
// freopen("input", "r", stdin);
int N; cin >> N;
for (int i = ; i < N; i++) {
int M; cin >> M;
set<Product> s;
for (int j = ; j < M; j++) {
string id, date, price;
cin >> id >> date >> price;
s.insert(Product(id, price));
}
for (const auto& p : s) {
cnt[p]++;
}
}
vector<string> ret;
for (const auto& pair: cnt) {
if (pair.second >= N) {
ret.push_back(pair.first.id);
}
}
sort(ret.begin(), ret.end());
for (int i = ; i < ret.size(); i++) {
cout << ret[i] << endl;
}
return ;
}
題目3 : Counting Islands II
時間限制:10000ms
單點時限:1000ms
記憶體限制:256MB
描述
Country H is going to carry out a huge artificial islands project. The project region is divided into a 1000x1000 grid. The whole project will last for N weeks. Each week one unit area of sea will be filled with land.
As a result, new islands (an island consists of all connected land in 4 – up, down, left and right – directions) emerges in this region. Suppose the coordinates of the filled units are (0, 0), (1, 1), (1, 0). Then after the first week there is one island:
#…
….
….
….
After the second week there are two islands:
#…
.#..
….
….
After the three week the two previous islands are connected by the newly filled land and thus merge into one bigger island:
#…
##..
….
….
Your task is track the number of islands after each week’s land filling.
輸入
The first line contains an integer N denoting the number of weeks. (1 ≤ N ≤ 100000)
Each of the following N lines contains two integer x and y denoting the coordinates of the filled area. (0 ≤ x, y < 1000)
輸出
For each week output the number of islands after that week’s land filling.
樣例輸入
3
0 0
1 1
1 0
樣例輸出
1
2
1
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const int MAX = ;
int fa[MAX * MAX];
int grid[MAX][MAX];
int dx[] = {, , , -};
int dy[] = {, -, , };
void clear() {
memset(fa, -, sizeof fa);
memset(grid, , sizeof grid);
}
int findset(int x) {
if (fa[x] == -) {
return fa[x] = x;
}
return x == fa[x] ? x : fa[x] = findset(fa[x]);
}
void unionset(int x, int y) {
int fx = findset(x), fy = findset(y);
if (fx != fy) {
fa[fx] = fy;
}
}
int main() {
// freopen("input", "r", stdin);
clear();
int cnt = ;
int N; cin >> N;
for (int i = ; i < N; i++) {
int x, y; cin >> x >> y;
grid[x][y] = ;
cnt++;
for (int j = ; j < ; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
if (nx >= && ny >= && nx < && ny < ) {
if (grid[nx][ny] && findset(nx * + ny) != findset(x * + y)) {
cnt--;
unionset(nx * + ny, x * + y);
}
}
}
cout << cnt << endl;
}
return ;
}
代碼取自第一名zp19911109，值得學習。
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)