1002 A+B for Polynomials （25 分）

PAT-Advanced Level
C/C++, PAT, PTA

1002 A+B for Polynomials （25 分）

This time, you are supposed to find A+B where A and B are two polynomials.

Input Specification

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial:
K N​1​​ a​N​1​​ ​​ N​2​​ a​N​2​​ ​​ … N​K​​ a​N​K
where K is the number of nonzero terms in the polynomial, N​i​​ and a​N​i​​ (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10，0≤N
​K​​ <⋯<N​2​​ <N​1​​ ≤1000.

Output Specification

​​
​​ For each test case you should output the sum of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate to 1 decimal place.
​​

Sample Input

1
2
2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output

1
3 2 1.5 1 2.9 0 3.2

​​

题目理解

​​
​​给两个多项式，然后计算相加的结果。第一个数是非零项的个数，然后是指数 系数 指数 系数。
​​

AC代码

​​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
​​//
//  main.cpp
//  1002 A+B for Polynomials （25 分）
//
//  Created by ARCHer's MAC on 2018/10/7.
//  Copyright © 2018年 ARCHer's MAC. All rights reserved.
//

#include <iostream>
#include <cstdio>
#define MAXN 1005
using namespace std;

double cases[MAXN];
int main(int argc, const char * argv[]) {
    // insert code here...
    int noZero1, noZero2, sum = 0;
    scanf("%d", &noZero1);
    for (int i = 0; i < noZero1; i++) {
        int zs; scanf("%d", &zs);
        double xs; scanf("%lf", &xs);
        cases[zs] += xs;
    }
    scanf("%d", &noZero2);
    for (int i = 0; i < noZero2; i++) {
        int zs; scanf("%d", &zs);
        double xs; scanf("%lf", &xs);
        cases[zs] += xs;
    }
    for (int i = 0; i < MAXN; i++) {
        if (cases[i] != 0.0) sum++;
    }
    printf("%d", sum);
    if (sum == 0) return 0;
    for (int i = MAXN - 1; i >= 0; i--) {
        if (cases[i] != 0.0) printf(" %d %.1lf", i, cases[i]);
    }
    return 0;
}

​​

部署Flask项目

Flask
Django, Flask, Gunicorn, Python, 部署

部署Flask项目

说两句

Python-Flask一直以来是快速开发的好方法，方便简单的调试和安全性让我欲罢不能。但是，在部署上，却不像PHP、C#、Java等语言那样简单的部署。经过Google，终于找到了一个比较简单而又不错的部署方法。

准备工具

VPS或是独立服务器，使用Centos或是Ubuntu。
SSH工具（我用的FinalShell）

部署步骤

1.安装容器

这里省略了flask及其依赖库的安装。

1
pip install gunicorn

注意！我是用的conda，所以pip对应的是python3.6的pip。

2.上传项目

将项目上传到服务器中。并进入项目目录中。此时当前目录中有manage.py

1
cd /project/app

3.运行容器

1
gunicorn manage:app -p manage.pid -b 127.0.0.1:10086 -D
  • -p 是为了将manage的pid进程保存在文件中，方便我们关闭。
  • -b 是设置容器运行ip，127.0.0.1只能本机运行，如果要远程访问设置成0.0.0.0
  • 之所以127.0.0.1是为了加一层反向代理（我使用的nginx），保障并发。

4.反向代理

我安装了服务器管理面板。
提供一下nginx的配置文件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Redirect www.example.com to example.com
server {
        server_name www.example.com;
        rewrite ^ http://example.com/ permanent;
}

# Handle requests to example.com on port 80
server {
        listen 80;
        server_name example.com;

        # Handle all locations
        location / {
                # Pass the request to Gunicorn
                proxy_pass http://127.0.0.1:10086;

                # Set some HTTP headers so that our app knows where the request really came from
                proxy_set_header Host $host;
                proxy_set_header X-Real-IP $remote_addr;
                proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
        }
}

5.部署完成

此时可以打开浏览器访问啦。

【随时更新】深入理解二叉树

algorithm
bintree, bst, 二叉树, 搜索二叉树

深入理解二叉树

这里以C++的代码（不用STL）进行演示。C语言的话引用改为指针即可。

准备工作

引入所需的头文件，重定义一些数据结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;

struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

关于后两个typedef的意义何在，我也没法解释，有增加代码可读性一说，也有使用封装思想一说。

二叉树的遍历

二叉树的遍历分四种：

  • 前序遍历 （PreorderTraversal）
  • 后序遍历 （PostorderTraversal）
  • 中序遍历 （InorderTraversal）
  • 层序遍历 （LevelorderTraversal）

至于什么是前中后序遍历，和离散数学中的前中后序遍历是一个意思。如果忘记参考百度。层序遍历就是按照从左到右，从上倒下的顺序遍历。

前序遍历

使用了递归的思想。

1
2
3
4
5
6
7
8
void PreorderTraversal (BinTree T) {
    if (T == NULL) return;
    else {
        printf(" %d", T -> Data);
        PreorderTraversal(T -> Left);
        PreorderTraversal(T -> Right);
    }
}

后序遍历

1
2
3
4
5
6
7
8
void PostorderTraversal (BinTree T) {
    if (T == NULL) return;
    else {
        PostorderTraversal(T -> Left);
        PostorderTraversal(T -> Right);
        printf(" %d", T -> Data);
    }
}

中序遍历

1
2
3
4
5
6
7
8
void InorderTraversal (BinTree T) {
    if (T == NULL) return;
    else {
        InorderTraversal(T -> Left);
        printf(" %d", T -> Data);
        InorderTraversal(T -> Right);
    }
}

层序遍历

运用了队列的思想，其中 if (T) 一定不要漏掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
void LevelorderTraversal (BinTree T) {
    Position Queue[1000000];//开大了会出错哦
    int Front = 0, Tail = 0;
    if (T) Queue[Tail++] = T;
    
    while (Front != Tail) {
        Position temp = Queue[Front];
        Front++;
        printf(" %d", temp -> Data);
        if (temp -> Left != NULL) Queue[Tail++] = temp -> Left;
        if (temp -> Right != NULL) Queue[Tail++] = temp -> Right;
    }
}

二叉搜索树

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树。
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
它的左右子树也分别为二叉搜索树。

创建并插入二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//创建节点
BinTree CreateTreeNode (ElementType data) {
    BinTree node = (BinTree)malloc(sizeof(struct TNode));
    node -> Data = data;
    node -> Left = NULL;
    node -> Right = NULL;
    return node;
}

//二叉搜索树的插入
void insertBsTree (BinTree &T, ElementType data) {
    if (T == NULL) {
        T = CreateTreeNode(data);
        cout << "insert succeed" << endl;
        return;
    }
    if (T -> Data > data) insertBsTree(T -> Left, data);
    else if (T -> Data < data) insertBsTree(T -> Right, data);
    else {
        cout << "insert failed" << endl;
        return;
    }
}

//创建树
BinTree CreateBinTree () {
    BinTree root = NULL;
    //为了方便后面，新建一个二叉搜索树（BST）-> 左子树小于根 右子树大于根
    //      7
    //     / \
    //    5   8
    //   / \   \
    //  4   6   9
    insertBsTree(root, 7);
    insertBsTree(root, 5);
    insertBsTree(root, 8);
    insertBsTree(root, 4);
    insertBsTree(root, 6);
    insertBsTree(root, 9);
    return root;
}

二叉搜索树的查找

循序渐进，由易到难，查找还是比较清晰明朗的。

1
2
3
4
5
6
7
8
9
10
11
12
13
//二叉搜索树的查找
void findBsTreeNode (BinTree T, int data) {
    while (T != NULL) {
        if (T -> Data == data) {
            cout << "Find the Node!" << endl;
            return;
        } else {
            if (T -> Data > data) T = T -> Left;
            else T = T -> Right;
        }
    }
    cout << "Can not find the node!" << endl;
}

二叉搜索树的删除

这里就是二叉搜索树的难点。分4种情况：

  • 要删除的结点无子结点
  • 要删除的结点只有左子结点
  • 要删除的结点只有右子结点
  • 要删除的结点有左、右子结点

解决方案：

  • 直接删除该结点
  • 删除该结点且使被删除节点的双亲结点指向被删除节点的左子结点
  • 删除该结点且使被删除节点的双亲结点指向被删除结点的右子结点
  • 在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，在来处理该结点的

对于实际操作，第一种情况可以并入到第二第三种。看代码可以结合注释进行理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//二叉搜索树的删除
void delBsTreeNode (BinTree &T, int data) {
    BinTree cur = T;
    BinTree Parent = T;
    BinTree DelNode = NULL;
    while (cur) {
        //寻找到要删除的节点
        if (cur -> Data > data) {
            Parent = cur;
            cur = cur -> Left;
        } else if(cur -> Data < data) {
            Parent = cur;
            cur = cur -> Right;
        } else {
            //找到了要删除的节点
            DelNode = cur;
            if (DelNode -> Left == NULL) {
                //左子节点为空
                if (Parent -> Left == cur) Parent -> Left = cur -> Right;
                else if (Parent -> Right == cur) Parent -> Right = cur -> Right;
                else if (Parent == cur) T = Parent -> Right;
            } else if (DelNode -> Right == NULL) {
                //右子节点为空
                if (Parent -> Left == cur) Parent -> Left = cur -> Left;
                else if (Parent -> Right == cur) Parent -> Right = cur -> Left;
                else if (Parent == cur) T = Parent -> Left;
            } else {
                //左右子节点均不为空
                BinTree temp = cur -> Right;
                while (temp) {
                    Parent = temp;
                    temp = temp -> Left;
                }
                
                DelNode = temp;
                cur -> Data = temp -> Data;
                
                if (Parent -> Left == temp)
                    Parent-> Left = temp -> Right;
                else
                    Parent-> Right = temp -> Right;
            }
            //释放节点
            free(DelNode);
            DelNode = NULL;
            cout << "Delete succeed" << endl;
            return;
        }
    }
    cout << "Delete failed" << endl;
    return;
}

对于遍历和查找删除的测试

把所有情况测试一遍

1
2
3
4
5
6
7
8
9
10
int main(int argc, const char * argv[]) {
    BinTree root = CreateBinTree();
    LevelorderTraversal(root);
    cout << endl;
    findBsTreeNode(root, 9);
    findBsTreeNode(root, 11);
    delBsTreeNode(root, 4);
    LevelorderTraversal(root);
    return 0;
}

运行结果如下：

1
2
3
4
5
6
7
8
9
10
11
insert succeed
insert succeed
insert succeed
insert succeed
insert succeed
insert succeed
 7 5 8 4 6 9
Find the Node!
Can not find the node!
Delete succeed
 7 5 8 6 9

正在学习，未完待续

写给自己，写给我的下一级

随笔杂文
大学, 感悟, 日常, 经验

一年之感 写个自己 写给下一级

回忆

  还记得一年前自己考完高考的时候，特别的激动，心想终于离开了这个是非之地。当时对人生根本就没有什么规划，不知道程序设计，不知道C语言，不知道PAT，不知道递归，不知道数论，甚至不知道自己能不能学计算机。倒不是因为我不喜欢计算机，相反我特别喜欢。是因为，我的分数不足以去一个计算机还说的过去的学校。由于是第一年改革的报考方式，我与前三个志愿以几十分的差距失之交臂，于是乎——青大选择了我，我也选择了青大。
  尽管，软外的录取的分数比我考的分数高了20多分，但是，我并不感觉我是亏的，也没有什么遗憾。相反，到现在我感觉我是十分幸运的。大概原因有二：高考我努力过了；今年的录取分已经超过了去年我考的分。我这里并没有幸灾乐祸的意思，我这是感慨我自己是幸运的。因为，大学的选择可能改变了我的人生轨迹，我认识了好兄弟，见识了好老师，学到了新技术，参加了实验室……可以说是咸鱼翻身。所以，如果你也考到了软外，无论你以什么样的心情和姿态，没考好保底被录取、超常发挥、正常发挥等等，我都希望你能够以谦虚、虔诚的姿态进入这个专业。虽然分数只有525，但是，里面真的有很多大牛，有很多值得学习的地方。
  一年过的好快，这个感慨应该很多人都有。当然，现在的我再也不是一年前坐在破旧的教室中复习到12点的我了。

生活之感

  青岛大学，四个字的名字，给人一种很正式的感觉（毕竟和清华就差了一个音）。我是本地人，当我报道的时候才发现青岛居然有个这么破，破的不能再破的校区了，破的连个正门都没有，地上的砖都破破烂烂的，楼里楼外都很旧，楼里的课桌仿佛都是高中的那种用过好几届的那种，好吧事实上就是一个高职学校改的。尽管这样，我到现在才知道，我们住的14号楼是全青大除了留学生宿舍最大最宽敞的宿舍了。
  说到生活上的感悟，我认为最重要的就是团结。我们宿舍有时候会到4点才睡，并不是因为我们在打游戏，而是在“促膝长谈”，一起聊各种各样的事情，聊人，聊事，聊人生…… 我想，没有比我们宿舍更团结的团体了吧。
  我们不回因为什么小事而计较，诸如垃圾袋、卫生纸这些东西，大家一起用就好了，自己吃点亏又有什么呢？一个宿舍的团结我感觉太重要了，这也使得我们这一年里特别的快乐，在宿舍里特别的无拘无束。当然，不是所有宿舍都和我们宿舍一样，打架或是不和而退宿的也不在少数。所以，宿舍团结是我生活中可能最大的感悟，可能对毕业以后的工作态度，也会有很大的影响。
  嗯，还有可能就要说说尾卫生了，在青岛大学，宿舍卫生真的是特别特别重要，你高数考个80-90都不如人家考个70，宿舍平常满分的同学成绩高。尽管这可能是不公平的，但是，我们得适应这种不公平，我们宿舍就吃了这个亏，最后别的宿舍9分我们才0.8分，多考几十分才能拿到这分差呀。

学习之感

做个未完待续，有时间继续更。至于学习，可以说完全的靠自学。当然我指的是专业知识，高数什么的跟着老师学还是很靠谱的。就拿基础学科C语言来举个例子，老师上课完全都是读PPT，一个学期就憋出个链表的项目。至于指针什么的精华所在，根本就不会给你细讲。
  因此，自学就变得异常的重要，衡量一个大学的好坏，老师应该只是占小部分的原因，而学生的学习能力才是占一大部分的原因。
  到底应该如何学习？（专业相关知识）至少大一一年我做过很多尝试，尝试不同的方法，立过各种Flag，有实现的也有没实现的。到了现在，我总结出的方法就是，学什么都可以，只要是专业相关的，只要在学就可以了。比如说你喜欢PHP，而学校大一的课程并没有PHP，你完全可以在课余的时间泡网课，比如网易云课堂、幕课等，自己撸完PHP的原生课程。而我就是用原生的PHP写了一套简单的博客系统，虽然很简陋。这种学习经历让我知道自己实际上不喜欢PHP，PHP也不适合自己，就把经历投入到了其他的地方。你可能会觉得这种学习很占用时间，但是，这样往往会使自己找到真正适合自己的目标。适合自己的目标往往是最难找到的，没有目标的大学注定是碌碌无为的。
  游戏和学习冲突吗？不冲突，可以说根本不冲突。相反真正的游戏高手往往也是学习高手，毕竟貌似全班只有我上过王者（农药），而我这里并不是说自己是高手，只是说，学习和游戏并不是势不两立的东西，毕竟我还有充足的时间打篮球。所以，我希望这一级的新生有个精彩的大一生活。（毕竟分比去年高好多）
  对于想在计算机方面有所学术的，我还是有一些建议的：

  • 加入实验室，学习基础，学习算法；
  • 多买书，多看书，《C程序设计语言》、《啊哈，算法》、《C Prime Plus》、《挑战算法竞赛》等买回来看看绝对不会吃亏；
  • 刷刷PTA（pintia.cn)，争取在暑假就能刷过半，大一的上学期之前刷完乙级；
  • 对自己狠一点，熬夜虽然不提倡，但是有时候熬夜确实很重要；
  • 建立自己的博客，经济状况好的可以自己买VPS搭建，不想投入太多的就用Hexo、CSDN、博客园等；
  • 注册自己的Github，并且上传一些自己的写的不错的代码，可以是一个小算法，也可以是一个小项目；
  • 多与大牛一起，多向大牛请教；
  • 一些竞赛还是不要错过，毕竟大一的时间比较充裕；
  • 此处省略1w条

