1.凑算式
如图，这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。
比如：
6+8/3+952/714 就是一种解法，
5+3/1+972/486 是另一种解法。
这个算式一共有多少种解法？
思路：暴力解决，注意每个字母代表的数字不相等。
答案：29
#include<iostream>
using namespace std;
int main(){
int count=0;
for(int a=1;a<10;a++){
for(int b=1;b<10;b++){
if(a==b)continue;
for(int c=1;c<10;c++){
if(a==c||b==c)continue;
for(int d=1;d<10;d++){
if(a==d||b==d||c==d)continue;
for(int e=1;e<10;e++){
if(a==e||b==e||c==e||d==e)continue;
for(int f=1;f<10;f++){
if(a==f||b==f||c==f||d==f||e==f)continue;
for(int g=1;g<10;g++){
if(a==g||b==g||c==g||d==g||e==g||f==g)continue;
for(int h=1;h<10;h++){
if(a==h||b==h||c==h||d==h||e==h||f==h||g==h)continue;
for(int i=1;i<10;i++){
if(a==i||b==i||c==i||d==i||e==i||f==i||g==i||h==i)continue;
int t1=a*c*(g*100+h*10+i);
int t2=b*(g*100+h*10+i);
int t3=c*(d*100+e*10+f);
int t=10*c*(g*100+h*10+i);
if(t1+t2+t3==t)count++;
}
}
}
}
}
}
}
}
}
cout<<count<<endl;
return 0;
}
2.ADV-205算法提高 拿糖果（动态规划）
问题描述
妈妈给小B买了N块糖！但是她不允许小B直接吃掉。
假设当前有M块糖，小B每次可以拿P块糖，其中P是M的一个不大于根号下M的质因数。这时，妈妈就会在小B拿了P块糖以后再从糖堆里拿走P块糖。然后小B就可以接着拿糖。
现在小B希望知道最多可以拿多少糖。
输入格式
一个整数N
输出格式
最多可以拿多少糖
样例输入
15
样例输出
6
数据规模和约定
N <= 100000
【思路】：
动态规划的思想，设已经拿了n块糖，则最终最多可以拿的糖取决于从剩下的M块糖里，最多可以拿多少糖，则有
solve(M,n)=n+MAX(M)
而MAX(M)=max{solve((M-2P1),P1),solve((M-2P2),P2),solve((M-2*P3),P3)….}
所以有solve(M,n)=n+max{solve((M-2P1),P1),solve((M-2P2),P2),solve((M-2*P3),P3)….}
求MAX(M)的过程可以在循环中做，最后将MAX(M)的保存在数组里，优化递归，减少运算。
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=100000+10;
int MAX[maxn];
int is_zhishu(int n){
for(int i=2;i<=sqrt(n);i++)
if(n%2==0) return 0;
return 1;
}
int solve(int M,int n){
if(MAX[M]>=0) return MAX[M]+n;
int t=0,max=0;
for(int i=2;i<=sqrt(M);i++){//循环求MAX[M]
if(M%i==0&&is_zhishu(i))
t=solve(M-i*2,i);
if(max<t) max=t;
}
return (MAX[M]=max)+n;
}
int main(){
int N;
scanf("%d",&N);
memset(MAX,-1,sizeof(MAX));
MAX[0]=0,MAX[1]=0,MAX[2]=0,MAX[3]=0;
printf("%d\n",solve(N,0));
return 0;
}
3.ADV-171 身份证号码升级
问题描述
从1999年10月1日开始，公民身份证号码由15位数字增至18位。(18位身份证号码简介)。
升级方法为：
1、把15位身份证号码中的年份由2位(7,8位)改为四位。
2、最后添加一位验证码。验证码的计算方案：
将前 17 位分别乘以对应系数 (7 9 10 5 8 4 2 1 6 3 7 9 10 5 8 4 2) 并相加，然后除以 11 取余数，0-10 分别对应 1 0 x 9 8 7 6 5 4 3 2.
请编写一个程序，用户输入15位身份证号码，程序生成18位身份证号码。假设所有要升级的身份证的四位年份都是19××年
输入格式
一个15位的数字串，作为身份证号码
输出格式
一个18位的字符串，作为升级后的身份证号码
样例输入
110105491231002
样例输出
11010519491231002x
数据规模和约定
不用判断输入的15位字符串是否合理
【思路】字符串模拟
#include<stdio.h>
int main(){
int i,sum=0;
int t[]={7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};
char end[]={'1','0','x','9','8','7','6','5','4','3','2'};
char id[19];
gets(id);
for(i=14;i>=6;i--)
id[i+2]=id[i];
id[6]='1';id[7]='9';
for(i=0;i<17;i++)
sum+=(id[i]-'0')*t[i];
id[17]=end[sum%11];
id[18]='\0';
puts(id);
return 0;
}