头像

洛白さん

$$青涩の醉挽清风Team$$




离线:9小时前


最近来访(522)
用户头像
ljh_lxy
用户头像
Finn2009
用户头像
BaNg059
用户头像
起名字真难
用户头像
lpq1234
用户头像
18064672445
用户头像
清风qwq
用户头像
种花家的虎式坦克
用户头像
面条小王子
用户头像
拼凑未来
用户头像
北海没有WA
用户头像
jyhak
用户头像
Bochi
用户头像
incra
用户头像
wt20
用户头像
Acwer
用户头像
糖醋-诗酒
用户头像
sealt
用户头像
smr666
用户头像
种花家的市长


这里是 @洛白さん个人主页


$个人信息:$


用户名: @洛白さん

组织: $青涩の醉挽清风Team$

LUOGU洛谷:$\color{Blue}{本菜鸡のLUOGU账号}$

LUOGU咕值:119(火警电话?!)

姓名:wzt(不可能告诉你的)

年级:五年级

地区:伤害(好像打错了)

学校:你猜猜看

住址:只能告诉你静安区

同学:没有(呜呜呜)

朋友:好像有(呜呜呜😥)

粉丝:44个!!!

感谢我的粉丝们!!!

ありがとうございます!


$acwingの阶段:$


$\color{Blue}{阅读量4000}$
$2022年03月04日19:25:33$

$\color{Red}{阅读量5000}$
$2022年04月04日09:56:20$

$\color{Green}{100题解}$
$2022年04月11日18:00:41$

$\color{Orange}{阅读量6000}$
$2022年04月25日21:46:20$

$\color{Purple}{阅读量7000}$
$2022年05月14日10:33:04$

$\color{Green}{阅读量8000}$
$2022年05月25日12:19:08$

$\color{DarkOrchid}{阅读量9000}$
$2022年06月01日21:47:59$

$\color{GoldEnrod}{200题解}$
$2022年06月08日15:23:44$

$\Huge\color{Coral}{阅读量1w}$
$2022年06月12日22:26:54$

$\Huge\color{Blue}{阅读量2w}$
$不知道$


30.gif


$优质题解和分享:$


1、 【分享】十个电脑使用技巧

2、 $\color{Blue}{《高效算法(分治二分)》——第一期}$

3、 $\color{Blue}{《高效算法(分治二分)》——第二期}$

4、 高精度汇总

5、 星期几

6、 洛谷P1706. 全排列问题

7、 洛谷P1923. 求第 k 小的数


$好玩的游戏:$


【分享】不知道写啥


完结撒花!(走咯💨)



新鲜事 原文

整理了两个小时的题解和分享 没人看?! QWQ



P1923.求第 k 小的数


题目描述


输入 $n$($1 \le n < 5000000$ 且 $n$ 为奇数)个数字 $a_i$($1 \le a_i < {10}^9$),输出这些数字的第 $k$ 小的数。最小的数是第 $0$ 小。

请尽量不要使用 $nth_element$ 来写本题,因为本题的重点在于练习分治算法。

输入格式


输出格式


样例 #1


样例输入 #1

5 1
4 3 2 1 5

样例输出 #1

2

方法一:

题目不让我用
$nth_element$
我就偏要用(不过 STL 常数普遍较大……但还是能过此题)

重点(敲黑板):

它的用法是 $nth_element(a+x,a+x+y,a+x+len);$

执行之后数组 $a$ 下标 $x$ $x + y - 1$ 的元素都小于 $a[x + y] $。下标 $ x + y + 1$ $x + len - 1$ 的元素都大于 $ a[x + y]$ ,但不保证数组有序。此时 $ a[x + y] $ 就是数组区间 $x$ $x+len-1$ 中第 $ y $ 小的数,当然也可以自己定义 $ cmp $ 函数。


$code$:

#include<bits/stdc++.h>
using namespace std;
int x[5000005], k;
int main(){
    int n;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i ++) scanf("%d", &x[i]);
    nth_element(x, x + k, x + n);
    printf("%d", x[k]);
    return 0;
}

方法二:

对原数组进行快速排序,然后 $O(1)$ 输出。


$code$:

#include<bits/stdc++.h>
using namespace std;
int x[5000005], k;
int main(){
    int n;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i ++) scanf("%d", &x[i]);
    sort(x, x + n);
    printf("%d", x[k]);
    return 0;
}

方法三:

根据快排思想来寻找第 $k$ 小的数。
快排的核心思想是二分。
在原二分的基础上可以进行修改:因为每次递归都会将数组划分为三部分,
而答案只会在这三部分中的一个,不需要再对其他部分进行搜索,
从而达到优化时间复杂度的效果。


$code$:

#include<bits/stdc++.h>
using namespace std;
int x[5000005], k;
void qsort(int l, int r){
    int i = l, j = r, mid = x[(l+r)/2];
    do{
        while(x[j] > mid) j--;
        while(x[i] < mid) i++;
        if(i <= j){
            swap(x[i], x[j]);
            i ++, j --;
        }
    }while(i <= j);
    if(k <= j) qsort(l, j);
    else if(i <= k) qsort(i, r);
    else{
        printf("%d", x[j+1]);
        exit(0);
    }
}
int main(){
    int n;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++) scanf("%d", &x[i]);
    qsort(0, n - 1);
    return 0;
}




<-制作不易,如果满意就点一下吧


P1923.求第 k 小的数


题目描述


输入 $n$($1 \le n < 5000000$ 且 $n$ 为奇数)个数字 $a_i$($1 \le a_i < {10}^9$),输出这些数字的第 $k$ 小的数。最小的数是第 $0$ 小。

请尽量不要使用 $nth_element$ 来写本题,因为本题的重点在于练习分治算法。

输入格式


输出格式


样例 #1


样例输入 #1

5 1
4 3 2 1 5

样例输出 #1

2

方法一:

题目不让我用
$nth_element$
我就偏要用(不过 STL 常数普遍较大……但还是能过此题)

重点(敲黑板):

它的用法是 $nth_element(a+x,a+x+y,a+x+len);$

执行之后数组 $a$ 下标 $x$ $x + y - 1$ 的元素都小于 $a[x + y] $。下标 $ x + y + 1$ $x + len - 1$ 的元素都大于 $ a[x + y]$ ,但不保证数组有序。此时 $ a[x + y] $ 就是数组区间 $x$ $x+len-1$ 中第 $ y $ 小的数,当然也可以自己定义 $ cmp $ 函数。


$code$:

#include<bits/stdc++.h>
using namespace std;
int x[5000005], k;
int main(){
    int n;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i ++) scanf("%d", &x[i]);
    nth_element(x, x + k, x + n);
    printf("%d", x[k]);
    return 0;
}

方法二:

对原数组进行快速排序,然后 $O(1)$ 输出。


$code$:

#include<bits/stdc++.h>
using namespace std;
int x[5000005], k;
int main(){
    int n;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i ++) scanf("%d", &x[i]);
    sort(x, x + n);
    printf("%d", x[k]);
    return 0;
}

方法三:

根据快排思想来寻找第 $k$ 小的数。
快排的核心思想是二分。
在原二分的基础上可以进行修改:因为每次递归都会将数组划分为三部分,
而答案只会在这三部分中的一个,不需要再对其他部分进行搜索,
从而达到优化时间复杂度的效果。


$code$:

#include<bits/stdc++.h>
using namespace std;
int x[5000005], k;
void qsort(int l, int r){
    int i = l, j = r, mid = x[(l+r)/2];
    do{
        while(x[j] > mid) j--;
        while(x[i] < mid) i++;
        if(i <= j){
            swap(x[i], x[j]);
            i ++, j --;
        }
    }while(i <= j);
    if(k <= j) qsort(l, j);
    else if(i <= k) qsort(i, r);
    else{
        printf("%d", x[j+1]);
        exit(0);
    }
}
int main(){
    int n;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++) scanf("%d", &x[i]);
    qsort(0, n - 1);
    return 0;
}




<-制作不易,如果满意就点一下吧


题目描述


按照字典序输出自然数 $1$ 到 $n$ 所有不重复的排列,即 $n$ 的全排列,要求所产生的任一数字序列中不允许出现重复的数字。

输入格式


一个整数 $n$。

输出格式


由 $1 \sim n$ 组成的所有不重复的数字序列,每行一个序列。

每个数字保留 $5$ 个场宽。

样例 #1


样例输入 #1

3

样例输出 #1

    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1

提示


$1 \leq n \leq 9$。

类似题型


$\color{Red}{823. 排列}$
$\color{Red}{842. 排列数字}$
$\color{Red}{51. 数字排列}$
$\color{Red}{3429. 全排列}$


方法一:

这是一道好题,用STL的好题
在#include <algorithm>里有一个函数,全排列函数:
next_permutation!
仅需15行代码即可AC!