罗列了这么多，虽然自己也没完全做到，但确实个人的一些总结、教训得来的。

为人之感

  其实不想写这个感悟的，因为写出来可能会得罪很多的人。但是我还是想写出来，因为上大学前我父母就教导我，让我到了大学的时候当个班长或是班委。到了竞选的时候，为了不辜负父母也就参加了，大概是因为代码能力还不错的缘故得票数居然不低，但因为我选择的是不可调剂（额我的性格就是这样子），就没走上”官路“。不过并没有什么失望，反而现在还很庆幸，有更多时间用来学习，更多的时间丰富自己的专业知识。而且，我们的班长也十分的负责人（对我也很照顾），一起打球也特别开心。However，我不希望下一级想要一心学知识的你加入班委，原因有很多，当然最大的原因就是时间，还有一些原因在这里不能多说。不过，你要是成为了班委以后，一定要认真负责班级的事物，但绝对不能耽误代码。等以后到了社会，谁管你是不是班长，是不是团支书，阿里不会因为你是班委就多瞅一眼你的简历，腾讯也不会因为你是班长而对你特殊关照。
  说说为人处事吧，我的个人还是很喜欢帮助别人的，有人找我帮什么忙，我都会尽量去帮助他们。并不是说我自我感觉良好，为人处事做的很完美。相反，很多时候，自己的言行不是很到位，甚至可能伤害过他人。不论男生女生，都应该友好的相处，记得投票优秀团员的时候，有不少（我们班一共12个女生）女生投了票给我（我才不会告诉你怎么知道的），能得到她们的信赖和肯定，心里还是特别开心的（逃。

