空格问题

1. 在不少题中要求末尾无空格，所以我们要在第一个满足条件的数后无空格，而在后面的每一个满足条件的数前面加上空格
2. 加空格有两种方式，一种是利用题中的循环条件来，另一种是自己创建一个条件

例1、在PTA_Basic_Level 1062 最简分数中

bool flag = false;
while(n1 * k >= m1 * num) num++;
while(n1 * k < m1 * num && m2 * num < n2 * k){
    if(gcd(num, k) == 1){
        printf("%s%d/%d", flag ? " " : "", num, k);
        flag = true;
    }
    num++;
}

建立一个bool类型的变量flag并让其为false，在打印的时候运用三目运算符来判断如果为flase则输出空字符""如果为true则输出" "，即达成第一个数后无空个的要求。

例1、在PTA_Basic Level 1066 图像过滤

for(int i = 0; i < m; i++){
    for(int j = 0; j < n; j++){
        scanf("%d", &temp);
        if(temp >= a && temp <= b)
            temp = num;
        if(j) printf(" ");
        printf("%03d", temp);
    }
    printf("\n");
}

运用循环条件j当j不等于0的时候来输出空格

---

多行数据

B1066

不一定用数组储存每一行的数据，可以优先考虑边输入，边处理输出

---

多点测试（输出到文件尾）

与之对应的是单点测试，区别在于多点测试只执行一次代码则要验证所有数据，单点测试则是每次验证一组数据，执行多次。

B1010

//方式一
int a, b;
while(cin >> a >> b) {}

// 方式二
int a, b;
while(~scanf("%d %d", &a, &b)) {}

方式三
int a, b;
while(scanf("%d %d", &a, &b) != EOF) {}

//方式四
int a, b;
while(scanf("%d %d", &a, &b) == 2) {}

---

字符串吸收换行符

B1067

#include <bits/stdc++.h>
using namespace std;
int main(){
    string password, temp;
    int n;
    cin >> password >> n;
    getchar(); //吸收换行符
    for(int i = 1;; i++){
        getline(cin, temp);

1. 注意在cin >> password >> n;后面要加一句getchar();来吸收换行符，不然会用for循环里的getline(cin, temp)吸收。会减少一次循环

---

倒序输出一个数

前面无0形

方法一

1. 利用循环
2. 可以做成函数返回

int sum, n;
cin >> sum;
do{
    n = sum % 10 + n * 10;
    sum /= 10;
}while(sum);
cout << n;

方法二

利用string字符串倒序

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    printf("%d", stoi(s)); //stio()将n进制的字符串转化为十进制
    return 0;
}

前面有0形

方法一

1. 利用循环
2. 直接输出形

int n;
cin >> n;
do{
    cout << n % 10;
    n /= 10;
}while(n);

方法二

1. 利用数组储存倒序的数字
2. 然后倒序输出即可

int n, k = 0, q[MAXN];
cin >> n;
do{
    q[k++] = n % 10;
    n /= 10;
}while(n);
for(int i = 0; i < k; i++) cout << q[i];

方法三

1. 利用string字符串倒序
2. 与上面的前面无0形相比只是没有调用stoi()函数

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    cout << s << endl;
    return 0;
}

---

为什么要对1000000007取模

1. 大数阶乘，大数排列组合等，一般结果都会要求将输出结果对1000000007取模（取余）
2. 1000000007是一个质数，对质数取余能最大程度避免冲突
3. int32位的最大值为2147483647，所以对于int32位来说1000000007足够大
4. int64位的最大值为$2^63-1$，对于1000000007来说它的平方不会在int64中溢出所以在大数相乘的时候，因为(a * b) % c = ((a % c) * (b % c)) % c，所以相乘时两边都对1000000007取模，再保存在int64里面不会溢出。

---

最大公约数

递归法

int gcd(int a, int b){
    return a % b ? gcd(b, a % b) : b;
}
//或者
int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

辗转相除法

int temp, a, b;
cin >> a >> b;
while(b){
    temp = b;
    b = a % b;
    a = temp;
}
return a;

---

对应关系

一对一

方法一map映射

#include <iostream>
#include <map>
using namespace std;
int main(){
    map<string, int> m;
    return 0;
}

方法二结构体

#include <iostream>
using namespace std;
struct student{
    string s;
    int n;
}stu;

开辟数组()

方法一动态数组

