刷算法的小技巧

空格问题

  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;
文章作者: Mr.Zhang
文章标题: 刷算法的小技巧
文章链接: https://www.codewing.cn/index.php/56/tips-algorithm/
版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 许可协议。转载请注明来自Ying's Blog!

评论

  1. Ashore
    Windows Chrome
    2周前
    2022-8-01 14:24:13

    Ashore

    • 博主
      Ashore
      Android Chrome
      2周前
      2022-8-01 14:37:39

      加油hh

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