1048 Find Coins(25)

tags: [PAT, 算法, two pointers]
Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she could only use exactly two coins to pay the exact amount. Since she has as many as 10^5coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find two coins to pay for it.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive numbers: N (≤10^5, the total number of coins) and M (≤10
​3, the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers no more than 500. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the two face values V1 and V2(separated by a space) such that V1+V2=M and V1 ≤V2. If such a solution is not unique, output the one with the smallest V1
. If there is no solution, output No Solution instead.

Sample Input 1:

8 15
1 2 8 7 2 4 11 15

Sample Output 1:

4 11

Sample Input 2:

7 14
1 8 7 2 4 11 15

Sample Output 2:

No Solution

Solution:

排序后两个指针, 一个从头, 一个从尾, 向中间扫描, 两数相加是否能得到M

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int N, M, temp = 0; scanf("%d %d", &N, &M);
  vector<int> v;
  for (int i = 0; i < N; i++) {
    scanf("%d", &temp);
    v.push_back(temp);
  }

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

  int i = 0, j = N-1;
  while (i < j) {                  // case2
    if (v[i] + v[j] < M) i++;
    else if (v[i] + v[j] > M) j--;
    else if (v[i] + v[j] == M){
      printf("%d %d", v[i], v[j]);
      return 0;
    }
  }
  printf("No Solution\n");
  return 0;
}

1042 Shuffling Machine(20)

Shuffling is a procedure used to randomize a deck of playing cards. Because standard shuffling techniques are seen as weak, and in order to avoid “inside jobs” where employees collaborate with gamblers by performing inadequate shuffles, many casinos employ automatic shuffling machines. Your task is to simulate a shuffling machine.

The machine shuffles a deck of 54 cards according to a given random order and repeats for a given number of times. It is assumed that the initial status of a card deck is in the following order:

S1, S2, …, S13,
H1, H2, …, H13,
C1, C2, …, C13,
D1, D2, …, D13,
J1, J2

where “S” stands for “Spade”, “H” for “Heart”, “C” for “Club”, “D” for “Diamond”, and “J” for “Joker”. A given order is a permutation of distinct integers in [1, 54]. If the number at the i-th position is j, it means to move the card from position i to position j. For example, suppose we only have 5 cards: S3, H5, C1, D13 and J2. Given a shuffling order {4, 2, 5, 3, 1}, the result will be: J2, H5, D13, S3, C1. If we are to repeat the shuffling again, the result will be: C1, H5, S3, J2, D13.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer K (≤20) which is the number of repeat times. Then the next line contains the given order. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the shuffling results in one line. All the cards are separated by a space, and there must be no extra space at the end of the line.

Sample Input:

2
36 52 37 38 3 39 40 53 54 41 11 12 13 42 43 44 2 4 23 24 25 26 27 6 7 8 48 49 50 51 9 10 14 15 16 5 17 18 19 1 20 21 22 28 29 30 31 32 33 34 35 45 46 47

Sample Output:

S7 C11 C10 C12 S1 H7 H8 H9 D8 D9 S11 S12 S13 D10 D11 D12 S3 S4 S6 S10 H1 H2 C13 D2 D3 D4 H6 H3 D13 J1 J2 C1 C2 C3 C4 D1 S5 H5 H11 H12 C6 C7 C8 C9 S2 S8 S9 H10 D5 D6 D7 H4 H13 C5

Solution:

shuffling:洗牌
这题题目不怎么理解, 能做出来猜测占了大多数。

初始给出一个打乱次数K, 和一个order序列;

这个order有两个作用,

• 1, 代表了这张是什么牌, 根据1234..对应S1,S2,S3,S4..;
• 2, 这是一个始终不变的order, 这个位置的牌下一次就要被放到该位置order表中对应的值的位置中去。

有点抽象, 不过看数据。
只有五张牌 (不是一种特殊情况, 而是为了简化的假设)

1   2   3    4    5
S3, H5, C1, D13, J2
4   2   5    3    1
-------------------  k = 1;
1   2   3    4    5
5   2   4    1    3
J2  H5  D13  S3   C1
4   2   5    3    1
-------------------  k = 2;
1   2   3    4    5
3   2   1    5    4
C1  H5  S3   J2   D13
4   2   5    3    1
------------------- k ..
...

