柳婼の blog – 第198页 – 我不管，反正我最萌～

1067. Sort with Swap(0,*) (25)-PAT甲级真题（贪心算法）

Given any permutation of the numbers {0, 1, 2,…, N-1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:
Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}
Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.
Input Specification:
Each input file contains one test case, which gives a positive N (<=105) followed by a permutation sequence of {0, 1, …, N-1}. All the numbers in a line are separated by a space.
Output Specification:
For each case, simply print in a line the minimum number of swaps need to sort the given permutation.

Sample Input:
10 3 5 7 2 6 4 9 0 8 1
Sample Output:
9
题目大意：给出一个n个数的序列，数字为0~n-1的乱序，每次用两两交换的方式而且只能用0和另一个数交换，使序列变成有序的，问最少需要多少步骤。
分析：1.0号为哨兵，用哨兵与其他数字交换，使其他数字回到有序的位置（最后有序时所处的位置），则排序完成
2.a[t] = i; 表示t数字当前正在占着哪一个位置。（如果想实时监测每个数字的位置，可以用 b 数组{b[a[i]] = i } 缓存一下数据，输出查看的）
3.依次遍历每个位置i，如果当前位置不是与之对应的数字，那么我们让这哨兵来去该数执行操作回到正确位置
4.数字如何被哨兵执行操作回到序的位置：
如果哨兵此时不在自己有序的位置上，那就，先让哨兵去让他占的那个位置上的真正应该放的数字回到此位置，即交换哨兵和此数字，我们swap(a[0],a[a0])，直到哨兵在交换的过程中回到了自己的有序位置。字词再次检查该位置是不是应该放的数字（别的数字回到有序位置的时候即哨兵执行操作的过程中，有可能让此位置该有的数字回到位置）。如果此位置不是当前数字，那哨兵和他交换swap(a[0],a[i])，就是让他先去哨兵的有序位置待一会，等下一轮操作，哨兵会把他交换回来的。如果此位置已经是该数字了，那就什么都不做。
5.当到达最后一个位置时候，两种情况 1）。如果第一个数字和最后一个数字都在自己的有序位置那ok~ 2）.哨兵和最后一个数字互相占着对方的位置，那最后一个数字就是哨兵，交换一次后，哨兵在交换后的位置等待，就是已经回到自己的有序位置，此时排序也是完成的。此过程包括在4里面了，怕你们不理解，单独说一下～