$code$:

#include<bits/stdc++.h>
#define for(a,b,c) for(register int a = b; a <= c; a ++)
using namespace std;
int x[11];
int main(){
    int n;
    scanf("%d",&n);
    for(i,1,n) x[i] = i, printf("    %d", i);
    while(next_permutation(x + 1, x + 1 + n)){
        printf("\n");
        for(i,1,n) printf("    %d", x[i]);
    }
    return 0;
}

$\color{Red}{STL yyds}$


方法二:

其实可以直接用main()来递归!

$code$:

#include<bits/stdc++.h>
using namespace std;
int n, step = 1, int i;
int a[15];
bool ans[15];
int main(){
    if(step == 1){
        cin >> n;
    }
    if(step - 1 == n){
        for(i = 1; i <= n; i ++){
            printf("%5d", a[i]);
            printf("\n");
        }
    }
    for(i = 1; i <= n; i++){
        if(ans[i] == 0){
            ans[i] = 1;
            a[step] = i;
            step ++;
            main();
            step --;
            ans[i] = 0;
        }
    }
    return 0;
}

$\color{Red}{main()也可以用来递归!}$


方法三:

咱是个蒟蒻,咱不会DFS,也不会高端做法,打表费时,所以,暴力枚举出奇迹!(逃)

(不建议食用)!

其实就是枚举所有数字,很简单,n最大是9,那就用9个for循环分别枚举,从1-n,
只输出1-n的全排序,那就每个循环后面加个判断语句,看是否到第n个数了,到了的话直接输出。