s3从1->4->3, 实际上pos = arr[pos].value;

定一个结点, 存放下标pos和实际元素value, 相当于链表next;这样能求出每个结点最后的pos, 然后对pos从小到大进行统一的排序。

坑点:

• 注意进位问题, 若13 / 13 = 1; 实际要需要0…13, 于是用整数部分用(i-1)/13, 余数(i-1)%13 +1
• 排序和遍历都是从1开始到54, 闭区间, 0位置不做处理.

实际代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

struct Node {
  int value;
  int pos;
};

bool cmp(Node n1, Node n2) {
  return n1.pos < n2.pos;
}

int main() {
  int K; scanf("%d", &K);
  Node arr[60];
  memset(arr, 0, sizeof(arr));
  for (int i = 1; i <= 54; i++) {
    Node node;
    node.pos = i;
    scanf("%d", &node.value);
    arr[i] = node;
  }

  for (int i = 1; i <= 54; i++) {
    int pos = i, cnt = 0;
    if (pos == arr[pos].value) continue;
    while (cnt <= K) {
      pos = arr[pos].value;
      cnt++;
    }
    arr[i].pos = pos;
  }

  sort(arr+1, arr+55, cmp);

  char chs[6] = {'S', 'H', 'C', 'D', 'J'};
  for (int i = 1; i <= 54; i++) {
    if (i != 1) printf(" ");
    int a = (arr[i].value-1) / 13,
        b = (arr[i].value-1) % 13 + 1;   // debug02
    printf("%c%d", chs[a], b);           // debug01:b+1 error
  }
  return 0;
}

1035 Password(20)

To prepare for PAT, the judge sometimes has to generate random passwords for the users. The problem is that there are always some confusing passwords since it is hard to distinguish 1 (one) from l (L in lowercase), or 0 (zero) from O (o in uppercase). One solution is to replace 1 (one) by @, 0 (zero) by %, l by L, and O by o. Now it is your job to write a program to check the accounts generated by the judge, and to help the juge modify the confusing passwords.

Input Specification:

Each input file contains one test case. Each case contains a positive integer N (≤1000), followed by N lines of accounts. Each account consists of a user name and a password, both are strings of no more than 10 characters with no space.

Output Specification:

For each test case, first print the number M of accounts that have been modified, then print in the following M lines the modified accounts info, that is, the user names and the corresponding modified passwords. The accounts must be printed in the same order as they are read in. If no account is modified, print in one line There are N accounts and no account is modified where N is the total number of accounts. However, if N is one, you must print There is 1 account and no account is modified instead.

Sample Input 1:

3
Team000002 Rlsp0dfa
Team000003 perfectpwd
Team000001 R1spOdfa

Sample Output 1:

2
Team000002 RLsp%dfa
Team000001 R@spodfa

Sample Input 2:

1
team110 abcdefg332

Sample Output 2:

There is 1 account and no account is modified

Sample Input 3:

2
team110 abcdefg222
team220 abcdefg333

Sample Output 3:

There are 2 accounts and no account is modified

Solution:

题目要求出修改密码后的信息.

• 1类分成, 没被修改的, 修改的;
• 2类没被修改的分成, 复数和单数.

把修改的字符建成unodered_map用于查找.
用struct将name和password关联, 读入password进行修改和过滤, 被修改的node放入vector;
vector.size(), N决定了属于上述哪一类。

#include <cstdio>
#include <cstring>
#include <vector>
#include <unordered_map>
using namespace std;

struct Node {
  char name[11];
  char password[11];
};