最后的话

  额额额额，别嫌我话多呀，都是肺腑之言。之前一直觉得青大不好，现在感觉青大挺好的，毕竟也算是自己的一个家。如果你有什么问题想要问我，可以加我的QQ，emmm找不到？翻到最底下就找到啦～

集训复习-栈

algorithm
C, C++, prehappy, stack, 栈

好久没更新了，今天来总结复习一下栈。

如何描述栈？

栈其实可以理解为一个细口的桶（比如盛羽毛球的球桶），放的东西必须先进先出，与队列正好相反。

举个例子

我们有一个栈 {} 现在他是空的。
现在我要将一个5压入栈(push) ，就成了{5}。
接着压入一个3，就成了{5, 3}。
现在我要弹出栈，只能先弹出3， -> {5} 后，才能弹出3 -> {}。

其实就是涉及到了两个操作push()和pop()，即压入和弹出。

应用到实例

大家都知道我们平常的写法都是中缀表达式，即a + b。有中缀自然就有前缀和后缀，今天的例子就是后缀表达式（逆波兰表达式）

C++为我们封装好了stack类型，我们可以引入stack直接使用。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//
//  main.cpp
//  stack
//
//  Created by ARCHer's MAC on 2018/7/30.
//  Copyright © 2018年 ARCHer's MAC. All rights reserved.
//

