# Pat_solution

**Repository Path**: alecstark/pat_solution

## Basic Information

- **Project Name**: Pat_solution
- **Description**: 浙大甲级pat题解。附机试小技巧。
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2021-08-05
- **Last Updated**: 2021-09-06

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# PAT Solution

> 每天5题PAT，医生远离我！记录自己的每日成就能提高效率！

## 机试小trick

* ### IO操作

  1. 提高读速度

     ```c++
     //当只有一个回车出现时，cin会直接忽略这个回车。当读完一定内容后会在空格和回车处停止。此时可以用cin.get()读到空格或回车。
     char f[160];
     while(scanf("%s", f) == 1){} // 可以加快读取速度
     string s
     while (getline(cin, s)) // 读取整行内容然后再用字符串的find进行切割
     {
     	if (s.empty())   break;
     } 
     ```

  2. 提高写速度

     ```c++
     string str;//printf在输出字符串方面比cout要快很多，因为在编译阶段str就能确定输出类型
     printf("%s",str.c_str());
     ```

  3. 读long long数据类型时，建议使用scanf

     ```c++
     scanf("%lld %lld %lld", &a, &b, &c);
     ```

  4. 字符串的输入与输出

     * 输出

       ```c++
       //printf只能输出自带的char*类型或者其他的数据类型，但是String类型不是自带的类型，所以不能直接输出。
       cout << str; //解决1：将cout和printf混合使用
       printf("%s",str.c_str());//解决2：通过cstr函数进行转化即可输出，而且效率更高
       printf("%c",c);//输出单个字符
       ```

     * 输入

       ```c++
       //cin.get()与getchar；cin.getline()与getline(cin, s)与gets(char *)
       getline(cin,s)//会抛弃回车
       ```

  5. 格式化输出

     ```c++
     //2表示输出数字的位数，0高位补零。如m=1时，输出01
     printf("%02d", m);
     //printf不会自动转型，所以需要强制转型后再作为变量输出
     printf("%.1f",(float)nc/nt)
     ```

  6. printf中%的转义：printf("%%");

* ### 结构体相关

  1. 构造函数

     ```c++
     struct book{
      string name;
      double cost;
      book(string name,double cost):name(name),cost(cost){}
     };
     ```

  2. 声明

     ```c++
     book* b = new book(name,cost);
     //or
     book b;b.name = "name";b.cost = 12.3;
     ```

  3. 排序

     ```c++
     bool cmp(book b1,book b2){
      //自定义，其中只有<和>,而没有>=,<=这种。
     }
     vector<book> books;
     sort(books.begin(),books.end(),cmp)
     ```

* ### 常用的STL

  1. 遇到去重的问题可以优先考虑`set`
  2. map中是按照键的顺序从小到大排序的
  3. `vector<int>tmp(st);`，可以实现vector的深拷贝

* ### 考试相关

  1. 输出数字的时候，需要考虑是否补零。
  
  2. 当邻接矩阵超内存时，可以用邻接表来存储。（但我觉得从做题策略而言没必要花费过多时间）
  
  3. 初始化，可以使用fill函数来代替memset。
  
     ```c++
     int d[maxn];
     fill(d,d+maxn,INT_MAX);
     ```
  
  4. 线性 + 有序 = 二分优化
  
  5. 图中路径可以用递归的方式反向输出
  
  6. 经典题：`1086 Tree Traversals Again`、`1107 Social Clusters`、`1064 Complete Binary Search Tree`、`1030 Travel Plan（建议温习）`、`1018 Public Bike Management（部分比较不满足贪心。可以将所有可能的结果用vector<int> p[maxn]存储起来，最后利用递回溯的方法遍历所有结果选取最优）`、`1045 Favorite Color Stripe（最长上升子序列）`、`1057 Stack（分块思想，实时查询第k大元素，时间复杂度为 sqrt(n) ）`
  
  7. 1066待做