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

[Java] 1001. A+B Format (20)-PAT甲级

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).

Input
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.

Output
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.

Sample Input
-1000000 9
Sample Output
-999,991

题目大意：计算A+B的和，然后以每三位加一个”,”的格式输出。

PS：感谢github用户@fs19910227提供的pull request～

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] split = reader.readLine().split(" ");
        Integer x = Integer.valueOf(split[0]) + Integer.valueOf(split[1]);
        char[] chars = x.toString().toCharArray();
        int modOffset = chars.length % 3;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '-') {
                System.out.print('-');
                continue;
            }
            System.out.print(chars[i] - 48);
            if (i == chars.length - 1) {
                System.out.println();
            } else if ((i + 1) % 3 == modOffset) {
                System.out.print(',');
            }
        }
    }
}

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class Main {

public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

String[] split = reader.readLine().split(" ");

Integer x = Integer.valueOf(split[0]) + Integer.valueOf(split[1]);

char[] chars = x.toString().toCharArray();

int modOffset = chars.length % 3;

for (int i = 0; i < chars.length; i++) {

if (chars[i] == '-') {

System.out.print('-');

continue;

}

System.out.print(chars[i] - 48);

if (i == chars.length - 1) {

System.out.println();

} else if ((i + 1) % 3 == modOffset) {

System.out.print(',');

}

[Java] 1001. 害死人不偿命的(3n+1)猜想 (15)-PAT乙级

1001. 害死人不偿命的(3n+1)猜想 (15)
卡拉兹(Callatz)猜想：
对任何一个自然数n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把(3n+1)砍掉一半。这样一直反复砍下去，最后一定在某一步得到n=1。卡拉兹在1950年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证(3n+1)，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展……
我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过1000的正整数n，简单地数一下，需要多少步（砍几下）才能得到n=1？
输入格式：
每个测试输入包含1个测试用例，即给出自然数n的值。
输出格式：
输出从n计算到1需要的步数。
输入样例：
3
输出样例：
5

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    int number = Integer.parseInt(bufferedReader.readLine());
    bufferedReader.close();
    int cnt = 0;
    while (number != 1) {
      if (number % 2 != 0) number = 3 * number + 1;
      number /= 2;
      cnt++;
    }
    System.out.print(cnt);
  }
}

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class Main {

public static void main(String[] args) throws IOException {

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

int number = Integer.parseInt(bufferedReader.readLine());

bufferedReader.close();

int cnt = 0;

while (number != 1) {

if (number % 2 != 0) number = 3 * number + 1;

number /= 2;

cnt++;

}

System.out.print(cnt);

}

《自私的皮球》读书笔记

这本书写的特别好，里面很多内容都对我特别有启发～

第一部分　价格与市场

标注(粉色) – 02．饭店为何要收开瓶费 > 位置 324

许多餐馆对自带酒水者收取开瓶费，是因为他们刻意压低了饭菜的毛利而抬高了酒水的毛利，以此对喝酒和不喝酒的客户实施差别定价。这一策略让他们既能吸引那些只是想吃顿便饭的、预算较拮据的、善于精打细算的客户，又能从那些亲友聚餐、商务宴请、有幸垂顾的大款等消费意愿强烈、价格承受能力较高的客户那里，挣得尽可能多的收入。

标注(粉色) – 02．饭店为何要收开瓶费 > 位置 330

实际上，对于许多饭店，尽管酒水只占其销售额的 20％～ 30％，但常常要贡献 50％～ 60％的毛利；而从消费者的角度看，这其实是在让喝酒客户补贴不喝酒或少喝酒的客户。

标注(粉色) – 02．饭店为何要收开瓶费 > 位置 348

谢绝自带酒水的基本理由是饭店不想无偿提供（即便是部分的）休闲和用餐场所，这与谢绝自带食物道理一样，也是容易想到的。不过酒水有其特殊之处，点了酒水的客人通常会将饭局拖得较长，所以，酒水溢价也可视为饭店对喝酒客人额外占用的座位资源所收取的租金，座位资源属饭店核心资源，而“翻台率”也是饭店管理的重要指标。

标注(粉色) – 04．宜家是做家居还是做地产的 > 位置 412

二流商家必须挤进最热闹的地方，而一流商家则可以制造热闹，并且在与土地供应方谈判时拥有足够的筹码；其次是恰当的选址，对于该战略，好的店址是那些交通方便、处于闹市区边缘，因而有较大增值空间的地段，而其中尤以城市环线附近为佳，宜家已有七家店的选址看来都符合这一条件，

继续阅读《自私的皮球》读书笔记

Mac 蓝牙触控板（Magic trackpad）和原来自带的内建触控板同时使用

之前使用Magic trackpad 2时候出了点小问题，发现断开trackpad后依然无法使用内建触控板，导致自己用了一天的鼠标ORZ……然后就想到了能否两个触控板一起使用的功能……果然在辅助功能里面有～（不过似乎朋友的MacBook里这个功能是默认关闭的，不知道为什么我的是默认打开的…）

所以这个问题也可以解决：蓝牙触控板Magic trackpad断开连接后原触控板依然无法使用的问题

系统偏好设置 – 辅助功能 – 鼠标与触控板 – 取消勾选“有鼠标或无线触控板时忽略内建触控板”

PAT 1143. Lowest Common Ancestor (30) – 甲级

The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants.
A binary search tree (BST) is recursively defined as a binary tree which has the following properties:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.
Given any two nodes in a BST, you are supposed to find their LCA.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers: M (<= 1000), the number of pairs of nodes to be tested; and N (<= 10000), the number of keys in the BST, respectively. In the second line, N distinct integers are given as the preorder traversal sequence of the BST. Then M lines follow, each contains a pair of integer keys U and V. All the keys are in the range of int.
Output Specification:
For each given pair of U and V, print in a line “LCA of U and V is A.” if the LCA is found and A is the key. But if A is one of U and V, print “X is an ancestor of Y.” where X is A and Y is the other node. If U or V is not found in the BST, print in a line “ERROR: U is not found.” or “ERROR: V is not found.” or “ERROR: U and V are not found.”.
Sample Input:
6 8
6 3 1 2 5 4 8 7
2 5
8 7
1 9
12 -3
0 8
99 99
Sample Output:
LCA of 2 and 5 is 3.
8 is an ancestor of 7.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.

题目大意：给出一棵二叉搜索树的前序遍历，问结点u和v的共同最低祖先是谁～
分析：map<int, bool> mp用来标记树中所有出现过的结点，遍历一遍pre数组，将当前结点标记为a，如果u和v分别在a的左、右，或者u、v其中一个就是当前a，即(a >= u && a <= v) || (a >= v && a <= u)，说明找到了这个共同最低祖先a，退出当前循环～最后根据要求输出结果即可～
PS：30分的题目30行代码解决，1行1分，惊不惊喜？意不意外？（真的是水题啊…）

#include <iostream>
#include <vector>
#include <map>
using namespace std;
map<int, bool> mp;
int main() {
    int m, n, u, v, a;
    scanf("%d %d", &m, &n);
    vector<int> pre(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &pre[i]);
        mp[pre[i]] = true;
    }
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        for(int j = 0; j < n; j++) {
            a = pre[j];
            if ((a >= u && a <= v) || (a >= v && a <= u)) break;
        } 
        if (mp[u] == false && mp[v] == false)
            printf("ERROR: %d and %d are not found.\n", u, v);
        else if (mp[u] == false || mp[v] == false)
            printf("ERROR: %d is not found.\n", mp[u] == false ? u : v);
        else if (a == u || a == v)
            printf("%d is an ancestor of %d.\n", a, a == u ? v : u);
        else
            printf("LCA of %d and %d is %d.\n", u, v, a);
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <map>

using namespace std;

map<int, bool> mp;

int main() {

int m, n, u, v, a;

scanf("%d %d", &m, &n);

vector<int> pre(n);

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

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

mp[pre[i]] = true;

}

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

scanf("%d %d", &u, &v);

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

a = pre[j];

if ((a >= u && a <= v) || (a >= v && a <= u)) break;

}

