Gym-101502B Linear Algebra Test

题意：给出n个矩阵的行数与列数，问有多少对矩阵可以相乘。做法：矩阵可以相乘的条件是，前一个矩阵的列数=后一个的行数。我们只要分别用一个数组，保存行数a[]与列数b[]，遍历b[]，对b[]中每一个数，遍历a[]，找到可以配对的行数个数，累加。然而这样做是会超时的，1≤n≤10^5。因为1≤ai,bi≤10^9，即行数与列数的范围，我想到建立一个10^9的数组a[]，a[i]中保存的是行数为i的矩阵个数，保存所有列数至b[]。遍历b[]，直接a[b[i]]，累加。可是我发现不能够用10^9的数组(win10, codeblocks16.01)，说数组太大。然后，我就用了两个500000005的数组，哈哈。但是，超内存了。最后，我们用map(映射)优雅的解决了这个问题，思路差不多。

(1)ac代码

#include 
   
    #include 
    
     #include 
     using namespace std;intmain() {    int t, n, i, j, a[2][100005];    long long ans;    map 
      
        m;    cin >> t;    while( t-- ) {        m.clear();  //        cin >> n;        for( j = 0; j < n; j++ ) {            for( i = 0; i < 2; i++ ) {                scanf("%d", &a[i][j]);  // cin会超时            }        }        for( j = 0; j < n; j++ ) {            m[a[0][j]]++;            //cout << a[0][j] << endl;        }        //cout << endl;        ans = 0;        for( j = 0; j < n; j++ ) {            ans += m[a[1][j]];            //cout << a[1][j] << endl;        }        cout << ans << endl;    }    return 0;}

(2)超内存，初始版本

#include 
   
    #include 
    
     int a[100000005], b[100005];intmain() {    int t, n, e, i, ans;    scanf("%d", &t);    while( t-- ) {        ans = 0;        memset(a, 0, sizeof(a));        scanf("%d", &n);        for( i = 0; i < n; i++ ) {            scanf("%d %d", &e, &b[i]);            a[e]++;        }        for( i = 0; i < n; i++ ) {            ans += a[b[i]];        }        printf("%d\n", ans);    }    return 0;}

(3)超内存/编译错误，两个数组

#include 
   
    #include 
    
     int a1[500000005], a2[500000005], b[100005];intmain() {    int t, n, e, i, ans;    scanf("%d", &t);    while( t-- ) {        ans = 0;        memset(a1, 0, sizeof(a1));        memset(a2, 0, sizeof(a2));        scanf("%d", &n);        for( i = 0; i < n; i++ ) {            scanf("%d %d", &e, &b[i]);            if( e > 500000000 ) {                a2[e % 500000000]++;            }            else {                a1[e]++;            }        }        for( i = 0; i < n; i++ ) {            if( b[i] > 500000000 ) {                ans += a2[b[i] % 500000000];            }            else {                ans += a1[b[i]];            }        }        printf("%d\n", ans);    }    return 0;}

(4)超时

#include 
   
    #include 
    
     int a[100005], b[100005];intmain() {    int t, n, i, j, ans;    scanf("%d", &t);    while( t-- ) {        ans = 0;        scanf("%d", &n);        for( i = 0; i < n; i++ ) {            scanf("%d %d", &a[i], &b[i]);        }        for( i = 0; i < n; i++ ) {            for( j = 0; j < n; j++ ) {                if( a[i] == b[j] ) {                    ans++;                }            }        }        printf("%d\n", ans);    }    return 0;}

转载地址：http://zvkxi.baihongyu.com/

你可能感兴趣的文章

Objective-C学习准备__C语言4

查看>>

bzoj1195 最短母串

查看>>

从产品展示页面谈谈Hybris的特有概念和设计结构