头像

MarkCup马克杯

$$\href{https://www.acwing.com/blog/content/21245/}{\Huge\color{gold}{个人主页}}$$ $$超级蒟蒻无条件互粉,刷题家族!$$




离线:7小时前


最近来访(645)
用户头像
Cold_heartless
用户头像
AcWing2AK
用户头像
陌上花开Charlie
用户头像
JcWing
用户头像
watermelon_Learn
用户头像
永封用户
用户头像
WаWing
用户头像
hiehie
用户头像
迎风飘扬
用户头像
星星星星丶星
用户头像
wangyc
用户头像
种花家的兔兔
用户头像
天元之弈
用户头像
人间过客_追梦人
用户头像
john02017
用户头像
冰之韵
用户头像
max2021
用户头像
挑战全AcWing关注第一人
用户头像
incra
用户头像
Finn2009


#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<a+b;
}


活动打卡代码 AcWing 4275. Dijkstra序列

#include <bits/stdc++.h>
using namespace std;
int n,m,f[1005][1005],d[1005],a[1005],x,y,z;
bool g[1005];
bool dij(int x){
    memset(d,127,sizeof d);
    memset(g,0,sizeof g);
    d[x]=0;
    g[x]=1;
    for(int i=1;i<=n;i++){
        int t=a[i];
        g[t]=1;
        for(int j=1;j<=n;j++)
            if(!g[j]&&d[j]<d[t])
                return 0;
        for(int j=1;j<=n;j++)
            if(d[j]>d[t]+f[t][j])
                d[j]=d[t]+f[t][j];
    }
    return 1;
}
int main(){
    cin>>n>>m;
    memset(f,127,sizeof f);
    while(m--){
        cin>>x>>y>>z;
        f[x][y]=f[y][x]=z;
    }
    cin>>m;
    while(m--){
        for(int i=1;i<=n;i++)cin>>a[i];
        puts(dij(a[1])?"Yes":"No");
    }   
}



活动打卡代码 AcWing 4274. 后缀表达式

#include<bits/stdc++.h>
using namespace std;
int n,l[25],r[25],f[25];
string s[25];
string g(int x){
    if(l[x]==-1&&r[x]==-1)
        return "("+s[x]+")";
    if(l[x]==-1&&r[x])
        return "("+s[x]+g(r[x])+")";
    return "("+g(l[x])+g(r[x])+s[x]+")";
}

int main(){
    memset(l,-1,sizeof l);
    memset(r,-1,sizeof r);
    cin>>n;
    for(int i=1;i<=n;i ++){
        cin>>s[i]>>l[i]>>r[i];
        if(l[i])f[l[i]]=1;
        if(r[i])f[r[i]]=1;
    }
    int x=1;
    while(f[x])x++;
    cout<<g(x);
    return 0;
}

作者:不拿NOI金牌不改名
链接:https://www.acwing.com/solution/content/120750/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


活动打卡代码 AcWing 3596. a+b

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3526. 素数

/*
//\\ \\ \\ \\ \\ \\ \\ \\ || || || || || || // // // // // // // //
//\\ \\ \\ \\ \\ \\ \\        _ooOoo_          // // // // // // //
//\\ \\ \\ \\ \\ \\          o8888888o            // // // // // //
//\\ \\ \\ \\ \\             88" . "88               // // // // //
//\\ \\ \\ \\                (| -_- |)                  // // // //
//\\ \\ \\                   O\  =  /O                     // // //
//\\ \\                   ____/`---'\____                     // //
//\\                    .'  \\|     |//  `.                      //
//==                   /  \\|||  :  |||//  \                     ==
//==                  /  _||||| -:- |||||-  \                    ==
//==                  |   | \\\  -  /// |   |                    ==
//==                  | \_|  ''\---/''  |   |                    ==
//==                  \  .-\__  `-`  ___/-. /                    ==
//==                ___`. .'  /--.--\  `. . ___                  ==
//==              ."" '<  `.___\_<|>_/___.'  >'"".               ==
//==            | | :  `- \`.;`\ _ /`;.`/ - ` : | |              \\
////            \  \ `-.   \_ __\ /__ _/   .-` /  /              \\
////      ========`-.____`-.___\_____/___.-`____.-'========      \\
////                           `=---='                           \\
//// //   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^  \\ \\
//// // //      佛祖保佑      永无BUG      永不修改       \\ \\ \\ \\
//// // // // // // || || || || || || || || || || \\ \\ \\ \\ \\ \\
*/
#include <bits/stdc++.h>
using namespace std;
bool sushu(int n){
    if(n==1) return false;
    for(int i=2;i*i<=n;i++){
        if(n%i==0) return false;
    }
    return true;
}
int main()
{
    int n;
    while(cin>>n){int f=0;
        for(int i=2;i<n;i++){
            if(sushu(i)){
                if(i%10==1){
                    cout<<i<<" ";
                    f=1;
                }
            }
        }
        if(f==0) cout<<"-1 ";
        cout<<endl;
    }
}


