基础

可重复集全排列

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    s.pop_back();
    sort(s.begin(),s.end());
    do{
        cout<<s<<' ';
    }while(next_permutation(s.begin(),s.end()));
    system("pause");
    return 0;
}


快速幂

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 100000007
ll fastpow(ll x,ll y){
    if(y==0) return 1;
    ll tmp=fastpow(x,y/2)%MOD;
    ll t=(tmp*tmp)%MOD;
    if(y%2==0) return t%MOD;
    else return t*x%MOD;
}
int main(){
    int x;
    while(cin>>x){
        ll ans=0;
        for(int i=1;i<=x;i++){
            ll t=fastpow(i,i)%MOD;
            ans=(ans+t)%MOD;
        }
        cout<<(ans+1)%MOD<<endl;
    }
    system("pause");
    return 0;
}

第 k 小

#include<bits/stdc++.h>
using namespace std;
int n,k;
int v[1000010];
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    sort(v,v+n);
    cout<<v[k-1];
    system("pause");
    return 0;
}

内部收益率

// 二分

#include<bits/stdc++.h>
using namespace std;
const int N=12;
const double eps=1e-6;
int cf[N];
int main(){
    int t;
    while (~scanf("%d",&t))
    {
        if(t==0) break;
        for(int i=0;i<=t;i++){
            cin>>cf[i];
        }
        double l=-1e6,r=1e6,x,npv=0;
        while(1){
            npv=cf[0];
            x=(l+r)/2;
            for(int i=1;i<=t;i++){
                npv+=cf[i]/pow(x,i);
            }
            if(fabs(npv)<=eps) break;
            if(npv<0){
                r=x;
            }else{
                l=x;
            }
        }
        printf("%.2f\n",x-1);
    }

    system("pause");
    return 0;
}

跳台阶

// 斐波那契
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        if(n==1||n==2){
            cout<<1<<endl;
            break;
        }
        n--;
        int a=1,b=1,c;
        while(n--){
            c=(a+b)%1000000007;
            b=a;
            a=c;
        }
        cout<<c<<endl;
    }
    //system("pause");
    return 0;
}

模拟

数据加密

密码学是研究编制密码和破译密码的技术科学。研究密码变化的客观规律，应用于编制密码以保守通信秘密的，称为编码学；应用于破译密码以获取通信情报的，称为破译学，总称密码学。密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照这些法则，变明文为密文，称为加密变换；变密文为明文，称为脱密变换。密码在早期仅对文字或数码进行加、脱密变换，随着通信技术的发展，对语音、图像、数据等都可实施加、脱密变换。
现在要求你用下面给定的方法对数据实现加密。给定长度为 n 的字符串 S（1<=n<=2000,S 中只有大写字母）作为明文，要求构造一个字符串 T 作为密文，起初 T 是一个空串，之后反复执行以下任意操作

1.从 S 的头部删除一个字符，加入到 T 的尾部 2.从 S 的尾部删除一个字符，加入到 T 的尾部

最后 S 会变成空串，T 会变成一个长度为 n 的字符串作为密文。当然并非所有的构造方案都是符合条件的，我们要求构造出的密文 T 的字典序尽可能小，你能找出这个字典序最小的密文吗？

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        string s;
        cin>>s;
        int p1=0,p2=n-1;
        for(int i=0;i<n;i++){
            int ok=1;
            int l=p1,r=p2;
            while(l<r){
                if(s[l]<s[r]){
                    ok=1;
                    break;
                }else if(s[l]>s[r]){
                    ok=0;
                    break;
                }else{
                    l++;
                    r--;
                }
            }
            if(ok){
                cout<<s[p1];
                p1++;
            }else{
                cout<<s[p2];
                p2--;
            }
        }
    }
    system("pause");
    return 0;
}

动态规划

0-1 背包

// f[j]=max(f[j],f[j-v[i]]+w[i])
// j--

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N];
int v[N],w[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
    return 0;
}

完全背包

// f[j]=max(f[j],f[j-v[i]]+w[i])
// j++

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N];
int v[N],w[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=v[i];j<=m;j++){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
    return 0;
}

沙子的质量