int main() {
  int N; scanf("%d", &N);
  unordered_map<char, char> mp;
  mp['1'] = '@'; mp['0'] = '%'; mp['l'] = 'L'; mp['O'] = 'o';
  vector<Node> v;
  for (int i = 0; i < N; i++) {
    Node node;
    scanf("%s %s", node.name, node.password);
    int modified = 0;
    for (int j = 0; j < strlen(node.password); j++) {
      auto it = mp.find(node.password[j]);
      if (it != mp.end()) {
        node.password[j] = it->second;
        modified = 1;
      }
    }
    if (modified) {
      v.push_back(node);
    }
  }

  if (v.size() != 0) {
    printf("%lu\n", v.size());
    for (int i = 0; i < v.size(); i++) {
      printf("%s %s\n", v[i].name, v[i].password);
    }
  } else {
    if (N == 1) {
      printf("There is 1 account and no account is modified\n");
    } else {
      printf("There are %d accounts and no account is modified\n", N);
    }
  }

  return 0;
}

1024 Palindromic Number(25)

A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers.

Non-palindromic numbers can be paired with palindromic ones via a series of operations. First, the non-palindromic number is reversed and the result is added to the original number. If the result is not a palindromic number, this is repeated until it gives a palindromic number. For example, if we start from 67, we can obtain a palindromic number in 2 steps: 67 + 76 = 143, and 143 + 341 = 484.

Given any positive integer N, you are supposed to find its paired palindromic number and the number of steps taken to find it.

Input Specification:

Each input file contains one test case. Each case consists of two positive numbers N and K, where N (≤10^10) is the initial numer and K (≤100) is the maximum number of steps. The numbers are separated by a space.

Output Specification:

For each test case, output two numbers, one in each line. The first number is the paired palindromic number of N, and the second number is the number of steps taken to find the palindromic number. If the palindromic number is not found after K steps, just output the number obtained at the Kth step and K instead.

Sample Input 1:

67 3

Sample Output 1:

484
2

Sample Input 2:

69 3

Sample Output 2:

1353
3

Solution:

实现了大整数类中的相加, 字符串转大整数, 大整数转字符串;
是否回文仍旧用string来进行判断.

坑点:

• 字符串转大整数时, 字符需要-‘0’, 转化成整数.

代码如下:

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

struct Bign {
  int d[1005];
  int len;
  Bign() {
    memset(d, 0, sizeof(d));
    len = 0;
  }
};

Bign add(Bign a, Bign b) {
  Bign ans;
  int carry = 0;
  for (int i = 0; i < a.len || i < b.len; i++) {
    int tmp = a.d[i] + b.d[i] + carry;
    ans.d[ans.len++] = tmp % 10;
    carry = tmp / 10;
  }
  if (carry) {
    ans.d[ans.len++] = carry;
  }
  return ans;
}

Bign stringToBign(string s) {
  Bign ans;
  ans.len = s.length();
  for (int i = 0; i < ans.len; i++) {
    ans.d[i] = s[ans.len-1-i]-'0';    // bug01
  }
  return ans;
}

string bignToString(Bign a) {
  string s = "";
  for (int i = a.len-1; i >= 0; i--) {
    s += to_string(a.d[i]);
  }
  return s;
}

bool is_p(string s) {
  int n = s.length();
  int i = 0, j = n-1;
  while (i <= j) {
    if (s[i] != s[j]) return false;
    i++; j--;
  }
  return true;
}

int main() {
  string s; int step_max;
  cin >> s >> step_max;
  int step = 0;
  while (!is_p(s) && step < step_max) {
    string temp_s = s;
    reverse(temp_s.begin(), temp_s.end());
    Bign a = stringToBign(s), b = stringToBign(temp_s);
    s = bignToString(add(a, b));
    step++;
  }
  cout << s << "\n" << step << endl;
  return 0;
}

1015 Reversible Primes(20)

A reversible prime in any number system is a prime whose “reverse” in that number system is also a prime. For example in the decimal system 73 is a reversible prime because its reverse 37 is also a prime.

Now given any two positive integers N (<10^5) and D (1<D≤10), you are supposed to tell if N is a reversible prime with radix D.

Input Specification:

The input file consists of several test cases. Each case occupies a line which contains two integers N and D. The input is finished by a negative N.

Output Specification:

For each test case, print in one line Yes if N is a reversible prime with radix D, or No if not.

Sample Input:

73 10
23 2
23 10
-2

Sample Output:

Yes
Yes
No

Solution:

难点不在于判断素数, 而是理解不了进制转换。
先按d进制逆转, 将逆转后的数转成10进制, 判断素数.

