suan-fa-xun-lian-shen-mei-ke

title: ‘算法训练-审美课’date: 2020-03-20 21:57:14
tags: [蓝桥杯]
published: true
hideInList: false
feature:
isTop: false

/*
试题 算法训练 审美课

资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
　　《审美的历程》课上有n位学生，帅老师展示了m幅画，
其中有些是梵高的作品，另外的都出自五岁小朋友之手。
老师请同学们分辨哪些画的作者是梵高，但是老师自己
并没有答案，因为这些画看上去都像是小朋友画的……
老师只想知道，有多少对同学给出的答案完全相反，
这样他就可以用这个数据去揭穿披着皇帝新衣的抽象艺术了
（支持帅老师）。
　　答案完全相反是指对每一幅画的判断都相反。
输入格式
　　第一行两个数n和m，表示学生数和图画数；
　　接下来是一个nm的01矩阵A：
　　如果aij=0，表示学生i觉得第j幅画是小朋友画的；
　　如果aij=1，表示学生i觉得第j幅画是梵高画的。
输出格式
　　输出一个数ans：表示有多少对同学的答案完全相反。
样例输入
3 2
1 0
0 1
1 0
样例输出
2
样例说明
　　同学1和同学2的答案完全相反；
　　同学2和同学3的答案完全相反；
　　所以答案是2。
数据规模和约定
　　对于50%的数据：n<=1000；
　　对于80%的数据：n<=10000；
　　对于100%的数据：n<=50000，m<=20。/

//直接暴力-超时
#include <iostream>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    int a[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int k = i + 1; k < n; k++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] == a[k][j]) {
                    break;
                }
                if (j == m - 1){
                    ans++;
                }        
            }
        }
    }
    cout << ans;
    return 0;
}

#include <iostream>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    int a[n];
    for (int i = 0; i < n; i++) {
        a[i] = 0;
        for (int j = 0; j < m; j++) {
            int k;
            cin >> k;
            a[i] = a[i] * 10 + k;
        }
    }
    int ans = 0;
    int l = 0;
    for (int j = 0; j < m; j++) {
        l = l * 10 + 1;
    }
    // cout << l << endl;
    for (int i = 0; i < n; i++) {
        for (int k = i + 1; k < n; k++) {
            int x = a[i] + a[k];
            if (x == l) {
                ans++;
            }
        }

    }
    cout << ans;
    return 0;
}

1101+0010=1111 全部相反 两数相加等于全一 这样时间复杂度会下降 但是依旧超时

看网上的解析别人有用散列 改了下果然过了 这也是之前忽略的一个地方 明天再好好看看相关的知识点

#include <iostream>
#include <map>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    map<int, int> num;
    for (int i = 0; i < n; i++) {
        int t = 0;
        for (int j = 0; j < m; j++) {
            int k;
            cin >> k;
            t = t * 10 + k;
        }
        num[t]++;
    }

    int ans = 0;
    int l = 0;
    for (int j = 0; j < m; j++) {
        l = l * 10 + 1;
    }
    for (map<int, int>::iterator it = num.begin(); it != num.end(); ++it){
        for (map<int, int>::iterator it2 = num.begin(); it2 != num.end(); ++it2){
            if(it->first+it2->first==l){
                ans += it->second * it2->second;
            }
        }
    }

    cout << ans;
    return 0;
}