if (mp[u] == false && mp[v] == false)

printf("ERROR: %d and %d are not found.\n", u, v);

else if (mp[u] == false || mp[v] == false)

printf("ERROR: %d is not found.\n", mp[u] == false ? u : v);

else if (a == u || a == v)

printf("%d is an ancestor of %d.\n", a, a == u ? v : u);

else

printf("LCA of %d and %d is %d.\n", u, v, a);

}

return 0;

}

PAT 1146. Topological Order (25) – 甲级

This is a problem given in the Graduate Entrance Exam in 2018: Which of the following is NOT a topological order obtained from the given directed graph? Now you are supposed to write a program to test each of the options.

Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers N (<= 1,000), the number of vertices in the graph, and M (<= 10,000), the number of directed edges. Then M lines follow, each gives the start and the end vertices of an edge. The vertices are numbered from 1 to N. After the graph, there is another positive integer K (<= 100). Then K lines of query follow, each gives a permutation of all the vertices. All the numbers in a line are separated by a space.
Output Specification:
Print in a line all the indices of queries which correspond to “NOT a topological order”. The indices start from zero. All the numbers are separated by a space, and there must no extra space at the beginning or the end of the line. It is graranteed that there is at least one answer.
Sample Input:
6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
5
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6
Sample Output:
3 4

题目大意：给一个有向图，判断给定序列是否是拓扑序列～
分析：用邻接表v存储这个有向图，并将每个节点的入度保存在in数组中。对每一个要判断是否是拓扑序列的结点遍历，如果当前结点的入度不为0则表示不是拓扑序列，每次选中某个点后要将它所指向的所有结点的入度-1，最后根据是否出现过入度不为0的点决定是否要输出当前的编号i～flag是用来判断之前是否输出过现在是否要输出空格的～judge是用来判断是否是拓扑序列的～

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m, a, b, k, flag = 0, in[1010];
    vector<int> v[1010];
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &a, &b);
        v[a].push_back(b);
        in[b]++;
    }
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        int judge = 1;
        vector<int> tin(in, in+n+1);
        for (int j = 0; j < n; j++) {
            scanf("%d", &a);
            if (tin[a] != 0) judge = 0;
            for (int it : v[a]) tin[it]--;
        }
        if (judge == 1) continue;
        printf("%s%d", flag == 1 ? " ": "", i);
        flag = 1;
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n, m, a, b, k, flag = 0, in[1010];

vector<int> v[1010];

scanf("%d %d", &n, &m);

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

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

v[a].push_back(b);

in[b]++;

}

scanf("%d", &k);

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

int judge = 1;

vector<int> tin(in, in+n+1);

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

scanf("%d", &a);

if (tin[a] != 0) judge = 0;

for (int it : v[a]) tin[it]--;

}

if (judge == 1) continue;

printf("%s%d", flag == 1 ? " ": "", i);

flag = 1;

}

return 0;

}