本文共 3712 字，大约阅读时间需要 12 分钟。
1、
2、题目大意：
知道东西两岸各有n,m个城市，现在给出两岸城市的连接情况，连线都是直线，求东西两岸的各个城市之间的连线有多少个交点
实际上画图就可以看出来，只需要将所有连线按照东岸的城市从大到小排序，那么对于西岸的城市来说，前边比自己小的将都有交点，也就是转换成求该点前边有多少个比自己小的数的个数
3、题目
| Time Limit: 1000MS | | Memory Limit: 65536K |
| Total Submissions: 18985 | | Accepted: 5143 |
Description
Japan plans to welcome the ACM ICPC World Finals and a lot of roads must be built for the venue. Japan is tall island with N cities on the East coast and M cities on the West coast (M <= 1000, N <= 1000). K superhighways will be build. Cities on each coast are numbered 1, 2, ... from North to South. Each superhighway is straight line and connects city on the East coast with city of the West coast. The funding for the construction is guaranteed by ACM. A major portion of the sum is determined by the number of crossings between superhighways. At most two superhighways cross at one location. Write a program that calculates the number of the crossings between superhighways.
Input
The input file starts with T - the number of test cases. Each test case starts with three numbers – N, M, K. Each of the next K lines contains two numbers – the numbers of cities connected by the superhighway. The first one is the number of the city on the East coast and second one is the number of the city of the West coast.
Output
For each test case write one line on the standard output:
Test case (case number): (number of crossings)
Sample Input
13 4 41 42 33 23 1
Sample Output
Test case 1: 5
Source
#include #include #include using namespace std;#define N 1000005#define ll long longint n,m;int c[N];struct node{ int x; int y;} a[1000005];int cmp(node a,node b){ if(a.x==b.x) return a.y 0;i-=lowbit(i)) { sum+=c[i]; } return sum;}int main(){ int t,k,cas=0; scanf("%d",&t); while(t--) { cas++; memset(c,0,sizeof(c)); scanf("%d%d%d",&n,&m,&k); for(int i=1; i<=k; i++) { scanf("%d%d",&a[i].x,&a[i].y); } sort(a+1,a+k+1,cmp); ll sum=0; for(int i=1;i<=k;i++) { update(a[i].y,1); sum+=(getSum(m)-getSum(a[i].y)); } printf("Test case %d: %lld\n",cas,sum); } return 0;}/*203 4 41 42 33 23 43 4 41 42 33 23 13 4 41 42 33 23 1*/
4、wrong answer代码
#include #include #include using namespace std;#define N 1000005int n,m;int c[N];int ans[1000005];struct node{ int x; int y;} a[1000005];int cmp(node a,node b){ if(a.x==b.x) return a.y b.x;}int lowbit(int i){ return i&(-i);}void update(int x,int v){ for(int i=x;i<=m;i+=lowbit(i)) { c[i]+=v; }}int getSum(int x){ int sum=0; for(int i=x;i>0;i-=lowbit(i)) { sum+=c[i]; } return sum;}int main(){ int t,k,cas=0; scanf("%d",&t); while(t--) { cas++; memset(c,0,sizeof(c)); scanf("%d%d%d",&n,&m,&k); for(int i=1; i<=k; i++) { scanf("%d%d",&a[i].x,&a[i].y); } sort(a+1,a+k+1,cmp); memset(ans,0,sizeof(ans)); for(int i=1;i<=k;i++) { if(a[i].x==a[i-1].x && a[i].y==a[i-1].y && i>1) { ans[i]=0; } else if(a[i].x==a[i-1].x && i>1) { ans[i]=ans[i-1]; } else { ans[i]=getSum(a[i].y); } update(a[i].y,1); } int sum=0; for(int i=1;i<=k;i++) { //printf("%d\n",ans[i]); sum+=ans[i]; } printf("Test case %d: %d\n",cas,sum); } return 0;}/*203 4 41 42 33 23 43 4 41 42 33 23 13 4 41 42 33 23 1*/
转载地址：http://rwcdi.baihongyu.com/