设有 N 堆沙子排成一排，其编号为 1，2，3，…，N（N< =300）。每堆沙子有一定的数量，可以用一个整数来描述，现在要将 N 堆沙子合并成为一堆，每次只能合并相邻的两堆，合并的代价为这两堆沙子的数量之和，合并后与这两堆沙子相邻的沙子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同，如有 4 堆沙子分别为 1 3 5 2 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2 又合并 1，2 堆，代价为 9，得到 9 2，再合并得到 11，总代价为 4+9+11=24，如果第二步是先合并 2，3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22；问题是：找出一种合理的方法，使总的代价最小。输出最小代价。

// 状态转移方程
// dp[i][j]表示[i,j]区间合并最小代价
// dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1])


#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N],s[N],dp[N][N];
int main(){
    int n,t;
    cin>>n;
    for(int i=1;i<=n;i++){ // 1开始
        cin>>s[i];
        s[i]+=s[i-1];
    }
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            dp[i][j]=0x3fffffff; //初始化
            for(int k=i;k<=j;k++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
            }
        }
    }
    cout<<dp[1][n];
    system("pause");
    return 0;
}

最长公共子序列

// dp[i][j] a的前i位和b的前j位最长公共子序列长度
// dp[i][j]=dp[i-1][j-1] a[i]=b[j]
// dp[i][j]=max(dp[i-1][j],dp[i][j-1]) a[i]!=b[j]


#include<bits/stdc++.h>
using namespace std;
const int N=2010;
char a[N],b[N];
int dp[N][N];
int main(){
    cin>>a+1>>b+1;
    int l1=strlen(a+1);
    int l2=strlen(b+1);
    for(int i=1;i<=l1;i++){
        for(int j=1;j<=l2;j++){
            if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    cout<<dp[l1][l2];
    system("pause");
    return 0;
}

三角形的路径权

如输入样例所示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。每一步可沿左斜线向下或右斜线向下走；1< 三角形行数< 25；三角形中的数字为整数< 1000；

// dp[i][j] 第i行第j列为路径顶点的最大路径权的长度
// dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];


#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N][N],dp[N][N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=1;j<=i;j++){
            dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
        }
    }
    cout<<dp[1][1];
    system("pause");
}

字母排序

XXXX 年突然有外星人造访，但大家语言不通，不过科学家们经过研究发现外星人用 26 个英文字母组成的单词中最长不降子序列的长度来表述数字，且英文字母的排列顺序不同，现给出其排列顺序，再给出外星人说的每个数字（其实是每个英文单词，用空格隔开），翻译出外星人所说的数字（连续输出，最后加回车）。(因为是最长不降子序列，所以数字中没有 0，也就是说外星人的数字是大于 0 的数字)。例如，我们正常的字母排列顺序是 abcdefg…….xyz，代表 a< b< c< …..< x< y< z abcd efg hhh ihg 四个字符串的最长不降子序列的长度分别为 4 3 3 1。

// 最长上升子序列
// dp[i] 以a[i]结尾的最长上升子序列的长度
// dp[i]=max(dp[i],dp[j]+1) dp[i]初始化为1


#include<bits/stdc++.h>
using namespace std;
const int N=300;
int dp[N];
map<char,int> al;
// dp[i]=max(dp[j])+1 | 1
int main(){
    string s;
    cin>>s;
    int l1=s.length();
    for(int i=0;i<l1;i++){
        al[s[i]]=i;
    }
    while (cin>>s)
    {
        int ans=0;
        memset(dp,0,sizeof(dp));
        l1=s.length();
        for(int i=0;i<l1;i++){
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(al[s[i]]>=al[s[j]])
                dp[i]=max(dp[i],dp[j]+1);
            }
            ans=max(ans,dp[i]);
        }
        cout<<ans;
    }

    system("pause");
    return 0;
}

最长子序列

在一个数组中找出和最大的连续几个数。（至少包含一个数）

例如：

数组 A[] = [-2,1,-3,4,-1,2,1,-5,4]，则连续的子序列[4,-1,2,1]有最大的和 6.

// dp[i]以a[i]结尾的最大子序列和
// dp[i]=max(a[i],dp[i-1]+a[i])


#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N],dp[N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int u=-0x3fffffff;
    for(int i=1;i<=n;i++){
        dp[i]=max(a[i],dp[i-1]+a[i]);
        u=max(u,dp[i]);
    }
    cout<<u<<endl;
    system("pause");
    return 0;
}

简单的密码