#include <iostream>
#include <stack>
#include <cstdio>
using namespace std;

int main(int argc, const char * argv[]) {
    //create a stack named s
    stack<int> s;
    //now -> {}
    char c;
    //read the c input
    while (scanf("%c", &c) != EOF) {
        if (c >= '0' && c <= '9') s.push(c - '0');
        //add
        else if (c == '+') {
            int a = s.top();
            s.pop();
            int b = s.top();
            s.pop();
            s.push(a + b);
        } else if (c == '-') {
            //sub
            int a = s.top();
            s.pop();
            int b = s.top();
            s.pop();
            s.push(b - a);
        } else if (c == '*') {
            //mul
            int a = s.top();
            s.pop();
            int b = s.top();
            s.pop();
            s.push(a * b);
        }
    }
    cout << s.top() << endl;
    return 0;
}

1001 A+B Format (20)

PAT-Advanced Level
C, C++, PAT, PTA

1001 A+B Format (20)

题目

Calculate a + b and output the sum in standard format – that is, the digits must be separated into groups of three by commas (unless there are less than four digits).

输入

Each input file contains one test case. Each case contains a pair of integers a and b where -1000000 <= a, b <= 1000000. The numbers are separated by a space.

输出

For each test case, you should output the sum of a and b in one line. The sum must be written in the standard format.