d进制逆转属于中间过程, 用一个数组存放.

#include <cstdio>
#include <cmath>
using namespace std;


// is_prime改进
bool is_prime(int a) {
  if (a <= 1) return false;
  int sqr =  int(sqrt(a * 1.0));
  for (int i = 2; i <= sqr; i++) {
    if (a % i == 0) {
      return false;
    }
  }
  return true;
}

int main() {
  int n, d, flag = 0;
  while (scanf("%d %d", &n, &d) != EOF) {
    if (n < 0) break;
    int ok = 0;
    if (is_prime(n)) {
      // reverse a num
      int len = 0, arr[6];
      while (n) {
        arr[len++] = n % d;
        n /= d;
      }
      for (int i = 0; i < len; i++) {
        n = n * d + arr[i];
      }
      // judge
      if (is_prime(n)) {
        ok = 1;
      }
    }

    if (flag) printf("\n");
    ok ? printf("Yes") : printf("No");
    flag = 1;
  }
  return 0;
}

再附上我原先的求素数版本, 以便警示自己.

// 原先的求素数
int is_prime(int a) {
  if (a < 2) return 0;
  if (a == 2) return 1;
  int sq = sqrt(a);
  for (int i = 2; i <= sq; i++) {
    if (a % i == 0) return 0;
  }
  return 1;
}

1058 选择题(20)

批改多选题是比较麻烦的事情，本题就请你写个程序帮助老师批改多选题，并且指出哪道题错的人最多。

输入格式：

输入在第一行给出两个正整数 N（≤ 1000）和 M（≤ 100），分别是学生人数和多选题的个数。随后 M 行，每行顺次给出一道题的满分值（不超过 5 的正整数）、选项个数（不少于 2 且不超过 5 的正整数）、正确选项个数（不超过选项个数的正整数）、所有正确选项。注意每题的选项从小写英文字母 a 开始顺次排列。各项间以 1 个空格分隔。最后 N 行，每行给出一个学生的答题情况，其每题答案格式为 (选中的选项个数 选项1 ……)，按题目顺序给出。注意：题目保证学生的答题情况是合法的，即不存在选中的选项数超过实际选项数的情况。

输出格式：

按照输入的顺序给出每个学生的得分，每个分数占一行。注意判题时只有选择全部正确才能得到该题的分数。最后一行输出错得最多的题目的错误次数和编号（题目按照输入的顺序从 1 开始编号）。如果有并列，则按编号递增顺序输出。数字间用空格分隔，行首尾不得有多余空格。如果所有题目都没有人错，则在最后一行输出 Too simple。

输入样例：

3 4
3 4 2 a c
2 5 1 b
5 3 2 b c
1 5 4 a b d e
(2 a c) (2 b d) (2 a c) (3 a b e)
(2 a c) (1 b) (2 a b) (4 a b d e)
(2 b d) (1 e) (2 b c) (4 a b c d)

输出样例：

3
6
5
2 2 3 4

Solution:

坑点:
1, 理解错题意的打印, 正确的是先打印最大错误次数, 然后依次打印题目编号, 从1开始
2, 二维数组在开的时候, 手误开小了, 题目数量一大, 就溢出错误了。

另外, 探究几种初始化的方法:

int opt[1010][10]; memset(opt, 0, sizeof(opt));   // 稳妥的办法, 但需要"string.h"
int opt[1010][10] = {0};   // 不太行
int opt[1010][10] = {};    // 可以将二维数组都初始化0

int arr[10] = {0};         // 同上, 可以将数组初始化0
vector<int> v(10);         // vector有10个元素, 均为初始值0
vector<vector<int>> v(5);  // 这样也能构造5*4的vector
··// ...
··v[i].resize(4);
··// ..

实际代码如下:

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

