D，http://acm.uestc.edu.cn/#/problem/show/1584
题意：平面上n个点，询问每个点左下方的点有多少个？ 解法：排序（以Y坐标为第一关键字，X坐标为第二关键字）+树状数组
#include <bits/stdc++.h> using namespace std; const int maxn=100010; int n,rnk[maxn],c[maxn]; struct node{ int x,y; }a[maxn]; bool cmp(node x, node y){ if(x.y==y.y) return x.x<y.x; return x.y<y.y; } inline int lowbit(int x){ return x&-x; } void add(int x){ while(x<maxn){ c[x]++; x+=lowbit(x); } } int sum(int x){ int ans=0; while(x>0){ ans+=c[x]; x-=lowbit(x); } return ans; } int main() { int n; while(~scanf("%d",&n)){ for(int i=1; i<=n; i++) scanf("%d %d", &a[i].x,&a[i].y); sort(a+1,a+n+1,cmp); memset(rnk,0,sizeof(rnk)); memset(c,0,sizeof(c)); for(int i=1; i<=n; i++){ rnk[sum(a[i].x)]++; add(a[i].x); } for(int i=1; i<n; i++) printf("%d\n", rnk[i-1]); printf("%d\n", rnk[n-1]); } return 0; } E，http://acm.uestc.edu.cn/#/problem/show/1583
题意：一个排列，用最少的交换次数次数变换到另一个排列，每次只能交换相邻两个元素。
解法：处理一个数组d，d[i]表示a[i]应该到b数组哪个位置。答案就是d数组的逆序对数
#include <bits/stdc++.h> using namespace std; const int maxn=1e5+10; typedef long long LL; int n,a[maxn],c[maxn]; void add(int x){ while(x<maxn){ c[x]++; x+=x&-x; } } int sum(int x){ int ans=0; while(x>0){ ans+=c[x]; x-=x&-x; } return ans; } int main() { while(~scanf("%d",&n)){ memset(c,0,sizeof(c)); memset(a,0,sizeof(a)); LL ans=0; for(int i=1; i<=n; i++){ int x; scanf("%d", &x); a[x]=i; } for(int i=1; i<=n; i++){ int x; scanf("%d", &x); ans+=1LL*(sum(n)-sum(a[x]-1)); add(a[x]); } printf("%lld\n", ans); } return 0; }F,http://acm.uestc.edu.cn/#/problem/show/1582
题意：给你n个元素的数组{a}，m次询问，每次给你一个数X，每次问你max{a1 xor X, a2 xor X, …, an xor X} 解法：对{a}里每个元素的二进制串从高位到低位建立trie（零一字典树） 询问时贪心（显然，让更高位的二进制位为1是要更优的）地向下，如果x该位是1，那么走0，如果是0，那么走1。 如果该位仅有1或0，那没办法，只能往这里走。
#include <bits/stdc++.h> using namespace std; const int maxn = 1e7+2; struct node{ int root,tot,ch[maxn][2]; int newnode(){ ch[tot][0]=ch[tot][1]=-1; return tot++; } void init(){ tot=0,root=newnode(); } void Insert(int x){ int now=root; for(int j=30; j>=0; j--){ int go=(x&(1<<j))?1:0; if(ch[now][go]==-1){ ch[now][go]=newnode(); now=ch[now][go]; } else{ now=ch[now][go]; } } } int query(int x){ int now=root; int ans=0; for(int j=30; j>=0; j--){ int go=(x&(1<<j))?1:0; if(ch[now][!go]!=-1) ans|=(1<<j),now=ch[now][!go]; else now=ch[now][go]; } return ans; } }trie; int main() { int n, q; while(~scanf("%d",&n)){ trie.init(); for(int i=1; i<=n; i++){ int x; scanf("%d",&x); trie.Insert(x); } scanf("%d",&q); while(q--){ int x; scanf("%d", &x); printf("%d\n", trie.query(x)); } } return 0; }