密码是按特定法则编成，用以对通信双方的信息进行明密变换的符号。密码是隐蔽了真实内容的符号序列。其实就是把用公开的、标准的信息编码表示的信息通过一种变换手段，将其变为除通信双方以外其他人所不能读懂的信息编码，这种独特的信息编码就是密码。

现在我们定义一种非常简单的密码，它的长度固定为 n（n<=30）并且每一位只能由数字 0 或者数字 1 组成，但是有一个特殊的要求：一个密码序列中至少要有连续的 3 个 0 出现才可以，否则就是无效的。现在给定你密码序列的长度 n，你的任务是计算长度为 n 的序列能产生多少种不同的并且有效的密码？

// 递推公式，不像dp
// dp[i]=dp[i-1]*2+(1<<(i-4))-dp[i-4];

#include<bits/stdc++.h>
using namespace std;
int dp[40]={0,0,0,1};
int main(){
    int n;
    for(int i=4;i<=30;i++){
        dp[i]=2*dp[i-1]+(1<<(i-4))-dp[i-4];

    }
    while(cin>>n){
        cout<<dp[n]<<endl;
    }
    system("pause");
    return 0;
}

贪心

跳跃游戏 2

给定一个非负整数数组，假定你的初始位置为数组第一个下标。数组中的每个元素代表你在那个位置能够跳跃的最大长度。你的目标是到达最后一个下标，并且使用最少的跳跃次数。例如：A = [2,3,1,1,4]，到达最后一个下标的最少跳跃次数为 2。（先跳跃 11 步，从下标 0 到 1，然后跳跃 3 步，到达最后一个下标。一共两次）

两种方法第一种好理解，第二种时间复杂度低

倒着遍历

比较好理解，贪心的选择距离终点最远能跳到终点的位置

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int a[N];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int t=n-1;
    int ans=0;
    while(t>0){
        for(int i=0;i<t;i++){
            if(i+a[i]>=t){
                cout<<i+a[i]<<endl;
                t=i;
                ans++;
                break;
            }
        }
    }
    cout<<ans;
    system("pause");
    return 0;
}


正着遍历

难理解，但是 O(n)的复杂度

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int a[N];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int ans=0;
    int m=0; // 当前能够到达的最大下标位置
    int end=0; // 上次跳跃范围的边界|下次起跳的起点
    for(int i=0;i<n-1;i++){ //注意这里是n-1
        if(m>=i){
            m=max(m,i+a[i]); // 维护能跳到的最远范围
            if(i==end){ // 到达边界
                end=m; // 更新边界
                ans++;
            }
        }
    }
    cout<<ans;
    system("pause");
    return 0;
}

Homework

临近开学了，大家都忙着收拾行李准 备返校，但 I_Love_C 却不为此担心! 因为他的心思全在暑假作业上：目前为止还未开动。

暑假作业是很多张试卷，我们这些从试卷里爬出来的人都知道，卷子上的题目有选择题、填空题、简答题、证明题等。而做选择题的好处就在于工作量很少，但又因为选择题题目都普遍很长。如果有 5 张试卷，其中 4 张是选择题，最后一张是填空题，很明显做最后一张所花的时间要比前 4 张长很多。但如果你只做了选择题，虽然工作量很少，但表面上看起来也已经做了 4/5 的作业了。

I_Love_C 决定就用这样的方法来蒙混过关，他统计出了做完每一张试卷所需的时间以及它做完后能得到的价值（按上面的原理，选择题越多价值当然就越高咯）。

现在就请你帮他安排一下，用他仅剩的一点时间来做最有价值的作业。

贪心策略： 先做价值高的作业

// 多组测试数据

#include<bits/stdc++.h>
using namespace std;
const int N=10000+10;
struct node{
    int t,v;
    double a;
}nd[N];
int cmp(node x,node y){
    return x.a>y.a;
}
int main(){
    int m,n;
    while(cin>>m>>n){
        if(m==0&&n==0) break;
        int t1,t2;
        for(int i=0;i<m;i++){
            cin>>t1>>t2;
            nd[i].t=t1;
            nd[i].v=t2;
            nd[i].a=1.0*t2/t1;
        }
        sort(nd,nd+m,cmp);
        int ans=0;
        double sum=0.0;
        for(int i=0;i<m;i++){
            if(nd[i].t+ans>n){
                sum+=(n-ans)*nd[i].a;
                break;
            }else{
                sum+=nd[i].v;
                ans+=nd[i].t;
            }
        }
        printf("%.2f\n",sum);
    }
    system("pause");
    return 0;
}

