Brush notes

2021.7.12—2021.7.14

1084 broken keyboard

For the problem of string traversal, in this example, although there is no value for finding b[10] in the IDE, there will be no problem with cout < < b[10], and cout < < B [11] will report an error

To be on the safe side, add '#' at the end of the b string

#include<iostream>
#include<algorithm>
#include<string>
#include<unordered_set>
using namespace std;

/*
7_This_is_a_test
_hs_s_a_es
*/
bool los[200];

int main()
{
	string a, b;
	cin >> a >> b;
	int cnt = 0;
	//It's possible that before the first pointer is traversed, the second pointer has been traversed, so '#' is added after the second string
	for (int i = 0, j = 0; i < a.size(); i++)
	{
		char x = toupper(a[i]), y = toupper(b[j]);
		if (x == y) {
			j++;
			if (j == 9)
				getchar();
		}
		else {
			if (!los[x]) cout << x, los[x] = true;
		}
	}
	return 0;
}

1108 average

#include<iostream>
#include<string>
using namespace std;
const int N = 1010;
int cnt;
float sum;

int main()
{
	string a[N];
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		bool flag = true;
		size_t idx;
		float t;
		try {
			t = stof(a[i], &idx);  //idx here can point to the next address of the last digit successfully converted
		}
		catch (...) {
			flag = false;
		}
		if (idx < a[i].size()) flag = false;
		if (t < -1000 || t>1000) flag = false;
		int k = a[i].find('.');
		if (k != -1 && a[i].size() - k > 3) flag = false;

		if (flag) cnt++, sum += t;
		else printf("ERROR: %s is not a legal number\n", a[i].c_str());

	}

	if (cnt > 1) printf("The average of %d numbers is %.2lf\n", cnt, sum / cnt);
	else if (cnt == 1) printf("The average of 1 number is %.2lf\n", sum);
	else puts("The average of 0 numbers is Undefined");

	return 0;
}

This problem involves many library functions

• The functions stoi(),stof() can convert string to int/float

  • They can throw exceptions when strings are illegal
  • It can contain two parameters. The second parameter &idx can bring out the next address of the last bit successfully converted

• Use try{} catch(...) The {} statement catches an exception and records it as an illegal number

  • catch(...) Catch all types of exceptions

• String type The find(x) function can find the subscript of the first X in the specified string and return it. If x is not found in the string, the return value is - 1

try catch statement in c + +

size_t

1124 microblog forwarding lucky draw

This question uses unordered_set to judge the weight

#include<iostream>
#include<algorithm>
#include<string>
#include<unordered_set>
using namespace std;
const int N = 1010;
string	name[N];

int main() {
	int m, n, s;
	cin >> m >> n >> s; 
	for (int i = 1; i <= m; i++) //Notice here that s starts from 1, so i also starts from 1
		cin >> name[i];

	unordered_set<string> hash;
	int i = s;
	while(i<=m)
	{
		if (hash.count(name[i])) i++;
		else {
			cout << name[i] << endl;
			hash.insert(name[i]);
			i += n;
		}
	}

	if (hash.empty()) puts("Keep going...");
	return 0;
}

1125 PAT unit ranking

#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<vector>
using namespace std;

struct School
{
    string name;
    int cnt;
    double sum;

    School() : cnt(0), sum(0) {}

    bool operator< (const School& t) const //Operator overload
    {
        if (sum != t.sum) return sum > t.sum;
        if (cnt != t.cnt) return cnt < t.cnt;
        return name < t.name;
    }
};

