I've had a good time these days. I had a good time with my family and felt super bored when I was ready to go back to school. After all the updated dramas were finished, I picked a few topics that could not form a group to pass the time. I'm going to set foot on the bullet train back to school in Nanjing in the afternoon.
catalogue
1039 Course List for Student (25 points)
1040 Longest Symmetric String (25 points)
1039 Course List for Student (25 points)
Zhejiang University has 40000 students and provides 2500 courses. Now given the student name lists of all the courses, you are supposed to output the registered course list for each student who comes for a query.
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers: N (≤40,000), the number of students who look for their course lists, and K (≤2,500), the total number of courses. Then the student name lists are given for the courses (numbered from 1 to K) in the following format: for each course i, first the course index i and the number of registered students 
(≤200) are given in a line. Then in the next line, student names are given. A student name consists of 3 capital English letters plus a one-digit number. Finally the last line contains the N names of students who come for a query. All the names and numbers in a line are separated by a space.
Output Specification:
For each test case, print your results in N lines. Each line corresponds to one student, in the following format: first print the student's name, then the total number of registered courses of that student, and finally the indices of the courses in increasing order. The query results must be printed in the same order as input. All the data in a line must be separated by a space, with no extra space at the end of the line.
Sample Input:
11 5 4 7 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1 1 4 ANN0 BOB5 JAY9 LOR6 2 7 ANN0 BOB5 FRA8 JAY9 JOE4 KAT3 LOR6 3 1 BOB5 5 9 AMY7 ANN0 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1 ZOE1 ANN0 BOB5 JOE4 JAY9 FRA8 DON2 AMY7 KAT3 LOR6 NON9
Sample Output:
ZOE1 2 4 5 ANN0 3 1 2 5 BOB5 5 1 2 3 4 5 JOE4 1 2 JAY9 4 1 2 4 5 FRA8 3 2 4 5 DON2 2 4 5 AMY7 1 5 KAT3 3 2 4 5 LOR6 4 1 2 4 5 NON9 0
This problem is not A problem as long as you are familiar with the map data structure!
[code of this question]
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int N, K;
cin >> N >> K;
string* query = new string[N];
string* name;
map<string,vector<int>> choose;
for (int i = 0; i < K; i++)
{
int index,N_;
cin >> index >> N_;
name = new string[N_];
for (int j = 0; j < N_; j++)
{
cin >> name[j];
if (choose.find(name[j]) != choose.end())
choose.find(name[j])->second.push_back(index);
else {
vector<int> c;
c.push_back(index);
choose.insert(pair<string, vector<int>>(name[j], c));
}
}
}
for (int i = 0; i < N; i++)
{
cin >> query[i];
cout << query[i] << " ";
if (choose.find(query[i]) != choose.end()) {
vector<int> c = choose.find(query[i])->second;
cout << c.size();
sort(c.begin(), c.end());
for (int j = 0; j < c.size(); j++)
cout << " " << c[j];
cout << endl;
}
else
cout << 0 << endl;
}
return 0;
}1040 Longest Symmetric String (25 points)
Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given Is PAT&TAP symmetric?, the longest symmetric sub-string is s PAT&TAP s, hence you must output 11.
Input Specification:
Each input file contains one test case which gives a non-empty string of length no more than 1000.
Output Specification:
For each test case, simply print the maximum length in a line.
Sample Input:
Is PAT&TAP symmetric?
Sample Output:
11
The essence of this question: find the largest palindrome substring.
First of all, my thinking is to think about recursive search from large to small (longestSymmetricSubstr function), but it's expected t. Then I consider starting from the two forms of palindromes, and I don't know what the boss's standard answer is. First, let's talk about the idea of A drop I came up with later.
The length of palindrome substring is no more than odd and even. For example, the odd number is 32123, and the even number is 321123. This time, it will be searched from small to large. When traversing the string, take it as the symmetry center of palindrome substring for each character (even number corresponds to the right one of the middle two numbers), so that the comparison can be ended when both sides are unequal, The time complexity of the algorithm should be reduced (the results are in line with expectations). For the even length palindrome substring, the whole string should be processed separately, which is a case of palindrome (test point 3). Pay attention to the plus boundary processing!
[code of this question]
#include<iostream>
#include<vector>
using namespace std;
int longestSymmetricSubstr(vector<char>, int, int);
int lSSubstr(vector<char>);
int main()
{
char c;
vector<char> str;
c = getchar();
while (c != '\n') {
str.push_back(c);
c = getchar();
}
//cout << longestSymmetricSubstr(str, 0, str.size() - 1);
cout << lSSubstr(str);
return 0;
}
int lSSubstr(vector<char> str)
{
int L = 1;
for (int i = 0; i < str.size(); i++) {
int temp = min(i, int(str.size() - 1 - i));
int j = 1;
int k1 = 0, k2 = 0;
int l1 = 0, l2 = 0;
for (j = 1; j <= temp; j++) {
if (!k1) {//There is a symmetry center str[i], i.e. odd term
if (str[i - j] != str[i + j])
k1 = 1;
else
l1++;
}
if (!k2) {//There is no symmetry center, that is, the even term is expanded by str[i-1],str[i]
if (str[i - j] != str[i - 1 + j])
k2 = 1;
else
l2++;
}
if (k1 && k2)
break;
}
if (str.size() % 2 == 0 && i == str.size() / 2 && str[0] == str[str.size() - 1])//Test point 3 (omitted in the case of no center of symmetry)
l2++;
L = max(L, 2 * l1 + 1);
L = max(L, 2 * l2);
}
if (str[str.size()-1] == str[str.size() - 2])//There is no center of symmetry
L = max(L, 2);
return L;
}
int longestSymmetricSubstr(vector<char> str, int left, int right)//Recursion timed out too much
{
if (left > right || left < 0 || right > str.size() - 1)
return 0;
for (int i = 0; i <= (left + right) / 2 - left; i++)
if (str[left + i] != str[right - i]) {
return max(longestSymmetricSubstr(str, left + i, right - i - 1), longestSymmetricSubstr(str, left + i + 1, right - i));
}
return right - left + 1;
}1041 Be Unique (20 points)
Being unique is so important to people on Mars that even their lottery is designed in a unique way. The rule of winning is simple: one bets on a number chosen from [1,
]. The first one who bets on a unique number wins. For example, if there are 7 people betting on { 5 31 5 88 67 88 17 }, then the second one who bets on 31 wins.
Input Specification:
Each input file contains one test case. Each case contains a line which begins with a positive integer N (≤
) and then followed by N bets. The numbers are separated by a space.
Output Specification:
For each test case, print the winning number in a line. If there is no winner, print None instead.
Sample Input 1:
7 5 31 5 88 67 88 17
Sample Output 1:
31
Sample Input 2:
5 888 666 666 888 888
Sample Output 2:
None
The score of this question is the lowest in this blog (the corresponding difficulty should be the lowest). It is indeed the one I spent the longest time on. I have been thinking about complexity. I have been trying these kinds: ① map data structure. I found that the map is orderly, no longer the order of input, and failed; ② vector data structure + count function of algorithm library, test point 4 5 timeout, failure; ③ vector data structure + visit array tag + count function of algorithm library. Test point 4 timed out and failed; ④unordered_map data structure. As a result, the PAT compiler does not support it and fails; ⑤ Have a try, because the question limits the given number ≤Therefore, I directly opened an int array to store the occurrence times of these numbers. As a result, I couldn't think of how to find the first unique in the order of input. I compromised to the help blog and found that it was a clever but common practice to use the array to save the number of input as an index. I didn't think it was successful because of less questions.
[code of this question]
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<unordered_map>
using namespace std;
int main()
{
int n;
cin >> n;
int* t = new int[n];
int m[10001] = { 0 };
for (int i = 0; i < n; i++)
{
cin >> t[i];
m[t[i]]++;
}
int i;
for (i = 0; i < n; i++)
if (m[t[i]] == 1)
{
cout << t[i];
break;
}
if (i == n)cout << "None";
return 0;
}
/*
map<int,int> m;
for (int i = 0; i < n; i++)
{
cin >> t;
if (m.find(t) != m.end())
m.find(t)->second = m.find(t)->second + 1;
else
m.insert(pair<int, int>(t, 1));
}
map<int, int>::iterator i;
for (i = m.begin(); i != m.end(); i++)
if (i->second == 1) {
cout << i->first; break;
}
if (i == m.end())cout << "None";
*/
/*
for (i = 0; i < map.size(); i++)//The last two test points timed out
if (count(map.begin(), map.end(), map[i]) == 1)
{
cout << map[i];
break;
}
*/
/*
vector<int> map;
bool* vis = new bool[n];
for (int i = 0; i < n; i++)
{
cin >> t;
map.push_back(t);
vis[i] = false;
}
int i;
for (i = 0; i < map.size(); i++) {//The fourth test point timed out
int key = 0;
if (!vis[i])
for (int j = 0; j < map.size(); j++)
if (i != j && map[i] == map[j])
{
map[j] = true; key = 1; break;
}
if (!key) { cout << map[i]; break; }
}
if(i == map.size())
cout << "None";
*/
/*
unordered_map<int, int> m;//c++0x/c++11 The standard is unordered_map incorporated into std standard
for (int i = 0; i < n; i++)
{
cin >> t;
if (m.find(t) != m.end())
m.find(t)->second = m.find(t)->second + 1;
else
m.insert(pair<int, int>(t, 1));
}
unordered_map<int, int>::iterator i;
for (i = m.begin(); i != m.end(); i++)
if (i->second == 1) {
cout << i->first; break;
}
if (i == m.end())
cout << "None";
*/
/*
vector<int> m;
vector<int> vis;//Run timeout
for (int i = 0; i < n; i++)
{
cin >> t;
if (count(m.begin(), m.end(), t) == 0) {
m.push_back(t);
vis.push_back(1);
}
else {
vis[find(m.begin(), m.end(), t) -m.begin()]++;
}
}
int i;
for (i = 0; i < vis.size(); i++)
if (vis[i] == 1)
{
cout << m[i];
break;
}
if (i == vis.size())cout << "None";
*/that's all, happy start of school. Although I'm not looking forward to the winter school, it's also important to go back to school and prepare for the guarantee and research! We should work harder in the new semester. Xiaohe wishes you all the best!