输入样例

-1000000 9

输出样例

-999,991

题目分析

大体意思是按照一定格式输出a+b的值。从最后一位到第一位每三个数带一个“，”。
这个方法可能有很多，我的方法是：

  • 负数先输出 “-” 然后取绝对值。
  • 取长度
  • 输出直到长度能被3整除
  • 然后循环每当长度被3整除，就输出“，”。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//
//  main.cpp
//  1001
//
//  Created by ARCHer's MAC on 2018/7/26.
//  Copyright © 2018年 ARCHer's MAC. All rights reserved.
//

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

int getlen(int a) {
    if (a == 0) return 1;
    int len = 0;
    while (a != 0) {
        a /= 10;
        len++;
    }
    return len;
}
int gethead(int a, int b) {
    while (a / (int)pow(10, b) != 0) a /= 10;
    return a % 10;
}
int main(int argc, const char * argv[]) {
    int a, b;
    cin >> a >> b;
    int c = a + b;
    if (c < 0) cout << "-";
    c = abs(c);
    int len = getlen(c);
    int i = 1;
    while (len % 3 != 0) {
        cout << gethead(c, i);
        i++;
        len--;
        if (len % 3 == 0 && len != 0) cout << ",";
    }
    for (; len > 0; i++) {
        cout << gethead(c, i);
        len--;
        if (len % 3 == 0 && len != 0) cout << ",";
    }
    cout << "\n";
    return 0;
}