int main()
{
	int n;
    cin >> n;
    unordered_map<string, School> hash;

    while (n--)
    {
        string id, sch;
        double grade;
        cin >> id >> grade >> sch;

        //Convert all uppercase letters to lowercase letters
        for (auto& c : sch)
            c = tolower(c);

        if (id[0] == 'B') grade = grade / 1.5;
        else if (id[0] == 'T') grade = grade * 1.5;

        hash[sch].sum += grade;
        hash[sch].cnt++;
        hash[sch].name = sch;
    }

    vector<School> schools;
    for (auto item : hash) {
        item.second.sum = (int)(item.second.sum + 1e-8); //Note the second here, which refers to the second in < string, School >
        schools.push_back(item.second);
    }

    //Sort by multiple keywords
    sort(schools.begin(), schools.end());
    cout << schools.size() << endl;

    int rank = 1;
    for (int i = 0; i < schools.size(); i++)
    {
        auto s = schools[i];
        if (i && s.sum != schools[i - 1].sum) rank = i + 1;
        printf("%d %s %d %d\n", rank, s.name.c_str(), (int)s.sum, s.cnt);
    }
    return 0;
}

Notable points:

• When c + + performs division, there may be accuracy problems. For example, when / 1.5 occurs, 2.9999999 is rounded to 2

  • Solution: add the empirical value eps (generally 1e-8) after division

• Use unordered_map maps the school name to a structure

• Overloaded operator for multi keyword sorting

1153 decoding PAT admission card

1058 Hogwarts A + B

1629 number of deferred palindromes

1579 insert or merge

1484 best ranking

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<cmath>
using namespace std;
/*
	Use vector to save the scores of each subject
*/
unordered_map<string, vector<int>> grades;
vector<int> q[4]; //A:q[0] C:q[1] M:q[2] E:q[3] for ranking


//Binary search index of fraction x in array a
int get_rank(vector<int>& a, int x)
{
	int l = 0, r = a.size() - 1;
	while (l < r)
	{
		int mid = l + r + 1 >> 1;
		if (a[mid] <= x) l = mid;
		else r = mid - 1;
	}
	return a.size() - r;

}


int main()
{
	int n, m;
	cin >> n >> m;
	
	for (int i = 0; i < n; i++)
	{
		string id;
		int t[4] = { 0 };
		cin >> id;
		for (int j = 1; j < 4; j++)
		{
			cin >> t[j];
			t[0] += t[j];
		}
		t[0] = round(t[0] / 3.0);

		for (int j = 0; j < 4; j++)
		{
			q[j].push_back(t[j]);
			grades[id].push_back(t[j]);
		}

	}

	for (int i = 0; i < 4; i++)
		sort(q[i].begin(), q[i].end());


	//Processing queries
	char names[] = "ACME";
	while (m--)
	{
		string id;
		cin >> id;
		if (grades.count(id) == 0) puts("N/A");
		else
		{
			int res = n + 1;
			char c;
			//Find the best ranking by id
			for (int i = 0; i < 4; i++)
			{
				int rank = get_rank(q[i], grades[id][i]);
				if (rank < res)
				{
					res = rank;
					c = names[i];
				}
			}
			cout << res << ' ' << c << endl;
		}
	}
	return 0;
}

Main points to note:

1. This question uses unordered_ Map < string, vector < int > > mapping id to grade
2. In the case of a given score, the method of ranking
   • 1. dichotomy
   • 1. Simulation method
3. I haven't done the question of dichotomy for a long time. Here are some points to pay attention to in dichotomy:
   • If the desired subscript is the right endpoint of the left interval, use mid=(l+r+1), and the interval is divided into [l,mid] and [mid+1,r]
     If you want to get the left end point of the right interval, use mid=(l+r)/2, and the interval is divided into [l,mid-1] and [mid,r]

1499 Digital Library

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<sstream>
using namespace std;


/*It is more convenient for complex information to exist in the structure*/
struct Book {
	string id, name, author;
	set<string> keywords;
	string publisher, year;
};