int main() {
  int n, m; scanf("%d %d", &n, &m);
  int hash[] = {1, 2, 4, 8, 16};
  int temp = 0, opt_num = 0, right_num = 0, opt[1010][100] = {};   // case4
  vector<int> full_score(m), right_opt(m);
  char c;
  vector<int> err_cnt(m);
  for (int i = 0; i < m; i++) {
    scanf("%d %d %d", &full_score[i], &opt_num, &right_num);
    for (int j = 0; j < right_num; j++) {
      scanf(" %c", &c);
      right_opt[i] += hash[c-'a'];
    }
  }
  for (int i = 0; i < n; i++) {
    int score = 0;
    for (int j = 0; j < m; j++) {
      getchar();
      getchar();   // '('
      scanf("%d", &temp);
      for (int k = 0; k < temp; k++) {
        scanf(" %c", &c);
        opt[i][j] += hash[c-'a'];
      }
      getchar();   // ')'
      int el = opt[i][j] ^ right_opt[j];
      if (el) {
        err_cnt[j]++;
      } else {
        score += full_score[j];
      }
    }
    printf("%d\n", score);
  }
  int max_cnt = 0;
  for (int i = 0; i < m; i++) {
    max_cnt = err_cnt[i] > max_cnt ? err_cnt[i] : max_cnt;
  }
  if (max_cnt) {
    printf("%d", max_cnt);
    for (int i = 0; i < m; i++) {
      if (err_cnt[i] == max_cnt) {
        printf(" %d", i+1);        // debug02:
      }
    }
  } else {
    printf("Too simple\n");
  }

  return 0;
}

1073 多选题常见计分法(20)

批改多选题是比较麻烦的事情，有很多不同的计分方法。有一种最常见的计分方法是：如果考生选择了部分正确选项，并且没有选择任何错误选项，则得到 50% 分数；如果考生选择了任何一个错误的选项，则不能得分。本题就请你写个程序帮助老师批改多选题，并且指出哪道题的哪个选项错的人最多。

输入格式：

输入在第一行给出两个正整数 N（≤1000）和 M（≤100），分别是学生人数和多选题的个数。随后 M 行，每行顺次给出一道题的满分值（不超过 5 的正整数）、选项个数（不少于 2 且不超过 5 的正整数）、正确选项个数（不超过选项个数的正整数）、所有正确选项。注意每题的选项从小写英文字母 a 开始顺次排列。各项间以 1 个空格分隔。最后 N 行，每行给出一个学生的答题情况，其每题答案格式为 (选中的选项个数 选项1 ……)，按题目顺序给出。注意：题目保证学生的答题情况是合法的，即不存在选中的选项数超过实际选项数的情况。

输出格式：

按照输入的顺序给出每个学生的得分，每个分数占一行，输出小数点后 1 位。最后输出错得最多的题目选项的信息，格式为：错误次数 题目编号（题目按照输入的顺序从1开始编号）-选项号。如果有并列，则每行一个选项，按题目编号递增顺序输出；再并列则按选项号递增顺序输出。行首尾不得有多余空格。如果所有题目都没有人错，则在最后一行输出 Too simple。

输入样例 1：

3 4
3 4 2 a c
2 5 1 b
5 3 2 b c
1 5 4 a b d e
(2 a c) (3 b d e) (2 a c) (3 a b e)
(2 a c) (1 b) (2 a b) (4 a b d e)
(2 b d) (1 e) (1 c) (4 a b c d)

输出样例 1：

3.5
6.0
2.5
2 2-e
2 3-a
2 3-b

输入样例 2：

2 2
3 4 2 a c
2 5 1 b
(2 a c) (1 b)
(2 a c) (1 b)

输出样例 2：

5.0
5.0
Too simple

Solution:

每个选项都对应一个二进制位,共有五位, ac对应的是10100, a对应是10000, 当这两个二进制数进行异或运算时, 结果是00100, 表明c选项有误。full_score存总分, right_opt存正确选项, 二进制分别由Hash给出是{1, 2, 4, 8, 16}
|运算用于判断出是漏选还是多选, 漏选的选择和正确选项进行|运算, 与正确选项相同.
&运算的作用判断是哪个选项出错了.

位运算技巧:

^异或运算对应位相同, 为0; 否则为1, 如下:

0 ^ 1 = 1
1 ^ 0 = 1
0 ^ 0 = 0
1 ^ 1 = 0

11100
    ^  = 11011
00111

abc = 11100
          ^   = 01110
ad  = 10010