区间包含问题

已知 n 个左闭右开区间 [a,b)，对其进行 m 次询问，求区间[l,r]最多可以包含 n 个区间中的多少个区间，并且被包含的所有区间都不相交。

贪心策略： 优先选择早结束的

// 多组测试数据

#include<bits/stdc++.h>
using namespace std;
const int N=100000+10;
struct node{
    int s,e;
}nd[N];
int cmp(node x,node y){
    return x.e<y.e;
}
int main(){
    int n,m,t1,t2,l,r;
    while(cin>>n>>m){
        for(int i=0;i<n;i++){
            cin>>nd[i].s>>nd[i].e;
        }
        sort(nd,nd+n,cmp);
        for(int i=0;i<m;i++){
            cin>>l>>r;
            int ans=0;
            for(int i=0;i<n;i++){
                if(nd[i].e>r) break;
                if(nd[i].s>=l){
                    l=nd[i].e;
                    ans++;
                }
            }
            cout<<ans<<endl;
        }
    }
    system("pause");
    return 0;
}

三值排序

排序是一种很频繁的计算任务。一个实际的例子是，当我们给某项竞赛的优胜者按金银铜牌排序的时候。在这个任务中可能的值只有三种 1，2 和 3。我们用交换的方法把他排成升序的。

写一个程序计算出，计算出的一个包括 1、2、3 三种值的数字序列，排成升序所需的最少交换次数。

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N],b[N];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    int ans1=0,ans2=0;
    sort(a,a+n);
    for(int i=0;i<n;i++){
        int t=b[i]-a[i];
        if(t>0) ans1++;
        else if(t<0) ans2++;
    }
    cout<<max(ans1,ans2);
    system("pause");
    return 0;
}

法师康的工人

三个法师康的工人每天早上 6 点到工厂开始到三条产品生产线上组装桔子手机。第一个工人在 200 时刻开始（从 6 点开始计时，以秒作为单位）在生产线上开始生产，一直到 1000 时刻。第二个工人，在 700 时刻开始，在 1100 时刻结束。第三个工人从 1500 时刻工作到 2100 时刻。期间最长至少有一个工人在生产线上工作的连续时间为 900 秒（从 200 时刻到 1100 时刻），而最长的无人生产的连续时间（从生产开始到生产结束）为 400 时刻（1100 时刻到 1500 时刻）。

你的任务是用一个程序衡量 N 个工人在 N 条产品线上的工作时间列表（1≤N≤5000，以秒为单位）。

·最长的至少有一个工人在工作的时间段

·最长的无人工作的时间段（从有人工作开始计）

贪心策略： 优先选择开始时间早的

// 按开始时间从小到大排序


#include<bits/stdc++.h>
using namespace std;
const int N=5010;
struct node{
    int s,e;
}nd[N];
int cmp(node x,node y){
    return x.s<y.s;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>nd[i].s>>nd[i].e;
    }
    sort(nd,nd+n,cmp);
    int l=0,r=0;
    l=nd[0].s,r=nd[0].e;
    int ans=0,MAX=-1,MAX2=-1;
    for(int i=1;i<n;i++){
        if(nd[i].s<=r&&nd[i].e>r){
            r=nd[i].e;
        }else if(nd[i].s>r){
            ans=r-l;
            MAX=max(MAX,ans);
            l=nd[i].s;
            MAX2=max(MAX2,l-r);
            r=nd[i].e;
        }
    }
    cout<<MAX<<' '<<MAX2;
    system("pause");
    return 0;
}

回溯

八皇后问题

努比亚和苏丹没有子女，所以他要从一些有集成资格的继承者中挑选一个出来继承王位。他希望这个继承者足够聪明，所以他准备了一个西洋棋盘，上面的每个格子中均有一个 1-99 的数字。他又准备了 8 个皇后棋子。

8 皇后的规则就是不能有任何棋子同行或者同列或者同斜线，在满足这个规则的同时，王位继承者还需要让 8 个皇后所在的位置的数字的和是最大的。

// 八皇后

