2017 JUST Programming Contest 3.0 B. Linear Algebra Test

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

B. Linear Algebra Test

time limit per test

3.0 s

memory limit per test

256 MB

input

standard input

output

standard output

Dr. Wail is preparing for today's test in linear algebra course. The test's subject is Matrices Multiplication.

Dr. Wail has n matrices, such that the size of the i th matrix
is ( a i × b i ),
where a i is
the number of rows in the i th matrix,
and b i is
the number of columns in the i th matrix.

Dr. Wail wants to count how many pairs of indices i and j exist,
such that he can multiply the i th matrix
with the j th matrix.

Dr. Wail can multiply the i th matrix
with the j th matrix,
if the number of columns in the i th matrix
is equal to the number of rows in the j th matrix.

Input

The first line contains an integer T (1 ≤ T ≤ 100),
where T is the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 105),
where n is the number of matrices Dr. Wail has.

Then n lines follow, each line contains two integers a i and b i (1 ≤ a i , b i ≤ 109) ( a i ≠ b i ),
where a i is
the number of rows in the i th matrix,
and b i is
the number of columns in the i th matrix.

Output

For each test case, print a single line containing how many pairs of indices i and j exist,
such that Dr. Wail can multiply the i th matrix
with the j th matrix.

Example

input

output

Note

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printfinstead of cin/cout in
C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in
Java.

In the first test case, Dr. Wail can multiply the 1 st matrix (2 × 3) with
the 4 th matrix (3 × 5),
the 2 nd matrix (2 × 3) with
the 4 th matrix (3 × 5),
the 3 rd matrix (4 × 2) with
the 1 st and
second matrices (2 × 3), and the 5 th matrix (9 × 4) with
the 3 rd matrix (4 × 2).
So, the answer is 5.

题意：给你多个矩阵ai表示行数，bi表示列数

要你求行数与列数相等的对数有多少种？

思路：利用map可以把复杂度降到O（n）

需要注意的是

2 3

3 2

这一类的情况结果是2对，而不是一对；另外由于数据是1e9，所以以后见到1e9都用上long long

#include <iostream>

#include<string.h>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<map>

using namespace std;

const int maxn=1e5+10;

typedef long long ll;

struct node

{

    ll col,row;

    int flag;

};

struct mnode

{

    int flag;

};

int main()

{

    ll t;

    scanf("%lld",&t);

    while(t--)

    {

        map<ll,node> m;

       // map<mnode,mnode>mab;

       map<int,int>mab;

        ll n;

        scanf("%lld",&n);

        ll a,b;

        ll ans=0,flag=0;

        for(ll i=1;i<=n;i++)

            {

                scanf("%lld%lld",&a,&b);

                mab[a]=b;

                    m[a].col+=1;

                    m[b].row+=1;

            }

        map<ll,node>::iterator it;

        for(it=m.begin();it!=m.end();it++){

                ans+=it->second.col*it->second.row;

        }

        printf("%lld\n",ans-flag);

    }

    return 0;

}