int main()
{
	int n, m;
	cin >> n;
	vector<Book> books;
	while (n--)
	{
		string id, name, author;
		cin >> id;
		getchar(); //When you want to use getline, you need to read the carriage return of the previous line, otherwise you will read a carriage return
		getline(cin, name);
		getline(cin, author);
		string line;
		getline(cin, line);
		stringstream ssin(line);
		string keyword;
		set<string> keywords;
		while (ssin >> keyword)
			keywords.insert(keyword);
		string publisher, year;
		getline(cin, publisher);
		cin >> year;

		books.push_back({ id, name, author, keywords, publisher, year });

	}
	cin >> m;
	getchar();
	string line;
	while (m--)
	{
		getline(cin, line);
		cout << line << endl;
		string info = line.substr(3);
		char t = line[0];
		vector<string> res;
		if (t == '1')
		{
			for (auto& book : books)
				if (book.name == info)
					res.push_back(book.id);
		}
		else if (t == '2')
		{
			for (auto& book : books)
				if (book.author == info)
					res.push_back(book.id);
		}
		else if (t == '3')
		{
			/*Query keyword*/
			for (auto& book : books)
			{
				if (book.keywords.count(info))
					res.push_back(book.id);
			}
		}
		else if (t == '4')
		{
			for (auto& book : books)
				if(book.publisher==info)
				res.push_back(book.id);
		}
		else
		{
			for (auto& book : books)
				if(book.year==info)
				res.push_back(book.id);
		}

		if (res.empty()) puts("Not Found");
		else
		{
			sort(res.begin(), res.end());
			for (auto id : res) cout << id << endl;
		}
	}

	return 0;
	
}

difficulty

1. Input of data
   • When reading a string containing spaces, you need to use getline(cin,string)
     • When using getline(), you need to pay attention to whether the carriage return of the previous row has been read in. If not, you need to use getchar() to read the carriage return of the previous row
2. Data storage
   • Using structures to store data
   • Use set to store the keyword (it's easier to find this keyword)

1505 list sorting

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;

int n;
struct Row{
    string id,name;
    int grade;
    //Because overloading can only be overloaded once, it is not very convenient in the case of three sorting
}rows[N];

bool cmp1(Row a,Row b)
{
    return a.id<b.id;
}

bool cmp2(Row a,Row b)
{
    if(a.name!=b.name) return a.name<b.name;
    return a.id<b.id;
}

bool cmp3(Row a,Row b)
{
    if(a.grade!=b.grade) return a.grade<b.grade;
    return a.id<b.id;
}


int main()
{
    int c;
    scanf("%d%d", &n,&c);
    
    char id[10],name[10];
    for(int i=0;i<n;i++)
    {    
        int grade;
        scanf("%s%s%d",id,name,&grade);
        rows[i]={id,name,grade};
    }      
    if(c==1) sort(rows,rows+n,cmp1);
    else if(c==2) sort(rows,rows+n,cmp2);
    else if(c==3) sort(rows,rows+n,cmp3);
    
    
    for(int i=0;i<n;i++)
        printf("%s %s %d\n",rows[i].id.c_str(),rows[i].name.c_str(),rows[i].grade);
        
        
    return 0;
}

This problem is not difficult in algorithm, but it involves the efficiency between cin, cout, scanf and printf

Using cin and cout to process input and output, it is easy to timeout when the amount of input data is greater than 100000

Consider changing to scanf and printf to handle input and output

Notable points

1. If you replace scanf and printf to process input and output, you must replace all scanf and printf, otherwise the speed increase is not obvious

   • Reason: if cin and cout need to be synchronized with scanf and printf, the efficiency will be significantly reduced

2. scanf's method of reading string: introduce an intermediate array and assign a value to the string (you can't directly use the. c_str() method to read the value!!!)

3. printf output string method: use c_str() method

1523 student schedule

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
unordered_map<string, vector<int>> students;

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);

	/*unordered_map Realize the mapping of students' course selection information*/

	while (k--)
	{
		int a, b;	//There are b students in course a
		scanf("%d%d", &a, &b);

		for (int i = 0; i < b; i++)
		{
			string name;
			char temp[100];
			scanf("%s", temp);
			name = temp;
			students[name].push_back(a);
		}
	}

	while (n--)
	{
		string query;
		char temp[100];
		scanf("%s", temp);
		query=temp;
		printf("%s %d", query.c_str(), students[query].size());
		sort(students[query].begin(),students[query].end());
		for (auto c : students[query])
		{
			printf(" %d", c);
		}
		printf("\n");
	}
	return 0;
}

This question has stepped on the pit again and is used directly c_str() assigns a string. The correct approach should be to introduce an intermediate char array and assign the char array to string