#include<bits/stdc++.h>
using namespace std;
const int N=10;
int c[N],a[100][100];
int maxvalue;
void dfs(int cur){
    if(cur>8){
        int ans=0;
        for(int i=1;i<=cur;i++){
            ans+=a[i][c[i]];
        }
        maxvalue=max(maxvalue,ans);
        return;
    }else
    for(int i=1;i<=8;i++){
        int ok=1;
        c[cur]=i;
        for(int j=1;j<cur;j++){
            if(c[cur]==c[j]||abs(c[cur]-c[j])==abs(cur-j)){
                ok=0;
                break;
            }
        }
        if(ok) dfs(cur+1);
        // c[cur]=0;
    }
}
int main(){
    int k;
    cin>>k;
    while(k--){
        maxvalue=-1;
        memset(a,0,sizeof(a));
        memset(c,0,sizeof(c));
        for(int i=1;i<=8;i++){
            for(int j=1;j<=8;j++){
                cin>>a[i][j];
            }
        }
        dfs(1);
        cout<<maxvalue<<endl;
    }
    system("pause");
    return 0;
}

2n 皇后问题

给定一个 n*n 的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入 n 个黑皇后和 n 个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n 小于等于 8。

// 先放黑的再放白的

#include<bits/stdc++.h>
using namespace std;
const int N=100;
int n;
int a[N][N];
int cblack[N],cwhite[N];
int sum;
void dfs2(int cur){
    if(cur>n){
        sum++;
        return;
    }
    for(int i=1;i<=n;i++){
        if(!a[cur][i]) continue; // 不要放在里面判断，否则cur=1时会跳过判断
        cwhite[cur]=i;
        int ok=1;
        for(int j=1;j<cur;j++){
            if(cwhite[cur]==cwhite[j]||abs(cwhite[cur]-cwhite[j])==cur-j||cblack[cur]==i){
                ok=0;
                break;
            }
        }
        if(ok) dfs2(cur+1);
        // cwhite[cur]=0;
    }
}
void dfs1(int cur){
    if(cur>n){
        dfs2(1);
        return;
    }else for(int i=1;i<=n;i++){
        if(!a[cur][i]) continue;
        cblack[cur]=i;
        int ok=1;
        for(int j=1;j<cur;j++){
            if(cblack[cur]==cblack[j]||abs(cblack[cur]-cblack[j])==abs(cur-j)){
                ok=0;
                break;
            }
        }
        if(ok){
            // a[cur][i]=0;
            dfs1(cur+1);
        }
    }
}
int main(){
    cin>>n;
    sum=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    dfs1(1);
    cout<<sum;
    system("pause");
    return 0;
}

组合运算式

请考虑一个被空格分隔的，由 1 到 N 的整数组成的递增数列：1 2 3 …N。现在请在数列中插入表示加的“+”，或者表示减“-”，亦或者表示空白的“ ”(例如 1-2 3 就等于 1-23)，来将每一对数字组合成一个表达式（第一个数字前无空格）。计算该表达式的结果并判断其值是否为 0。请你写一个程序找出所有产生和为零的长度为 N 的数列。

感觉是最难的了，用 py 写的，不得不说 py 真是神中神，c++还要写计算字符串的函数。。。


n=int(input())
cnt=0
s=[]
def dfs(i):
    global s,cnt,n
    if(i==n):
        s+=str(i)
        ss=''.join(s)
        sss=ss.replace(' ','')
        if eval(sss)==0:
            print(ss)
            cnt+=1
        s.pop()
        return
    t=str(i)
    s+=t
    s+=' '
    dfs(i+1)
    s.pop()
    s+='+'
    dfs(i+1)
    s.pop()
    s+='-'
    dfs(i+1)
    s.pop()
    s.pop()

dfs(1)

无脑博士的试管们

无脑博士有三个容量分别是 A,B,C 升的试管，A,B,C 分别是三个从 1 到 20 的整数，最初，A 和 B 试管都是空的，而 C 试管是装满硫酸铜溶液的。有时，无脑博士把硫酸铜溶液从一个试管倒到另一个试管中，直到被灌试管装满或原试管空了。当然每一次灌注都是完全的。由于无脑博士天天这么折腾，早已熟练，溶液在倒的过程中不会有丢失。

写一个程序去帮助无脑博士找出当 A 试管是空的时候，C 试管中硫酸铜溶液所剩量的所有可能性。