#include <iostream>
#include <vecotr>
using namespace std;
int main(){
    vecotr<int> array;
    return 0;
}

方法二数组

#include <iostream>
using namespace std;
int main(){
    int array[10]; //开辟较小的时候
    return 0;
}

#include <iostream>
using namespace std;
const maxn = 10001;
int array[maxn]; //开辟较大的时候在main函数外开辟，因为较大的数组会占用较大的内存，防止爆栈。
int main(){
    return 0;
}

一对多

#include <iostream>
#include <map>
using namespace std;
int main(){
    map<string, vector<int>> m; //相当于用动态数组做了一个“多”
    return 0;
}

---

txt输入

#include <iostream>
using namespace std;
int main(){
    freopen("input.txt", "r", stdin); //可以不用重复粘贴，提交的时候注释掉即可。
    return 0;
}

---

C++使用printf输出string类

利用s.c_str()函数。

string s;
printf("%s", s.c_str());

C++中string字符串前补0

利用insert函数

string s, s1;
s1.insert(0, s1.length() - s.length(), '0');

---

n个点直接距离最小和对应的点

将n个点从大到小排序，n为奇数的话点为最中间的那个点，n为偶数时候点为最中间两个点中的任意一个。该结论用绝对值不等式来证明。

104. 货仓选址

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n, ave;
    cin >> n;
    vector<int> array(n);
    for(int i = 0; i < n; i++) cin >> array[i];
    sort(array.begin(), array.end());
    for(int i = 0; i < n; i++) ave += abs(array[i] - array[n / 2]);
    cout << ave << endl;
    return 0;
}

对拍

Windows下对拍

1. 一个数据生成器代码data.cpp写好之后编译成data.exe
2. 一个自己的代码my.cpp编译成my.exe
3. 一个暴力解决的代码std.cpp编译成std.exe
4. 再写一个对拍.bat

eg
  设一个数 A 的最低 D 位形成的数是 ad。如果把 a​d截下来移到 A 的最高位前面，就形成了一个新的数 B。B 是 A 的多少倍？例如将 12345 的最低 2 位 45 截下来放到 123 的前面，就得到 45123，它约是 12345 的 3.66 倍。

输入格式：
输入在一行中给出一个正整数 A（≤10^​9）和要截取的位数 D。题目保证 D 不超过 A 的总位数。

输出格式：
计算 B 是 A 的多少倍，输出小数点后 2 位。

输入样例 1：
12345 2

输出样例 1：
3.66

输入样例 2：
12345 5

输出样例 2：
1.00

对拍.bat

color B
echo off 
:loop
    echo 已运行%a%次
    set /a a+=1
    rand.exe
    my.exe
    std.exe
    fc my.out std.out
    if not errorlevel 1 goto loop
pause

my.cpp

#include <bits/stdc++.h>
using namespace std;
int main() {
    freopen("data.in", "r", stdin); freopen("my.out", "w", stdout);
    string s;
    int n;
    cin >> s >> n;
    string res = s.substr(s.size() - n, n) + s.substr(0, s.size() - n);
    printf("%.2f", 1.0 * stoi(res) / stoi(s));
}

std.cpp

#include <bits/stdc++.h>

using namespace std;

int main() {
    freopen("data.in", "r", stdin); freopen("std.out", "w", stdout);
    string s;
    int n;
    cin >> s >> n;
    string ans = s.substr(s.length() - n, n) + s.substr(0, s.length() - n);
    long long a = stoi(ans), b = stoi(s);
    printf("%.2f", a * 1.0 / b);
}

rand.cpp

#include <bits/stdc++.h>

using namespace std;

int main() {
    freopen("data.in", "w", stdout);
    srand(time(NULL));
    for (int i = 1; i <= 1e3; i++){
        int x = rand() % 1000000000 + 1;
        int n = x, sum = 0;
        while(n){
            sum++;
            n /= 10;
        }
        for(int j = 1; j <= sum; j++) cout << x << ' ' << j << endl;
    }
}

加快读入

用scanf最快

cin

也可以使用cin但可能超时
一般大于1e6不建议使用cin

cin.tie(0);
ios::sync_with_stdio(false);

加入上述两句代码会加快速度，但是还是没有scanf快，加入这句话的副作用是不能和scanf混用了

一维坐标转二维坐标

//将一维坐标转化成二维[3*3]的坐标
int k = 4;
int x = 4 / 3, y = 4 % 3;