Bestcoder Round#45
给定数n，要我们求该数的二进制中有多少组1， 相邻的1称为1组， 直接位运算摸你即可
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <algorithm> 5 #include <iostream> 6 #include <queue> 7 #include <stack> 8 #include <vector> 9 #include <map> 10 #include <set> 11 #include <string> 12 #include <math.h> 13 using namespace std; 14 #pragma warning(disable:4996) 15 typedef long long LL; 16 const int INF = 1<<30; 17 /* 18 19 */ 20 21 int main() 22 { 23 int t; 24 LL n; 25 scanf("%d", &t); 26 while (t--) 27 { 28 scanf("%I64d", &n); 29 int ans = 0; 30 bool flag = true; 31 while (n) 32 { 33 if ((n & 1)) 34 { 35 if (flag) 36 { 37 ans++; 38 flag = false; 39 } 40 } 41 else 42 flag = true; 43 44 n >>= 1; 45 } 46 printf("%d\n", ans); 47 } 48 return 0; 49 }
View Code
比赛的时候，一直认为求逆序对，要用树状数组做， 就YY出了一个树状数组的解法。
我把询问按照L从小到大排序，然后分为两种情况
对于第一种情况，我们只要将左边的数从树状数组中减去，然后加上右边的数即可。
对于第二种情况，我们将数状数组情况， 重新建树状数组
其实比赛完之后，仔细想想，如果存在很多第二种情况（应该最多只有1000种，因为N<=1000） ， 那么时间复杂度是N*N*logN， 应该是勉强可以过， 或者直接TLE
不过自己YY出来这种想法， 还是挺好的。
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <algorithm> 5 #include <iostream> 6 #include <queue> 7 #include <stack> 8 #include <vector> 9 #include <map> 10 #include <set> 11 #include <string> 12 #include <math.h> 13 using namespace std; 14 #pragma warning(disable:4996) 15 typedef long long LL; 16 const int INF = 1<<30; 17 /* 18 19 */ 20 struct Node 21 { 22 int l, r; 23 int id; 24 bool operator<(const Node &rhs)const 25 { 26 if (l == rhs.l) 27 return r < rhs.r; 28 return l < rhs.l; 29 } 30 }Q[100000+10]; 31 int a[1000 + 10]; 32 int b[1000 + 10]; 33 map<int, int> mark; 34 int ans[100000 + 10]; 35 int sum[1000 + 10]; 36 int lowbit(int x) 37 { 38 return x & (-x); 39 } 40 void modify(int pos, int val, int n) 41 { 42 while (pos <= n) 43 { 44 sum[pos] += val; 45 pos += lowbit(pos); 46 } 47 } 48 int getSum(int pos) 49 { 50 int ret = 0; 51 while (pos > 0) 52 { 53 ret += sum[pos]; 54 pos -= lowbit(pos); 55 } 56 return ret; 57 } 58 int main() 59 { 60 int n, q; 61 while (scanf("%d%d", &n, &q) != EOF) 62 { 63 memset(sum, 0, sizeof(sum)); 64 for (int i = 0; i < n; ++i) 65 { 66 scanf("%d", &a[i]); 67 b[i] = a[i]; 68 } 69 for (int i = 0; i < q; ++i) 70 { 71 scanf("%d%d", &Q[i].l, &Q[i].r); 72 Q[i].l--; 73 Q[i].r--; 74 Q[i].id = i; 75 } 76 sort(a, a + n); 77 sort(Q, Q + q); 78 n = unique(a, a + n) - a; 79 //printf("%d\n", n); 80 for (int i = 0; i < n; ++i) 81 { 82 mark[a[i]] = i + 1; 83 //printf("%d %d\n", a[i], i + 1); 84 } 85 int preL = 0; 86 int preR = 0; 87 int t; 88 int tmp = 0; 89 for (int i = 0; i < q; ++i) 90 { 91 if (preR - 1 > Q[i].r)//第二种情况， 清空树状数组 92 { 93 memset(sum, 0, sizeof(sum)); 94 preR = Q[i].l; 95 preL = Q[i].l; 96 tmp = 0; 97 } 98 for (int j = preL; j < Q[i].l; ++j)//减去左边的区间 99 { 100 tmp -= getSum(mark[b[j]]-1); 101 modify(mark[b[j]], -1, mark[a[n - 1]]); 102 preL = Q[i].l; 103 104 } 105 106 for (int j = preR; j <= Q[i].r; ++j) 107 { 108 109 modify(mark[b[j]], 1, mark[a[n-1]]); 110 tmp += getSum(mark[a[n-1]])-getSum(mark[b[j]]); 111 } 112 preR = Q[i].r + 1; 113 ans[Q[i].id] = tmp; 114 } 115 for (int i = 0; i < q; ++i) 116 printf("%d\n", ans[i]); 117 } 118 return 0; 119 }
View Code
正解应该是。
设ans1[i][j] 为区间i–>j,包含a[i]的逆序对数， 首先我们暴力算好ans1[i][j] ,时间复杂度为O(N*N)
设ans2[i][j] 为区间i–>j中的逆序对数，
那么ans2[i][j] = ans1[i][j] + ans[i+1][j] +…+ans[j][j]
优化一下就是， 如果ans2[i+1][j] 已经算好了， 那么ans2[i][j] = ans2[i+1][j] + ans1[i][j];
所以这个的时间复杂度也是O(N*N),而且 ans1 和ans2可以合成一个数组
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <algorithm> 5 #include <iostream> 6 #include <queue> 7 #include <stack> 8 #include <vector> 9 #include <map> 10 #include <set> 11 #include <string> 12 #include <math.h> 13 using namespace std; 14 #pragma warning(disable:4996) 15 typedef long long LL; 16 const int INF = 1<<30; 17 /* 18 19 */ 20 const int N = 1000 + 10; 21 int ans[N][N]; 22 int a[N]; 23 int main() 24 { 25 int n, q; 26 while (scanf("%d%d", &n, &q) != EOF) 27 { 28 for (int i = 1; i <= n; ++i) 29 scanf("%d", &a[i]); 30 31 //这里的ans[i][j] 表示区间i-->j， 包含元素a[i]的逆序对数 32 for (int i = 1; i <= n; ++i) 33 for (int j = i; j <= n; ++j) 34 ans[i][j] += ans[i][j - 1] + (a[i] > a[j] ? 1 : 0); 35 36 //那么 ans[i][j] 要表示区间i-->j的逆序对数时， ans[i][j] += ans[i+1][j] + ans[i+2][j]+...+ans[j][j] 37 // 如果ans[i+1][j]已经算出来了， 那么ans[i][j] += ans[i+1][j] 即可, 因为贡献是后缀和性质的 38 for (int j = 1; j <= n; ++j) 39 for (int i = j; i >= 1; --i) 40 ans[i][j] += ans[i + 1][j]; 41 int l, r; 42 while (q--) 43 { 44 scanf("%d%d", &l, &r); 45 printf("%d\n", ans[l][r]); 46 } 47 } 48 return 0; 49 }
View Code
给我们一棵树，每个节点都有权值， 有两个操作
0 x y , 将节点x的权值改为y
1 x y 询问x->y 的路径上， 是否有权值的次数出现奇数次（保证最多只有一个奇数次） 如果没有，输出-1， 如果有， 输出那个权值
任意两点的路径， 可以用lca求出， 然后要求权值是不是出现奇数次， 可以用异或， a^a = 0 , a^a^a=a,
然而这并没有什么用，TLE， 如果树退化成链， 那么每次询问的时间复杂度是O(N)，每次询问的复杂度要O(logN)才行
1 #pragma comment(linker, "/STACK:102400000,102400000") 2 #include <stdio.h> 3 #include <string.h> 4 #include <stdlib.h> 5 #include <algorithm> 6 #include <iostream> 7 #include <queue> 8 #include <stack> 9 #include <vector> 10 #include <map> 11 #include <set> 12 #include <string> 13 #include <math.h> 14 using namespace std; 15 #pragma warning(disable:4996) 16 typedef long long LL; 17 const int INF = 1<<30; 18 /* 19 RE 20 */ 21 const int N = 100000 + 10; 22 struct Edge 23 { 24 int to, next; 25 }g[N]; 26 27 int value[N], head[N], e, parent[N], depth[N]; 28 void addEdge(int a, int b) 29 { 30 g[e].to = b; 31 g[e].next = head[a]; 32 head[a] = e++; 33 } 34 void dfs(int u, int fa, int d) 35 { 36 depth[u] = d; 37 for (int i = head[u]; i != -1; i = g[i].next) 38 { 39 int v = g[i].to; 40 if (v == fa) continue; 41 dfs(v, u,d + 1); 42 } 43 } 44 45 int solve(int x, int y) 46 { 47 if (x == y) 48 return value[x]; 49 int ret = 0; 50 ret ^= value[x]; 51 //ret ^= value[y]; 52 if (depth[x] < depth[y]) 53 swap(x, y); 54 int t = y; 55 int d = depth[x]; 56 while(d > depth[y]) 57 { 58 x = parent[x]; 59 d--; 60 ret ^= value[x]; 61 } 62 while (x!=y) 63 { 64 x = parent[x]; 65 y = parent[y]; 66 ret ^= value[x]; 67 ret ^= value[y]; 68 } 69 if (t != y) 70 ret ^= value[y]; 71 return ret; 72 73 } 74 int main() 75 { 76 int t, n, q, a, b, op; 77 scanf("%d", &t); 78 while (t--) 79 { 80 memset(parent, -1, sizeof(parent)); 81 memset(depth, 0, sizeof(depth)); 82 memset(head, -1, sizeof(head)); 83 e = 0; 84 scanf("%d%d", &n, &q); 85 for (int i = 1; i < n; ++i) 86 { 87 scanf("%d%d", &a, &b); 88 addEdge(a, b); 89 addEdge(b, a); 90 parent[b] = a; 91 92 } 93 int root = 1; 94 while (parent[root] != -1) 95 root = parent[root]; 96 dfs(root,-1,1); 97 for (int i = 1; i <= n; ++i) 98 { 99 scanf("%d", &value[i]); 100 value[i]++; 101 } 102 for (int i = 0; i < q; ++i) 103 { 104 scanf("%d%d%d", &op, &a, &b); 105 if (op == 0) 106 value[a] = b; 107 else 108 { 109 int ret = solve(a, b); 110 printf("%d\n", ret ? ret-1 : -1); 111 } 112 } 113 } 114 return 0; 115 }
View Code
题解说这题要用树链剖分， 然后我并不懂
版权声明：本文为justPassBy原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。