|运算对应位有1一个1, 则1; 否则0, 如下：

0 | 1 = 1
1 | 0 = 1
0 | 0 = 0
1 | 1 = 1

11100
    ^  = 11111
00111

&运算对应位两个都位1, 则1; 否则0, 如下:

0 & 1 = 0
1 & 0 = 0
0 & 0 = 0
1 & 1 = 1

11100
    &  = 00100
00111

el      = 01100
              &  = 00000 or 0 => a不错
hash[0] = 10000

el      = 01100
              &  = 01000 or 2 => b出错
hash[0] = 01000

el      = 01100
              &  = 00100 or 4 => c出错
hash[0] = 00100

如下同理
// ..

scanf技巧:

用getchar()读掉换行’\n’,’(‘,’)’, 读字符的时候用scanf(“ %c”, &c); 新发现是scanf中读空格的技巧.

用scanf读取题目给出的N, M, K中间加括号没什么问题和技巧性可言，但在这题中, getchar()配合scanf在一个循环中处理了字符串.

实际代码:

#include <cstdio>
#include <vector>
using namespace std;

int main() {
  int temp = 0, right_num = 0, opts_num = 0, opts[1010][110] = {};
  char c;
  int N, M; scanf("%d %d", &N, &M);
  vector<int> full_score(M), right_opts(M);
  vector<vector<int> > err_cnt(M);    // 仍要初始化内层
  int hash[] = {1, 2, 4, 8, 16};
  for (int i = 0; i < M; i++) {
    scanf("%d %d %d", &full_score[i], &opts_num, &right_num);
    for (int j = 0; j < right_num; j++) {
      scanf(" %c", &c);
      right_opts[i] += hash[c-'a'];
    }
    err_cnt[i].resize(5);             // 对应初始化二维vector
  }

  for (int i = 0; i < N; i++) {
    double score = 0.0;
    for (int j = 0; j < M; j++) {
      getchar();
      getchar();  // "("
      scanf("%d", &temp);
      for (int k = 0; k < temp; k++) {
        scanf(" %c", &c);
        opts[i][j] += hash[c - 'a'];
      }
      getchar();  // ")"      // debug01
      int el = opts[i][j] ^ right_opts[j];

      if (el) {
        if ((opts[i][j] | right_opts[j]) == right_opts[j]) {
          score += 0.5*full_score[j];
        }

        if (el & hash[0]) err_cnt[j][0]++;   // a
        if (el & hash[1]) err_cnt[j][1]++;   // b
        if (el & hash[2]) err_cnt[j][2]++;   // c
        if (el & hash[3]) err_cnt[j][3]++;   // d
        if (el & hash[4]) err_cnt[j][4]++;   // e
      } else {
        score += full_score[j];
      }
    }
    printf("%.1lf\n", score);
  }

  int max_cnt = 0;
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < 5; j++) {
      max_cnt = err_cnt[i][j] > max_cnt ? err_cnt[i][j] : max_cnt;
    }
  }

  if (max_cnt) {
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < 5; j++) {
        if (err_cnt[i][j] == max_cnt) {
          printf("%d %d-%c\n", max_cnt, i+1, j+'a');
        }
      }
    }
  } else {
    printf("Too simple\n");
  }

  return 0;
}

1025 反转链表(25)

给定一个常数 K 以及一个单链表 L，请编写程序将 L 中每 K 个结点反转。例如：给定 L 为 1→2→3→4→5→6，K 为 3，则输出应该为 3→2→1→6→5→4；如果 K 为 4，则输出应该为 4→3→2→1→5→6，即最后不到 K 个元素不反转。

输入格式：

每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤10^5)、以及正整数 K (≤N)，即要求反转的子链结点的个数。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。

接下来有 N 行，每行格式为：
Address Data Next
其中 Address 是结点地址，Data 是该结点保存的整数数据，Next 是下一结点的地址。

输出格式：

对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。

输入样例：

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

输出样例：

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

Solution:

map+node存放结点, 再按链表顺序添加到vector中, 对vector每个局部进行reverse, 之后打印每个结点信息, 打印之前需要更新next

通过,新链表的总长N和给定结点间隔K, 能求出”链表”如果哪些位置反转.

