PJ可能会考的模拟与枚举-自学教程

文/Pleiades_Antares

之前学校里看一个小可爱复习的时候偷偷听来着XD

简单记了一下重点吧，希望能对看官您有所帮助XD

以下⬇️是几个复习时讲过的题，里面放了一下笔记啦！重点是笔记和方法昂

然后过几天我会出一个NOIP初赛复习的帖子吧带着大家过一遍。

程序是次要的重点是理解+文字，因为是上课顺便记的草稿，所以很多是不全的orz

表达式求值

//

//  表达式求值.cpp

//

//

//

//scanf

//"%[]"

//luoguP1981

#include <cstdio>

#include<iostream>

using namespace std;

const int maxn=100050;

int a[maxn];

char op[maxn];

int main(){

    int n=0;

    while(scanf("%d%[+*]",&a[n],&op[n])==2) {

        n++;

    }

    n++;

    //不结束就一直乘下去

    int ans=0;

    for(int i=0;i<n;i++){

        int t=a[i]%10000;

        for(;i<n&&op[i]=='*';i++){

            t*=a[i+1];

            t%=10000;

        }

        ans+=t;

        ans%=10000;

    }

    printf("%d\n",ans);

    return 0;

}

寻宝

//

//  寻宝.cpp

//

//

//

//

#include <cstdio>

#include<iostream>

using namespace std;

int main(){

    return 0;

}

//模拟这里常见的问题

//模拟题目需要清晰的思路，找到尽量简洁的实现，这些取决于平时的积累也就是刷题量。这方面代码能力的提升不仅是靠刷模拟题，在做各种题目的时候，注意其代码实现的方式，也可以参考一些经验丰富的人的做法，这一点在以后的学习之路上都是适用的。

选数

//

//  选数.cpp

//

//

//

//

//P1036

//枚举精讲内容题目1

#include <cstdio>

#include<iostream>

using namespace std;

const int maxn=25;

int n,k;

int x[maxn];

int ans;

bool isPrime(int a){

    if (a==2||3) return 1;

    for(int i=2;i*i<=a;i++){

        if (a%i==0) return 0;

    }

    return 1;

}

void dfs(int cnt,int now,int sum){

    if (now==n){

        if (cnt==k&&isPrime(sum)){

            ans++;

        }

    }

    else{

        dfs(cnt,now+1,sum);

        dfs(cnt+1,now+1,sum+x[now]);

    }

}

int main(){

    cin>>n>>k;

    for(int i=1;i<=n;i++){

        cin>>x[i];

    }

    dfs(0,0,0);

    cout<<ans<<endl;

    return 0;

}

//DFS枚举

//非常重要的一段DFS代码！！

int ans;

int a[maxn];

int n,k;

void dfs(int now,int cnt,int s){

    if (now==n){

        if (cnt==k&&isPrime(s)){

            ans++;

        }

    }

    else{

        dfs(now+1,cnt,s);//第一种情况，不选这个数

        dfs(now+1,cnt+1,s+a[now]);//选了的话

    }

}

dfs(0,0,0);

//DFS枚举排列

int ans,n,p[maxn];

bool flag[maxn];

void dfs(int now){

    if (test(p)) {

        ans++;

    }

    else {

        for(int i=1;i<=n;i++){

            if (!flag[i]){

                p[now]=i;

                flag[i]=true;

                dfs(now+1);

                flag[i]=false;

            }

        }

    }

}

dfs(0);

//DFS：用递归来枚举很多很多的变量

//图论DFS是寻找最短路，但是这个主要是寻找解什么的...

//更高效的枚举集合

//前置知识：位运算

//将最低位记作第0位，二进制表示第i位为1则表示取集合中的第i位元素

for(int state=0;state<(1<<n);state++){

    int s=0;

    for(int i=0;i<n;i++){

        if (state&(1<<i)){

            s+=a[i];

        }

    }

}

//更高效的枚举排列

//algorithm

//std::next_permutation

//std::prev_permutation

//STL中的函数，接受两个参数表示数组的起止位置。

//会将数组变为对应的下/上一个排列

//如果当前数组是最后一个排列，则变为第一个排列，并且返回false，否则返回true

//时间复杂度O（n）

#include<algorithm>

int p[maxn];

for(int i=0;i<n;i++){

    p[i]=i+1;

}

do{

    test(p);

}while(std::next_permutation(p,p+n));

