PAT-Advanced Vector

2020-04-02

Abstract：不定长Vector & STL

1039 Course List for Student (25分)

解法一：unordered_map【超时】

第一反应hashmap，提交发现居然超时，看了柳婼のblog才知道是string cin cout这几个东西速度不行

#include <iostream>
#include <unordered_map>
#include <string>

int c_num, s_num;
int curr_idx, curr_num;
std::string curr_name;
std::unordered_map<std::string, std::string> map;

void ParseInput() {
	std::cin >> s_num >> c_num;
	for (int i = 0; i < c_num; i++) {
		std::cin >> curr_idx >> curr_num;
		for (int j = 0; j < curr_num; j++) {
			std::cin >> curr_name;
			auto key = map.find(curr_name);
			if (key != map.end()) key->second += " " + std::to_string(curr_idx);
			else map.insert(std::make_pair(curr_name," " + std::to_string(curr_idx)));
		}
	}
}

int main() {
	ParseInput();
	for (int i = 0; i < s_num; i++) {
		std::cin >> curr_name;
		std::cout << curr_name;
		auto key = map.find(curr_name);
		if (key != map.end())std::cout << key->second << std::endl;
		else std::cout << " 0" << std::endl;
	}	
}

解法二：手动hash + cstdio

手动hash对我来说还是比较少见的操作，唯一一次是在Jdk1.8的String源码里看到过类似的东西

#include <cstdio>
#include <vector>
#include <algorithm>

int s_num, c_num, curr_idx, curr_num, id = 0;
char curr_name[5];

const int maxn = 26 * 26 * 26 * 10 + 10;
std::vector<int> map[maxn];

int hash(char* name) {
    int id = 0;
    for (int i = 0; i < 3; i++)
        id = 26 * id + (name[i] - 'A');
    id = id * 10 + (name[3] - '0');
    return id;
}

void ParseInput() {
    scanf("%d %d", &s_num, &c_num);

    for (int i = 0; i < c_num; i++) {
        scanf("%d %d", &curr_idx, &curr_num);

        for (int j = 0; j < curr_num; j++) {
            scanf("%s", curr_name);
            id = hash(curr_name);
            map[id].push_back(curr_idx);
        }
    }
}

int main() {
    ParseInput();

    for (int i = 0; i < s_num; i++) {
        scanf("%s", curr_name);

        id = hash(curr_name);
        std::sort(map[id].begin(), map[id].end());

        printf("%s %lu", curr_name, map[id].size());

        for (int j = 0; j < map[id].size(); j++)
            printf(" %d", map[id][j]);

        printf("\n");
    }
    return 0;
}

1002 A+B for Polynomials (25分)

解法一：unordered_map

也就是哈希表，剩下的就是将输入解析到map中再遍历输出，但是由于输出顺序原因没法通过的样子…

#include <iostream>
#include <unordered_map>

std::unordered_map<float, float> map;

// Parse input
void ParseInput() {
	int num;
	float coef, exp;
	std::cin >> num;
	for (int i = 0; i < num; i++) {
		std::cin >> exp >> coef;
		auto key = map.find(exp);                   // find exp
		if (key != map.end()) key->second += coef;  // Update value
		else map.insert(std::make_pair(exp, coef)); // If not exist , insert a new node
	}
}

int main() {
	ParseInput(); // First line
	ParseInput(); // Second line

	// Output
	std::cout << map.size(); 
	for (const auto &it : map) {
		std::cout << " " << it.first << " " << it.second;
	}
	return 0;
}

解法二：数组模拟哈希表

比上面更消耗空间，如果有更多的exp的话是没法这样做的，但这里只有1000个而且这种办法可以逆序遍历

#include <iostream>
#include <iomanip>

float map[1005] = { 0 };
int size = 0;

// Parse input
void ParseInput() {
    int num, exp;
    float coef;
    std::cin >> num;
    for (int i = 0; i < num; i++) {
        std::cin >> exp >> coef;
        if (map[exp] == 0)size++;       // Count size
        map[exp] += coef;               // Update value
        if (map[exp] == 0)size--;       // If coef back to zero , delete it , or you have to transverse the map again
    }
}

int main() {
    ParseInput(); // First line
    ParseInput(); // Second line

    std::cout << size;

    for (int i = 1000; i >= 0; i--) {
        if (map[i] != 0.0)
            std::cout << " " << i << " " << std::setiosflags(std::ios::fixed) << std::setprecision(1) << map[i]; 
        // fix the format of float
    }
    return 0;
}

1059 Prime Factors (25分)

解法一: std::map

从2开始除，只要能除尽就继续，除到只剩1，基本都不会超过2000吧，记得对1特殊处理

#include<iostream>
#include<map>

int num;
std::map<long long, long long> factors;

void parseFactor(long long n) {
	int i = 2;
	while (n > 1) {
		while (n % i == 0) {
			factors[i]++;
			n /= i;
		}
		i++;
	}
}

int main() {
	std::cin >> num;
	parseFactor(num);
	if (num == 1) {
		std::cout << "1=1";
		return 0;
	}
	std::cout << num << "=";
	for (auto& i : factors) {
		if (i != *--factors.end()) {
			if (i.second == 1) std::cout << i.first << '*';
			else if (i.second > 1) std::cout << i.first << '^' << i.second << '*';
		}
		else {
			if (i.second == 1) std::cout << i.first;
			else if (i.second > 1) std::cout << i.first << '^' << i.second;
		}
	}
}

New Trick in coding

C++下的精度控制

// include others
#include <iomanip>

// main ...
std::cout << std::setiosflags(std::ios::fixed) << std::setprecision(1) << floatNumber;

Lambda遍历unordered_map

for(const auto& it : map){
    std::cout << it->first << " " << it->second << std::endl;
}

Overyam