for (int i = 0; i < v.size() / K; i++) {
  reverse(v.begin() + i*k, v.begin() + (i+1)*k);
}

reverse函数的用法:

vector<int> v = {1, 2, 3, 4, 5, 6};
reverse(v.begin(), v.begin() + 3);
for (int i = 0; i < v.size(); i++) {
    printf("%d ", v[i]);
}
printf("\n");
// 3 2 1 4 5 6

坑点:
1, 如果测试给出多余的结点的话， 新链表的总长不为N了; 我之前认为我用vector存放了node, v.size()是绝对安全的, 是, 明枪易躲, 暗箭难防, 对于这题最重要的reverse会出错; 如果不改好这个, case6通不过.

2, unordered_map<char*, Node> mp; 将node存入之后, 用字符数组作为键值是无法查找到的。如果要用字符串作为key值的话, map定义时用string不用char*, 暂时就这么理解

#include <cstdio>
#include <cstring>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;


struct Node {
  char addr[6];
  int data;
  char next[6];
};

int main() {
  char head[6]; int N, K;
  scanf("%s %d %d", head, &N, &K);
  // unordered_map<char*, Node> mp;             // error, why?
  unordered_map<string, Node> mp;
  for (int i = 0; i < N; i++) {
    Node node;
    scanf("%s %d %s", node.addr, &node.data, node.next);
    mp[node.addr] = node;
  }

  vector<Node> v;
  char pNode[6]; strcpy(pNode, head);
  while (strcmp(pNode, "-1") != 0) {
    v.push_back(mp[pNode]);
    strcpy(pNode, mp[pNode].next);              // debug01
  }
  for (int i = 0; i < v.size()/K; i++) {        // case6
    reverse(v.begin()+i*K, v.begin()+i*K+K);    // 哨兵元素, i从0开始
  }
  int flag = 0;
  for (int i = 0; i < v.size(); i++) {
    if (i != v.size()-1) {
      strcpy(v[i].next, v[i+1].addr);
    } else {
      strcpy(v[i].next, "-1");
    }
    if (flag) printf("\n");
    printf("%s %d %s", v[i].addr, v[i].data, v[i].next);
    flag = 1;
  }

  return 0;
}

/*
case6:
00100 4 2
00100 1 12309
12309 2 23333
77777 7 22222
23333 3 -1
*/

1075 链表元素分类(25)

给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而 [0, K] 区间内的元素都排在大于 K 的元素前面。但每一类内部元素的顺序是不能改变的。例如：给定链表为 18→7→-4→0→5→-6→10→11→-2，K 为 10，则输出应该为 -4→-6→-2→7→0→5→10→18→11。

输入格式：

每个输入包含一个测试用例。每个测试用例第 1 行给出：第 1 个结点的地址；结点总个数，即正整数N (≤10
​5)；以及正整数K (≤10^3)。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。

接下来有 N 行，每行格式为：

Address Data Next

其中 Address 是结点地址；Data 是该结点保存的数据，为 [−10^5,10^5] 区间内的整数；Next 是下一结点的地址。题目保证给出的链表不为空。

输出格式：

对每个测试用例，按链表从头到尾的顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例：

00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218

输出样例：

33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1

Solution:

链表的特性用map+node来解决. 一个key对应node的addr值, 可以访问到这个node.next值.

这题的主要问题是, 将所有负值元素都排在非负值元素之前, [0,K]排在中间, 最后排大于K的元素, 且他们的结点要保持原本的顺序.

思路是在每个结点node中, rank来确定是属于哪一类, 0为负, 1为[0,K], 2为大于K的元素; node_p保存结点在原链表中的顺序。

对所有结点进行排序, 也就是说, rank小的肯定被排在前面, 相同rank的比谁的node_p更小, node_p小说明出现的早, 也被排在前面。
这样写一个cmp后对vector进行sort就可以实现目标.

最后在打印的之前, 还要修改每个结点的下一个结点, 也就是v[i].next; 实际上就是v[i+1].addr; 但是最后一个除外 它是”-1”;

坑点:

