You took a peek on Thanos wearing Infinity Gauntlet. In the Gauntlet there is a place for six Infinity Gems:
the Power Gem of purple color, the Time Gem of green color, the Space Gem of blue color, the Soul Gem of orange color, the Reality Gem of red color, the Mind Gem of yellow color.
Using colors of Gems you saw in the Gauntlet determine the names of absent Gems.
In the first line of input there is one integer n(0 ≤ n ≤ 6) — the number of Gems in Infinity Gauntlet.
Output
In the first line output one integer m(0 ≤ m ≤ 6) — the number of absent Gems.
Then in m lines print the names of absent Gems, each on its own line. Words used for names are: Power, Time, Space, Soul, Reality, Mind. Names can be printed in any order. Keep the first letter uppercase, others lowercase.
Examples
input
4
red
purple
yellow
orange
output
2
Space
Time
input
0
output
6
Time
Mind
Soul
Power
Reality
Space
Note
In the first sample Thanos already has Reality, Power, Mind and Soul Gems, so he needs two more: Time and Space.
In the second sample Thanos doesn't have any Gems, so he needs all six.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
/************************************************** filename :a.cpp author :maksyuki created time :2018/5/29 23:13:08 last modified :2018/5/29 23:46:36 file location :C:\Users\abcd\Desktop\codeforces ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; map<string, string> dict; void init() { dict["purple"] = "Power"; dict["green"] = "Time"; dict["blue"] = "Space"; dict["orange"] = "Soul"; dict["red"] = "Reality"; dict["yellow"] = "Mind"; } int main() { #ifdef LOCAL CFF; //CFO; #endif int n; init(); while(cin >> n) { string s; map<string, int> vis; for(int i = 1; i <= n; i++) { cin >> s; vis[s] = 1; } cout << 6 - n << endl; for(map<string, string> :: iterator it = dict.begin(); it != dict.end(); it++) { if(vis[it->first] == 1) continue; else cout << it->second << endl; } } return 0; } |
On the only line of input there are two integers x and y(1≤ x, y ≤ 10^9).
If x^y < y^x , then print '<' (without quotes). If x^y > y^x, then print '>' (without quotes). If x^y = y^x, then print '=' (without quotes).
5 8
output
>
input
10 3
output
<
input
6 6
output
=
Note
In the first example 5^8 = 5 ⋅ 5 ⋅ 5 ⋅ 5 ⋅ 5 ⋅ 5 ⋅ 5 ⋅ 5 = 390625, and 8^5 = 8 ⋅ 8 ⋅ 8 ⋅ 8 ⋅ 8 = 32768. So you should print '>'.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
/************************************************** filename :b.cpp author :maksyuki created time :2018/5/29 23:46:44 last modified :2018/5/30 0:05:28 file location :C:\Users\abcd\Desktop\codeforces ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; int main() { #ifdef LOCAL CFF; //CFO; #endif LL x, y; while(cin >> x >> y) { double tmpx = log(x); double tmpy = log(y); double va = y * tmpx; double vb = x * tmpy; //DB(va), DB(vb); if(va > vb + EPS) cout << ">" << endl; else if(va + EPS < vb) cout << "<" << endl; else cout << "=" << endl; } return 0; } |
算法分析：更好的方法是xlny和ylnx同时除以xy(xy > 1)，则转换成比较lnx/x和lny/y之间的大小关系，易知f(x)=lnx/x在x=e处取得最大值，题目给定x为整数，则可以得到f(3) > f(2)=f(4) > f(5) > f(6) > ...f(n) > f(1)，按照这个大小关系直接判断即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
/************************************************** filename :z.cpp author :maksyuki created time :2018/6/2 17:52:44 last modified :2018/6/2 18:24:56 file location :C:\Users\abcd\Desktop\codeforces ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; int main() { #ifdef LOCAL CFF; //CFO; #endif int x, y; while(cin >> x >> y) { if(x > 3 && y > 3) { if(x > y) cout << "<"; else if(x < y) cout << ">"; else cout << "="; } else if(x <= 3 && y <= 3) { if(x > y) cout << ">"; else if(x < y) cout << "<"; else cout << "="; } else if(x <= 3 && y > 3) { if(x == 1) cout << "<"; else if(x == 3) cout << ">"; else { if(y == 4) cout << "="; else cout << ">"; } } else if(x > 3 && y <= 3) { if(y == 1) cout << ">"; else if(y == 3) cout << "<"; else { if(x == 4) cout << "="; else cout << "<"; } } cout << endl; } return 0; } |
C Three displays
It is the middle of 2018 and Maria Stepanovna, who lives outside Krasnokamensk (a town in Zabaikalsky region), wants to rent three displays to highlight an important problem.
There are n displays placed along a road, and the i-th of them can display a text with font size si
only. Maria Stepanovna wants to rent such three displays with indices i<j<k that the font size increases if you move along the road in a particular direction. Namely, the condition si < sj < sk should be held.
The rent cost is for the i-th display is ci. Please determine the smallest cost Maria Stepanovna should pay.
Input
The first line contains a single integer n(3 ≤ n ≤ 3000) — the number of displays.
The second line contains n integers s1, s2, …, sn(1 ≤ si ≤ 10^9) — the font sizes on the displays in the order they stand along the road.
The third line contains n integers c1, c2, …, cn(1 ≤ ci ≤ 10^8) — the rent costs for each display.
Output
If there are no three displays that satisfy the criteria, print -1. Otherwise print a single integer — the minimum total rent cost of three displays with indices i < j < k such that si < sj < sk.
Examples
input
5
2 4 5 4 10
40 30 20 10 40
output
90
input
3
100 101 100
2 4 5
output
-1
input
10
1 2 3 4 5 6 7 8 9 10
10 13 11 14 15 12 13 13 18 13
output
33
Note
In the first example you can, for example, choose displays 1, 4 and 5, because s1 < s4 < s5(2 < 4 < 10), and the rent cost is 40 + 10 + 40 = 90.
In the second example you can't select a valid triple of indices, so the answer is -1.
题目类型：暴力枚举
算法分析：如果每次从枚举i的位置开始的话，那么j和k的位置是会相互牵连的，求解时间复杂度是O(n^3)的。此时若枚举j的位置，i和k的位置就被j所划分开来，然后分别在其左边范围内枚举i，在右边范围内枚举k，则时间复杂度为O(n^2)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
/************************************************** filename :d.cpp author :maksyuki created time :2018/6/2 18:56:56 last modified :2018/6/2 19:11:39 file location :C:\Users\abcd\Desktop\codeforces ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 6666; LL v[maxn], c[maxn]; int main() { #ifdef LOCAL CFF; //CFO; #endif int n; while(cin >> n) { for(int i = 1; i <= n; i++) cin >> v[i]; for(int i = 1; i <= n; i++) cin >> c[i]; LL ans = 0; bool have_val = false; for(int i = 2; i <= n - 1; i++) { LL minvala = INF; LL minvalb = INF; for(int j = 1; j < i; j++) if(v[j] < v[i]) minvala = min(minvala, c[j]); for(int j = i + 1; j <= n; j++) if(v[j] > v[i]) minvalb = min(minvalb, c[j]); if(!have_val) { have_val = true; ans = c[i] + minvala + minvalb; } else ans = min(ans, c[i] + minvala + minvalb); } if(ans > (LL)INF) cout << "-1" << endl; else cout << ans << endl; } return 0; } |
D Fair
Some company is going to hold a fair in Byteland. There are n towns in Byteland and m two-way roads between towns. Of course, you can reach any town from any other town using roads. There are k types of goods produced in Byteland and every town produces only one type. To hold a fair you have to bring at least s different types of goods. It costs d(u, v) coins to bring goods from town u to town v where d(u, v) is the length of the shortest path from u to v. Length of a path is the number of roads in this path.
The organizers will cover all travel expenses but they can choose the towns to bring goods from. Now they want to calculate minimum expenses to hold a fair in each of n towns.
Input
There are 4 integers n, m, k, s in the first line of input (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^5, 1 ≤ s ≤ k ≤ min(n, 100)) — the number of towns, the number of roads, the number of different types of goods, the number of different types of goods necessary to hold a fair.
In the next line there are n integers a1, a2, …, an(1 ≤ ai ≤ k), where ai is the type of goods produced in the i-th town. It is guaranteed that all integers between 1 and k occur at least once among integers ai.
In the next m lines roads are described. Each road is described by two integers u v(1 ≤ u, v ≤ n, u ≠ v) — the towns connected by this road. It is guaranteed that there is no more than one road between every two towns. It is guaranteed that you can go from any town to any other town via roads.
Output
Print n numbers, the i-th of them is the minimum number of coins you need to spend on travel expenses to hold a fair in town i. Separate numbers with spaces.
Examples
input
5 5 4 3
1 2 4 3 2
1 2
2 3
3 4
4 1
4 5
output
2 2 2 2 3
input
7 6 3 2
1 2 3 3 2 2 1
1 2
2 3
3 4
2 5
5 6
6 7
output
1 1 1 2 2 1 1
Note
Let's look at the first sample.
To hold a fair in town 1 you can bring goods from towns 1(0 coins), 2(1 coin) and 4(1 coin). Total numbers of coins is 2.
Town 2: Goods from towns 2(0), 1(1), 3(1). Sum equals 2.
Town 3: Goods from towns 3(0), 2(1), 4(1). Sum equals 2.
Town 4: Goods from towns 4(0), 1(1), 5(1). Sum equals 2.
Town 5: Goods from towns 5(0), 4(1), 3(2). Sum equals 3.
题目类型：BFS搜索
算法分析：首先使用BFS计算k个物品所在的点对每个点的花费(最短路)，这里可以将具有相同物品种类的点放到一个BFS中计算。之后对于每个点累加前s小的花费即可，时间复杂度为O(k(m+n))+O(nklnk)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 |
/************************************************** filename :e.cpp author :maksyuki created time :2018/6/2 19:27:17 last modified :2018/6/2 23:22:57 file location :C:\Users\abcd\Desktop\codeforces ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 66; int n, m, k, s; int v[maxn]; vector<int> g[maxn]; vector<int> dict[maxn]; int dis[maxn]; int ans[maxn][133]; void init() { for(int i = 0; i < maxn; i++) g[i].clear(), dict[i].clear(); } void bfs(int f) { queue<int> qu; for(int i = 0; i < maxn; i++) dis[i] = INF; int ddlen = dict[f].size(); for(int i = 0; i < ddlen; i++) { qu.push(dict[f][i]); dis[dict[f][i]] = 0; } while(!qu.empty()) { int u = qu.front(); qu.pop(); int glen = g[u].size(); for(int i = 0; i < glen; i++) { int v = g[u][i]; if(dis[v] <= dis[u] + 1) continue; dis[v] = dis[u] + 1; qu.push(v); } } for(int i = 1; i <= n; i++) ans[i][f] = dis[i]; } int main() { #ifdef LOCAL CFF; //CFO; #endif while(cin >> n >> m >> k >> s) { init(); for(int i = 1; i <= n; i++) { cin >> v[i]; dict[v[i]].emplace_back(i); } int in_u, in_v; for(int i = 1; i <= m; i++) { cin >> in_u >> in_v; g[in_u].emplace_back(in_v); g[in_v].emplace_back(in_u); } for(int i = 1; i <= k; i++) bfs(i); //int tmp[maxn]; bool is_first = true; for(int i = 1; i <= n; i++) { //for(int j = 1; j <= k; j++) // tmp[j] = ans[j][i]; // sort(tmp + 1, tmp + 1 + k); //ans[i][1~k]; nth_element(ans[i] + 1, ans[i] + 1 + s, ans[i] + 1 + k); int sum = 0; for(int j = 1; j <= s; j++) sum += ans[i][j]; if(is_first) { is_first = false; cout << sum; } else cout << " " << sum; } cout << endl; } return 0; } |
E Petr and Permutations
Petr likes to come up with problems about randomly generated data. This time problem is about random permutation. He decided to generate a random permutation this way: he takes identity permutation of numbers from 1 to n and then 3n times takes a random pair of different elements and swaps them. Alex envies Petr and tries to imitate him in all kind of things. Alex has also come up with a problem about random permutation. He generates a random permutation just like Petr but swaps elements 7n + 1 times instead of 3n times. Because it is more random, OK?!
You somehow get a test from one of these problems and now you want to know from which one.
Input
In the first line of input there is one integer n(10^3 ≤ n ≤ 10^6).
In the second line there are n distinct integers between 1 and n— the permutation of size n from the test.
It is guaranteed that all tests except for sample are generated this way: First we choose n— the size of the permutation. Then we randomly choose a method to generate a permutation — the one of Petr or the one of Alex. Then we generate a permutation using chosen method.
Output
If the test is generated via Petr's method print "Petr" (without quotes). If the test is generated via Alex's method print "Um_nik" (without quotes).
Example
input
5
2 4 5 1 3
output
Petr
Note
Please note that the sample is not a valid test (because of limitations for n) and is given only to illustrate input/output format. Your program still has to print correct answer to this test to get AC. Due to randomness of input hacks in this problem are forbidden.
题目类型：逆序对/置换群
算法分析：置换群求解逆序对问题的经典模型，逆序对的奇偶性和构成置换的循环的个数的奇偶性相关
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
/************************************************** filename :f.cpp author :maksyuki created time :2018/6/3 15:07:04 last modified :2018/6/3 15:58:00 file location :C:\Users\abcd\Desktop\codeforces ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e6 + 6666; int aa[maxn]; bool vis[maxn]; int main() { #ifdef LOCAL CFF; //CFO; #endif int n; while(cin >> n) { for(int i = 1; i <= n; i++) cin >> aa[i]; memset(vis, false, sizeof(vis)); int cnt = 0; for(int i = 1; i <= n; i++) { if(vis[i]) continue; int p = i; cnt++; while(!vis[p]) { int tmp = p; p = aa[p]; vis[tmp] = true; } } // DB(cnt); if(cnt & 1) cout << "Um_nik" << endl; else cout << "Petr" << endl; } return 0; } |
F AND Graph
You are given a set of size m with integer elements between 0 and 2^n − 1 inclusive. Let's build an undirected graph on these integers in the following way: connect two integers x and y with an edge if and only if x&y = 0. Here & is the bitwise AND operation. Count the number of connected components in that graph.
Input
In the first line of input there are two integers n and m(0 ≤ n ≤ 22, 1 ≤ m ≤ 2^n).
In the second line there are m integers a1, a2, …, am(0 ≤ ai < 2^n) — the elements of the set. All ai are distinct.
Output
Print the number of connected components.
Examples
input
2 3
1 2 3
output
2
input
5 5
5 19 10 20 12
output
2
题目类型：DFS搜索
算法分析：重要的是依据'a&b'构造出图，然后计算图中的连通块数量，时间复杂度为O(n*2^n)，详见解法请参考CF485解题报告
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
/************************************************** filename :g.cpp author :maksyuki created time :2018/6/3 16:49:05 last modified :2018/6/3 17:04:38 file location :C:\Users\abcd\Desktop\codeforces ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = (1 << 22) + 666; int n, m; int aa[maxn]; bool hv[maxn]; bool vis[maxn*2]; void init() { memset(hv, false, sizeof(hv)); memset(vis, false, sizeof(vis)); } void dfs(int p) { vis[p] = true; if(p < (1 << n)) { if(hv[p] && !vis[p+(1<<n)]) dfs(p + (1<<n)); } else { int tt = (1 << (n + 1)) - 1 - p; if(hv[tt] && !vis[tt]) dfs(tt); for(int i = 0; i < n; i++) if(!vis[p|(1<<i)]) dfs(p|(1<<i)); } } int main() { #ifdef LOCAL CFF; //CFO; #endif while(scanf("%d %d", &n, &m) != EOF) { init(); for(int i = 1; i <= m; i++) { scanf("%d", &aa[i]); hv[aa[i]] = true; } int ans = 0; for(int i = 1; i <= m; i++) if(!vis[aa[i]]) { dfs(aa[i]); ans++; } printf("%d\n", ans); } return 0; } |
- « 上一篇：uva10129
- uva10562：下一篇 »