#include<bits/stdc++.h>
using namespace std;
const int N=30;
int vis[N][N][N];
int cnt[N]; //全局声明数组不用初始化 主函数内部需要
int A,B,C;
void dfs(int a,int b,int c){
    if(vis[a][b][c]) return;
    vis[a][b][c]=1;
    if(a>0){
        (a+b>B)?dfs(a-(B-b),B,c):dfs(0,a+b,c);
        (a+c>C)?dfs(a-(C-c),b,C):dfs(0,b,a+c);
    }
    if(b>0){
        (b+a>A)?dfs(A,b-(A-a),c):dfs(a+b,0,c);
        (b+c>C)?dfs(a,b-(C-c),C):dfs(a,0,b+c);
    }
    if(c>0){
        (c+a>A)?dfs(A,b,c-(A-a)):dfs(a+c,b,0);
        (c+b>B)?dfs(a,B,c-(B-b)):dfs(a,b+c,0);
    }
}

int main(){
    memset(vis,0,sizeof(vis));
    // memset(cnt,0,sizeof(cnt));
    cin>>A>>B>>C;
    dfs(0,0,C);
    for(int i=0;i<=B;i++){
        for(int j=0;j<=C;j++){
            if(vis[0][i][j]) cnt[j]=1;
        }
    }
    for(int i=0;i<=C;i++){
        if(cnt[i]) cout<<i<<' ';
    }
    system("pause");
    return 0;
}

图的 m 着色问题

请考虑一个被空格分隔的，由 1 到 N 的整数组成的递增数列：1 2 3 …N。现在请在数列中插入表示加的“+”，或者表示减“-”，亦或者表示空白的“ ”(例如 1-2 3 就等于 1-23)，来将每一对数字组合成一个表达式（第一个数字前无空格）。计算该表达式的结果并判断其值是否为 0。请你写一个程序找出所有产生和为零的长度为 N 的数列。

// 顶点从1开始不是从0开始。。。

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int G[N][N];
int n,k,m;
int sum,c[N];
bool ok(int u){
    for(int i=0;i<u;i++){
        if(G[u][i]==1&&c[u]==c[i]) return false;
    }
    return true;
}
void dfs(int u){
    if(u==n+1){
        sum++;
        return;
    }
    for(int i=1;i<=m;i++){
        c[u]=i;
        if(ok(u)) dfs(u+1);
        c[u]=0;
    }
}
int main(){
    cin>>n>>k>>m;
    int t1,t2;
    sum=0;
    memset(c,0,sizeof(c));
    memset(G,0,sizeof(G));
    for(int i=0;i<k;i++){
        cin>>t1>>t2;
        G[t1][t2]=G[t2][t1]=1;
    }
    dfs(1);
    cout<<sum;
    system("pause");
    return 0;
}

有趣的素数

素数被广泛地应用于密码学中，所谓的公钥就是将想要传递的信息在编码时加入砠数，编码之后传给收信人，任何人收到此信息之后，若没有此收信人所拥有的秘钥，则在解密的过程中将会因为分解质因数过久而无法破解信息，可见素数在密码学中的重要性。
现在给你 n（2<=n<=16）个正整数 1,2,3…n，你的任务是把这 n 个正整数组成一个环，使得任意相邻的两个整数之和为一个素数，输出有多少种合法方案。

#include<bits/stdc++.h>
using namespace std;
const int N=40;
bool prime[N],vis[N]={false};
int a[N],n,cnt;
bool isprime(int x){
    if(x==1) return false;
    for(int i=2;i<=sqrt(x);i++){ // 用= 😅
        if(x%i==0) return false;
    }
    return true;
}
void dfs(int s){
    if(s==n){
        if(prime[a[s-1]+1]){
            // for(int i=0;i<n;i++){
            //     cout<<a[i]<<' ';
            // }
            // cout<<endl;
            cnt++;
        }
        return;
    }
    for(int i=2;i<=n;i++){
        if(!vis[i]&&prime[i+a[s-1]])
        {
            a[s]=i;
            vis[i]=1;
            dfs(s+1);
            vis[i]=0;
        }

    }
}
int main(){
    for(int i=1;i<=36;i++){
        prime[i]=isprime(i);
    }
    while(cin>>n){
        cnt=0;
        memset(a,0,sizeof(a));
        memset(vis,0,sizeof(vis));
        a[0]=1;
        dfs(1);
        cout<<cnt<<endl;
    }
    system("pause");
    return 0;
}