部分题 所有题见链接
链接：https://pan.baidu.com/s/1gqmAgmnPQcZ48U5zjrGyUg
提取码：jpoz
T3 方格填数
如下的10个格子
+--+--+--+
| | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | |
+--+--+--+
（如果显示有问题，也可以参看【图1.jpg】）
填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <cstring>
using namespace std ;
int ans = 0;
int check(int a[]){
if(a[0]-a[4]==-1||a[0]-a[4]==1)
return 0;
if(a[3]-a[4]==-1||a[3]-a[4]==1)
return 0;
if(a[5]-a[4]==-1||a[5]-a[4]==1)
return 0;
if(a[7]-a[4]==-1||a[7]-a[4]==1)
return 0;
if(a[8]-a[4]==-1||a[8]-a[4]==1)
return 0;
if(a[9]-a[4]==-1||a[9]-a[4]==1)
return 0;
if(a[1]-a[4]==-1||a[1]-a[4]==1)
return 0;
if(a[1]-a[5]==-1||a[1]-a[5]==1)
return 0;
if(a[1]-a[6]==-1||a[1]-a[6]==1)
return 0;
if(a[0]-a[5]==-1||a[0]-a[5]==1)
return 0;
if(a[2]-a[5]==-1||a[2]-a[5]==1)
return 0;
if(a[8]-a[5]==-1||a[8]-a[5]==1)
return 0;
if(a[9]-a[5]==-1||a[9]-a[5]==1)
return 0;
if(a[6]-a[5]==-1||a[6]-a[5]==1)
return 0;
if(a[6]-a[9]==-1||a[6]-a[9]==1)
return 0;
if(a[6]-a[2]==-1||a[6]-a[2]==1)
return 0;
if(a[3]-a[0]==-1||a[3]-a[0]==1)
return 0;
if(a[3]-a[7]==-1||a[3]-a[7]==1)
return 0;
if(a[8]-a[7]==-1||a[8]-a[7]==1)
return 0;
if(a[8]-a[3]==-1||a[8]-a[3]==1)
return 0;
if(a[9]-a[8]==-1||a[9]-a[8]==1)
return 0;
if(a[1]-a[0]==-1||a[1]-a[0]==1)
return 0;
if(a[1]-a[2]==-1||a[1]-a[2]==1)
return 0;
}
//手动全排列
void f(int k ,int a[]){
//出口
if(k == 10){
if(check(a)!= 0 ){
ans++;
}
return ;
}
for(int i = k; i<10 ; ++i){
{int temp = a[k] ; a[k] = a[i] ; a[i] = temp ;} //深入
f(k+1,a);
{int temp = a[k] ; a[k] = a[i] ; a[i] = temp ;} //回溯
}
}
void i2s(int x, string &basic_string) {
stringstream ss;
ss << x;
ss >> basic_string;
}
void s2i(string &basic_string , int &x ) {
stringstream ss;
ss << basic_string;
ss >> x;
}
void c2i(char &basic_string , int &x ) {
stringstream ss;
ss << basic_string;
ss >> x;
}
void c2s(char c , string & s){
stringstream stream;
stream << c;
s = stream.str();
}
//自动全排列
void f1(string s, int a[]){
do{
for(int i=0 ; i<10 ; ++i){
int temp ;
// string temps ;
// c2s (s[i],temps);
// s2i(temps,temp);
c2i(s[i],temp);
a[i] = temp ;
}
check(a);
}while(next_permutation(s.begin(),s.end()));
}
int main(){
//int a[10]={0,1,2,3,4,5,6,7,8,9};
//f(0,a);
int a[10];
string s ="0123456789" ;
f1(s,a);
cout<<ans<<endl;
}
T6 寒假作业
现在小学的数学题目也不是那么好玩的。
看看这个寒假作业：
□ + □ = □
□ - □ = □
□ × □ = □
□ ÷ □ = □
(如果显示不出来，可以参见【图1.jpg】)
每个方块代表1~13中的某一个数字，但不能重复。
比如：
6 + 7 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5
以及：
7 + 6 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5
就算两种解法。（加法，乘法交换律后算不同的方案）
你一共找到了多少种方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <math.h>
using namespace std ;
int ans = 0;
int check(int a[]){
bool b1 = (a[0]+a[1])==a[2] ;
bool b2 = (a[3]-a[4])==a[5] ;
bool b3 = (a[6]*a[7])==a[8] ;
bool b4=(fabs((a[9]*1.0)/(a[10]*1.0)-a[11]*1.0)<=0.00000000000001);
if(b1&&b2&&b3&&b4)return 1;
return 0;
}
//手动全排列
void f(int k ,int a[]){
//出口
if(k==4){
if(a[0]+a[1] != a[2])return ;
}
if(k==7){
if(a[3]-a[4] != a[5])return ;
}
if(k==10){
if(a[6]*a[7] != a[8])return ;
}
if(k == 13){
if(check(a)==1){
ans++;
for(int i = 0; i<13 ; ++i){
cout<<a[i];
}cout<<endl;
}
return ;
}
for(int i = k; i<13 ; ++i){
{int temp = a[k] ; a[k] = a[i] ; a[i] = temp ;} //深入
f(k+1,a);
{int temp = a[k] ; a[k] = a[i] ; a[i] = temp ;} //回溯
}
}
int main (){
int a[13]={1,2,3,4,5,6,7,8,9,10,11,12,13};
f(0,a);
cout<<ans<<endl; //64
}
T7 剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <math.h>
using namespace std ;
int ans = 0;
int check1(int a[],int i){
switch (i){
case 0: if(a[1]>0 || a[4]>0)return 1;
case 1: if(a[i-1]>0 || a[i+1]>0 || a[i+4]>0)return 1;
case 2 : if(a[i-1]>0 || a[i+1]>0 || a[i+4]>0)return 1;
case 3: if(a[2]>0 || a[7]>0)return 1;
case 4: if(a[0]>0 || a[5>0] || a[8]>0)return 1;
case 5: if(a[i-4]>0 || a[i-1]>0 || a[i+1]>0 || a[i+4]>0)return 1;
case 6: if(a[i-4]>0 || a[i-1]>0 || a[i+1]>0 || a[i+4]>0)return 1;
case 7: if(a[3]>0 || a[6]>0 || a[11]>0)return 1;
case 8: if(a[4]>0 || a[9]>0 )return 1;
case 9: if(a[i-1]>0 || a[i+1]>0 || a[i-4]>0)return 1;
case 10: if(a[i-1]>0 || a[i+1]>0 || a[i-4]>0)return 1;
case 11: if(a[7]>0 || a[10]>0 )return 1;
default: return 0;
}
}
int check(int a[]){
for(int i =0; i<12 ; ++i ){
if(a[i]==1){
if(check1(a,i)!=1) return 0;
}
}
return 1;
}
void c2i(char &basic_string , int &x ) {
stringstream ss;
ss << basic_string;
ss >> x;
}
//自动全排列
void f1(string s, int a[]){
do{
for(int i=0 ; i<12 ; ++i){
int temp ;
c2i(s[i],temp);
a[i] = temp ;
}
if(check(a)==1){
ans++;
for(int i = 0; i<12 ; ++i){
cout<<a[i];
}cout<<endl;
}
}while(next_permutation(s.begin(),s.end()));
}
//手动全排列
void f(int k ,int a[]){
//出口
if(k == 12){
if(check(a)==1){
ans++;
for(int i = 0; i<12 ; ++i){
cout<<a[i];
}cout<<endl;
}
return ;
}
for(int i = k; i<12 ; ++i){
{int temp = a[k] ; a[k] = a[i] ; a[i] = temp ;} //深入
f(k+1,a);
{int temp = a[k] ; a[k] = a[i] ; a[i] = temp ;} //回溯
}
}
int main (){
//int a[12]={1,2,3,4,5,-1,-2,-3,-4,-5,-6,-7};
string s = "123400000005" ;
int a[12];
f1(s,a);
cout<<ans<<endl;
}
T8 四平方和
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多4个正整数的平方和。
如果把0包括进去，就正好可以表示为4个数的平方和。
比如：
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
（^符号表示乘方的意思）
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对4个数排序：
0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法
程序输入为一个正整数N (N<5000000)
要求输出4个非负整数，按从小到大排序，中间用空格分开
例如，输入：
5
则程序应该输出：
0 0 1 2
再例如，输入：
12
则程序应该输出：
0 2 2 2
再例如，输入：
773535
则程序应该输出：
1 1 267 838
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 3000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
#include <iostream>
#include <math.h>
#include <map>
#include <cmath>
#include <time.h>
#include <stdio.h>
using namespace std;
map<int , int> cache;
void f1(int n){
for(int c = 0 ; c*c<n/10 ;++c){
for(int d = c ; c*c+d*d<=n ; ++d )
{
if(cache.find(c*c+d*d)==cache.end()) cache[c*c+d*d]=c;
}
}
}
//a b找
void f2(int n){
for(int a =0;a*a<n/8;++a){
for(int b=a;a*a+b*b <n/4 ;++b){
if(cache.find(n-a*a-b*b)!=cache.end()){
//找到了符合的c d
int c = cache[n-a*a-b*b] ;
int d = sqrt(n-a*a-b*b-c*c);
printf("%d %d %d %d
",a,b,c,d);
return ;
}
}
}
}
int main(){
long int n;
cin>>n;
// 使用clock()构造clock_t对象(实际上是long类型的变量)
clock_t t1 = clock();
//缓存
f1(n);
//找
f2(n);
// 计算clock差，除以clock数/每秒，即可求出秒数
// 将秒数乘以1000得到毫秒数
cout << (clock() - t1) * 1.0 / CLOCKS_PER_SEC * 1000 << endl;
return 0 ;
}