煤球数目
有一堆煤球，堆成三角棱锥形。具体： 第一层放1个， 第二层3个（排列成三角形）， 第三层6个（排列成三角形）， 第四层10个（排列成三角形）， .... 如果一共有100层，共有多少个煤球？
请填表示煤球总数目的数字。 注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。 Ans=171700
解题思路：画图找规律。每层的三角形煤球出了边外，边内部分 有空间 也会 填充对应三角形数目的煤球。画出大约6 层的煤球三角形分布，便能找出规律：第i层 三角形的 煤球数目 =3*(i-1）+第（i-3）层三角形的煤球数目 。（i>=4）
Codes： #include <iostream>
using namespace std;
typedef long long LL;
LL arr[110];
int main(int argc, char** argv) { arr[1]=1; arr[2]=3; arr[3]=6; arr[4]=10; arr[5]=15; arr[6]=21; for(int i=7;i<=100;i++){ arr[i]=3*(i-1)+arr[i-3]; }
LL sum=0; for(int i=1;i<=100;i++){ sum+=arr[i]; } cout<<sum<<endl; return 0; }
生日蜡烛
某君从某年开始每年都举办一次生日party，并且每次都要吹熄与年龄相同根数的蜡烛。
现在算起来，他一共吹熄了236根蜡烛。
请问，他从多少岁开始过生日party的？
请填写他开始过生日party的年龄数。 注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。 Ans=26
Codes: #include <iostream>
using namespace std;
//暴力解法，从1岁 遍历到100岁
int main(int argc, char** argv) {
for(int i=1;i<=100;i++){ long long sum=0; for(int j=i;j<=100;j++){ sum+=j; if(sum==236){ cout<<"i= "<<i<<endl; cout<<"j= "<<j<<endl; break; } } }
return 0; }
凑算式
B DEF A + --- + ------- = 10 C GHI （如果显示有问题，可以参见【图1.jpg】） 这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。
比如： 6+8/3+952/714 就是一种解法， 5+3/1+972/486 是另一种解法。
这个算式一共有多少种解法？
注意：你提交应该是个整数，不要填写任何多余的内容或说明性文字。 Ans=29 Codes: #include <iostream> #include <algorithm>
using namespace std;
int arr[9];
//全排列 解题 int main(int argc, char** argv) { for(int i=0;i<9;i++) arr[i]=i+1; long long cnt=0; do{ int A=arr[0]; int B=arr[1]; int C=arr[2]; int D=arr[3]; int E=arr[4]; int F=arr[5]; int G=arr[6]; int H=arr[7]; int I=arr[8]; long long X=B*(G*100+H*10+I)+C*(D*100+E*10+F);//注意要 先通分 ，再做商 long long Y=C*(G*100+H*10+I); if(X%Y==0 && (A+X/Y)==10) cnt++; }while(next_permutation(arr,arr+9)); cout<<cnt<<endl;
return 0; }
快速排序
排序在各种场合经常被用到。 快速排序是十分常用的高效率的算法。
其思想是：先选一个“标尺”， 用它把整个队列过一遍筛子， 以保证：其左边的元素都不大于它，其右边的元素都不小于它。
这样，排序问题就被分割为两个子区间。 再分别对子区间排序就可以了。
下面的代码是一种实现，请分析并填写划线部分缺少的代码。
#include <stdio.h>
void swap(int a[], int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
int partition(int a[], int p, int r) { int i = p; int j = r + 1; int x = a[p]; while(1){ while(i<r && a[++i]<x); while(a[--j]>x); if(i>=j) break; swap(a,i,j); } _______swap(a,p,j)_______________; return j; }
void quicksort(int a[], int p, int r) { if(p<r){ int q = partition(a,p,r); quicksort(a,p,q-1); quicksort(a,q+1,r); } } int main() { int i; int a[] = {5,13,6,24,2,8,19,27,6,12,1,17}; int N = 12; quicksort(a, 0, N-1); for(i=0; i<N; i++) printf("%d ", a[i]); printf("\n"); return 0; }
注意：只填写缺少的内容，不要书写任何题面已有代码或说明性文字。 Ans= swap(a,p,j)
抽签
X星球要派出一个5人组成的观察团前往W星。 其中： A国最多可以派出4人。 B国最多可以派出2人。 C国最多可以派出2人。 ....
那么最终派往W星的观察团会有多少种国别的不同组合呢？
下面的程序解决了这个问题。 数组a[] 中既是每个国家可以派出的最多的名额。 程序执行结果为： DEFFF CEFFF CDFFF CDEFF CCFFF CCEFF CCDFF CCDEF BEFFF BDFFF BDEFF BCFFF BCEFF BCDFF BCDEF .... (以下省略，总共101行)
#include <stdio.h> #define N 6 #define M 5 #define BUF 1024
void f(int a[], int k, int m, char b[]) { int i,j; if(k==N){ b[M] = 0; if(m==0) printf("%s\n",b); return; } for(i=0; i<=a[k]; i++){ for(j=0; j<i; j++) b[M-m+j] = k+'A'; ___________f(a,k+1,m-i,b)___________; //填空位置 } } int main() { int a[N] = {4,2,2,1,1,3}; char b[BUF]; f(a,0,M,b); return 0; }
仔细阅读代码，填写划线部分缺少的内容。
注意：不要填写任何已有内容或说明性文字。 Codes Illustration： #include <iostream>
using namespace std;
#define N 6 #define M 5 #define BUF 1024
void f(int a[], int k, int m, char b[]) { int i,j; if(k==N){ b[M] = 0; if(m==0) printf("%s\n",b); return; } for(i=0; i<=a[k]; i++){//第k个国家 还剩 m 个 空位 for(j=0; j<i; j++) b[M-m+j] = k+'A'; // ______________________; //填空位置 //毋庸置疑, 必然是个递归 f(a,k+1,m-i,b); //递归 到 第k+1个国家 } } int main() { int a[N] = {4,2,2,1,1,3}; char b[BUF]; f(a,0,M,b); return 0; }
方格填数
如下的10个格子 +--+--+--+ | | | | +--+--+--+--+ | | | | | +--+--+--+--+ | | | | +--+--+--+
（如果显示有问题，也可以参看【图1.jpg】）
填入0~9的数字。要求：连续的两个数字不能相邻。 （左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
请填写表示方案数目的整数。 注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。 Ans=1580
解题思路：看成一维数组，全排列 遍历所有情况并检验 解题。
Codes: #include <iostream> #include <algorithm> #include <cmath>
using namespace std;
int b[10]; long long ans=0;
bool check(){ if( abs(b[0]-b[1])==1 || abs(b[0]-b[3])==1 || abs(b[0]-b[4])==1 || abs(b[0]-b[5])==1 || abs(b[1]-b[2])==1 || abs(b[1]-b[4])==1 || abs(b[1]-b[5])==1 || abs(b[1]-b[6])==1 || abs(b[2]-b[5])==1 || abs(b[2]-b[6])==1 || abs(b[3]-b[4])==1 || abs(b[3]-b[7])==1 || abs(b[3]-b[8])==1 || abs(b[4]- b[7])==1 || abs(b[4]-b[8])==1 || abs(b[4]-b[9])==1 || abs(b[4]-b[5])==1 || abs(b[5]-b[6])==1 || abs(b[5]-b[8])==1 || abs(b[5]-b[9])==1 || abs(b[6]-b[9])==1 || abs(b[7]-b[8])==1 || abs(b[8]-b[9])==1 ) return false ; return true; }
int main(int argc, char** argv) { for(int i=0;i<10;i++) b[i]=i; do{ if(check()) ans++; }while(next_permutation(b,b+10)); cout<<ans<<endl; return 0; }
剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。 现在你要从中剪下5张来，要求必须是连着的。 （仅仅连接一个角不算相连） 比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。 注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。 Ans=116
Codes: #include <iostream> #include <algorithm> #include <vector> #include <string.h>
using namespace std;
//智慧 全排列 + DFS 解题
int a[]={0,0,0,0,0,0,0,1,1,1,1,1};//数组 a 用来模拟选出的 5 个数 int ar[13];// 1->12 int dir[]={-4,1,4,-1}; long long ans=0;
void initAR(){ for(int i=0;i<12;i++) ar[i+1]=a[i]; }
void DFS(int S){ ar[S]=0; for(int i=0;i<4;i++){//S点 可以走的四个方向 int to=S+dir[i]; if( (S%4==0 && i==1) || (S%4==1 && i==3))//撞墙 跳过 continue; if(to>=1 && to<=12 && ar[to]==1 ) DFS(to); } }
bool check(){ int cnt=0; for(int i=1;i<=12;i++){ if(ar[i]==1){ DFS(i); cnt++; } } return cnt==1; }
int main(int argc, char** argv) { do{ initAR(); if(check()) ans++; }while(next_permutation(a,a+12)); cout<<ans<<endl; return 0; }
四平方和
四平方和定理，又称为拉格朗日定理： 每个正整数都可以表示为至多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>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
Codes: #include <iostream> #include <cmath> #include <map> #include <cmath>
using namespace std;
typedef long long LL;
map<LL,LL> cache; LL N; //枚举+优化 int main(int argc, char** argv) { cin>>N; //先把c^2+d^2存到 cache中 for(LL c=0;c*c<=N/2;c++){// c^2+d^2<=N =>2*c^2<=N => c^2<=N/2 for(LL d=c;c*c+d*d<=N;d++){ if(!cache[c*c+d*d]) cache[c*c+d*d]=c; } } for(LL a=0;a*a<=N/4;a++){// 4*a^2<=N => a^2<+N/4 for(LL b=a;a*a+b*b<=N/2;b++){/* a^2+b^2+c^2+d^2<=N =>( b <= c <= d ),st a=b=c=d时,4*a^2<=N => (a^2+b^2)+2*a^2<=N => a^2+b^2<=N/2 */ if(cache[N-a*a-b*b]){ LL c=cache[N-a*a-b*b]; LL d=sqrt(N-a*a-b*b-c*c); cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl; return 0; } } } return 0; }
交换瓶子
有N个瓶子，编号 1 ~ N，放在架子上。
比如有5个瓶子： 2 1 3 5 4
要求每次拿起2个瓶子，交换它们的位置。 经过若干次后，使得瓶子的序号为： 1 2 3 4 5
对于这么简单的情况，显然，至少需要交换2次就可以复位。
如果瓶子更多呢？你可以通过编程来解决。
输入格式为两行： 第一行: 一个正整数N（N<10000）, 表示瓶子的数目 第二行：N个正整数，用空格分开，表示瓶子目前的排列情况。
输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。
例如，输入： 5 3 1 2 5 4
程序应该输出： 3
再例如，输入： 5 5 4 3 2 1
程序应该输出： 2
资源约定： 峰值内存消耗 < 256M CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0 注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。 注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
解题思路：交换排序 +计数
Codes： #include <iostream> #include <algorithm> #include <map>
using namespace std;
int N; vector<int> arr; vector<int> vkt; map<int,int> Pos;// Pos->first:arr中存放的 元素 ;Pos->second：vkt中排好序的元素 对应的下标
int main(int argc, char** argv) { cin>>N; for(int i=0;i<N;i++){ int x; cin>>x; arr.push_back(x); vkt.push_back(x); } sort(vkt.begin(),vkt.end()); for(int i=0;i<N;i++){ Pos[vkt[i]]=i; } int time=0; for(int i=0;i<N;i++){ if(arr[i]!=vkt[i]){ swap(arr[i],arr[Pos[arr[i]]]); time++; } } cout<<time<<endl;
return 0; }
未完待续。。。加油！Hooah！Cheerio！
