洛古P1036 选数 题解

[我是传送门]

这是一道很经典的深搜与回溯(难度一般)

可是就这个"普及-"

让本蒟蒻做了一晚上+半个上午(实际我不会深搜回溯,全靠框架+去重);

下面让我分享下本蒟蒻的(全排列+暴搜去重)

#include<bits/stdc++.h>

using namespace std;

int n,r,ttt;//n是总数,r是选的数,ttt是答案

int a[],b2[],c[][];//a用来储存排列的编号,b2用来储存输入的数,c用来去重(储存符合条件的数组的编号)

bool b[];//用来判断是否用过

bool ss2(int t[]){//暴搜判重

    int tot=;//计数器

    for(int i=;i<=ttt;i++){//循环所有储存的数组

        for(int j=;j<=r;j++){//循环r次,比较每一个字符

            if(t[j] != c[i][j])//判重

                tot++;

        }

        if(tot==)//如果没有一个不一样的说明重复

            return ;

        tot=;//一定要清空!!!!

    }

    return ;//如果全不重复,说明不重

}

bool sus(int y){//判断素数

    if(y==||y==)//防止特殊值

        return ;

    if(y==)

        return ;

    for(int i=;i<=sqrt(y);i++){//循环到sqrt就够了

        if(y%i==)

            return ;

    }

    return ;

}

void print(){//其实不能叫print,因为没有输出

    int y=;

    int b3[r+];//定义新数组避免动原先(a)数组

    for(int i=;i<=r;i++)//判断素数

        y+=b2[a[i]];

    if(sus(y)==){//不是素数直接跳过

        for(int i=;i<=r;i++)

            b3[i]=a[i];

        sort(b3+,b3+r+);//一定要排序,因为类似"组合"

        if(ss2(b3)==){//如果不重复

            u++;//这一步可以不要

            ttt++;//答案加1

            for(int i=;i<=r;i++)

                c[u][i]=b3[i] ;//如果不要u++这里u要换成ttt

        }

    }

}

void ss(int k){//程序主体

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

        if(b[i] ==){//只要没标记过就能用

            a[k]=i;//记录编号

            b[i]=;//标记

            if(k==r) print();//到了r"输出"

            else ss(k+);//否则继续

            b[i]=;//回溯

        }

    }

}

int main(){

    cin>>n>>r;//输入

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

        cin>>b2[i];

    ss();//深搜

    cout<<ttt;//输出答案

    return ;

}