$code$:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[10], n;
    for(int i = 1; i <= 9; i ++) a[i] = i;
    cin >> n;
    for(int i1 = 1; i1 <= n; i1 ++){//把第一个数从1-n枚举
        if(n == 1){//如果n是1,即从1-1全排序 
            cout<<"    "<<i1<<"\n"; //输出全排序结果 
            continue;//跳过后面几个数的枚举
        }
        for(int i2 = 1; i2 <= n; i2 ++){//把第二个数从1-n枚举 ,后面嵌套的for循环同理,即把第3、4、5...9个数枚举 
            if(i2 == i1) continue;//当i2和前面的数重复时,跳过后面的判断,继续循环。后面嵌套的循环同理,即当i3、i4、i5、......i9和前面数重复时,跳过后面的判断,继续循环 
            if(n == 2){//如果n是2 ,即从1-2全排序。后面同理,即从1-3、1-4......1-9全排序 
                cout<<"    "<<i1<<"    "<<i2<<"\n";//输出全排序结果,后面同理 
                continue;//跳过后面几个数的枚举,后面同理 
            }
            for(int i3 = 1; i3 <= n; i3 ++){
                if(i3 == i2 || i3 == i1) continue;
                if(n == 3){
                    cout<<"    "<<i1<<"    "<<i2<<"    "<<i3<<"\n";
                    continue;
                }
                for(int i4 = 1; i4 <= n; i4 ++){
                    if(i4 == i3 || i4 == i2 || i4 == i1) continue;
                    if(n == 4){
                        cout << "    " << i1 << "    " << i2 << "    " << i3 << "    " << i4 << "\n";
                        continue;
                    }
                    for(int i5 = 1; i5 <= n; i5++){
                        if(i5 == i4 || i5 == i3 || i5 == i2 || i5 == i1) continue;
                        if(n == 5){
                            cout << "    " << i1 << "    " << i2 << "    " << i3 << "    " << i4 << "    " << i5 << "\n";
                            continue;
                        }
                        for(int i6 = 1; i6 <= n; i6++){
                            if(i6 == i5 || i6 == i4 || i6 == i3 || i6 == i2 || i6 == i1) continue;
                            if(n == 6){
                                cout << "    " << i1 << "    " << i2 << "    " << i3 << "    " << i4 << "    " << i5 << "    " << i6 << "\n";
                                continue;
                            }
                            for(int i7 = 1; i7 <= n; i7++){
                                if(i7 == i6 || i7 == i5 || i7 == i4 || i7 == i3 || i7 == i2 || i7 == i1) continue;
                                if(n == 7){
                                    cout << "    " << i1 << "    " << i2 << "    " << i3 << "    " << i4 << "    " << i5 << "    " << i6 << "    " << i7 << "\n";
                                    continue;
                                }
                                for(int i8 = 1; i8 <= n; i8++){
                                    if(i8 == i7 || i8 == i6 || i8 == i5 || i8 == i4 || i8 == i3 || i8 == i2 || i8 == i1) continue;
                                    if(n == 8){
                                        cout << "    " << i1 << "    " << i2 << "    " << i3 << "    " << i4 << "    " << i5 << "    " << i6 << "    " << i7 << "    " << i8 << "\n";
                                        continue;   
                                    }   
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;//好习惯呀! 
}

微信图片_20221129112411.jpg

本当に疲れそうです


方法四:

说实话一道简单的水题做成这个样子,我也是没谁了,
经典的DFS模板真的很经典!

提醒:

printf("%5d", ans);

输出方式为 “%5d” 表示按5位的固定位宽输出整型数值。
如果不足5位,则在前面补空格;超过5位,则按实际位数输出。

#include<bits/stdc++.h>
using namespace std;
int n, ans[10];
bool a[10];
void search(int now){
    if(now == n+1){
        for(int i = 1; i <= n; i ++){
            printf("%5d", ans[i]);
        }
        cout << endl;
        return;    
    }
    for(int i = 1; i <= n; i ++){       
        if(a[i] == false){
            a[i] = true;
            ans[now] = i;
            search(now + 1);
            a[i] = false;    
        }    
    }
}
int main(){
    cin >> n;
    search(1);
    return 0;
}




题目描述


按照字典序输出自然数 $1$ 到 $n$ 所有不重复的排列,即 $n$ 的全排列,要求所产生的任一数字序列中不允许出现重复的数字。

输入格式


一个整数 $n$。

输出格式


由 $1 \sim n$ 组成的所有不重复的数字序列,每行一个序列。

每个数字保留 $5$ 个场宽。

样例 #1


样例输入 #1

3

样例输出 #1

    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1

提示


$1 \leq n \leq 9$。

类似题型


$\color{Red}{823. 排列}$
$\color{Red}{842. 排列数字}$
$\color{Red}{51. 数字排列}$
$\color{Red}{3429. 全排列}$


方法一:

这是一道好题,用STL的好题
在#include <algorithm>里有一个函数,全排列函数:
next_permutation!
仅需15行代码即可AC!

$code$:

#include<bits/stdc++.h>
#define for(a,b,c) for(register int a = b; a <= c; a ++)
using namespace std;
int x[11];
int main(){
    int n;
    scanf("%d",&n);
    for(i,1,n) x[i] = i, printf("    %d", i);
    while(next_permutation(x + 1, x + 1 + n)){
        printf("\n");
        for(i,1,n) printf("    %d", x[i]);
    }
    return 0;
}

$\color{Red}{STL yyds}$


方法二:

其实可以直接用main()来递归!

$code$:

#include<bits/stdc++.h>
using namespace std;
int n, step = 1, int i;
int a[15];
bool ans[15];
int main(){
    if(step == 1){
        cin >> n;
    }
    if(step - 1 == n){
        for(i = 1; i <= n; i ++){
            printf("%5d", a[i]);
            printf("\n");
        }
    }
    for(i = 1; i <= n; i++){
        if(ans[i] == 0){
            ans[i] = 1;
            a[step] = i;
            step ++;
            main();
            step --;
            ans[i] = 0;
        }
    }
    return 0;
}

$\color{Red}{main()也可以用来递归!}$


方法三:

咱是个蒟蒻,咱不会DFS,也不会高端做法,打表费时,所以,暴力枚举出奇迹!(逃)

(不建议食用)!

其实就是枚举所有数字,很简单,n最大是9,那就用9个for循环分别枚举,从1-n,
只输出1-n的全排序,那就每个循环后面加个判断语句,看是否到第n个数了,到了的话直接输出。

$code$:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[10], n;
    for(int i = 1; i <= 9; i ++) a[i] = i;
    cin >> n;
    for(int i1 = 1; i1 <= n; i1 ++){//把第一个数从1-n枚举
        if(n == 1){//如果n是1,即从1-1全排序 
            cout<<"    "<<i1<<"\n"; //输出全排序结果 
            continue;//跳过后面几个数的枚举
        }
        for(int i2 = 1; i2 <= n; i2 ++){//把第二个数从1-n枚举 ,后面嵌套的for循环同理,即把第3、4、5...9个数枚举 
            if(i2 == i1) continue;//当i2和前面的数重复时,跳过后面的判断,继续循环。后面嵌套的循环同理,即当i3、i4、i5、......i9和前面数重复时,跳过后面的判断,继续循环 
            if(n == 2){//如果n是2 ,即从1-2全排序。后面同理,即从1-3、1-4......1-9全排序 
                cout<<"    "<<i1<<"    "<<i2<<"\n";//输出全排序结果,后面同理 
                continue;//跳过后面几个数的枚举,后面同理 
            }
            for(int i3 = 1; i3 <= n; i3 ++){
                if(i3 == i2 || i3 == i1) continue;
                if(n == 3){
                    cout<<"    "<<i1<<"    "<<i2<<"    "<<i3<<"\n";
                    continue;
                }
                for(int i4 = 1; i4 <= n; i4 ++){
                    if(i4 == i3 || i4 == i2 || i4 == i1) continue;
                    if(n == 4){
                        cout << "    " << i1 << "    " << i2 << "    " << i3 << "    " << i4 << "\n";
                        continue;
                    }
                    for(int i5 = 1; i5 <= n; i5++){
                        if(i5 == i4 || i5 == i3 || i5 == i2 || i5 == i1) continue;
                        if(n == 5){
                            cout << "    " << i1 << "    " << i2 << "    " << i3 << "    " << i4 << "    " << i5 << "\n";
                            continue;
                        }
                        for(int i6 = 1; i6 <= n; i6++){
                            if(i6 == i5 || i6 == i4 || i6 == i3 || i6 == i2 || i6 == i1) continue;
                            if(n == 6){
                                cout << "    " << i1 << "    " << i2 << "    " << i3 << "    " << i4 << "    " << i5 << "    " << i6 << "\n";
                                continue;
                            }
                            for(int i7 = 1; i7 <= n; i7++){
                                if(i7 == i6 || i7 == i5 || i7 == i4 || i7 == i3 || i7 == i2 || i7 == i1) continue;
                                if(n == 7){
                                    cout << "    " << i1 << "    " << i2 << "    " << i3 << "    " << i4 << "    " << i5 << "    " << i6 << "    " << i7 << "\n";
                                    continue;
                                }
                                for(int i8 = 1; i8 <= n; i8++){
                                    if(i8 == i7 || i8 == i6 || i8 == i5 || i8 == i4 || i8 == i3 || i8 == i2 || i8 == i1) continue;
                                    if(n == 8){
                                        cout << "    " << i1 << "    " << i2 << "    " << i3 << "    " << i4 << "    " << i5 << "    " << i6 << "    " << i7 << "    " << i8 << "\n";
                                        continue;   
                                    }   
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;//好习惯呀! 
}

微信图片_20221129112411.jpg

本当に疲れそうです


方法四:

说实话一道简单的水题做成这个样子,我也是没谁了,
经典的DFS模板真的很经典!

提醒:

printf("%5d", ans);

输出方式为 “%5d” 表示按5位的固定位宽输出整型数值。
如果不足5位,则在前面补空格;超过5位,则按实际位数输出。

#include<bits/stdc++.h>
using namespace std;
int n, ans[10];
bool a[10];
void search(int now){
    if(now == n+1){
        for(int i = 1; i <= n; i ++){
            printf("%5d", ans[i]);
        }
        cout << endl;
        return;    
    }
    for(int i = 1; i <= n; i ++){       
        if(a[i] == false){
            a[i] = true;
            ans[now] = i;
            search(now + 1);
            a[i] = false;    
        }    
    }
}
int main(){
    cin >> n;
    search(1);
    return 0;
}






新鲜事 原文

嗨害嗨!我又回来了啊🥳😄



洛白さん
3个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 310;
int main(){
    int a, b, n;
    cin >> a >> b >> n;
    int res = 0;
    for(int i = 0, j = b; i <= a; i ++){
        while(j >= 0 && i + j > n) j --;
        if(i + j == n && j >= 0){
            res ++;
        }
    }
    cout << res << endl;
    return 0;
}




洛白さん
3个月前
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    while(n --){
        string st;
        cin >> st;
        if(st[st.size() - 1] == 'o' && st[st.size() - 2] == 'p'){
            puts("FILIPINO");
        }else if(st[st.size() - 1] == 'u' && st[st.size() - 2] == 's' && st[st.size() - 3] == 'e' && st[st.size() - 4] == 'd' || st[st.size() - 1] == 'u' && st[st.size() - 2] == 's' && st[st.size() - 3] == 'a' && st[st.size() - 4] == 'm'){
            puts("JAPANESE");
        }else{
            puts("KOREAN");
        }
    }
    return 0;
}