//test是啥？比如判断是否是最优的解或者计数的东西等等等等...

火星人

//

//  火星人.cpp

//

//

//

//

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=10005;

int n;

int m;

int a[maxn];

int main(){

    cin>>n>>m;

    for(int i=1;i<=n;i++){

        cin>>a[i];

    }

    for(int i=1;i<=m;i++){

        next_permutation(a+1,a+1+n);

    }

    for(int i=1;i<=n;i++){

        cout<<a[i]<<" ";

    }

    return 0;

}

//小结：以上两种方法，对特定的枚举都有显著减少代码长度和常数的优势

//但是当无用状态较多的时候，DFS可以设计各种剪枝优化，能过掉更大的数据

导弹拦截，只给思路

//

//  导弹拦截.cpp

//

//

//  Created by demi on 2018/10/1.

//

#include<iostream>

#include<cstdio>

using nameespace std;

int n;

struct T {

    ll d1,d2;

    T(){}

}

int n;

int

//由于实际要取的是数组后缀的导弹距离第二个系统距离最大值，可以预处理

//按照后缀从短到长处理，每次添加一个导弹，维护最大值

另外一道经典题目

//

//  another练习.cpp

//

//

//

//

//题目描述

//给出一个正整数集合，求出有多少组数，满足（a+b-c）*d/e=f，且六个数均在集合内

//注：

int cnt[maxn],ans;

for(int f=0;f<n;f++){

    cnt[x[f]]++;

}

for(int a=0;a<n;a++){

    for(int b=0;b<n;b++){

        for(int c=0;c<n;c++){

            for(int d=0;d<n;d++){

                for(int e=0;e<n;e++){

                    ans+=cnt[(x[a]+x[b]-x[c])*x[d]/x[e]];

                }

            }

        }

    }

}

//难道要这个样子吗？

//错误1:没有处理不能整除（WA）

//错误2:没有判断负数（RE）

//Meet-in-他和-middle

int cnt[maxn],ans;

for(int f=0;f<n;f++){

    for(int e=0;e<n;e++){

        for(int d=0;d<n;d++){

            if (!x[f]*f[e]%f[d]&& x[f]*f[e]/f[d] < maxn ){

                cnt[x[f]*f[e]/f[d]]++;

            }

        }

    }

}

for(int a=0;a<n;a++){

    for(int b=0;b<n;b++){

        for(int c=0;c<n;c++){

            if (x[a]+x[b]-x[c])

        }

    }

}

//有多个变量需要枚举时，可以枚举一部分，计算出中间值

//再枚举另一个部分，寻找是否有对应的中间值

//寻找部分可用到二分查找或者std：：set

经典题目+1

//

//  经典题目加一.cpp

//

//

//

//

#include<iostream>

#include<cstdio>

using namespace std;

//思路1:枚举每个区间的左右端点，再循环求和，O（n三次方）

//思路2:枚举左端点后考虑合法的右端点，

//可以发现是左端点后面的一段连续区间

//找到最大的右端点，计数即可。O（n方）

Two-Pointers

int ans=0;

int l,r,tsum;

for(l=0;l<n;l++){

    for(;tsum+a[r]<=k&&r<n;r++){

        tsum+=a[r];

    }

    ams+=r-l;

    tsum-=a[l];

}

然后说明一下MAC端怎么编程

Xcode很好用呐完全不需要用在线IDE（当然有一些特别好看还是值得用的233）

据说很火的sublime是编辑器不是编译器！！！

but很多人不会用xcode

这里说一下：

运行terminal配合xcode完全OK

mac os应该是内置的g++和c++

输入如下图指令（图片来源：洛谷IDdemi用户，已获得授权）

可能我太老了还在用原始方法吧qwq

巴特西

PJ可能会考的模拟与枚举-自学教程

PJ可能会考的模拟与枚举-自学教程

文/Pleiades_Antares

之前学校里看一个小可爱复习的时候偷偷听来着XD

简单记了一下重点吧，希望能对看官您有所帮助XD

以下⬇️是几个复习时讲过的题，里面放了一下笔记啦！重点是笔记和方法昂

程序是次要的重点是理解+文字，因为是上课顺便记的草稿，所以很多是不全的orz

表达式求值

寻宝

选数

火星人

导弹拦截，只给思路

另外一道经典题目

经典题目+1

最新文章

热门文章