A.Dylans loves numbers
Problem Description
Who is Dylans?You can find his ID in UOJ and Codeforces. His another ID is s1451900 in BestCoder. And now today's problems are all about him.Dylans is given a number N.
He wants to find out how many groups of "1" in its Binary representation.
If there are some "0"（at least one）that are between two "1",
then we call these two "1" are not in a group,otherwise they are in a group.
Input
In the first line there is a number T.
T is the test number.
In the next T lines there is a number N.
0≤N≤1018,T≤1000
Output
For each test case,output an answer.
Sample Input
15
Sample Output
2
Source
题目类型：简单模拟
算法分析：直接按照题意将long long型整数转换成二进制存储到数组中，然后扫一遍数组，判断有多少个相连的”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 |
#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; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const int mod = 1000000000 + 7; const int maxn = 1000 + 66; int a[maxn]; int main() { // ifstream cin ("aaa.txt"); int t; cin >> t; while (t--) { long long n; cin >> n; if (n == 0) { cout << "0" << endl; continue; } int len = 0; do { a[len++] = n % 2; n /= 2; } while (n); int res = 0, cnt = 0; for (int i = 0; i < len; ) { if (a[i] == 1) { while (i < len && a[i] == 1) { i++; cnt++; } } else { i++; if (cnt > 0) res++; cnt = 0; } } if (a[len-1] == 1) res++; cout << res << endl; } return 0; } |
B.Dylans loves sequence
Problem Description
Dylans is given N numbers a[1]....a[N]
And there are Q questions.
Each question is like this (L,R)
his goal is to find the “inversions” from number L to number R.
more formally,his needs to find the numbers of pair（x,y）,
that L≤x,y≤R and x<y and a[x]>a[y]
Input
In the first line there is two numbers N and Q.
Then in the second line there are N numbers:a[1]..a[N]
In the next Q lines,there are two numbers L,R in each line.
N≤1000,Q≤100000,L≤R,1≤a[i]≤231−1
Output
For each query,print the numbers of "inversions”
Sample Input
3 23 2 11 21 3
Sample Output
13 Hint You shouldn't print any space in each end of the line in the hack data.
Source
题目类型：区间DP
算法分析：使用dp[i][j]表示[i,j]区间中逆序对的个数，状态转移方程为：dp[i][j] = dp[i][j-1] + tempsum，其中tempsum表示[i,j-1]区间中比a[j]大的数的个数。时间复杂度大约是O(n^3/k)
的，其中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 |
#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 lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const int mod = 1000000000 + 7; const int maxn = 1000 + 66; int a[maxn]; int dp[maxn][maxn]; int main() { // freopen ("aaa.txt", "r", stdin); int n, q; while (scanf ("%d%d", &n, &q) != EOF) { for (int i = 1; i <= n; i++) scanf ("%d", &a[i]); memset (dp, 0, sizeof (dp)); for (int i = 1; i <= n; i++) { for (int j = 1; j + i <= n; j++) { for (int k = j + i - 1; k >= j; k--) if (a[k] > a[j+i]) dp[j][i+j]++; dp[j][i+j] += dp[j][i+j-1]; } } int L, R; for (int i = 1; i <= q; i++) { scanf ("%d%d", &L, &R); printf ("%d\n", dp[L][R]); } } return 0; } |
前缀优化：先简单说一下算法，使用dp[i][j]表示[i,j]区间中有多少个数比j大，然后一个优化是边读入边处理，从小区间到大区间计算dp数组并维护一个前缀性质，时间复杂度是O(n^2)的。状态转移方程为：
if (a[j] > a[i]) dp[j][i] = dp[j+1][i] + 1; else dp[j][i] = dp[j+1][i];
由于[i,j]区间内的逆序对个数=dp[i][i] + dp[i][i+1] + dp[i][i+2] + ……dp[i][j]，所以再使用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 |
#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 lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const int mod = 1000000000 + 7; const int maxn = 1000 + 66; int a[maxn]; int dp[maxn][maxn]; int main() { // freopen ("aaa.txt", "r", stdin); int n, q; while (scanf ("%d%d", &n, &q) != EOF) { memset (dp, 0, sizeof (dp)); for (int i = 1; i <= n; i++) { scanf ("%d", &a[i]); for (int j = i - 1; j >= 1; j--) { if (a[j] > a[i]) dp[j][i] = dp[j+1][i] + 1; else dp[j][i] = dp[j+1][i]; } } for (int i = 1; i <= n; i++) { int sum = 0; for (int j = i; j <= n; j++) { sum += dp[i][j]; dp[i][j] = sum; } } int L, R; for (int i = 1; i <= q; i++) { scanf ("%d%d", &L, &R); printf ("%d\n", dp[L][R]); } } return 0; } |
树状数组(线段树)求解：这是一个比较常规的思路，在求解时使用DP递推，则可以将时间复杂度优化到O(n^2log(n))。注意这里元素的值比较大，在求解之前需要先进行离散化处理，这里将输入的数映射成一个连续的下标
|
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 |
#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 lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const int mod = 1000000000 + 7; const int maxn = 1000 + 66; int a[maxn], sum[maxn<<2], temp[maxn]; int dp[maxn][maxn], len; void PushUp (int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } int Query (int rt, int l, int r, int L, int R) { if (L <= l && r <= R) return sum[rt]; int res = 0, m = (l + r) >> 1; if (L <= m) res += Query (lson, L, R); if (R > m) res += Query (rson, L, R); return res; } void UpDate (int rt, int l, int r, int val) { if (l == r) { sum[rt]++; return ; } int m = (l + r) >> 1; if (val <= m) UpDate (lson, val); else UpDate (rson, val); PushUp (rt); } int main() { // freopen ("aaa.txt", "r", stdin); int n, q; while (scanf ("%d%d", &n, &q) != EOF) { for (int i = 1; i <= n; i++) { scanf ("%d", &a[i]); temp[i] = a[i]; } sort (temp + 1, temp + 1 + n); len = unique (temp + 1, temp + 1 + n) - (temp + 1); for (int i = 1; i <= n; i++) a[i] = lower_bound (temp + 1, temp + 1 + len, a[i]) - temp; memset (dp, 0, sizeof (dp)); for (int i = 1; i <= n; i++) { memset (sum, 0, sizeof (sum)); for (int j = i; j <= n; j++) { dp[i][j] = dp[i][j-1] + Query (1, 1, len, a[j] + 1, len); UpDate (1, 1, len, a[j]); } } int L, R; for (int i = 1; i <= q; i++) { scanf ("%d%d", &L, &R); printf ("%d\n", dp[L][R]); } } return 0; } |