The Balance 扩展欧几里德算法

欧几里德
C, C++, algorithm, 扩展欧几里德

The Balance (POJ)

题目

Ms. Iyo Kiffa-Australis has a balance and only two kinds of weights to measure a dose of medicine. For example, to measure 200mg of aspirin using 300mg weights and 700mg weights, she can put one 700mg weight on the side of the medicine and three 300mg weights on the opposite side (Figure 1). Although she could put four 300mg weights on the medicine side and two 700mg weights on the other (Figure 2), she would not choose this solution because it is less convenient to use more weights.
You are asked to help her by calculating how many weights are required.

题目图片

输入

The input is a sequence of datasets. A dataset is a line containing three positive integers a, b, and d separated by a space. The following relations hold: a != b, a <= 10000, b <= 10000, and d <= 50000. You may assume that it is possible to measure d mg using a combination of a mg and b mg weights. In other words, you need not consider “no solution” cases.
The end of the input is indicated by a line containing three zeros separated by a space. It is not a dataset.

输出

The output should be composed of lines, each corresponding to an input dataset (a, b, d). An output line should contain two nonnegative integers x and y separated by a space. They should satisfy the following three conditions.

  • You can measure dmg using x many amg weights and y many bmg weights.
  • The total number of weights (x + y) is the smallest among those pairs of nonnegative integers satisfying the previous condition.
  • The total mass of weights (ax + by) is the smallest among those pairs of nonnegative integers satisfying the previous two conditions.

No extra characters (e.g. extra spaces) should appear in the output.

样例输入

700 300 200
500 200 300
500 200 500
275 110 330
275 110 385
648 375 4002
3 1 10000
0 0 0

样例输出

1 3
1 1
1 0
0 3
1 1
49 74
3333 1

分析

最近刚刚学了扩展欧几里德算法，谷老师讲的真的是好棒呀。有不会的都会给我耐心讲解。

  • 本题首先是使用 ex_gcd ( ) 求出 gcd 和一个解。
  • 然后求出 x 的最小正整数。
  • 根据x求出y
  • 使用上述方法求b和a的扩展欧几里德x1 和 y1
  • 将第一个 x 和 y 与 x1 和 y1 做比较，留之和较小的，输出。

注意的点

  • 第二种情况是 ay1 + bx1 = ? 所以要先输出 y1 在输出 x1。
  • x = x % (b / gcd)是求最小整数解，不要搞错。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//
//  main.cpp
//  The Balance
//
//  Created by ARCHer's MAC on 2018/7/24.
//  Copyright © 2018年 ARCHer's MAC. All rights reserved.
//

#include <iostream>
using namespace std;

int getabs(int a){
    if (a < 0) {
        return -1 * a;
    }else return a;
}

int ex_gcd(int a, int b, int &x, int &y){
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    } else {
        int gcd = ex_gcd(b, a % b, x, y);
        int temp = x;
        x = y;
        y = temp - a / b * y;
        return gcd;
    }
}

void mid (int a, int b, int d, int &g, int &x, int &y){
    g = ex_gcd(a, b, x, y);
    x *= d / g;
    int tmp = b / g;
    x = (x % tmp + tmp) % tmp;
    y = getabs((a * x - d) / b);
}
int main(int argc, const char * argv[]) {
    int a, b, d;
    while (1) {
        cin >> a >> b >> d;
        if (a == 0 & b == 0 & d == 0) {
            break;
        }
        int x, y, x1, y1, g;
        mid(a, b, d, g, x, y);
        mid(b, a, d, g, x1, y1);
        if (x + y > x1 + y1) {
            cout << y1 << " " << x1 << endl;
        } else cout << x << " " << y << endl;
        
    }
    return 0;
}

Hexo插入图片

Hexo
Coding, Hexo, Hexo插件, blog

Hexo 插入图片

安装插件

1
npm install hexo-asset-image --save

_config.yml配置

打开博客的配置文件_config.yml，将其中的 post_asset_folder: 改为 true

生成文章

然后按照markdown的方式添加图片即可。

图片测试

测试图片