• 可能会出现多余的结点, 因此将有效结点放入v中后, 用v.size()不用N, 否则case4凉凉。
• 用string来进行大部分操作, 会导致case5超时, 因此换成char *;

换成字符数组后, 赋值用strcpy(str1, str2); 比较用strcmp(str1, str2), 这些都需要

实际代码:

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

struct Node {
  int node_p;
  int rank;
  char addr[6];
  int data;
  char next[6];
};

bool cmp(Node n1, Node n2) {
  if (n1.rank != n2.rank) return n1.rank < n2.rank;
  return n1.node_p < n2.node_p;
}

int main() {
  char head[6]; int N, K;
  scanf("%s %d %d", head, &N, &K);
  unordered_map<string, Node> mp;
  for (int i = 0; i < N; i++) {
    Node node;
    scanf("%s %d %s", node.addr, &node.data, node.next);
    node.rank = node.data < 0 ? 0 : node.data <= K ? 1 : 2;
    mp[node.addr] = node;
  }

  vector<Node> v;
  char pNode[6];
  strcpy(pNode, head);
  int cnt = 0;
  while (strcmp(pNode, "-1") != 0) {
    auto it = mp.find(pNode);
    it->second.node_p = cnt++;
    v.push_back(it->second);
    strcpy(pNode, it->second.next);
  }

  sort(v.begin(), v.end(), cmp);
  int flag = 0;
  for (int i = 0; i < v.size(); i++) {    // case4, 不能用N, why?
    if (i != v.size()-1) {
      strcpy(v[i].next, v[i+1].addr);
    } else {
      strcpy(v[i].next, "-1");
    }
    if (flag) printf("\n");
    printf("%s %d %s", v[i].addr, v[i].data, v[i].next);
    flag = 1;
  }
  return 0;
}

1011 World Cup Betting(20)

With the 2010 FIFA World Cup running, football fans the world over were becoming increasingly excited as the best players from the best teams doing battles for the World Cup trophy in South Africa. Similarly, football betting fans were putting their money where their mouths were, by laying all manner of World Cup bets.

Chinese Football Lottery provided a “Triple Winning” game. The rule of winning was simple: first select any three of the games. Then for each selected game, bet on one of the three possible results – namely W for win, T for tie, and L for lose. There was an odd assigned to each result. The winner’s odd would be the product of the three odds times 65%.

For example, 3 games’ odds are given as the following:

 W    T    L
1.1  2.5  1.7
1.2  3.1  1.6
4.1  1.2  1.1

To obtain the maximum profit, one must buy W for the 3rd game, T for the 2nd game, and T for the 1st game. If each bet takes 2 yuans, then the maximum profit would be (4.1×3.1×2.5×65%−1)×2=39.31 yuans (accurate up to 2 decimal places).

Input Specification:

Each input file contains one test case. Each case contains the betting information of 3 games. Each game occupies a line with three distinct odds corresponding to W, T and L.

Output Specification:

For each test case, print in one line the best bet of each game, and the maximum profit accurate up to 2 decimal places. The characters and the number must be separated by one space.

Sample Input:

1.1 2.5 1.7
1.2 3.1 1.6
4.1 1.2 1.1

Sample Output:

T T W 39.31

Solution:

比较得到三个double中最大的那个值的序号, 0,1,2对应W, T, L;
对赔率进行累乘, 最后(sum*0.65-1)*2是所要的结果, 注意精确到小数点后两位

// 比较三个值的one line写法
int max = a > b ? a > c ? a : c : b > c ? b : c;

#include <cstdio>

char chs[3] = {'W', 'T', 'L'};
int main() {
  int flag = 0;
  double sum = 1;
  for (int i = 0; i < 3; i++) {
    double arr[3];
    scanf("%lf %lf %lf", &arr[0], &arr[1], &arr[2]);

    int pos = arr[0] > arr[1] ? arr[0] > arr[2] ? 0 : 2 : arr[1] > arr[2] ? 1 : 2;
    if (flag) printf(" ");
    printf("%c", chs[pos]);
    flag = 1;

    sum *= arr[pos];
  }
  sum = (sum * 0.65 - 1) * 2;
  printf(" %.2lf", sum);
  return 0;
}