#include <iostream>
using namespace std;
int main() {
    int n, t, cnt = 0, a[100010];
    cin >> n;
    for(int i = 0; i < n; i++){
    	cin >> t;
    	a[t] = i;
    }
    for(int i = 1; i < n; i++) {
        if(i != a[i]) {
            while(a[0] != 0) {
                swap(a[0],a[a[0]]);
                cnt++;
            }
            if(i != a[i]) {
                swap(a[0],a[i]);
                cnt++;
            }
        }
    }
    cout << cnt;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, t, cnt = 0, a[100010];

cin >> n;

for(int i = 0; i < n; i++){

cin >> t;

a[t] = i;

}

for(int i = 1; i < n; i++) {

if(i != a[i]) {

while(a[0] != 0) {

swap(a[0],a[a[0]]);

cnt++;

}

if(i != a[i]) {

swap(a[0],a[i]);

cnt++;

}

cout << cnt;

return 0;

}

1113. Integer Set Partition (25)-PAT甲级真题

Given a set of N (> 1) positive integers, you are supposed to partition them into two disjoint sets A1 and A2 of n1 and n2 numbers, respectively. Let S1 and S2 denote the sums of all the numbers in A1 and A2, respectively. You are supposed to make the partition so that |n1 – n2| is minimized first, and then |S1 – S2| is maximized.

Input Specification:

Each input file contains one test case. For each case, the first line gives an integer N (2 <= N <= 105), and then N positive integers follow in the next line, separated by spaces. It is guaranteed that all the integers and their sum are less than 231.

Output Specification:

For each case, print in a line two numbers: |n1 – n2| and |S1 – S2|, separated by exactly one space.

Sample Input 1:
10
23 8 10 99 46 2333 46 1 666 555
Sample Output 1:
0 3611
Sample Input 2:
13
110 79 218 69 3721 100 29 135 2 6 13 5188 85
Sample Output 2:
1 9359

题目大意：要求把一个集合分成两个不相交的集合，使得这两个集合的元素个数相差最小的前提下，两个集合的总和之差最大
分析：先把集合内n个元素排序，计算前n/2个元素的总和，然后用总的总和sum – 2 * halfsum即为 |S1 – S2|。
|n1 – n2|就是n % 2的结果，奇数为1，偶数为0。（总和sum的值其实可以在输入的时候就累加得到啦～）

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n, sum = 0, halfsum = 0;
    scanf("%d", &n);
    vector<int> v(n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
        sum += v[i];
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < n / 2; i++)
        halfsum += v[i];
    printf("%d %d", n % 2, sum - 2 * halfsum);
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main() {

int n, sum = 0, halfsum = 0;

scanf("%d", &n);

vector<int> v(n);

for(int i = 0; i < n; i++) {

scanf("%d", &v[i]);

sum += v[i];

}

sort(v.begin(), v.end());

for(int i = 0; i < n / 2; i++)

halfsum += v[i];

printf("%d %d", n % 2, sum - 2 * halfsum);

return 0;

}

1078. Hashing (25)-PAT甲级真题（二次方探查法）

The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be “H(key) = key % TSize” where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions.

Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive numbers: MSize (<=104) and N (<=MSize) which are the user-defined table size and the number of input numbers, respectively. Then N distinct positive integers are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the corresponding positions (index starts from 0) of the input numbers in one line. All the numbers in a line are separated by a space, and there must be no extra space at the end of the line. In case it is impossible to insert the number, print “-” instead.

Sample Input:
4 4
10 6 4 15
Sample Output:
0 1 4 –

题目大意：给出散列表长和要插入的元素，将这些元素按照读入的顺序插入散列表中，其中散列函数为h(key) = key % TSize，解决冲突采用只向正向增加的二次方探查法。如果题中给出的TSize不是素数，就取第一个比TSize大的素数作为TSize
分析：先解决size是否为素数，不是素数就要重新赋值的问题
然后根据二次方探查法：
– 如果hashTable里面key % size的下标对应的hashTable为false,说明这个下标没有被使用过，直接输出。否则step步长从1加到size-1，一次次尝试是否能使index = (key + step * step) % size;所对应的位置没有元素，如果都没有找到就输出“-”，否则就输出这个找到的元素的位置～
– 注意是(key + step * step) % size 而不是(key % size + step * step)

#include <iostream>
using namespace std;
int size, n, hashTable[10100];
bool isprime(int num) {
    if(num == 1) return false;
    for(int i = 2; i * i <= num; i++)
        if(num % i == 0) return false;
    return true;
}
void insert(int key) {
    for(int step = 0; step < size; step++) {
        int index = (key + step * step) % size;
        if(hashTable[index] == 0) {
            hashTable[index] = 1;
            cout << index % size;
            return ;
        }
    }
    cout << '-';
}
int main() {
    cin >> size >> n;
    while(!isprime(size)) size++;
    for(int i = 0; i < n; i++) {
        int key;
        cin >> key;
        if(i != 0) cout << ' ';
        insert(key);
    }
    return 0;
}

#include <iostream>

using namespace std;

int size, n, hashTable[10100];

bool isprime(int num) {

if(num == 1) return false;

for(int i = 2; i * i <= num; i++)

if(num % i == 0) return false;

return true;

}

void insert(int key) {

for(int step = 0; step < size; step++) {

int index = (key + step * step) % size;

if(hashTable[index] == 0) {

hashTable[index] = 1;

cout << index % size;

return ;

}

cout << '-';

}

int main() {

cin >> size >> n;

while(!isprime(size)) size++;

for(int i = 0; i < n; i++) {

int key;

cin >> key;

if(i != 0) cout << ' ';

insert(key);

}

return 0;

}

1022. Digital Library (30)-PAT甲级真题（map映射）

A Digital Library contains millions of books, stored according to their titles, authors, key words of their abstracts, publishers, and published years. Each book is assigned an unique 7-digit number as its ID. Given any query from a reader, you are supposed to output the resulting books, sorted in increasing order of their ID’s.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=10000) which is the total number of books. Then N blocks follow, each contains the information of a book in 6 lines:

Line #1: the 7-digit ID number;
Line #2: the book title — a string of no more than 80 characters;
Line #3: the author — a string of no more than 80 characters;
Line #4: the key words — each word is a string of no more than 10 characters without any white space, and the keywords are separated by exactly one space;
Line #5: the publisher — a string of no more than 80 characters;
Line #6: the published year — a 4-digit number which is in the range [1000, 3000].
It is assumed that each book belongs to one author only, and contains no more than 5 key words; there are no more than 1000 distinct key words in total; and there are no more than 1000 distinct publishers.

After the book information, there is a line containing a positive integer M (<=1000) which is the number of user’s search queries. Then M lines follow, each in one of the formats shown below:

1: a book title
2: name of an author
3: a key word
4: name of a publisher
5: a 4-digit number representing the year
Output Specification:

For each query, first print the original query in a line, then output the resulting book ID’s in increasing order, each occupying a line. If no book is found, print “Not Found” instead.

Sample Input:
3
1111111
The Testing Book
Yue Chen
test code debug sort keywords
ZUCS Print
2011
3333333
Another Testing Book
Yue Chen
test code sort keywords
ZUCS Print2
2012
2222222
The Testing Book
CYLL
keywords debug book
ZUCS Print2
2011
6
1: The Testing Book
2: Yue Chen
3: keywords
4: ZUCS Print
5: 2011
3: blablabla
Sample Output:
1: The Testing Book
1111111
2222222
2: Yue Chen
1111111
3333333
3: keywords
1111111
2222222
3333333
4: ZUCS Print
1111111
5: 2011
1111111
2222222
3: blablabla
Not Found

题目大意：模拟数字图书馆的查询功能。会给出n本书的信息，以及m个需要查询的命令，数字标号对应相应的命令，数字编号后面的字符串是查询的搜索词，要求输出这行命令以及输出满足条件的书的id，如果一个都没有找到，输出Not Found

分析：1、对除了id之外的其他信息都建立一个map<string, set>，把相应的id插入对应搜索词的map的集合里面，形成一个信息对应一个集合，集合里面是复合条件的书的id

2、因为对于输入的关键词（可以重复，算是书本对应的tag标签吧～）没有给定关键词的个数，可以使用while(cin >> s)并且判断c = getchar()，c是否等于\n，如果是再退出循环～

3、建立query，通过传参的形式可以将不同的map名称统一化，先要判断map.find()和m.end()是否相等，如果不等再去遍历整个map，输出所有满足条件的id，如果相等就说明不存在这个搜索词对应的id，那么就要输出Not Found～

4、传参一定要用引用，否则最后一组数据可能会超时

#include <iostream>
#include <map>
#include <set>
using namespace std;
map<string, set<int> > title, author, key, pub, year;
void query(map<string, set<int> > &m, string &str) {
    if(m.find(str) != m.end()) {
        for(auto it = m[str].begin(); it != m[str].end(); it++)
            printf("%07d\n", *it);
    } else
        cout << "Not Found\n";
}
int main() {
    int n, m, id, num;
    scanf("%d", &n);
    string ttitle, tauthor, tkey, tpub, tyear;
    for(int i = 0; i < n; i++) {
        scanf("%d\n", &id);
        getline(cin, ttitle);
        title[ttitle].insert(id);
        getline(cin, tauthor);
        author[tauthor].insert(id);
        while(cin >> tkey) {
            key[tkey].insert(id);
            char c = getchar();
            if(c == '\n') break;
        }
        getline(cin, tpub);
        pub[tpub].insert(id);
        getline(cin, tyear);
        year[tyear].insert(id);
    }
    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        scanf("%d: ", &num);
        string temp;
        getline(cin, temp);
        cout << num << ": " << temp << "\n";
        if(num == 1) query(title, temp);
        else if(num == 2) query(author, temp);
        else if(num == 3) query(key, temp);
        else if(num == 4) query(pub,temp);
        else if(num ==5) query(year, temp);
    }
    return 0;
}

#include <iostream>

#include <map>

#include <set>

using namespace std;

map<string, set<int> > title, author, key, pub, year;

void query(map<string, set<int> > &m, string &str) {

if(m.find(str) != m.end()) {

for(auto it = m[str].begin(); it != m[str].end(); it++)

printf("%07d\n", *it);

} else

cout << "Not Found\n";

}

int main() {

int n, m, id, num;

scanf("%d", &n);

string ttitle, tauthor, tkey, tpub, tyear;

for(int i = 0; i < n; i++) {

scanf("%d\n", &id);

getline(cin, ttitle);

title[ttitle].insert(id);

getline(cin, tauthor);

author[tauthor].insert(id);

while(cin >> tkey) {

key[tkey].insert(id);

char c = getchar();

if(c == '\n') break;

}

getline(cin, tpub);

pub[tpub].insert(id);

getline(cin, tyear);

year[tyear].insert(id);

}

scanf("%d", &m);

for(int i = 0; i < m; i++) {

scanf("%d: ", &num);

string temp;

getline(cin, temp);

cout << num << ": " << temp << "\n";

if(num == 1) query(title, temp);

else if(num == 2) query(author, temp);

else if(num == 3) query(key, temp);

else if(num == 4) query(pub,temp);

else if(num ==5) query(year, temp);

}

return 0;

}

1060. Are They Equal (25)-PAT甲级真题（科学计数法）

If a machine can save only 3 significant digits, the float numbers 12300 and 12358.9 are considered equal since they are both saved as 0.123*105 with simple chopping. Now given the number of significant digits on a machine and two float numbers, you are supposed to tell if they are treated equal in that machine.

Input Specification:

Each input file contains one test case which gives three numbers N, A and B, where N (<100) is the number of significant digits, and A and B are the two float numbers to be compared. Each float number is non-negative, no greater than 10100, and that its total digit number is less than 100.

Output Specification:

For each test case, print in a line “YES” if the two numbers are treated equal, and then the number in the standard form “0.d1…dN*10^k” (d1>0 unless the number is 0); or “NO” if they are not treated equal, and then the two numbers in their standard form. All the terms must be separated by a space, with no extra space at the end of a line.

Note: Simple chopping is assumed without rounding.

Sample Input 1:
3 12300 12358.9
Sample Output 1:
YES 0.123*10^5
Sample Input 2:
3 120 128
Sample Output 2:
NO 0.120*10^3 0.128*10^3

题目大意：给出两个数，问将它们写成保留N位小数的科学计数法后是否相等。如果相等，输出YES，输出他们的科学记数法表示方法。如果不相等输出NO，分别输出他们的科学计数法
分析：
1. cnta 和 cntb 通过扫描字符串得到小数点所在的下标（初始化cnta cntb为字符串长度，即下标为strlen(str））
2. 考虑到可能前面有多余的零，用 p 和 q 通过扫描字符串使 p q 开始于第一个非0（且非小数点）处的下标
3. 如果cnta >= p ，说明小数点在第一个开始的非0数的下标的右边，那么科学计数法的指数为cnta – p ; 否则应该为cnta – p + 1; 字符串b同理。
4. 如果 p 和 q 等于字符串长度，说明字符串是 0，此时直接把 cnta（或者cntb）置为0，因为对于0来说乘以几次方都是相等的，如果不置为0可能会出现两个0比较导致判断为它们不相等
5. indexa = 0开始给新的A数组赋值，共赋值n位除去小数点外的正常数字，从p的下标开始。如果p大于等于strlen，说明字符串遍历完毕后依旧没能满足需要的位数，此时需要在A数组后面补上0直到满足n位数字。indexb同理，产生新的B数组
6. 判断A和B是否相等，且cnta和cntb是否相等。如果相等，说明他们用科学计数法表示后是相同的，输出YES，否则输出NO，同时输出正确的科学计数法
注意：
– 10的0次方和1次方都要写。
– 题目中说，无需四舍五入。
– 数组开大点，虽然只有100位，但是很有可能前面的0很多导致根本不止100位。一开始开的110，几乎没有AC的任何测试点。。后来开了10000就AC了~

#include <iostream>
#include <cstring>
using namespace std;
int main() {
    int n, p = 0, q = 0;
    char a[10000], b[10000], A[10000], B[10000];
    scanf("%d%s%s", &n, a, b);
    int cnta = strlen(a), cntb = strlen(b);
    for(int i = 0; i < strlen(a); i++) {
        if(a[i] == '.') {
            cnta = i;
            break;
        }
    }
    for(int i = 0; i < strlen(b); i++) {
        if(b[i] == '.') {
            cntb = i;
            break;
        }
    }
    int indexa = 0, indexb = 0;
    while(a[p] == '0' || a[p] == '.') p++;
    while(b[q] == '0' || b[q] == '.') q++;
    if(cnta >= p)
        cnta = cnta - p;
    else
        cnta = cnta - p + 1;
    if(cntb >= q)
        cntb = cntb - q;
    else
        cntb = cntb - q + 1;
    if(p == strlen(a))
        cnta = 0;
    if(q == strlen(b))
        cntb = 0;
    while(indexa < n) {
        if(a[p] != '.' && p < strlen(a))
            A[indexa++] = a[p];
        else if(p >= strlen(a))
            A[indexa++] = '0';
        p++;
    }
    while(indexb < n) {
        if(b[q] != '.' && q < strlen(b))
            B[indexb++] = b[q];
        else if(q >= strlen(b))
            B[indexb++] = '0';
        q++;
    }
    if(strcmp(A, B) == 0 && cnta == cntb)
        printf("YES 0.%s*10^%d", A, cnta);
    else
        printf("NO 0.%s*10^%d 0.%s*10^%d" , A, cnta, B, cntb);
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

int n, p = 0, q = 0;

char a[10000], b[10000], A[10000], B[10000];

scanf("%d%s%s", &n, a, b);

int cnta = strlen(a), cntb = strlen(b);

for(int i = 0; i < strlen(a); i++) {

if(a[i] == '.') {

cnta = i;

break;

}

for(int i = 0; i < strlen(b); i++) {

if(b[i] == '.') {

cntb = i;

break;

}

int indexa = 0, indexb = 0;

while(a[p] == '0' || a[p] == '.') p++;

while(b[q] == '0' || b[q] == '.') q++;

if(cnta >= p)

cnta = cnta - p;

else

cnta = cnta - p + 1;

if(cntb >= q)

cntb = cntb - q;

else

cntb = cntb - q + 1;

if(p == strlen(a))

cnta = 0;

if(q == strlen(b))

cntb = 0;

while(indexa < n) {

if(a[p] != '.' && p < strlen(a))

A[indexa++] = a[p];

else if(p >= strlen(a))

A[indexa++] = '0';

p++;

}

while(indexb < n) {

if(b[q] != '.' && q < strlen(b))

B[indexb++] = b[q];

else if(q >= strlen(b))

B[indexb++] = '0';

q++;

}

if(strcmp(A, B) == 0 && cnta == cntb)

printf("YES 0.%s*10^%d", A, cnta);

else

printf("NO 0.%s*10^%d 0.%s*10^%d" , A, cnta, B, cntb);

return 0;

}

【C++】用sort函数产生的段错误问题

sort函数的cmp必须按照规定来写，即必须只是 > 或者 <

比如:
return a > b;
return a < b;

而不能是 <= 或者 >= ，（实际上等于号加了也是毫无意义，sort是不稳定的排序），否则可能会出现段错误