活动打卡代码 AcWing 3589. 平方因子

#include <bits/stdc++.h>
#include <cmath>
using namespace std;
int main()
{
    int n;
    while(cin>>n){
        string s="No";
        for(int i=2;i<=sqrt(n);i++){
            if(n%(i*i)==0){
                s="Yes";
                break;
            }
        }
        cout<<s<<endl;
    }
    return 0;
}


新鲜事 原文

兄弟砍砍!我正在参与AcWing《算法进阶课》砍价优惠,就差你啦!https://www.acwing.com/activity/content/introduction/32/bargain/7021/



《-点个赞吧qwq

经典的穷举 如果你还不了解,请移步


根据题意可知,他们和一定不超过n,所以我们可以枚举1~n的所有数,再判断

#include<bits/stdc++.h>
using namespace std;
int ans;
int main()
{
    int a,b,n;
    cin>>a>>b>>n;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            if(i>=0 && i<=a && j>=0 && j<=b && i+j==n){
                ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}

当然,i与j分别不超过a和b,所以我们还可以进一步优化

#include<bits/stdc++.h>
using namespace std;
int ans;
int main()
{
    int a,b,n;
    cin>>a>>b>>n;
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            if(i+j==n){
                ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}

由他们和一定是N,我们又可以优化成一重循环(简单多了)

#include<bits/stdc++.h>
using namespace std;
int ans;
int main()
{
    int a,b,n;
    cin>>a>>b>>n;
    for(int i=0;i<=n;i++){
        int j=n-i;
        if(0>=j && j<=b){
            ans++;
        }
    }
    cout<<ans;
    return 0;
}


分享 穷举

穷举

计算机的特点之一就是运算速度快,善于重复做一件事。“穷举”正是基于这一特点的最古老的算法。它一般是在一时找不出解决问题的更好途径,即从数学上找不到求解的公式或规则时,根据问题中的“约束条件”,将解的所有可能情况一一列举出来,然后再逐个验证是否符合整个问题的求解要求,从而求得问题的可行解或者最优解。

一、 穷举算法的应用举例

例1、楼层编号
【问题描述】
小林在 NOIP 比赛期间住在“新世界”酒店。和其他酒店不一样的是,这个酒店每天都有一个高能的数字 t,这个数字在楼层中是不会出现的,以 t=3 为例,则 3、13、31、33 等楼层是不存在的,楼层编号为 1,2,4,5,…所以实际上的 4 楼才是 3 楼。
已知小林预订了编号为 m 层的房间,并且当天高能数字是 t,现在他想知道房间所在的真实楼层是多少。
【输入格式】

一行两个整数 m 和 t,1≤m≤100000,0≤t≤9,保证 m 对 t 合法。
【输出格式】
一行一个整数,表示真实楼层。
【输入样例】
14 3
【输出样例】
12

【问题分析】
根据题意,只要从 1~m 穷举楼层编号,将所有含高能数字 t 的楼层计数存储在 ans 中,最后的答案就是 m-ans。

例2、火柴棒等式
【问题描述】
给出 n 根火柴棒,可以拼出多少个形如“A+B=C”的等式?
等式中的 A、B、C 是用火柴棒拼出的整数(若该数非零,则最高位不能是 0)。用火柴棒拼数字 0~9 的拼法如图 9.7-1 所示。

需要注意以下几点:

(1) 加号与等号各自需要两根火柴棒。
(2) 如果 A ≠ B,则 A+B=C 与 B+A=C 视为不同的等式(A、B、C 均大于或等于 0)。
(3) n 根火柴棒必须全部用上(n≤24)。
【输入样例】
14
【输出样例】
2
【样例说明】
两个等式分别为:0+1=1 和 1+0=1。

【问题分析】
首先,预处理每个数字(0~9)需要用几根火柴棒,存储在数组 f 中。然后,穷举 a 和 b,算出它们的和 c,再判断下列约束条件是否成立:f (a)+ f (b)+ f (c)= n-4。现在的问题是:a 和 b 的范围有多大?可以发现尽量用数字 1 拼成的数比较大,分析可知最多不会超过 1111。程序实现时,分别用三个循环语句预处理好所有两位数、三位数、四位数构成所需要的火柴棒数量。

例3、比例简化
【问题描述】
在社交媒体上,经常会看到针对某一个观点同意与否的民意调查以及结果。例如,对某观点表示支持的有 1498 人,反对的有 902 人,那么其比例可以简单地记为1498∶902。
因该比例的数值太大,难以一眼看出它们的关系。若把比例记为 5∶3,虽然与真实结果有一定的误差,但依然能够较为准确地反映调查结果,同时也显得比较直观。
现给出支持人数 A 和反对人数 B,以及一个上限 L,请将 A 比 B 化简为 A′ 比 B′,要求在 A′和 B′ 均不大于 L,且 A′ 和 B′ 互质(两个整数的最大公约数为 1)的前提下,A′/B′≥ A/B 且 A′/B′-A/B 的值尽可能小。

【输入格式】
一行三个整数 A,B,L,每两个整数之间用一个空格隔开,分别表示支持人数、反对人数以及上限。
【输出格式】
一行两个整数 A′ 和 B′,中间用一个空格隔开,表示化简后的比例。
【输入样例】
1498 902 10
【输出样例】
5 3
【数据规模】
对于 100% 的数据满足:1≤A≤10 6 ,1≤B≤10 6 ,1≤L≤100,A/B≤L。

【问题分析】
首先,答案为一个分数,而且分子,分母都小于或等于 L。所以,可以直接穷举分子 i (对应题目中的 A′)和分母 j (对应题目中的 B′)。结合题目的具体要求分析:
(1) i,j≤L,这个可以作为穷举的范围。
(2) i/j≥A/B,且 i/j-A/B 的值尽量小。前者只要转换成 iB≥jA,后者可以“打擂台”实现。
假设用K1/K2表示最后的答案,初值设置为1000000/1,min=abs (k1B-k2A)。如果abs (i/j-A/B)< abs(K1/K2-A/B),即如果 abs(iB-jA)< abs(k1B-k2A),则更新 K1、K2 和 min。
(3) 答案的分子、分母要互质,这个只要从小到大穷举 i、从大到小穷举 j,第一个符合条件的答案肯定就是最简分数。假设 L=10,如果先穷举到 1/5 得到一个答案,后面的 2/10 是不会更新答案的。

例4、奶牛碑文
【问题描述】
小伟暑假期间到大草原旅游,在一块石头上发现了一些有趣的碑文。碑文似乎是一个神秘古老的语言,只包括三个大写字母 C、O 和 W。尽管小伟看不懂,但是令他高兴的是,C、O、W的顺序形式构成了一句他最喜欢的奶牛单词“COW”。现在,他想知道有多少次 COW 出现在文本中。
如果 COW 内穿插了其他字符,只要 COW 字符出现在正确的顺序,小伟也不介意。甚至,他也不介意出现不同的 COW 共享一些字母。例如,CWOW 出现了 1 次 COW,CCOW 算出现了2 次 COW,CCOOWW 算出现了 8 次 COW。

【输入格式】
第 1 行为 1 个整数 N。
第 2 行为 N 个字符的字符串,每个字符是一个 C、O 或 W。
【输出格式】
输出 COW 作为输入字符串的字串出现的次数(不一定是连续的)。
提示:答案会很大,建议用 64 位整数(long long)。
【输入样例】
6
COOWWW
【输出样例】
6
【数据规模】
对于 50% 的数据满足:N≤60。
对于 100% 的数据满足:N≤105 。

【问题分析】
因为只有 3 个字母,所以可以穷举字符串中的每一个“O”,假设位置 i,然后分别计算其左边“C” 的个数 l[i] 和右边“W” 的个数 r[i],再利用乘法原理进行计数 l[i]*r[i],每次把答案累加到 ans 中。

二、 穷举算法的优化
穷举算法的特点是算法设计、实现都相对简单,但时间复杂度和空间复杂度往往较大。因此,用穷举算法解决问题时,往往需要尽量优化算法,从而减少穷举的次数,提高穷举的效率。
穷举算法优化的思路主要有结合约束条件,通过数学推导,减少穷举的范围和数量;通过预处理(如部分和、是否素数等),以空间换时间,避免在穷举过程中重复计算或判断等。

例5、三角形个数

【问题描述】
输入一根木棒的长度 n,1≤n≤10000,将该木棒分成三段,每段的长度为正整数,输出由该三段小木棒组成的不一样的三角形个数。
【输入样例】
10
【输出样例】
2
【样例说明】
两个能组成的三角形边长分别为 2、4、4 和 3、3、4。

【问题分析】
穷举三角形三条边长(假设为 a、b、c)的可能值,判断能否构成一个三角形,若能则计数,最后输出计数器的值。为了保证组成的三角形不重复,只要在穷举时设定 1≤a≤b≤c≤n-2。优化思想很简单但很重要,“能算不举”,穷举两条边,根据木棒长度直接计算出第三条边长。

例6、阿姆斯特朗数
【问题描述】
编程找出所有的三位数到七位数中的阿姆斯特朗数。阿姆斯特朗数也叫水仙花数,它的定义如下:若一个 n 位自然数的各位数字的 n 次方之和等于它本身,则称这个自然数为阿姆斯特朗数。例如,153(153=1×1×1+3×3×3 +5×5×5)是一个三位的阿姆斯特朗数,8208 则是一个四位的阿姆斯特朗数。
【问题分析】
由于阿姆斯特朗数是没有规律的,只能采用穷举法一一验证 100~9999999 内的所有数是否是阿姆斯特朗数,若是,则打印之。但是,如果对任意一个数 K,都去求它的各位的若干次方,再求和判断是否等于K,效率比较差。注意到,每个位只可能是0~9,而且只会算到3~7次方。所以,为了使得程序尽快运行出正确结果,采用“以空间换时间”的策略,使用一个数组 p 预处理出所有数字的各次幂之值,p[i,j]表示 i 的 j 次方。另外,为了避免每次都对一个数进行逐位分解操作,直接用数组 a[8]存储一个数的每一位,穷举 100~9999999。

例7、金币
【问题描述】
国王将金币作为工资,发放给忠诚的骑士。第一天,骑士收到一枚金币;之后两天(第二天和第三天)里,每天收到两枚金币;之后三天(第四、五、六天)里,每天收到三枚金币;之后四天(第七、八、九、十天)里,每天收到四枚金币……这种工资发放模式会一直这样延续下去。当连续 n天每天收到 n 枚金币后,骑士会在之后的连续 n+1 天里,每天收到 n+1 枚金币(n 为正整数)。
请编程确定从第一天开始的给定天数内,骑士一共获得了多少金币。
【输入格式】
输入包含至少一行,但不多于 1000 行。

除最后一行外,输入的每行是一组输入数据,包含一个正整数 n,表示天数。
输入的最后一行为 0,表示输入结束。
【输出格式】
对每个数据输出一行一个整数,表示该数据对应总金币数。
【输入样例】
10
6
7
11
15
16
100
10000
1000
21
22
0
【数据规模】
对于 60% 的数据满足:n≤103 ;
对于 80% 的数据满足:n≤106 ;
对于 100% 的数据满足:n≤1012 。

【问题分析】
每次穷举每天获得的金币数,或者将答案保存在数组中直接输出,可以获得部分分。下面利用数学推导进行优化。
因为:1 2 +2 2 +3 2 +…+k 2 = k ×(k+1)×(2k+1)/ 6,假设前 n 个数为 1,2,2,3,3,3,…,k,k,k,k,如何求 k 呢?根据 1+2+3+…+k = n,即 k 2 +k-2n = 0,把 k 看成未知数,解方程可求出 k =(-1 + sqrt (1+8n))/ 2 = sqrt (2n+0.25)- 0.5,另一个负数解不合法舍去。

三、 二进制穷举思想
对于二进制数 00000,00001,00010,…,11111,它们是严格递增有序的,如何生成类似的二进制数字序列,就是“二进制穷举”思想,其应用非常广泛。“二进制穷举”的实现代码如下:

#include<cstdio>
using namespace std;
int main(){
    int n;
    int b[100];
    scanf( “ %d ” ,&n);
    for(int i = 0; i <= n; i++) b[i] = 0;
    while(b[0] == 0){
        for(int i = 1; i <= n; i++) printf( “ %d ” ,b[i]);
        printf( “ \n ” );
        int j = n;
        while(b[j] == 1) j--;
        b[j]++;
        for(int i = j + 1; i <= n; i++) b[i] = 0;
    }
    return 0;
}

例8、0-1 背包问题
【问题描述】
有 n 件物品,每件物品有一个重量和一个价值,分别记为 W1 ,W2 ,…,Wn 和 C1 ,C2 ,…,Cn 。现在有一个背包,其容量为 WK,要从 n 件物品种任取若干件,要求:
(1) 重量之和小于或等于 WK。
(2) 价值之和最大。
【输入格式】
第 1 行 2 个整数,表示 n和WK,1≤n≤20,1≤WK≤106 。
第 2 行 n 个整数,表示每一个物品的重量,1≤Wi ≤104 。
第 3 行 n 个整数,表示每一个物品的价值,1≤Ci ≤108 。
【输出格式】
一行一个数,表示符合背包容量的最大价值。
【输入样例】
8 200
79 58 86 11 28 62 15 68
83 14 54 79 72 52 48 62
【输出样例】
334

【问题分析】
背包问题有很多类型,本题是最简单的一种模型“0-1 背包”,即每件物品只有不取和取两种情况,对应着二进制中的 0 和 1。0-1 背包有多种解决算法,具体在第 13 课详细讲解。这里采用二进制穷举思想,从 000…00 穷举到 111…11,即定义一个数组 b,元素 b[i] = 0 或者 1,表示第 i 件物品不取或者取,每次判断背包能否装的下,同时对于价值打擂台取最大值。

例9、组合数的生成
【问题描述】
从 1、2、3、4、5、6 这 6 个数字中任取 4 个数的组合有1 2 3 4、1 2 3 5、1 2 3 6、1 2 4 5、1 2 4 6、1 2 5 6、1 3 4 5、1 3 4 6、1 3 5 6、1 4 5 6、2 3 4 5、2 3 4 6、2 3 5 6、2 4 5 6、3 4 5 6,共 15 种。若把它们看成 4 位数,发现是递增的。
编程,输入 n 和 r,1≤r≤n≤20,按照以上顺序,输出从 n 个数字(1~n)中任取 r 个数的所有组合。
【输入样例】
3 2
【输出样例】
1 2
1 3
2 3

【问题分析】
观察第一个数到最后一个数的变化规律,可以看出最后一位先变化(加 1),变到 n 就要“进位”到上一位;对于倒数第二位,变化到 n-1 就要产生“进位”……每次“进位”后,本位及以后的所有位都要重新置成一个递增的序列。这个算法的思路就是二进制穷举思想,不过不是固定的“n 进制”。




用devc++运行!

#include <iostream>
#include <cstdlib>
#include <bits/stdc++.h>
#include <windows.h>
using namespace std;

int main() {

    system("mode con cols=230 lines=60");
    while (1) {
        system("color fc");
        Sleep(1);
        system("color e3");
        Sleep(1);
        system("color 9a");
        Sleep(1);
        system("color c2");
        Sleep(1);
    }
    return 0;
}