PAT 1065 1066 1067 1068

主要是注意一下加法溢出的情况，不要试图使用double，因为它的精度是15~16位，不能满足精度要求，代码如下：

 1 #include<cstdio>
 2 #include<climits>
 3 #include<cmath>
 4 //double精度为15~16位，不能满足精度要求
 5 int main()
 6 {
 7     int testNum;
 8     scanf("%d",&testNum);
 9     long long MAX = LONG_LONG_MAX; //pow(2,63) - 1,
10     long long MIN = LONG_LONG_MIN; //-1*pow(2,63);
11     for(int i = 1; i <= testNum; i++)
12     {
13         long long a,b,c;
14         scanf("%lld %lld %lld", &a, &b, &c);
15 
16         if(a >= 0 && b >=0)
17         {
18             if(MAX - a >= b)
19                 goto NORMAL;
20             else
21             {
22                 printf("Case #%d: true
", i);
23                 continue;
24             }
25         }
26         else if(a < 0 && b < 0)
27         {
28             if(MIN - a <= b)
29                 goto NORMAL;
30             else
31             {
32                 printf("Case #%d: false
", i);
33                 continue;
34             }
35         }
36         else ;
37 
38 NORMAL:
39         if(a + b > c)
40             printf("Case #%d: true
", i);
41         else
42             printf("Case #%d: false
", i);
43     }
44     return 0;
45 }

View Code

pat 1066 Root of AVL Tree 本文地址

最基本的AVL树的操作，关于AVL树可以参考here 或 here，代码如下：

  1 #include<cstdio>
  2 #include<climits>
  3 #include<cmath>
  4 
  5 //operate of AVL tree
  6 
  7 inline int max2(int a, int b)
  8 {
  9     return a>b? a:b;
 10 }
 11 
 12 struct avlnode
 13 {
 14     struct avlnode *rson;
 15     struct avlnode *lson;
 16     int data;
 17     int height;
 18 };
 19 
 20 inline int height(struct avlnode *tree)
 21 {
 22     if(NULL == tree)
 23         return -1;
 24     else return tree->height;
 25 }
 26 
 27 void rotateR(struct avlnode * &root)
 28 {
 29     struct avlnode *proot = root;
 30     root = root->lson;
 31     proot->lson = root->rson;
 32     root->rson = proot;
 33     proot->height = max2(height(proot->lson), height(proot->rson)) + 1;
 34     root->height = max2(height(root->lson), height(root->rson)) + 1;
 35 }
 36 
 37 void rotateL(struct avlnode * &root)
 38 {
 39     struct avlnode * proot = root;
 40     root = root->rson;
 41     proot->rson = root->lson;
 42     root->lson = proot;
 43     proot->height = max2(height(proot->lson), height(proot->rson)) + 1;
 44     root->height = max2(height(root->lson), height(root->rson)) + 1;
 45 }
 46 
 47 void rotateRL(struct avlnode * &root)
 48 {
 49     rotateR(root->rson);
 50     rotateL(root);
 51 }
 52 
 53 void rotateLR(struct avlnode * &root)
 54 {
 55     rotateL(root->lson);
 56     rotateR(root);
 57 }
 58 
 59 void insertAVL(struct avlnode * &root, int data)
 60 {
 61     if(root == NULL)
 62     {
 63         root = new struct avlnode;
 64         root->data = data;
 65         root->lson = NULL;
 66         root->rson = NULL;
 67         root->height = 0;
 68         return;
 69     }
 70 
 71     if(data < root->data)
 72     {
 73         insertAVL(root->lson, data);
 74         if(2 == height(root->lson) - height(root->rson))
 75         {
 76             if(data < root->lson->data)
 77                 rotateR(root);
 78             else rotateLR(root);
 79         }
 80     }
 81     else
 82     {
 83         insertAVL(root->rson, data);
 84         if(-2 == height(root->lson) - height(root->rson))
 85         {
 86             if(data > root->rson->data)
 87                 rotateL(root);
 88             else
 89             {
 90                 rotateRL(root);
 91             }
 92         }
 93     }
 94     root->height = max2(height(root->lson), height(root->rson)) + 1;
 95 }
 96 
 97 int main()
 98 {
 99     int N;
100     scanf("%d", &N);
101     struct avlnode *root = NULL;
102     for(int i = 1; i <= N; i++)
103     {
104         int data;
105         scanf("%d", &data);
106         insertAVL(root,data);
107     }
108     printf("%d", root->data);
109     return 0;
110 }

View Code

pat 1067 Sort with Swap(0,*) 本文地址

首先找出不在正确位置上的数字的个数N，假设每次交换都把一个元素放到了正确的位置则至少需要N-1次交换（最后一次交换把两个元素放到了正确的位置）。

但是在交换的过程中若0被交换到了第一个位置，那么下一次交换不会把一个元素交换到正确位置，即要做一次额外的交换。因此我们要知道整个过程中0几次被交换到了第一个位置，当输入序列和排序好的序列中存在一个循环时，0就会被交换到第一个位置一次：

如0 1 2 3 4
4 0 3 2 1 该序列存在2个循环 0-4-4-1-1-0,2-3-3-2 ，0被交换到了第一个位置2次，但是最后一次是刚好把0归为，因此交换次数为N-1+(2-1)。

因此最终交换次数是：N-1+循环个数-1

考虑到一个特殊情况：当0开始就在第一个位置时，我们开始就需要把他交换到某个循环中（和某个不在正确位置的数交换），这样交换次数+1，交换后不在正确位置的元素个数增加了一个，N也需要+1，，即总的交换次数+2。

代码如下：

 1 #include<cstdio>
 2 int main()
 3 {
 4     int N,*arry;
 5     scanf("%d", &N);
 6     arry = new int[N];
 7     bool *flag = new bool[N];
 8     int swaptimes = -1;
 9     for(int i = 0; i < N; i++)
10     {
11         scanf("%d", &arry[i]);
12         if(arry[i] == i)flag[i] = true;
13         else
14         {
15             flag[i] = false;
16             swaptimes++;
17         }
18     }
19     if(swaptimes == -1)
20     {
21         printf("0");
22         return 0;
23     }
24 
25     if(flag[0] == true)
26         swaptimes += 2;
27     for(int i = 0; i < N; i++)
28     {
29         int k = arry[i];
30         if(flag[k] == false)
31         {
32             //找到一个循环
33             swaptimes++;
34             while(flag[k] == false)
35             {
36                 flag[k] = true;
37                 k = arry[k];
38             }
39         }
40 
41     }
42     printf("%d", swaptimes - 1);
43     delete []arry;
44     delete []flag;
45     return 0;
46 }

View Code

pat 1068 Find More Coins 本文地址

典型的0-1背包问题，关于0-1背包的讲解可参考Cui Tianyi大神的背包九讲。

本题动态规划方程：f[i][v] = max{ f[i-1][v], f[i-1][v-coins[i]]+coins[i] } ,f[i][v]表示前i枚硬币能拼凑出不超过v的最大金额，v代表的是一个金额，coins[i]代表第i个硬币的面额；
由于题目还要求输出最小字典序，可以先对硬币按面值递减排序，并且在程序中，当f[i-1][v] = f[i-1][v-coins[i]]+coins[i] 时，我们选择后者，因为后者倾向于选择排在后面的硬币，越选择排在后面的硬币，结果序列的字典序越小。（开始我误认为先对硬币从小到大排序，然后当f[i-1][v] = f[i-1][v-coins[i]]+coins[i] 时，选择前者也可以得到正确答案，实验证明这是错误的，因为选择前者的意思是倾向于尽量不选择大面值的硬币，但是这样并不等价于结果序列的字典序小，比如2 3 4比1 3 5 的字典序大，但是1 3 5却选择了更大的面值5）
对于最后结果序列的输出，我们用数组path[i][j]保存结果，path[i][j]=true表示凑足价格 j 时，使用了前 i 个硬币中的第 i 个，false表示没有使用，最后可以从path中逆推结果，具体见代码

代码如下：

 1 #include<cstdio>
 2 #include<algorithm>
 3 
 4 int main()
 5 {
 6     //freopen("input.txt", "r", stdin);
 7     int coinNum, needPay;
 8     scanf("%d%d", &coinNum, &needPay);
 9     int coins[coinNum+1];
10     for(int i = 1; i <= coinNum; i++)
11         scanf("%d", &coins[i]);
12     //f[i][j] 表示前 i 枚硬币能拼凑出的小于等于 j 的最大值（j 这里代表一个价格）
13     int f[coinNum+1][needPay+1];
14     //path[i][j]=true表示凑足价格j时，使用了第i个硬币，false表示没有使用
15     bool path[coinNum+1][needPay+1];
16     for(int i = 0; i <= coinNum; i++)//初始化
17         for(int j = 0; j <= needPay; j++)
18         {
19             f[i][j] = 0;
20             path[i][j] = false;
21         }
22     std::sort(coins+1, coins+coinNum+1, std::greater<int>());
23     for(int i = 1; i <= coinNum; i++)
24         for(int j = coins[i]; j <= needPay; j++)
25         {
26             if(f[i-1][j] <= f[i-1][j-coins[i]] + coins[i])
27             {
28                 f[i][j] = f[i-1][j-coins[i]] + coins[i];
29                 path[i][j] = true;
30             }
31             else
32             {
33                 f[i][j] = f[i-1][j];
34                 path[i][j] = false;
35             }
36         }
37     if(f[coinNum][needPay] != needPay)
38         printf("No Solution
");
39     else
40     {//从path中恢复解
41         int tmp = needPay, i = coinNum;
42         while(tmp > 0)
43         {
44             if(path[i][tmp] == true)
45             {
46                 printf("%d", coins[i]);
47                 tmp -= coins[i];
48                 if(tmp > 0)
49                     printf(" ");
50             }
51             i--;
52         }
53     }
54     return 0;
55 }

View Code

对于该题，对于数据规模不大时，可以用递归解法，比如问题 “1...n个硬币凑足价格p” 可以分为 “2...n个硬币凑足价格p-coin[1]” 和"2...n个硬币凑足价格p"，即分为第一个硬币选择或者不选两种情。对于结果要求最小字典序，先将硬币按面值从小到大排序，分解问题时，先求第一个硬币选择时的子问题。1068的递归代码如下，但是最后一个测试数据超时，不知道是因为代码有问题还是数据规模太大，如果大家找出了问题，请留言，谢谢！

 1 #include<cstdio>
 2 #include<algorithm>
 3 
 4 bool gatherCoinRecur(int money, int coins[], int n, int start, bool choose[])
 5 {
 6     if(money == 0)return true;
 7     else if(money < 0)return false;
 8     if(start >= n)return false;
 9     choose[start] = true;
10     if(gatherCoinRecur(money - coins[start], coins, n, start+1, choose))
11         return true;
12     choose[start] = false;
13     if(gatherCoinRecur(money, coins, n, start+1, choose))
14         return true;
15     return false;
16 }
17 
18 int main()
19 {
20     freopen("input.txt", "r", stdin);
21     int coinNum, needPay;
22     scanf("%d%d", &coinNum, &needPay);
23     int coins[coinNum];
24     bool choose[coinNum];
25     for(int i = 0; i < coinNum; i++)
26     {
27         scanf("%d", &coins[i]);
28         choose[i] = false;
29     }
30     std::sort(coins, coins+coinNum);
31     if(gatherCoinRecur(needPay, coins, coinNum, 0, choose))
32     {
33         int i = 0;
34         while(choose[i] == false)i++;
35         printf("%d", coins[i]);
36         for(i++; i < coinNum; i++)
37             if(choose[i])printf(" %d", coins[i]);
38     }
39     else printf("No Solution
");
40     return 0;
41 }

View Code