东华大学计算机软件工程 复试最后一百题
1、时间转换
给定一个t，将t秒转化为DD days HH:MM:SS的形式，表示DD天HH小时MM分钟SS秒。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> int main() { int t; scanf("%d",&t); int m=60; int h=60*60; int d=h*24; int D,H,M,S; D=t/d;t=t%d; H=t/h;t=t%h; M=t/m;t=t%m; printf("%d days %d:%d:%d\n",D,H,M,t); return 0; }
2、时间转换2
给定一个t，将t秒转化为DD days HH:MM:SS的形式，表示DD天HH小时MM分钟SS秒。
HH,MM,SS均是两位数，如果小于10用0补到两位。
如果大于等于2天，则输出DD days HH:MM:SS，比如 2 days 01:05:12
如果大于等于1天并小于2天，则输出 1 day HH:MM:SS，比如 1 day 01:05:12
如果大于等于1小时并小于1天，则只输出HH:MM:SS，比如 01:05:12
如果大于等于1分钟并小于1小时，则只输出MM:SS，比如 01:00
如果大于等于10秒并小于1分钟，则只输出SS，比如 10
如果小于10秒，则只输出一位，表示秒数，比如 9
//%02d代表宽度为两位 不足以0补齐 #include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> int main() { int t; scanf("%d",&t); int m=60; int h=60*60; int d=h*24; int D,H,M,S; D=t/d;t=t%d; H=t/h;t=t%h; M=t/m;t=t%m; if(D>=2) printf("%d days %02d:%02d:%02d",D,H,M,t); else if(D>=1) printf("%d day %02d:%02d:%02d",D,H,M,t); else if(H>=1) printf("%02d:%02d:%02d",H,M,t); else if(M>=1) printf("%02d:%02d",M,t); else if(t>=0) printf("%d",t); return 0; }
3、找圆心
有一个圆心以及圆上的两个点，输入它们的x座标和y座标，判断哪个点是圆心。
比如输入三个点座标（第一行是第1个点，第二行是第2个点，第三行是第3个点）：
0 0
3 0
0 -3
则可知，第一个点到第二个点的距离和它到第三个点的距离相等，因此可知第1个点是圆心（经过计算可知第2个点、第3个点不是圆心）。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> double dis(int a[2],int b[2]) { return pow(a[0]-b[0],2)+pow(a[1]-b[1],2); } int main() { int i,j; int a[3][2]; for(i=0;i<3;i++) for(j=0;j<2;j++) scanf("%d",&a[i][j]); if(dis(a[0],a[1])==dis(a[0],a[2]))printf("1"); else if(dis(a[1],a[0])==dis(a[1],a[2]))printf("2"); else if(dis(a[2],a[1])==dis(a[2],a[0]))printf("3"); else printf("no center"); return 0; }
4、求多少天
按月、年的顺序读入一个日期，输出该月一共有几天。
#include <stdio.h> // 1 2 3 4 5 6 7 8 9 10 11 12 // 闰年366 31 29 31 30 31 30 31 31 30 31 30 31 year%400==0||(year%4==0&&year%100!=0) //非闰年365 31 28 31 30 31 30 31 31 30 31 30 31 一三五七八十腊 31天永不差 int main() { int year,month; while(~scanf("%d%d",&month,&year)) { int flag=0; if(year%400==0||(year%4==0&&year%100!=0))flag=1; int days; switch(month) { case 4: case 6: case 9: case 11:days=30;break; case 2:days=flag?29:28;break; default:days=31;break; } printf("%d\n",days); } return 0; }
5、分数等级
给出一百分制成绩，要求输出成绩等级：
90分以上为A
80-89分为B
70-79分为C
60-69 分为D
60分以下为E
#include <stdio.h> int main() { int score; scanf("%d",&score); if(score>=90)printf("A\n"); else if(score>=80)printf("B\n"); else if(score>=70)printf("C\n"); else if(score>=60)printf("D\n"); else printf("E\n"); return 0; }
6、加班费
编写一个计算员工收入的程序，公司规定工资发放标准： 160个工时以内10元/小时，160个工时以外按3倍发放。
#include <stdio.h> int main() { int h; scanf("%d",&h); if(h<=160)printf("%d\n",h*10); else printf("%d\n",1600+(h-160)*30); return 0; }
7、幸运数字因数的个数
小李非常喜欢数字4和7，看到一个数字他就想快速计算出因子里面含有几个4和7，但是智商捉急的他总是要算很久，喜欢编程的你能够帮助他吗？
比如数字112，因为112=4*4*7，所以知道它的因子中包含2个4和1个7。
再比如数字56，因为56=2*4*7，所以知道它的因子中包含1个4和1个7。
而数字30不能被4或7整除，所以它的因子中包含0个4和0个7。
#include <stdio.h> int main() { int n; int i,j; while(~scanf("%d",&n)) { i=0;j=0; while(n%4==0&&n) { i++; n/=4; } while(n%7==0&&n) { j++; n/=7; } printf("%d %d\n",i,j); } }
8、初级运算
小学一年级学生正在学习多位数加法，从右到左每次一位数字。在运算过程中，进位对学生来讲是个难点。你的工作是统计每组加法运算的进位次数，老师根据你的统计结果就可以评估这些题目的难度。
#include <stdio.h> int main() { int m,n,carry,count,i,j; while(~scanf("%d%d",&m,&n)) { carry=0,count=0; while(m||n||carry) { i=m%10,j=n%10; m/=10,n/=10; carry=(i+j+carry)/10; if(carry)count++; } if(count==0)printf("No carry operation.\n"); else if(count==1)printf("1 carry operation.\n"); else printf("%d carry operations.\n",count); } return 0; }
9、数对
编写一个程序，该程序从用户读入一个整数，然后列出所有的数对，每个数对的乘积即为该数。
#include <stdio.h> int main() { int n; scanf("%d",&n); int i; for(i=1;i<=n;i++) { if(n%i==0) printf("%d * %d = %d\n",i,n/i,n); } return 0; }
10、求二进制表示位数
给定一个十进制整数，返回其对应的二进制数的位数。例如，输入十进制数9，其对应的二进制数是1001，因此位数是4。
#include <stdio.h>
#include <string.h> #include <stdlib.h> int main() { int n; scanf("%d",&n); char ch[100]; itoa(n,ch,2); printf("%d\n",strlen(ch)); return 0; }
11、蜜蜂飞舞
“两只小蜜蜂呀，飞在花丛中呀……”
话说这天天上飞舞着两只蜜蜂，它们在跳一种奇怪的舞蹈。用一个空间直角坐标系来描述这个世界，那么这两只蜜蜂初始坐标分别为(x1,y1,z1)，(x2,y2,z2) 。在接下来它们将进行n次飞行，第i次飞行两只蜜蜂分别按照各自的速度向量飞行ti个单位时间。对于这一现象，玮玮已经观察了很久。他很想知道在蜜蜂飞舞结束时，两只蜜蜂的距离是多少。现在他就求教于你，请你写一个程序来帮他计算这个结果。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> double dis(int* p1,int* p2) { return sqrt(pow(p1[0]-p2[0],2)+pow(p1[1]-p2[1],2)+pow(p1[2]-p2[2],2)); } int main() { int a[1000][7]; int p[6]; int i,j,n; scanf("%d",&n); for(i=0;i<n;i++) for(j=0;j<7;j++) scanf("%d",&a[i][j]); for(i=0;i<6;i++) scanf("%d",&p[i]); for(i=0;i<n;i++) for(j=0;j<6;j++) p[j]=p[j]+a[i][j]*a[i][6]; printf("%.4f\n",dis(&p[0],&p[3])); return 0; }
12、学做菜
涛涛立志要做新好青年，他最近在学做菜。由于技术还很生疏，他只会用鸡蛋，西红柿，鸡丁，辣酱这四种原料来做菜，我们给这四种原料标上字母A,B,C,D。
涛涛现在会做的菜有五种：
1、 西红柿炒鸡蛋 原料：AABDD
2、 酸辣鸡丁 原料：ABCD
3、 宫保鸡丁 原料：CCD
4、 水煮西红柿 原料：BBB
5、 怪味蛋 原料：AD
这天早上，开开去早市给涛涛买了一些原料回来。由于事先没有什么计划，涛涛决定，对于现存的原料，每次尽量做菜单上靠前（即编号小）的菜。
现在请你写一个程序，判断一下开开和涛涛中午能吃到哪些菜。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int main() { int a[4]; int i,j; for(i=0;i<4;i++)scanf("%d",&a[i]); int count=0; while(a[0]>=2&&a[1]>=1&&a[3]>=2) { count++; a[0]-=2; a[1]-=1; a[3]-=2; } printf("%d\n",count); count=0; while(a[0]>=1&&a[1]>=1&&a[2]>=1&&a[3]>=1) { count++; a[0]-=1; a[1]-=1; a[2]-=1; a[3]-=1; } printf("%d\n",count); count=0; while(a[2]>=2&&a[3]>=1) { count++; a[2]-=2; a[3]-=1; } printf("%d\n",count); count=0; while(a[1]>=3) { count++; a[1]-=3; } printf("%d\n",count); count=0; while(a[0]>=1&&a[3]>=1) { count++; a[0]-=1; a[3]-=1; } printf("%d\n",count); return 0; }
13、简单加法
首先给出简单加法算式的定义：
如果有一个算式(i)+(i+1)+(i+2),(i>=0)，在计算的过程中，没有任何一个数位出现了进位，则称其为简单的加法算式。
例如：i=3时，3+4+5=12，有一个进位，因此3+4+5不是一个简单的加法算式；又如i=112时，112+113+114=339，没有在任意数位上产生进位，故112+113+114是一个简单的加法算式。
问题：给定一个正整数n，问当i大于等于0且小于n时,有多少个算式(i)+(i+1)+(i+2)是简单加法算式。其中n<10000。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> int main() { int n,kilo,hundred,decade,unit,cnt=0; scanf("%d",&n); for(int i=0;i<n;i++) { unit=i%10;//个位 decade=i%100/10; hundred=i%1000/100; kilo=i/1000; //&&是左边只要有一个不满足就退出 if(unit<=2&&decade<=2&&hundred<=2&&kilo<=2) cnt++; } printf("%d",cnt); return 0; }
14、阿尔法乘积
计算一个整数的阿尔法乘积。对于一个整数x来说，它的阿尔法乘积是这样来计算的：如果x是一个个位数，那么它的阿尔法乘积就是它本身；否则的话，x的阿尔法乘积就等于它的各位非0的数字相乘所得到的那个整数的阿尔法乘积。例如：4018224312的阿尔法乘积等于8，它是按照以下的步骤来计算的：
4018224312 → 4*1*8*2*2*4*3*1*2 → 3072 → 3*7*2 → 42 → 4*2 → 8
编写一个程序，输入一个正整数（该整数不会超过6,000,000,000），输出它的阿尔法乘积。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> int main() { __int64 n=4018224312; scanf("%I64dd",&n); __int64 temp; while(n>10) { temp=1; while(n) { if(n%10) temp*=(n%10); n/=10; } n=temp; // printf("%I64d\n",n); } printf("%d",n); return 0; }
15、连续正整数的和
78这个数可以表示为连续正整数的和，1+2+3，18+19+20+21，25+26+27。
输入一个正整数 n(<=10000)
输出 m 行(n有m种表示法)，每行是两个正整数a，b，表示a+(a+1)+…+b=n。
对于多种表示法，a小的方案先输出。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> //从start开始累加 直到大于等于target为止 int addToTarget(int start,int target) { int sum=0; while(sum<target) sum+=start++; if(sum==target) return start-1; else return 0; } int main() { int i,n,temp; scanf("%d",&n); for(i=1;i<(n/2)+1;i++) { if(temp=addToTarget(i,n)) printf("%d %d\n",i,temp); } return 0; }
16、二进制数数
给定L,R。统计[L,R]区间内的所有数在二进制下包含的“1”的个数之和。
如5的二进制为101，包含2个“1”。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> int count1(char a[300]) { int len=strlen(a); int i,count=0; for(i=0;i<len;i++) if(a[i]==\'1\') count++; return count; } int fun(int m,int n) { char a[300]; int i; int count=0; for(i=m;i<=n;i++) { itoa(i,a,2); count+=count1(a); } return count; } int main() { int a,b; scanf("%d%d",&a,&b); printf("%d\n",fun(a,b)); return 0; }
17、质因数
将一个正整数N(1<N<32768)分解质因数。例如，输入90，打印出90=2*3*3*5。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int PRIME[3512]; int size; int isPrimeNum(int n) { int i; for(i=2;i<=sqrt(n);i++) if(n%i==0)return 0; return 1; } void initPrimeNum(int a,int b) { size=0; int i; for(i=a;i<=b;i++) { if(isPrimeNum(i)) PRIME[size++]=i; } } void fun(int n) { printf("%d=",n); int i; int pre_i=0; while(n!=1) { for(i=pre_i;i<size;i++) if(n%PRIME[i]==0) { printf("%d",PRIME[i]); pre_i=i; n/=PRIME[i]; if(n!=1)printf("*"); break; } } printf("\n"); } int main() { int a,i; scanf("%d",&a); initPrimeNum(2,a); fun(a); return 0; }
18、黑色星期五
有些西方人比较迷信，如果某个月的13号正好是星期五，他们就会觉得不太吉利，用古人的说法，就是“诸事不宜”。请你编写一个程序，统计出在某个特定的年份中，出现了多少次既是13号又是星期五的情形，以帮助你的迷信朋友解决难题。
说明：（1）一年有365天，闰年有366天，所谓闰年，即能被4整除且不能被100整除的年份，或是既能被100整除也能被400整除的年份；（2）已知1998年1月1日是星期四，用户输入的年份肯定大于或等于1998年。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int getYearDay(int year) { if(year%400==0||(year%4==0&&year%100!=0))return 366; else return 365; } int getMonthDay(int year,int month) { int flag=0; if(year%400==0||(year%4==0&&year%100!=0))flag=1; int days; switch(month) { case 4: case 6: case 9: case 11:days=30;break; case 2:days=flag?29:28;break; default:days=31;break; } return days; } int main() { int n,i; scanf("%d",&n); int days=0; for(i=1998;i<n;i++)days+=getYearDay(i); int count=0; for(i=1;i<=12;i++) { // printf("%d\n",days); // printf("%d\n",(days+13-4)%7); if((days+13-4)%7==5)count++; days+=getMonthDay(n,i); } printf("%d\n",count); return 0; }
19、平均成绩
从键盘输入10个学生成绩，求平均分数及高于平均分数的成绩。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int main() { int i,j; int a[10]; int sum=0; for(i=0;i<10;i++) { scanf("%d",&a[i]); sum+=a[i]; } double avg=sum/10.0; printf("%.1f\n",avg); for(i=0;i<10;i++) if(a[i]>avg) printf("%d ",a[i]); printf("\n"); return 0; }
20、整除的尾数
1个整数，只知道前几位为a，不知道末二位，被另一个整数b除尽了(即没有余数)，那么该数的末二位该是什么呢？
程序已完成主体框架,请完成以下函数getResult的函数体。
getResult的功能为：
根据传入的参数a和b，求出所有符合条件的末二位（尾数）放入数组weishu中，数组weishu按升序排列。函数返回符合条件的尾数个数。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> int getResult(int a, int b, int weishu[]) { int size=0; int i; int temp; for(i=0;i<100;i++) { temp=a*100+i; if(temp%b==0)weishu[size++]=i; } return size; } int main() { int a, b, weishu[100],count,i; scanf("%d%d", &a, &b); count=getResult(a,b,weishu); for(i=0; i<count; i++) { if (i>0) printf(" "); printf("%02d", weishu[i]); } printf("\n"); return 0; }
21、谁是老二？
一维数组中存储不超过100个整型数据，请找出其中第二大的元素，输出这些元素的值以及它们的下标。
注意，由于元素值可能相同，因此具有最大值的元素个数可能不只一个，第二大的元素是比它们小的那些元素。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> int getSecondMaxFirstIndex(int a[],int len) { int i,max=a[0]; for(i=1;i<len;i++) if(a[i]>max)max=a[i]; int res=-1; for(i=0;i<len;i++) { if(a[i]>=max)continue; if(res==-1)res=i; else if(a[i]>a[res])res=i; } return res; } int main() { int i,n,index; int a[100]; while(~scanf("%d",&n)) { for(i=0;i<n;i++) scanf("%d",&a[i]); index=getSecondMaxFirstIndex(a,n); if(index==-1)printf("none\n"); else { printf("%d %d",a[index],index); for(i=index+1;i<n;i++) if(a[i]==a[index]) printf(" %d",i); printf("\n"); } } return 0; }
22、骑士斗恶龙
你的王国里有一条n个头的恶龙，你希望雇佣一些骑士把它杀死（也就是砍掉所有的头）。
村里有m个骑士可以雇佣，一个能力值为 x 的骑士可以砍掉恶龙一个直径不超过 x 的头，且需要报酬 x 个金币。
如何雇佣骑士才能砍掉恶龙所有的头，并且支付最小的金币？
注意，一个骑士只能砍一个头并且仅能被雇佣1次。
//ability[i][0]代表能力 ability[i][1]代表是否被使用 将恶龙与骑士都从小到大排序 然后循环找出能满足恶龙的代价最小的骑士
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> //指针指向实数时 比较两个元素的大小 //当指针指向数组时 比较两个数组的第一维 int cmp(const void* p1,const void* p2) { int* a=(int*)p1; int* b=(int*)p2; return *a-*b; } int main() { int m,n,i,j,cost,flag; int len[20000],ability[20000][2]; while(~scanf("%d%d",&n,&m)) { cost=0; for(i=0;i<n;i++)scanf("%d",&len[i]); for(i=0;i<m;i++)scanf("%d",&ability[i][0]); for(i=0;i<m;i++)ability[i][1]=1; qsort(len,n,sizeof(int),cmp); //注意数组大小 qsort(ability,m,sizeof(int)*2,cmp); //for(i=0;i<m;i++)printf("%d ",ability[i][0]);printf("\n"); for(i=0;i<n;i++) { flag=0; for(j=0;j<m;j++) { if(ability[j][0]>=len[i]&&ability[j][1]) { cost+=ability[j][0]; ability[j][1]=0; flag=1; break; } } if(!flag){printf("Lose!\n");break;} } if(flag)printf("%d\n",cost); } return 0; }
23、只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
//排序后 两个两个遍历 如果遇到两个数不相等 则这两个中的第一个就是只出现一次的数 同时注意最后一个单独的数是只出现一次的可能性
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> int cmp(const void* p1,const void* p2) { int* a=(int*)p1; int* b=(int*)p2; return *a-*b; } int main() { int n,i,j,res,pre,flag; int a[100]; while(~scanf("%d",&n)) { flag=0; for(i=0;i<n;i++)scanf("%d",&a[i]); qsort(a,n,sizeof(int),cmp); //for(i=0;i<n;i++)printf("%d ",a[i]); pre=a[0]; i=1; while(i<n) { if(a[i]!=pre){res=pre;flag=1;break;} else { if(i+1<n)pre=a[i+1]; i+=2; } } if(flag) printf("%d\n",res); else printf("%d\n",pre); } return 0; }
24、分数统计
给定一个百分制成绩T，将其划分为如下五个等级之一：
90~100为A，80~89为B，70~79为C，60~69为D，0~59为E
现在给定的输入中包含若干百分制成绩（成绩个数不超过1000），请你统计五个等级段的人数，并找出人数最多的那个等级段，按照从大到小的顺序输出该段中所有人成绩（保证人数最多的等级只有一个）。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> int cmp(const void* p1,const void* p2) { int* a=(int*)p1; int* b=(int*)p2; return *b-*a; } int main() { int n,i,j,max_index; int a,b,c,d,e; int array[10000]; int level[5]; while(~scanf("%d",&n)) { memset(level,0,sizeof(int)*5); for(i=0;i<n;i++)scanf("%d",&array[i]); qsort(array,n,sizeof(int),cmp); for(i=0;i<n;i++) { if(array[i]>=90)level[0]++; else if(array[i]>=80)level[1]++; else if(array[i]>=70)level[2]++; else if(array[i]>=60)level[3]++; else level[4]++; } max_index=0; printf("%d",level[0]); for(j=1;j<5;j++) { printf(" %d",level[j]); if(level[j]>level[max_index]) max_index=j; } printf("\n%d\n",level[max_index]); int start=0; for(i=0;i<max_index;i++)start+=level[i]; for(i=start;i<start+level[max_index];i++) { if(i!=start)printf(" "); printf("%d",array[i]); } printf("\n"); } return 0; }
25、5科总分
输入10个学生的学号和5门课程的成绩，统计输出5门课总分最高和最低的学生的学号和他们的总分。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> int cmp(const void* p1,const void* p2) { int* a=(int*)p1; int* b=(int*)p2; return *b-*a; } int main() { int arr[10][2]; int i,j,temp,t; for(i=0;i<10;i++) { scanf("%d",&arr[i][1]); //printf("%d\n",arr[i][1]); temp=0; for(j=0;j<5;j++) { scanf("%d",&t); temp+=t; } //printf("%d\n",temp); arr[i][0]=temp; } qsort(arr,10,sizeof(int)*2,cmp); printf("%d %d\n",arr[0][1],arr[0][0]); printf("%d %d\n",arr[9][1],arr[9][0]); return 0; }
26、二维数组的平均值
在3*4的二维数组a中，计算出各行的平均值，放在一个一维数组b中，如：
a=(3 16 12 1
4 32 11 10
10 25 12 7)
b=(8 14.25 13.5)
////%g 不输出无用的0
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> int main() { int arr[3][4]; double res,sum; int i,j; for(i=0;i<3;i++) { sum=0; for(j=0;j<4;j++) { scanf("%d",&arr[i][j]); sum+=arr[i][j]; } res=sum/4.0; //%g 不输出无用的0 printf("%g ",res); } printf("\n"); return 0; }
27、蛇形方阵
输出一个如下的n阶方阵。例如，若读入11，则输出：
//设定一个flag控制 存储时是从左到右还是从右到左 依次存就好
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> int main() { int a[20][20]; int n,i,j,flag; int num=1; scanf("%d",&n); flag=1; for(i=0;i<n;i++) { if(flag) for(j=0;j<n;j++) a[i][j]=num++; else for(j=n-1;j>=0;j--) a[i][j]=num++; flag=!flag; } for(i=0;i<n;i++) { for(j=0;j<n-1;j++) printf("%4d",a[i][j]); printf("%4d\n",a[i][j]); } return 0; }
28、n层正方形
编写程序，输出n层正方形图案。正方形图案最外层是第一层，每层用的数字和层数相同。
1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> void my_print(int a[49][49],int n) { int i,j; for(i=0;i<2*n-1;i++) { for(j=0;j<2*n-2;j++) printf("%d ",a[i][j]); printf("%d\n",a[i][j]); } } int main() { int a[49][49]; int n,i,j,num; scanf("%d",&n); int len=2*n-1; for(num=0;num<n-1;num++) { //最上层 从左到右 i=num; for(j=num;j<len-num;j++)a[i][j]=num+1; //最右层 从上到下 j=len-num-1; for(i=num+1;i<len-num;i++)a[i][j]=num+1; //最下层 从右到左 i=len-num-1; for(j=len-num-2;j>=num;j--)a[i][j]=num+1; //最左层 从下到上 j=num; for(i=len-num-2;i>num;i--)a[i][j]=num+1; } //中间一个 a[num][num]=n; my_print(a,n); return 0; }
29、二维数组右上左下遍历
给定一个row行col列的整数数组array，要求从array[0][0]元素开始，依次取右上到左下的对角线上的元素，按从左上到右下的对角线顺序遍历整个数组。
如3行4列的array：
1 2 4 7
3 5 8 10
6 9 11 12
从右上到左下的对角线有6条，第1条包括数字1，第2条包括数字2和3，第3条包括数字4、5和6，第4条包括数字7、8和9……
依次取这些对角线上的元素输出，即可得到1、2、3、4、5、6、7、8、9、10、11、12
输入说明 :
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> void my_print(int a[100][100],int m,int n) { int i,j,temp; i=0; for(j=0;j<n;j++) { temp=j; while(i>=0&&j>=0&&i<m&&j<n) { printf("%d ",a[i][j]); i++,j--; } i=0; j=temp; } j=n-1; for(i=1;i<m;i++) { temp=i; while(i>=0&&j>=0&&i<m&&j<n) { printf("%d ",a[i][j]); i++,j--; } j=n-1; i=temp; } printf("\n"); } int main() { int a[100][100]; int m,n,i,j; scanf("%d%d",&m,&n); for(i=0;i<m;i++)for(j=0;j<n;j++)scanf("%d",&a[i][j]); my_print(a,m,n); return 0; }
30、特殊的矩阵运算
输入m个方阵，方阵的元素是非0整数。对于n阶方阵A，明明现在需要进行特殊的运算。
例如：
A: 5 1 3
5 8 7
2 6 9
方阵A有两条对角线：从左上角到右下角的对角线，元素为5 8 9，以及从左下角到右上角的对角线，元素为2 8 3。
求A两条对角线元素相乘的和（对角线积），5*2+8*8+9*3=101；
求A两条对角线元素相除的和（对角线商）：5/2+8/8+9/3=6。 （注意：求对角线商时用整除，所以5/2的结果为2。）
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> int main() { int a[10][10]; int p1[10]; int p2[10]; int i,j,k,m,n,res1,res2; scanf("%d",&m); scanf("%d",&n); while(m--) { for(i=0;i<n;i++)for(j=0;j<n;j++)scanf("%d",&a[i][j]); //第一条对角线 i=0,j=0; for(k=0;k<n;k++)p1[k]=a[i++][j++]; //第二条对角线 i=n-1;j=0; for(k=0;k<n;k++)p2[k]=a[i--][j++]; res1=res2=0; for(i=0;i<n;i++) { res1+=p1[i]*p2[i]; res2+=p1[i]/p2[i]; } printf("%d %d\n",res1,res2); } return 0; }
31、输出米字型
根据输入的正整数n ，米字形由一个(2n-1)*(2n-1)的矩阵组成，矩阵包含从大写A开始的n个字母
例如:n=3时，包含A,B,C；n=4时，包含A,B,C,D。
矩阵的正中间为n个字母中字典序最大的那个，从这个字母开始，沿着西北、正北、东北、正西、正东、西南、正南、东南八个方向各有一条由大写字母组成的直线。并且直线上的字母按字典序依次减小，直到大写字母A。
矩阵的其它位置用英文句号．填充。
样例输入一
3
样例输出一
Ａ．Ａ．Ａ
．ＢＢＢ．
ＡＢＣＢＡ
．ＢＢＢ．
Ａ．Ａ．Ａ
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> char res[40][40]; int n; void my_print() { int i,j; for(i=0;i<2*n-1;i++) { for(j=0;j<2*n-1;j++) printf("%c",res[i][j]); printf("\n"); } } int main() { memset(res,\'.\',sizeof(char)*40*40); scanf("%d",&n); char val=\'A\'+n-1; res[n-1][n-1]=val; int i,j,k; i=n-1,j=n-1,val=res[n-1][n-1]; for(k=0;k<n-1;k++) res[i][--j]=--val; i=n-1,j=n-1,val=res[n-1][n-1]; for(k=0;k<n-1;k++) res[i][++j]=--val; i=n-1,j=n-1,val=res[n-1][n-1]; for(k=0;k<n-1;k++) res[++i][j]=--val; i=n-1,j=n-1,val=res[n-1][n-1]; for(k=0;k<n-1;k++) res[--i][j]=--val; i=n-1,j=n-1,val=res[n-1][n-1]; for(k=0;k<n-1;k++) res[--i][++j]=--val; i=n-1,j=n-1,val=res[n-1][n-1]; for(k=0;k<n-1;k++) res[--i][--j]=--val; i=n-1,j=n-1,val=res[n-1][n-1]; for(k=0;k<n-1;k++) res[++i][++j]=--val; i=n-1,j=n-1,val=res[n-1][n-1]; for(k=0;k<n-1;k++) res[++i][--j]=--val; my_print(); return 0; }
32、模拟登陆
编写程序模拟简单的密码登录（正确的密码是123456），首先从键盘输入用户名（用户名随意，不超过10个字符）
然后输入密码，若密码正确（即为123456）则给出问候语。
若密码不正确，则给出错误提示，并允许再次输入，
直到输入正确的密码或输入0结束。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> int main() { char ch[100]; int pw; scanf("%s",&ch); while(1) { scanf("%d",&pw); if(pw==123456) { printf("Hello %s\n",ch); break; } else printf("Wrong Password!\n"); if(pw==0)break; } return 0; }
33、单词统计
从键盘上输入一个整数N，并输入N行字符串。每行字符串都包含多个单词，单词之间以空格分开。请输出每行字符串中单词的个数。
说明：以空格分隔开的任何字符串都认为是单词。比如“I\’m”认为是一个单词
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> int CountWords(char str[]) { int count=0; int flag=0; while(*str) { if(*str!=\' \')flag=1; else if(flag==1&&*str==\' \'){flag=0;count++;} str++; } return count+flag; } int main() { int n; scanf("%d",&n); getchar(); while(n--) { char ch[1000]; scanf("%[^\n]",&ch); getchar(); printf("%d\n",CountWords(&ch[0])); } }
34、倒数和
从键盘输入一串字符串（包含空格），将输入字符串中的所有数字（0除外）的倒数相加，列出算式，并输出最后的结果。如果除0外没有数字字符，则输出数字0。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> void fun(char str[]) { int i; double res=0; for(i=0;i<strlen(str);i++) { if(str[i]>\'0\'&&str[i]<=\'9\') { if(res!=0)printf("+"); printf("1/%c",str[i]); res+=1.0/(str[i]-\'0\'); } } if(res==0)printf("0\n"); else printf("=%.2lf\n",res); } int main() { char ch[201]; while(~scanf("%[^\n]",&ch)&&getchar()) { fun(&ch[0]); } }
35、幸运偶数
从键盘上输入一个整数(长度不大于200)，将其各位上为奇数的数字去除，剩余的数字按数字大小从大到小排序，组成一个新的数，并输出到屏幕上。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> int cmp(const void*a,const void *b) { char* p1=(char*)a; char* p2=(char*)b; return (*p2-\'0\')-(*p1-\'0\'); } void fun(char str[]) { int cur=0; int i=0; while(i<strlen(str)) { if((str[i]-\'0\')%2!=1) str[cur++]=str[i]; i++; } if(cur==0)printf("None\n"); else { str[cur]=\'\0\'; qsort(str,cur,sizeof(char),cmp); printf("%s\n",str); } } int main() { char ch[201]; while(~scanf("%[^\n]",&ch)&&getchar()) { fun(&ch[0]); } }
36、转换成十进制
编写一个程序，将一个2~20以内任意进制数转换成十进制。这些数据由数字0-9，大写字母A-J组成，其中A=10，B=11……J=19。例如16进制数5A转换为十进制数90（90=5*16+10*1）。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> int transformChar(char c) { if(c>=\'0\'&&c<=\'9\')return c-\'0\'; else return c-\'A\'+10; } int ntoDecade(int n,char str[100]) { int res=0,i,k=0,len=strlen(str); for(i=len-1;i>=0;i--) res+=(transformChar(str[i])*(int)(pow(n,k++)+0.5)); return res; } int main() { int n; char str[100]; while(~scanf("%d %s",&n,&str[0])&&getchar()) printf("%d\n",ntoDecade(n,str)); }
37、十进制转换换成其他进制
编写一个程序，将一个十进制数转换成任意的2~20以内的其他进制数。这些数据由数字0-9，字母A-J组成，其中A=10，B=11……J=19。例如90转换为16进制数为5A（90=5*16+10*1）。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> char* strHiger(char* s) { char *origin=s; for(;*s!=\'\0\';s++) { if(*s>=\'a\'&&*s<=\'z\') *s=\'A\'+(*s)-\'a\'; } return origin; } int main() { int n,r; char ch[10000]; while(~scanf("%d%d",&n,&r)) { itoa(n,&ch[0],r); printf("%s\n",strHiger(ch)); } return 0; }
38、求反数字字符串
编写一个程序，将输入的数字串反转过来并输出。如：输入123，输出321。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> void inverse_print(char ch[21]) { int i,len=strlen(ch); for(i=len-1;i>=0;i--) printf("%c",ch[i]); printf("\n"); } int main() { int n,r; char ch[21]; while(~scanf("%s",ch)) inverse_print(ch); return 0; }
39、判定字符位置
返回给定字符串s中元音字母的首次出现位置。英语元音字母只有‘a’、‘e’、‘i’、‘o’、‘u’五个。
若字符串中没有元音字母，则返回0。
只考虑小写的情况。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> int firstVowelIndex(char ch[1000]) { int i,len=strlen(ch); int res=-1; for(i=0;i<len;i++) { if(ch[i]==\'a\'|| ch[i]==\'e\'|| ch[i]==\'i\'|| ch[i]==\'o\'|| ch[i]==\'u\') { res=i; break; } } return res+1; } int main() { int n,r; char ch[1000]; while(~scanf("%s",ch)) printf("%d\n",firstVowelIndex(ch)); return 0; }
40、最大相同子串
输入两个字符串,获取两个字符串中最长相同子串并输出。
如果有多个相同子串，则输出（按ASCII排序）最小的那个“最长相同子串”。
如果无相同子串，则输出空字符串（即空行）。
//找出两个串中小的一个 然后枚举相同子串的长度为：从小串的长度循环到1 然后再枚举相同子串在小串中的位置 得到一个相同子串 再在长串中找是否有这个子串
int main() { char a[100]; char b[100]; char temp[100]; char res[100]; char *min,*max; while(~scanf("%s",a)&&getchar()) { scanf("%s",b);getchar(); res[0]=\'\0\'; int alen=strlen(a),blen=strlen(b); if(alen>blen) { min=&b[0]; max=&a[0]; } else { min=&a[0]; max=&b[0]; } int i,j,k,minlen=strlen(min),maxlen=strlen(max); int find=0; //printf("min:%s max:%s\n",min,max); //短子串的大小 for(i=minlen;i>0;i--) { //短子串位置 for(j=0;j<=minlen-i;j++) { strncpy(temp,&min[j],i); //temp当前短子串 temp[i]=\'\0\'; //逐个与长子串比较 for(k=0;k<=maxlen-i;k++) { //printf("%s %s %d\n",temp,&max[k],i); if(!strncmp(temp,&max[k],i)) { if(strlen(res)==0) { strcpy(res,temp); break; } else { if(strcmp(res,temp)>0) strcpy(res,temp); break; } } } } if(strlen(res)!=0) { printf("%s\n",res); find=1; break; } } if(!find)printf("\n"); } return 0; }
41、冰雹数
任意给定一个大于1的正整数N，
如果是偶数，执行： N / 2
如果是大于1的奇数，执行： N * 3 + 1
生成的新的数字再执行同样的动作，循环往复。
通过观察发现，这个数字会一会儿上升到很高，
一会儿又降落下来。
就这样起起落落的，但最终必会落到“1”
这有点像小冰雹粒子在冰雹云中翻滚增长的样子。
比如N=9
9,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
可以看到，N=9的时候，这个“小冰雹”最高冲到了52这个高度。
输入一个整数M，请输出一个正整数，表示所有不大于M的数字N中，经过冰雹数变换过程中，最高冲到了多少。
注意：从2到M这M-1个数字中，每一个数字N都能得到一系列冰雹数，需要求得所有冰雹数的最大值。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <stdio.h> int num[10001]; int createNum(int n) { int max=n; while(n!=1) { if(n%2==0) n/=2; else { n=3*n+1; if(n>max) max=n; } } return max; } void initNum(int num[10001],int n) { num[0]=0; num[1]=1; int i,temp; for(i=2;i<=n;i++) { temp=createNum(i); if(temp>num[i-1])num[i]=temp; else num[i]=num[i-1]; } } int main() { int n; scanf("%d",&n); initNum(num,n); printf("%d\n",num[n]); return 0; }
42、小数第n位
我们知道，整数做除法时，有时得到有限小数，有时得到无限循环小数。
如果我们把有限小数的末尾加上无限多个0，它们就有了统一的形式。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> // 被除数设置为temp 每次除法之后被除数temp=a%b; int main() { int a,b,n; scanf("%d%d%d",&a,&b,&n); int temp=a%b*10;//代表小数部分的第一个被除数 int t;//代表小数后第i位的值 int flag[10000]={0};//记录除数第一次出现的位置 int i,len,have=0; //have=0代表未遇到过循环节 have=1代表已经遇到过循环节 for(i=1;i<n;i++) { //遇到了循环节 (从小数的第一位开始 本例可通过) if(!have&&flag[temp])//之前出现过此值 代表是循环节的开始 { len=i-flag[temp];//循环节的长度 while(i+len<n)i+=len;//循环节直接跳过 have=1; i--; continue; } //已经遇到了循环节 else if(have) { temp=temp%b*10; } else//没有遇到循环节 { flag[temp]=i;//记录除数temp第一次出现的位置i temp=temp%b*10; } } for(i=0;i<3;i++)//得出结果 { printf("%d",temp/b); temp=temp%b*10; } return 0; }
43、丑数
对于一给定的素数集合 S = {p1, p2, …, pK}, 来考虑那些质因数全部属于S 的数的集合。
这个集合包括，p1, p1p2（即p1乘以p2）, p1p3, 和 p1p2p3 (还有其它很多)。
这是个对于一个集合S的丑数集合。注意：我们不认为1 是一个丑数。
你的工作是对于输入的集合S去寻找集合中的第N个丑数。
说明：结果不超过32位整数能表示的范围
比如：S={2, 3, 5, 7}
则前15个丑数为：
2,3,4,5,6,7,8,9,10,12,14,15,16,18,20
#include <stdio.h> int n,k,a[110],f[110000],bk[110]; int minn; //第i个丑数一定是前i-1个丑数中的某一个 乘以 某一个一个素数得到的 且其值为符合条件的值中最小的 int main() { int i,j,t; scanf("%d%d",&k,&n); for(i=1;i<=k;i++) scanf("%d",&a[i]);//输入 f[0]=1;//假设第0项是为1 for(i=1;i<=n;i++)//暴力的从1枚举到n 个丑数 { minn=2147483647;//2^31-1（最大值） for(j=1;j<=k;j++)//暴力枚举每一个素数 { /* for(t=0;t<i;t++)//枚举以前出现的过的丑数 { if(a[j]*f[t]>f[i-1])//如果素数乘以出现过的丑数 满足要求 { minn=minn<a[j]*f[t]?minn:a[j]*f[t]; break;//当前素数乘丑数结束 枚举下一个素数 } }*/ //改进第三个循环 在bk[j]中记录 上一次满足第j个素数的丑数是第几个 while(a[j]*f[bk[j]]<=f[i-1])bk[j]++; minn=minn<a[j]*f[bk[j]]?minn:a[j]*f[bk[j]]; } f[i]=minn;//赋值 }; printf("%d\n",f[n]);//输出 return 0; }
44、不同单词个数统计
对于一给定的素数集合 S = {p1, p2, …, pK}, 来考虑那些质因数全部属于S 的数的集合。
这个集合包括，p1, p1p2（即p1乘以p2）, p1p3, 和 p1p2p3 (还有其它很多)。
这是个对于一个集合S的丑数集合。注意：我们不认为1 是一个丑数。
你的工作是对于输入的集合S去寻找集合中的第N个丑数。
说明：结果不超过32位整数能表示的范围
比如：S={2, 3, 5, 7}
则前15个丑数为：
2,3,4,5,6,7,8,9,10,12,14,15,16,18,20
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> char words[100][100]; int size=0; int haveSame(char c[100]) { int i; for(i=0;i<size;i++) if(!strcmp(words[i],c))//相同 return 1; return 0; } int CountDifferentWords(char str[]) { int i,j,flag=0,len=strlen(str),start_index; char temp[100]; for(i=0;i<len;i++) { if(str[i]!=\' \'&&flag==0) { flag=1; start_index=i; } else if(flag==1&&str[i]==\' \') { flag=0; strncpy(temp,&str[start_index],i-start_index); temp[i-start_index]=\'\0\'; if(!haveSame(temp)) strcpy(words[size++],temp); } } if(flag) { strncpy(temp,&str[start_index],i-start_index); temp[i-start_index]=\'\0\'; if(!haveSame(temp)) strcpy(words[size++],temp); } return size; } int main() { char ch[101]; scanf("%[^\n]",&ch); printf("%d\n",CountDifferentWords(&ch[0])); return 0; }
45、笨小猴
笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！
这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> const int prime[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};//打表 int getLuckyWord(char ch[110]) { int words[26]={0}; int i,len=strlen(ch); if(!len)return 0; for(i=0;i<len;i++) words[ch[i]-\'a\']++; int max=0,min=110; for(i=0;i<26;i++) { if(words[i]>max)max=words[i]; if(words[i]>0&&words[i]<min)min=words[i]; } int res=max-min; for(i=0;i<25;i++) { if(res==prime[i])return res; else if(res<prime[i])return 0; } return 0; } int main() { char ch[110]; scanf("%s",&ch); int res=getLuckyWord(ch); if(!res) printf("No Answer\n0\n"); else printf("Lucky Word\n%d\n",res); return 0; }
46、字串统计
给定一个长度为n的字符串S，还有一个数字L，统计长度大于等于L的出现次数最多的子串（不同的出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> //将res值设为str 最多出现次数初值max为1 //从长度n=len-1开始 遍历到n=min_n 依次取子串 统计次数 int main() { int min_n,n,i,j,count; char str[61],res[61]; scanf("%d",&min_n);getchar(); scanf("%s",str); strcpy(res,str); int len=strlen(str); int max=1;//出现次数 for(n=len-1;n>=min_n;n--) { for(i=0;i<len-n;i++)//对比长度为n的串 { count=0; for(j=0;j<len-n;j++)//逐个对比 { if(strncmp(&str[i],&str[j],n)==0) count++; } if(count>max) { strncpy(res,&str[i],n); res[n]=\'\0\'; max=count; } } } printf("%s\n",res); return 0; }
47、Anagrams问题
Anagrams指的是具有如下特性的两个单词：在这两个单词当中，每一个英文字母（不区分大小写）所出现的次数都是相同的。例如，“Unclear”和“Nuclear”、“Rimon”和“MinOR”都是Anagrams。编写一个程序，输入两个单词，然后判断一下，这两个单词是否是Anagrams。每一个单词的长度不会超过80个字符，而且是大小写无关的。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int isAnagrams(char a[81],char b[81]) { int len1=strlen(a),len2=strlen(b); if(len1!=len2) return 0; int words1[26]; int words2[26]; memset(words1,0,sizeof(int)*26); memset(words2,0,sizeof(int)*26); int i; for(i=0;i<len1;i++) { if(a[i]>=\'a\'&&a[i]<=\'z\') words1[a[i]-\'a\']++; else words1[a[i]-\'A\']++; if(b[i]>=\'a\'&&b[i]<=\'z\') words2[b[i]-\'a\']++; else words2[b[i]-\'A\']++; } for(i=0;i<26;i++) if(words1[i]!=words2[i])return 0; return 1; } int main() { char a[81],b[81]; scanf("%s",a); getchar(); scanf("%s",b); int res=isAnagrams(a,b); if(!res) printf("N\n"); else printf("Y\n"); return 0; }
48、身份证号码升级
从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××年
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> void change(char a[16]) { char res[19]; int i,size; for(i=0;i<6;i++)res[i]=a[i]; res[6]=\'1\'; res[7]=\'9\'; size=8; for(i=6;i<15;i++)res[size++]=a[i]; int sum=0; int weight[17]={7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2}; res[17]=\'\0\'; for(i=0;i<17;i++) sum+=((res[i]-\'0\')*weight[i]); sum=sum%11; char val[11]={\'1\',\'0\',\'x\',\'9\',\'8\',\'7\',\'6\',\'5\',\'4\',\'3\',\'2\'}; res[17]=val[sum]; res[18]=\'\0\'; printf("%s\n",res); } int main() { char a[16];//="110105491231002"; scanf("%s",a); change(a); return 0; }
49、实数相加
计算两个实数相加的结果。
输入的实数满足如下要求: (1) 小数点前的整数部分最多100位，(2) 小数点后的小数部分最多100位.
int main() { string a,b; cin>>a>>b; //统计a,b的整数部分 与 小数部分的长度 int alen=a.length(),blen=b.length(); int i,flag; int azlen=0,axlen=0,bzlen=0,bxlen=0;//分别代表a,b的整数部分长度与小数部分长度 flag=0; for(i=0;i<alen;i++) { if(a[i]==\'.\')flag=1; else if(!flag)azlen++; else axlen++; } flag=0; for(i=0;i<blen;i++) { if(b[i]==\'.\')flag=1; else if(!flag)bzlen++; else bxlen++; } //统一整数部分格式 while(azlen>bzlen){b=\'0\'+b;bzlen++;} while(bzlen>azlen){a=\'0\'+a;azlen++;} //统一小数部分格式 while(axlen>bxlen){if(!bxlen)b=b+".0";else b=b+\'0\';bxlen++;} while(bxlen>axlen){if(!axlen)a=a+".0";else a=a+\'0\';axlen++;} //整数部分和小数部分 长度统一后的string 相加 zlen 整数部分长度, xlen小数部分的长度 int zlen=azlen,xlen=axlen; int z[zlen+1]; memset(z,0,sizeof(int)*(zlen+1)); int x[xlen+1]; memset(x,0,sizeof(int)*(xlen+1)); int x_size=0,carry=0; //先算小数部分 for(i=zlen+xlen;i>zlen;i--,x_size++) { x[x_size]+=a[i]-\'0\'+b[i]-\'0\'; if(x[x_size]>=10) { x[x_size+1]++; x[x_size]-=10; } } if(x[x_size]==0)x_size--;//无进位 else {carry=1;x_size--;} int z_size=0; z[0]=carry; for(i=zlen-1;i>=0;i--,z_size++) { z[z_size]+=a[i]-\'0\'+b[i]-\'0\'; if(z[z_size]>=10) { z[z_size+1]++; z[z_size]-=10; } } if(z[z_size]==0)z_size--;//无进位 for(i=z_size;i>=0;i--)cout<<z[i]; if(x_size>0)cout<<"."; for(i=x_size;i>=0;i--)cout<<x[i]; }
50、彩票
为丰富男生节活动，女生设置彩票抽奖环节，规则如下：
1、每张彩票上印有7个各不相同的号码，且这些号码的取值范围为[1, 33]；
2、每次在兑奖前都会公布一个由七个互不相同的号码构成的中奖号码；
3、共设置7个奖项，特等奖和一等奖至六等奖。兑奖规则如下：
特等奖：要求彩票上的7个号码都出现在中奖号码中；
一等奖：要求彩票上的6个号码出现在中奖号码中；
二等奖：要求彩票上的5个号码出现在中奖号码中；
……
六等奖：要求彩票上的1个号码出现在中奖号码中；
注：不考虑号码出现的顺序，例如若中奖号码为23 31 1 14 19 17 18，则彩票12 8 9 23 1 16 7由于其中有两个号码（23和1）出现在中奖号码中，所以该彩票中了五等奖。
现已知中奖号码和李华买的若干彩票的号码，请你写一个程序判断他的彩票中奖情况。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int main() { int n,i,j,temp,count; int arr[7]; int isTarget[34]; int res[7]; memset(isTarget,0,sizeof(int)*34); memset(res,0,sizeof(int)*7); scanf("%d",&n); for(i=0;i<7;i++) { scanf("%d",&temp); isTarget[temp]=1; } for(i=0;i<n;i++) { count=-1; for(j=0;j<7;j++) { scanf("%d",&temp); if(isTarget[temp])count++; } if(count!=-1)res[count]++; } for(i=6;i>=0;i--) printf("%d ",res[i]); printf("\n"); return 0; }
51、质数的后代
如果一个合数由两个质数相乘而得，那么我们就叫它是质数们的直接后代。现在，给你一系列自然数，判断它们是否是质数的直接后代。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int PrimeNum[100001]; int isPrimeNum(int num) { int i; for(i=2;i<=sqrt(num);i++) if(num%i==0)return 0; return 1; } int isOffspringOfPrimeNum(int num) { int i; for(i=2;i<=num/2;i++) { if(!PrimeNum[i])continue; if(num%i==0&&PrimeNum[num/i]) return 1; } return 0; } int main() { PrimeNum[1]=0; int i,n,t; for(i=2;i<100000;i++)PrimeNum[i]=isPrimeNum(i); scanf("%d",&n); while(n--) { scanf("%d",&t); if(isOffspringOfPrimeNum(t)) printf("Yes\n"); else printf("No\n"); } return 0; }
52、高精度乘法
在C/C++语言中，整型所能表示的范围一般为-231到231（大约21亿）,即使long long型，一般也只能表示到-263到263。要想计算更加规模的数，就要用软件来扩展了，比如用数组或字符串来模拟更多规模的数及共运算。
现在输入两个整数，请输出它们的乘积。
//用一个数的每一位乘以另一个数 再处理剩下的进位
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> char res[20001]; int res_size=0; char a[10001]; char b[10001]; int main() { scanf("%s",a);getchar(); scanf("%s",b); memset(res,\'0\',20001); int alen=strlen(a),blen=strlen(b); //将a当做被乘数,将b当做乘数 int i,j,b_val,a_val,carry=0,res_index,temp; for(i=blen-1;i>=0;i--)//对b中的每一位相乘 { b_val=b[i]-\'0\'; carry=0; res_index=(blen-1)-i;//代表当前这个b_val 乘完需要加到的位置 for(j=alen-1;j>=0;j--,res_index++)//b_val分别对 a中的每一位相乘 { a_val=a[j]-\'0\'; temp=a_val*b_val+carry+res[res_index]-\'0\'; res[res_index]=temp%10+\'0\'; carry=temp/10; } //处理剩下的进位 while(carry) { temp=carry+res[res_index]-\'0\'; res[res_index]=temp%10+\'0\'; carry=temp/10; res_index++; } } for(i=res_index-1;i>=0;i--) printf("%c",res[i]); return 0; }
53、阶乘尾数
给定n和len，输出n!末尾len位。
#include<stdio.h> int main() { int n,len; int i,j=0,a[10]={0}; scanf("%d%d",&n,&len); long long res=1; for(i=1;i<=n;i++) { res*=i; //因为len<=0 所以10位以上的并不影响答案 res%=10000000000; } //将剩下的10位存入数组a中 从低位向高位存 while(res) { a[j++]=res%10; res/=10; } //从高位len-1开始 输出末尾len位 for(i=len-1;i>=0;i--) printf("%d",a[i]); return 0; }
54、寂寞的数
道德经曰：一生二，二生三，三生万物。
对于任意正整数n，我们定义d(n)的值为为n加上组成n的各个数字的和。例如，d(23)=23+2+3=28, d(1481)=1481+1+4+8+1=1495。
因此，给定了任意一个n作为起点，你可以构造如下一个递增序列：n,d(n),d(d(n)),d(d(d(n)))….例如，从33开始的递增序列为：
33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, …
我们把n叫做d(n)的生成元，在上面的数列中，33是39的生成元，39是51的生成元，等等。有一些数字甚至可以有两个生成元，比如101，可以由91和100生成。但也有一些数字没有任何生成元，如42。我们把这样的数字称为寂寞的数字。
//从1-n开始生成数 对于生成出来的数 标记为1 未被标记的则为寂寞的数
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int generate(int n) { int res=n; int temp=n; while(temp) { res+=temp%10; temp/=10; } return res; } int main() { int n,i,temp; scanf("%d", &n); int res[10001]; memset(res,0,sizeof(int)*10001); res[1]=0; for(i=1;i<n;i++) { temp=i; while(temp<n) { temp=generate(temp); if(temp<n)res[temp]=1; } } for(i=1;i<n;i++) if(!res[i]) printf("%d\n",i); return 0; }
55 麦森数
作者: Turbo时间限制: 1S章节: 基本练习（数组）
问题描述 :
形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。
任务：输入P（1000<P<3100000），计算2P-1的位数及最后500位数字（用十进制高精度数表示）
输入说明 :
输入只包含一个整数P（100<P<3100000）
不必验证2P-1与P是否为素数。
输出说明 :
第一行：十进制高精度数2P-1的位数。
第2-11行：十进制高精度数2P-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）
输入范例 :
1279
输出范例 :
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087
#include <iostream> #include <cmath> #include <cstring> using namespace std; int t[1001], res[1001], tmp[1001]; void mul1()//奇数 { memset(tmp, 0, sizeof(tmp)); for (int i = 1; i <= 500; i++) { for (int j = 1; j <= 500; j++) { tmp[i + j - 1] += res[i] * t[j]; } for (int i = 1; i <= 500; i++) { tmp[i + 1] += tmp[i] / 10; tmp[i] = tmp[i] % 10; } } memcpy(res, tmp, sizeof(res)); } void mul2()//偶数 { memset(tmp, 0, sizeof(tmp)); for (int i = 1; i <= 500; i++) { for (int j = 1; j <= 500; j++) { tmp[i + j - 1]+= t[i] * t[j]; } for (int i = 1; i <= 500; i++) { tmp[i + 1] += tmp[i] / 10; tmp[i] = tmp[i] % 10; } } memcpy(t, tmp, sizeof(t)); } int main() { int p; cin >> p; cout << (int)(log10(2)*p + 1) << endl; res[1] = 1; t[1] = 2; while (p != 0) { if (p % 2 == 1) mul1(); p /= 2; mul2(); } res[1]--; for (int i = 500; i >= 1; i--) { if (i != 500 && i % 50 == 0) cout << endl << res[i]; else cout << res[i]; } return 0; }
56、数列
给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是：
1，3，4，9，10，12，13，…
（该序列实际上就是：30，31，30+31，32，30+32，31+32，30+31+32，…）
请你求出这个序列的第N项的值（用10进制数表示）。
例如，对于k=3，N=100，正确答案应该是981。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> //对于k //序列的形式其实就是 //k^0,k^1,k^0+k^1,3^2 //也就是k进制下 1,10,11,100 //十进制 1 2 3 4 //第n项就是 k进制形式的（n的二进制） 再转十进制 int my_pow(int k,int n) { int res=1,i; for(i=0;i<n;i++)res*=k; return res; } int main() { int k,n; char arr[12]; scanf("%d%d",&k,&n); itoa(n,arr,2); int len=strlen(arr),i; __int64 res=0; for(i=0;i<len;i++) //res+=(__int64)(pow(k,i)+0.5)*(__int64)(arr[len-i-1]-\'0\'); res+=(__int64)(my_pow(k,i))*(__int64)(arr[len-i-1]-\'0\'); printf("%I64d\n",res); return 0; }
57、孪生素数
孪生素数就是指相差2的素数对，例如3和5，5和7，11和13…。这个猜想正式由希尔伯特在1900年国际数学家大会的报告上第8个问题中提出，可以这样描述：存在无穷多个素数p，使得p + 2是素数。素数对（p, p + 2）称为孪生素数。
现在给定任何正整数 N (< 10 ^ 5), 请你计算不大于 N 的孪生素数的对数。
//动态规划 若新增素数与前面两个素数有一个是相差2 则素数对数+1
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int isPrimeNum(int n) { int i; for(i=2;i<=sqrt(n);i++) if(n%i==0)return 0; return 1; } int main() { int i,cur=1,pre_prime=3,cur_prime=5,arr[100001]; arr[0]=arr[1]=arr[2]=arr[3]=arr[4]=0; arr[5]=1; for(i=6;i<100001;i++) { if(isPrimeNum(i)) { if(i-pre_prime==2||i-cur_prime==2) arr[i]=(++cur); pre_prime=cur_prime; cur_prime=i; } arr[i]=cur; } int n; while(1) { scanf("%d",&n); if(n<0)break; printf("%d\n",arr[n]); } return 0; }
58、集合运算
给出两个整数集合A、B，求出他们的交集、并集以及B在A中的余集。
//交集是相同的
//余集是 该集合减去交集
//并集是 另一个集合加余集
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int cmp(const void* a,const void* b) { return *(int*)a-*(int*)b; } void my_print(int a[],int len) { if(!len)return; int i; for(i=0;i<len;i++) printf("%d ",a[i]); printf("\n"); } int main() { int a[1001],b[1001]; int m,n; scanf("%d",&n); int i,j; for(i=0;i<n;i++)scanf("%d",&a[i]); scanf("%d",&m); for(i=0;i<m;i++)scanf("%d",&b[i]); qsort(a,n,sizeof(int),cmp); qsort(b,m,sizeof(int),cmp); int res1[1001],res2[2002],res3[1001],l1=0,l2=0,l3=0; //算交集中的元素 for(i=0;i<n;i++) for(j=0;j<m;j++) if(a[i]==b[j])//同时在a b中是交集中的元素 res1[l1++]=a[i]; int t=0; //B在A中的余集 在A中但不在交集中 for(i=0;i<n&&t<l1;i++) { if(a[i]!=res1[t])//不在交集中 但在A中 res3[l3++]=a[i]; else t++; } //A中剩余的元素都是 B在A中的余集 for(;i<n;i++)res3[l3++]=a[i]; //AB的并集 等于B中的元素 加 B在A中的余集中的元素 for(i=0;i<m;i++)res2[i]=b[i]; for(i=m;i<m+l3;i++)res2[i]=res3[i-m]; l2=m+l3; qsort(res2,l2,sizeof(int),cmp); my_print(res1,l1); my_print(res2,l2); my_print(res3,l3); return 0; }
59、区间k大数查询
给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。
注意，由于存在相等的元素，因此，第2大的数可能和第1大的数相等。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int cmp(const void* a,const void* b) { return *(int*)b-*(int*)a; } int main() { int n,m,arr[1000],temp[1000]; scanf("%d",&n); int i,j; for(i=0;i<n;i++)scanf("%d",&arr[i]); scanf("%d",&m); int start,end,k,len; while(m--) { scanf("%d%d%d",&start,&end,&k); len=end-start+1; memcpy(temp,&arr[start-1],sizeof(int)*(len)); qsort(temp,len,sizeof(int),cmp); printf("%d\n",temp[k-1]); } return 0; }
60、明明的随机数
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int cmp(const void* a,const void* b) { return *(int*)a-*(int*)b; } void my_print(int a[],int n) { int i; for(i=0;i<n;i++)printf("%d ",a[i]); printf("\n"); } int main() { int arr[100]; int n,i; scanf("%d",&n); for(i=0;i<n;i++)scanf("%d",&arr[i]); qsort(arr,n,sizeof(int),cmp); int size=1; for(i=1;i<n;i++) { if(arr[i]!=arr[size-1]) arr[size++]=arr[i]; } printf("%d\n",size); my_print(arr,size); return 0; }
61、数的统计
在一个有限的正整数序列中，有些数会多次重复出现在这个序列中。
如序列：3，1，2，1，5，1，2。其中1就出现3次，2出现2次，3出现1 次，5出现1次。
你的任务是对于给定的正整数序列，从小到大依次输出序列中出现的数及出现的次数。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int cmp(const void* a,const void* b) { return *(int*)a-*(int*)b; } void my_print(int a[],int n) { int i; for(i=0;i<n;i++)printf("%d ",a[i]); printf("\n"); } int main() { int arr[1000]; int n,i; scanf("%d",&n); for(i=0;i<n;i++)scanf("%d",&arr[i]); qsort(arr,n,sizeof(int),cmp); int count=1,pre=arr[0]; for(i=1;i<n;i++) { if(arr[i]==pre) count++; else { printf("%d %d\n",pre,count); count=1; pre=arr[i]; } } printf("%d %d\n",pre,count); return 0; }
62、数字黑洞
任意一个四位数，只要它们各个位上的数字是不全相同的，就有这样的规律：
1)将组成该四位数的四个数字由大到小排列，形成由这四个数字构成的最大的四位数；
2)将组成该四位数的四个数字由小到大排列，形成由这四个数字构成的最小的四位数(如果四个数中含有0，则得到的数不足四位)；
3)求两个数的差，得到一个新的四位数(高位零保留)。
重复以上过程，最后一定会得到的结果是6174。
比如：4312 3087 8352 6174，经过三次变换，得到6174
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int cmp(const void* a,const void* b) { return *(int*)a-*(int*)b; } int getNext(int n) { int i,arr[4]; for(i=0;i<4;i++) { arr[i]=n%10; n/=10; } qsort(arr,4,sizeof(int),cmp); int max=0,min=0; for(i=0;i<4;i++) { max=max*10+arr[3-i]; min=min*10+arr[i]; } return max-min; } int main() { int n; scanf("%d",&n); int count=0; while(n!=6174) { n=getNext(n); count++; } printf("%d\n",count); return 0; }
63、质数的乘积
Torry从小喜爱数学。一天，老师告诉他，像2、3、5、7……这样的数叫做质数。Torry突然想到一个问题，前10、100、1000、10000……个质数的乘积是多少呢？他把这个问题告诉老师。老师愣住了，一时回答不出来。于是Torry求助于会编程的你，请你算出前n个质数的乘积。不过，考虑到你才接触编程不久，Torry只要你算出这个数模上50000的值。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> long long PRIME_NUM[100230]; long long isPrimeNum(long long n) { long long i; for(i=2;i*i<=n;i++) if(n%i==0)return 0; return 1; } int main() { long long i,size=0,n; for(i=2;i<1300000;i++) if(isPrimeNum(i))PRIME_NUM[size++]=i; scanf("%lld",&n); if(!n) { printf("1\n"); return 0; } long long res=1; for(i=0;i<n;i++) res=(res*PRIME_NUM[i])%50000; printf("%lld\n",res); return 0; }
64、暗恋
同在一个高中，他却不敢去找她，虽然在别人看来，那是再简单不过的事。暗恋，是他唯一能做的事。他只能在每天课间操的时候，望望她的位置，看看她倾心的动作，就够了。操场上的彩砖啊，你们的位置，就是他们能够站立的地方，他俩的关系就像砖与砖之间一样固定，无法动摇。还记得当初铺砖的工人，将整个操场按正方形铺砖（整个操场可视为R行C列的矩阵，矩阵的每个元素为一块正方形砖块），正方形砖块有两种，一种为蓝色，另一种为红色。我们定义他和她之间的“爱情指标”为最大纯色正方形的面积，请你写一个程序求出“爱情指标”
#define MAX 201 int arr[MAX][MAX]={0}; int help[MAX][MAX]={0};//更新max_len轮 每轮在(i,j)位置上记录 以(i,j)为左上角 len为边长内 所有值的加和 //以(x,y)为正方形的左上角的起点,len为边长 //根据加和与面积的关系检查此正方形内所有的值是否相同 int getRightAndBottomSum(int x,int y,int len) { int sum=0,i,j; for(i=x+len-1,j=y;j<y+len;j++)sum+=arr[i][j];//Right for(j=y+len-1,i=x;i<x+len-1;i++)sum+=arr[i][j];//Bottom return sum; } void my_print(int row,int col) { int i,j; for(i=0;i<row;i++) { for(j=0;j<col;j++) printf("%d ",help[i][j]); printf("\n"); } printf("\n"); } int main() { int row,col,i,j,len; scanf("%d %d",&row,&col); for(i=0;i<row;i++)for(j=0;j<col;j++) { scanf("%d",&arr[i][j]); help[i][j]=arr[i][j];//第一轮直接赋值 } int max_len=row>col?col:row;//最大的正方形边长为 col row中小的一个 int res_len=1;//一定有最小边长1 for(len=2;len<=max_len;len++) { //更新第len轮 //my_print(row,col); for(i=0;i<row;i++) { for(j=0;j<col;j++) { if(i+len-1<row&&j+len-1<col) { help[i][j]+=getRightAndBottomSum(i,j,len); if(help[i][j]==0||help[i][j]==len*len) res_len=len; } } } } printf("%d\n",res_len*res_len); return 0; }
65、扫雷
扫雷游戏你一定玩过吧！现在给你若干个n×m的地雷阵，请你计算出每个矩阵中每个单元格相邻单元格内地雷的个数，每个单元格最多有8个相邻的单元格。 0<n,m<=100
//对于每个非雷位置向一周判断有几个雷
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int getNeibeighorBomb(char arr[100][100],int m,int n,int x,int y) { int op[8][2]= {{-1,-1},{-1,0},{-1,1}, {0,-1},{0,1}, {1,-1},{1,0},{1,1} }; int k,i,j,res=0; for(k=0;k<8;k++) { i=x+op[k][0]; j=y+op[k][1]; if(i>=0&&i<m&&j>=0&&j<n&&arr[i][j]==\'*\') res++; } return res; } int main() { int m,n,i,j,cnt=1; char arr[100][100]; while(~scanf("%d%d",&m,&n)&&getchar()) { if(m==0&&n==0)break; for(i=0;i<m;i++) { for(j=0;j<n;j++) scanf("%c",&arr[i][j]); getchar(); } printf("Field #%d:\n",cnt++); for(i=0;i<m;i++) { for(j=0;j<n;j++) { if(arr[i][j]==\'*\') printf("*"); else printf("%d",getNeibeighorBomb(arr,m,n,i,j)); } printf("\n"); } printf("\n"); } return 0; }
66、矩阵乘方
给定一个矩阵A,一个非负整数b和一个正整数m，求A的b次方除m的余数。
其中一个nxn的矩阵除m的余数得到的仍是一个nxn的矩阵，这个矩阵的每一个元素是原矩阵对应位置上的数除m的余数。
要计算这个问题，可以将A连乘b次，每次都对m求余，但这种方法特别慢，当b较大时无法使用。下面给出一种较快的算法(用A^b表示A的b次方)：
若b=0，则A^b%m=I%m。其中I表示单位矩阵。
若b为偶数，则A^b%m=(A^(b/2)%m)^2%m，即先把A乘b/2次方对m求余，然后再平方后对m求余。
若b为奇数，则A^b%m=(A^(b-1)%m)*a%m，即先求A乘b-1次方对m求余，然后再乘A后对m求余。
这种方法速度较快，请使用这种方法计算A^b%m，其中A是一个2×2的矩阵，m不大于10000。
#include <stdio.h> #define SIZE 2 void copyMatrix(int a[][SIZE], int b[][SIZE]) { int i, j; for(i=0;i<SIZE;i++) for(j=0;j<SIZE;j++) a[i][j]=b[i][j]; } void matrixMulWithMod(int a[][SIZE],int b[][SIZE],int m) { int i,j,k; int sum,t[SIZE][SIZE]; for(i=0;i<SIZE;i++) for(j=0;j<SIZE;j++) { sum=0; for(k=0;k<SIZE;k++) sum+=a[i][k]*b[k][j]; t[i][j]=sum%m; } copyMatrix(a,t); } void fun(int res[][SIZE],int b,int m) { int i,j; if(!b) { for(i=0;i<SIZE;i++) for(j=0;j<SIZE;j++) { if(i==j)res[i][j]=1%m; else res[i][j]=0%m; } } //奇数 else if(b%2) { int temp[SIZE][SIZE]; copyMatrix(temp,res); fun(temp,b-1,m); matrixMulWithMod(res,temp,m); } //偶数 else { fun(res,b/2,m); matrixMulWithMod(res,res,m); } } int main() { int b,m,i,j,res[SIZE][SIZE]; scanf("%d %d",&b,&m); for(i=0;i<SIZE;i++)for(j=0;j<SIZE;j++)scanf("%d",&res[i][j]); fun(res,b,m); for(i=0;i<SIZE;i++) { for(j=0;j<SIZE;j++) printf("%d ",res[i][j]); printf("\n"); } return 0; }
67、字符串编辑
从键盘输入一个字符串（长度<=40个字符），并以字符 ’.’ 结束。编辑功能有：
1 D：删除一个字符，命令的方式为： D a 其中a为被删除的字符，例如：D s 表示删除字符 ’s’ ，若字符串中有多个 ‘s’，则删除第一次出现的。
2 I：插入一个字符，命令的格式为：I a1 a2 其中a1表示插入到指定字符前面，a2表示将要插入的字符。例如：I s d 表示在指定字符 ’s’ 的前面插入字符 ‘d’ ，若原串中有多个 ‘s’ ，则插入在最后一个字符的前面。
3 R：替换一个字符，命令格式为：R a1 a2 其中a1为被替换的字符，a2为替换的字符，若在原串中有多个a1则应全部替换。
在编辑过程中，若出现被改的字符不存在时，则给出提示信息。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> void del(char str[100],char ch) { int len=strlen(str),i,flag=0; for(i=0;i<len;i++) { if(str[i]==ch) { strcpy(&str[i],&str[i+1]); flag=1; break; } } if(flag==0)printf("指定字符不存在\n"); else printf("%s\n",str); } void insert(char str[100],char ch,char d) { int len=strlen(str),i,index=-1,flag=0; for(i=0;i<len;i++) if(str[i]==ch) index=i; if(index!=-1) { for(i=0;i<index;i++)printf("%c",str[i]); printf("%c",d); for(i=index;i<len;i++)printf("%c",str[i]); printf("\n"); } else printf("指定字符不存在\n"); } void replace(char str[100],char a1,char a2) { int len=strlen(str),i,flag=0; for(i=0;i<len;i++) { if(str[i]==a1) { str[i]=a2; flag=1; } } if(flag==0)printf("指定字符不存在\n"); else printf("%s\n",str); } int main() { char str[100]; scanf("%[^\n]",str); getchar(); char op,ch1,ch2; scanf("%c",&op); getchar(); if(op==\'D\') { scanf("%c",&ch1); del(str,ch1); } else if(op==\'I\') { scanf("%c %c",&ch1,&ch2); insert(str,ch1,ch2); } else { scanf("%c %c",&ch1,&ch2); replace(str,ch1,ch2); } return 0; }
68、S01串
s01串初始为”0″
按以下方式变换：
0变1，1变01
所以，变换规律如下：
1次变换后：1；
2次变换后：01;
3次变换后：101；
4次变换后：01101；
5次变换后：10101101；
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> char res[100000],temp[100000]; int size_res,size_temp; void fun() { size_temp=0; int i; for(i=0;i<size_res;i++) { if(res[i]==\'0\') temp[size_temp++]=\'1\'; else { temp[size_temp++]=\'0\'; temp[size_temp++]=\'1\'; } } size_res=size_temp; memcpy(res,temp,sizeof(int)*size_res); } int main() { int n,i; scanf("%d",&n); res[0]=\'0\'; size_res=1; while(n--)fun(); for(i=0;i<size_res;i++)printf("%c",res[i]); printf("\n"); return 0; }
69、身份证排序
安全局搜索到了一批(n个)身份证号码，希望按出生日期对它们进行从大到小排序，如果有相同日期，则按身份证号码从大到小进行排序。身份证号码为18位的数字组成，出生日期为第7到第14位
//先对比生日
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int cmp(const void* a,const void *b) { char* p2=(char*)a; char* p1=(char*)b; int t=strncmp(&p1[6],&p2[6],8); if(!t)return strcmp(&p1[0],&p2[0]); else return t; } int main() { int n,i; char list[100000][19]; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%s",list[i]); getchar(); } qsort(list,n,sizeof(char)*19,cmp); for(i=0;i<n;i++) printf("%s\n",list[i]); return 0; }
70、回文数
若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
我们现在需要产生回文数，步骤如下：
给定一个10进制数56，将56加65（即把56从右向左读），得到121是一个回文数。
//将一个r进制数的每位 当做十进制存入int数组中 先没有进位的相加 加一半复制一般 因为一个数的倒着 与正着相加 若不进位一定是回文数 然后再处理进位 再判断是否是回文
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> char s[201];//输入字符串 int a[401],size; //数组a为高精度数组，size为它的长度 int judge() //判断一个数是否回文 { int t=size/2; int i; for (i=0;i<=t;++i) if (a[i]!=a[size-i]) return 1; return 0; } int main() { int n,step=0; int i; scanf("%d%s",&n,s); size=strlen(s)-1; for (i=0;i<=size;++i) //将字符转化为数字 if (s[i]>=\'0\'&&s[i]<=\'9\') a[size-i]=s[i]-\'0\'; else a[size-i]=s[i]-\'A\'+10; //高进制数 while (judge()) { if (step>30) //如果超过三十步就直接结束程序 break; for (i=0;i<=size;i++) //算完再进位 if (i<=size/2) a[i]+=a[size-i]; else a[i]=a[size-i]; //因为最后算出来的数如果不进位的话就一定是回文的，所以数组的后一半直接复制前一半就好了 for (i=0;i<=size;i++) //进位 if (a[i]>=n) a[i+1]++,a[i]-=n; if (a[size+1]) //注意如果首位进位，长度要增加 size++; step++; } if(step<=30) printf("STEP=%d\n",step); else printf("Impossible!\n"); return 0; }
71 窗体面积
作者: 5.3.2时间限制: 1S章节: 模拟
问题描述 :
你刚刚接手一项窗体界面工程。窗体界面还算简单，而且幸运的是，你不必显示实际的窗体。
有 5 种基本操作：
创建一个新窗体 将窗体置顶 将窗体置底 删除一个窗体 输出窗体可见部分的百分比（就是，不被其它窗体覆盖的部分）。
在输入文件中，操作以如下的格式出现。
创建一个新窗体：w(I,x,y,X,Y)
将窗体置顶： t(I)
将窗体置底： b(I)
删除一个窗体：d(I)
输出窗体可见部分的百分比：s(I)
I 是每个窗体唯一的标识符。表示符可以是 \’a\’..\’z\’, \’A\’..\’Z\’ 和 \’0\’..\’9\’ 中的任何一个。
输入文件中没有多余的空格。
（x,y）和（X,Y）是窗体的对角。当你创建一个窗体的时候，它自动被”置顶”。
你不能用已经存在的标识符来创建窗体，但是你可以删除一个窗体后再用已删除窗体的标识符来创建窗体。
坐标用正整数来表示，并且所有的窗体面积都不为 0（x <> X 且 y <> Y）。x 坐标和 y 坐标在 1 — 32767 的范围内。
输入说明 :
输入文件包含给你的解释程序的一系列命令，每行一个。命令字符串中不包含空格。当输入文件结束时，停止程序。
输出说明 :
只对于 s() 命令进行输出。当然，输入文件可能有许多 s() 命令，所以输出文件应该是一个百分比的序列，每行一个，百分比是窗体可见部分的百分比。百分比应该四舍五入到三位小数。
输入范例 :
w(m,4433,29340,20489,23437)
t(m)
w(k,12561,32740,15894,23338)
s(k)
b(k)
s(m)
s(k)
s(m)
t(m)
w(3,25372,7602,19920,7404)
s(3)
s(k)
b(k)
b(3)
s(3)
s(3)
w(p,1646,13411,13986,1550)
s(m)
s(k)
s(m)
输出范例 :
100.000
100.000
37.215
100.000
100.000
37.215
100.000
100.000
100.000
37.215
100.000
72、选女婿
倾国倾城的大家闺秀潘小姐要选夫婿啦！武林中各门各派，武林外各大户人家，闻讯纷纷前来，强势围观。前来参与竞选的男生藏龙卧虎，高手云集，才子遍布，帅哥纷纭，更不乏富二代，官二代，可谓声势空前。
每个人参与竞选的帅哥除了进行一段激情洋溢的求婚演讲以外，还要报上自己姓名、身高和体重，以及个人简历。最后再进行文武选拔，最后夺魁者方能得到潘小姐的芳心。
潘小姐不爱名利，只看人，第一关就是身高和体重要合格，即必须在其要求的范围内，否则直接排除在外，不允许参加下一轮的选拔。
潘小姐把首轮根据身高体重进行选拔的任务交给了你，请输出晋级第二轮的选手信息。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> typedef struct boy { char name[21]; int h; int w; }Boys; int cmp(const void*a,const void* b) { Boys* pa=(Boys*)a; Boys* pb=(Boys*)b; if(pa->h==pb->h) return pa->w-pb->w; else return pa->h-pb->h; } int main() { int n,i; Boys boys[1000]; scanf("%d",&n); getchar(); int a,b,c,d; for(i=0;i<n;i++) { scanf("%s%d%d",&boys[i].name,&boys[i].h,&boys[i].w); getchar(); } scanf("%d%d%d%d",&a,&b,&c,&d); qsort(boys,n,sizeof(Boys),cmp); int flag=0; for(i=0;i<n;i++) { if(boys[i].h>=a&&boys[i].h<=b&&boys[i].w>=c&&boys[i].w<=d) { printf("%s %d %d\n",boys[i].name,boys[i].h,boys[i].w); flag=1; } } if(!flag)printf("No\n"); return 0; }
73、多级排序
本学期大家学习了C语言程序设计，现在需要你实现一个成绩排名系统。
假设他们每个人都有三门课程，C语言程序设计、计算机导论和英语，要求把成绩好的同学放到前面。
具体要求是先按个人的总成绩进行排名，如果某两个人的总分相同，则按他们的C语言程序设计成绩进行排名，如果总成绩和C语言程序设计成绩都相同时，则再按照他们的计算机导论成绩进行排名（输入的数据保证这两个人的计算机导论成绩不会再相同）。try to do it ^_^！
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> typedef struct stu { char name[21]; int a; int b; int c; int total; }Stus; int cmp(const void*a,const void* b) { Stus* pa=(Stus*)a; Stus* pb=(Stus*)b; if(pa->total==pb->total&&pa->a==pb->a) return pb->b-pa->b; else if(pa->total==pb->total) return pb->a-pa->a; else return pb->total-pa->total; } int main() { int n,i; Stus stus[100]; while(~scanf("%d",&n)&&getchar()) { for(i=0;i<n;i++) { scanf("%s%d%d%d",&stus[i].name,&stus[i].a,&stus[i].b,&stus[i].c); getchar(); stus[i].total=stus[i].a+stus[i].b+stus[i].c; } qsort(stus,n,sizeof(Stus),cmp); for(i=0;i<n;i++) printf("%s %d %d %d %d\n",stus[i].name,stus[i].total,stus[i].a,stus[i].b,stus[i].c); printf("\n"); } return 0; }
74、学生选拔
多组测试数据。每组数据的第一行的数字n,m(1≤m,n≤1000)。n表示该班级有n个同学，m表示要选取每门课排名前m的学生。
以下n行每行由一个名字，一个语文成绩，一个数学成绩，一个英语成绩组成，表示一个同学的信息。
名字是一个由大小写字母组成的字符串，名字字符串最长长度为20，名字中间没有空格。每门课成绩是一个0到10000之间的整数。
数据保证，在同一组测试数据中，任意两个同学同一门课程的分数一定不相同。
说明：总共三门课，每门课录取前m个学生，则总共最多录取3*m个学生，但这些学生可能重复，即某个学生的两门课甚至三门课成绩都排在前m个，这样，录取的学生数将少于3*m。
//insert函数用于每次排序后将前m个学生加入所选学生的数组中 并去重
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> char res[1000][21]; int res_size=0; typedef struct stu { char name[21]; int a; int b; int c; }Stus; int cmp1(const void*a,const void* b) { Stus* pa=(Stus*)a; Stus* pb=(Stus*)b; return pb->a-pa->a; } int cmp2(const void*a,const void* b) { Stus* pa=(Stus*)a; Stus* pb=(Stus*)b; return pb->b-pa->b; } int cmp3(const void*a,const void* b) { Stus* pa=(Stus*)a; Stus* pb=(Stus*)b; return pb->c-pa->c; } int cmp4(const void*a,const void* b) { char *pa=(char*)a; char *pb=(char*)b; return strcmp(pa,pb); } void insert(char name[21]) { int i; for(i=0;i<res_size;i++) if(!strcmp(res[i],name)) break; //printf("%s %d %d\n",name,i,res_size); if(i==res_size) strcpy(res[res_size++],name); } /*void my_print(Stus stus[1000],int n) { int i; for(i=0;i<n;i++) printf("%s %d %d %d\n",stus[i].name,stus[i].a,stus[i].b,stus[i].c); printf("\n"); }*/ int main() { int n,m,i; Stus stus[1000]; while(~scanf("%d%d",&n,&m)&&getchar()) { res_size=0; for(i=0;i<n;i++) { scanf("%s%d%d%d",&stus[i].name,&stus[i].a,&stus[i].b,&stus[i].c); getchar(); } qsort(stus,n,sizeof(Stus),cmp1); //my_print(stus,n); for(i=0;i<m;i++)insert(stus[i].name); qsort(stus,n,sizeof(Stus),cmp2); //my_print(stus,n); for(i=0;i<m;i++)insert(stus[i].name); qsort(stus,n,sizeof(Stus),cmp3); //my_print(stus,n); for(i=0;i<m;i++)insert(stus[i].name); qsort(res,res_size,sizeof(char)*21,cmp4); for(i=0;i<res_size;i++) printf("%s\n",res[i]); printf("\n"); } return 0; }
75、长方形排序
现在有很多长方形，每个长方形有自己的编号，这个编号可以重复。每个长方形的长、宽、编号都是正整数。现在要求按照以下方式排序（所有排序规则是从小到大）：
1. 按照编号从小到大排序；
2. 对于编号相等的长方形，按照长方形的长从小到大排序；
3. 对于编号和长都相同的长方形，按照长方形的宽从小到大排序；
4. 如果编号、长和宽都相同，就只保留一个长方形用于排序，删除多余的长方形。最后将排好序的长方形按照指定格式输出。
//由于是长方形 输入时需要注意长和宽 大的为长
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> typedef struct rect { int a; int b; int c; }Rects; Rects rects[10000]; Rects res[10000]; int n; int res_size; int cmp(const void*a,const void* b) { Rects* pa=(Rects*)a; Rects* pb=(Rects*)b; if(pa->a==pb->a&&pa->b==pb->b) return pa->c-pb->c; else if(pa->a==pb->a) return pa->b-pb->b; return pa->a-pb->a; } void del_same() { int i; res_size=1; memcpy(&res[0],&rects[0],sizeof(Rects)); for(i=1;i<n;i++) if(rects[i].a==res[res_size-1].a&& rects[i].b==res[res_size-1].b&& rects[i].c==res[res_size-1].c) continue; else memcpy(&res[res_size++],&rects[i],sizeof(Rects)); } void my_print() { int i; for(i=0;i<n;i++) printf("%d %d %d\n",rects[i].a,rects[i].b,rects[i].c); printf("\n"); } int main() { int m,i; int len,width,t; scanf("%d",&m);getchar(); while(~scanf("%d",&n)&&getchar()) { for(i=0;i<n;i++) { scanf("%d%d%d",&rects[i].a,&len,&width); if(width>len) { t=len; len=width; width=t; } rects[i].b=len; rects[i].c=width; getchar(); } qsort(rects,n,sizeof(Rects),cmp); //my_print(); del_same(); for(i=0;i<res_size;i++) printf("%d %d %d\n",res[i].a,res[i].b,res[i].c); printf("\n"); } return 0; }
76、新生舞会
第一行一个整数n（2<=n<=1000），表示学生人数。接下来的n行每行依次包含一名新生的姓名、学号、性别，分别用一个空格隔开。
之后的一行是一个整数m(1<=m<=1000)，表示询问舞伴的对数。接着的m行每行包含两个舞伴的信息（姓名或学号），保证两个信息不属于同一人，中间用一个空格隔开。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> typedef struct stu { char name[21]; char sno[11]; char sex[2]; }Stus; Stus stus[1000]; int n; int findStuByNameOrSno(char info[]) { int i; for(i=0;i<n;i++) if(strcmp(stus[i].name,&info[0])==0|| strcmp(stus[i].sno,&info[0])==0) return i; return -1; } int main() { int i,m; char a[21],b[21]; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%s%s%s",&stus[i].name,&stus[i].sno,&stus[i].sex); getchar(); } //printf("%s %s %s\n",stus[1].name,stus[1].sno,stus[1].sex); scanf("%d",&m); for(i=0;i<m;i++) { scanf("%s%s",&a[0],&b[0]); getchar(); if(!strcmp(stus[findStuByNameOrSno(&a[0])].sex, stus[findStuByNameOrSno(&b[0])].sex)) printf("N\n"); else printf("Y\n"); } }
77、班级排名
达达在陶陶的影响下，也对学习慢慢的产生了兴趣。
他在每次考试之后，都会追着老师问，自己在班级的总名次是多少。考试一多，老师也不耐烦了，于是他给了达达所有人的成绩，让他自己去算出自己的排名。
可人太多了，达达也无法立即算出来，于是他想让你帮帮他。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> typedef struct stu { char name[60]; int score; }Stus; Stus stus[200]; int n; int getDaDaNum() { int i; for(i=0;i<n;i++) if(!strcmp("DaDa",stus[i].name)) return i; return -1; } int cmp(const void*a ,const void *b) { Stus* pa=(Stus*) a; Stus* pb=(Stus*) b; if(pa->score==pb->score&&!strcmp("DaDa",pa->name)) return -1; else if(pa->score==pb->score&&!strcmp("DaDa",pb->name)) return 1; else return pb->score-pa->score; } int getIndexByName(char name[60]) { int i; for(i=0;i<n;i++) if(!strcmp(stus[i].name,name)) return i; return -1; } void my_print() { int i; printf("\n"); for(i=0;i<n;i++) printf("%s %d\n",stus[i].name,stus[i].score); printf("\n"); } int main() { int i,j,t; char name[60]; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%s",&stus[i].name); stus[i].score=0; getchar(); } int m; scanf("%d",&m); for(i=0;i<m;i++) { for(j=0;j<n;j++) { scanf("%d %s",&t,name); getchar(); stus[getIndexByName(name)].score+=t; } // my_print(); qsort(stus,n,sizeof(Stus),cmp); // my_print(); printf("%d\n",getDaDaNum()+1); } /*n=3; strcpy(stus[0].name,"A");stus[0].score=7; strcpy(stus[1].name,"DaDa");stus[1].score=5; strcpy(stus[2].name,"B");stus[2].score=6; qsort(stus,n,sizeof(Stus),cmp); printf("%d\n",getDaDaNum()+1);*/ return 0; }
78、铺地毯
为了准备一个学生节，组织者在会场的一片矩形区域（可看做是平面直角坐标
系的第一象限）铺上一些矩形地毯。一共有n 张地毯，编号从1 到n。现在将这些地毯按照
编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形
地毯边界和四个顶点上的点也算被地毯覆盖。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int position[10001][4]; //因为是从底 往 顶铺地毯 //要求的是 x,y位置上 最顶层的地毯 //就可以 从铺设地毯的编号最大的向最小的遍历 //第一个包含x,y的就是该地毯 //若都不包含 输出-1 int main() { int n,i,j; scanf("%d",&n); for(i=1;i<=n;i++) for(j=0;j<4;j++) scanf("%d",&position[i][j]); int x,y; scanf("%d%d",&x,&y); int flag=0; for(i=n;i>=1;i--) { if(x>=position[i][0]&&x<=position[i][0]+position[i][2] &&y>=position[i][1]&&y<=position[i][2]+position[i][3]) { printf("%d\n",i); flag=1; break; } } if(!flag)printf("-1\n"); return 0; }
79.联系
问题描述 :
奶牛们开始对用电波望远镜扫描牧场外的宇宙感兴趣。最近，他们注意到了一种非常奇怪的脉冲调制微波被从星系的中央发射出来。他们希望知道电波是否是被某些地外生命发射出来的，还是仅仅是普通的的星星的心跳。
帮助奶牛们用一个能够分析他们在文件中记下的记录的工具来找到真相。
他们在寻找长度在A到B之间（含）在每天的数据文件中重复得最多的比特序列 (1 <= A <= B <= 12)。他们在找那些重复得最多的比特序列。
符合条件的序列可能会重叠。
输入说明 :
第一行： 三个用空格分隔的整数: A, B, N; (1<= N < 50)
第二行及以后: 一个最多200，000字符的序列，全是0或1; 除最后一行，每行有80个字符。
输出说明 :
输出N个最高频率的序列（按照频率由高到低的次序）。由于每个频率可能有多个序列，因此，输出的序列数可能大于N。
对于每个频率，先输出该频率值，再在下一行输出以空格分隔的序列，每行最多六个，多于六个则在下一行接着输出。
对于频率相同的序列，按由短到长顺序输出，如果长度相同，按二进制大小由小到大顺序输出。
如果频率数目不到N，输出所有可能的频率。
输入范例 :
1 4 10
010100100100010001111011000010100
输出范例 :
20
0
13
1
10
00
9
01 10
7
010
6
100
5
001 0100
4
11 000 0010
3
101 0001 1000
2
011 110 111 0101 1001 1010
80、最小乘积
给两组数，各n个。
请调整每组数的排列顺序，使得两组数据相同下标元素对应相乘，然后相加的和最小。要求程序输出这个最小值。
例如两组数分别为:1 3 -5和-2 4 1
那么对应乘积取和的最小值应为：
(-5) * 4 + 3 * (-2) + 1 * 1 = -25
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int a[8],b[8]; //排序后 最大的乘以最小的 int cmp(const void* a,const void* b) { return *((int*)a)-*((int*)b); } int main() { int t,n,i,min; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=0;i<n;i++)scanf("%d",&a[i]); for(i=0;i<n;i++)scanf("%d",&b[i]); qsort(a,n,sizeof(int),cmp); qsort(b,n,sizeof(int),cmp); min=0; for(i=0;i<n;i++)min+=a[i]*b[n-i-1]; printf("%d\n",min); } return 0; }
81、完美的代价
回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
交换的定义是：交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文！完美！)
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> char arr[8000]; int flag=1;//当flag=0时不是回文 int res=0;//记录交换次数 //当每次交换都单向移动时 交换的次数最少 fun(start,end) len=end-start+1 flag=0直接退出 //当len为偶数时 start是开始位置 end是结束位置 ////从结束位置向前找，看是否能找到与arr[start] 相同的下标为target的元素 若找到 依次将其交换移动到end的位置 res+=end-target ////若找不到 则不是回文 falg=0 //当len为奇数时 start是开始位置 end是结束位置 ////从结束位置向前找，看是否能找到与arr[start] 相同的下标为target的元素 ////若找到 依次将其交换移动到end的位置 res+=end-target ////若找不到 则res+=(len-1)/2,fun(start+1,end) 意思就是第一个元素是奇数长度回文的中间那一个 void fun(int start,int end) { if(end<=start||!flag)return; int i,j,len=end-start+1,find=0; for(i=end;i>start;i--) if(arr[i]==arr[start])//找到了 { //target就是i for(j=i;j<end;j++)arr[j]=arr[j+1];//依次交换 arr[end]=arr[start]; res+=end-i;//记录交换次数 find=1; break; } // printf("%d %d %d %s\n",start,end,find,arr); if(find) fun(start+1,end-1); else//没找到 { if(len%2==0)//偶数 不是回文 { flag=0; return; } else//奇数 { res+=(len-1)/2; fun(start+1,end); } } } int main() { int n; scanf("%d",&n); scanf("%s",arr); fun(0,n-1); if(flag)printf("%d\n",res); else printf("Impossible\n"); return 0; }
82、纪念品分组
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值 相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时 间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。
//由于要分的均匀且 最多一组两件 //先将价值排序 再使用双指针 //若小的加大的小于特定整数则分组 //若大于 大的单独一组 #include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int a[30000]; //双指针法 int cmp(const void* a,const void* b) { return *((int*)a)-*((int*)b); } int main() { int w,n,i,j,res; scanf("%d",&w); scanf("%d",&n); for(i=0;i<n;i++)scanf("%d",&a[i]); qsort(a,n,sizeof(int),cmp); i=0,j=n-1,res=0; while(i<j) { if(a[i]+a[j]<=w) i++,j--; else j--; res++; } if(i==j)res++; printf("%d\n",res); return 0; }
83、银行家的预算
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> # define MAX 999999 //首先算出加满油能到达的距离 //如果加满油都不能通过相邻的两个加油站 则不能到达 //开始循环 // 算出在当前位置加满油能到达的最便宜的一个加油站 //找到的下一个最便宜油站的编号为next_index //如果下一个最便宜的油站 比当前的还要便宜 那油只加到能到next_index的量 ////下一个能到达的便宜的油站比当前油站更贵 且 无法从当前油站一次到达终点 则在当前油站加满油 //能从此油站到达终点 则油只加到可以到终点就够了 int main() { double distance,capaciy,distance_per_c,init_price;// int n,i; scanf("%lf%lf%lf%lf%d",&distance,&capaciy,&distance_per_c,&init_price,&n); //oil[i][0] 代表加油站的距离 oli[i][1]代表油价 double oil[100][2]; oil[0][0]=0; oil[0][1]=init_price; for(i=1;i<=n;i++)scanf("%lf%lf",&oil[i][0],&oil[i][1]); //加满油能走的距离 double max_distance=capaciy*distance_per_c; if(!n&&distance>max_distance) { printf("No Solution\n"); return 0; } else if(!n&&distance<max_distance) { printf("%.2lf\n",(distance/distance_per_c)*init_price); return 0; } //如果加满油都不能通过相邻的两个加油站 则不能到达 for(i=1;i<=n;i++)if((oil[i][0]-oil[i-1][0])>max_distance) { printf("No Solution\n"); return 0; } //total_money所有使用的钱 oil_left油箱剩下的油 moved_dis移动的距离 add_oil单次增加的油 double total_money=0,oil_left=0,moved_dis=0,add_oil; int index=0,next_index;//index当前所在加油站 double min_price=MAX; while(distance-moved_dis) { //从index+1遍历油站找到 在index处加油 可以到达的最便宜的油站 for(i=index+1;(oil[i][0]-oil[index][0])<=max_distance&&i<=n;i++) { if(oil[i][1]<min_price) { min_price=oil[i][1]; next_index=i; } } //找到的下一个最便宜油站的编号为next_index //如果下一个最便宜的油站 比当前的还要便宜 那油只加到能到next_index的量 if(oil[next_index][1]<oil[index][1]) { add_oil=(oil[next_index][0]-oil[index][0])/distance_per_c-oil_left; total_money+=add_oil*oil[index][1]; oil_left=add_oil; } //下一个能到达的便宜的油站比当前油站更贵 且 无法从当前油站一次到达终点 则在当前油站加满油 else if((distance-oil[index][0])>max_distance) { add_oil=capaciy-oil_left; total_money+=add_oil*oil[index][1]; oil_left=capaciy; } //能从此油站到达终点 else { add_oil=(distance-oil[index][0])/distance_per_c-oil_left; total_money+=add_oil*oil[index][1]; break; } //不能一次到达终点时 一定有next_index oil_left-=((oil[next_index][0]-oil[index][0])/distance_per_c); moved_dis=oil[next_index][0]; index=next_index; min_price=MAX; } printf("%.2lf\n",total_money); return 0; }
84、盾神与积木
最近的m天盾神都去幼儿园陪小朋友们玩去了~
每个小朋友都拿到了一些积木，他们各自需要不同数量的积木来拼一些他们想要的东西。但是有的小朋友拿得多，有的小朋友拿得少，有些小朋友需要拿到其他小朋友的积木才能完成他的大作。如果某个小朋友完成了他的作品，那么他就会把自己的作品推倒，而无私地把他的所有积木都奉献出来；但是，如果他还没有完成自己的作品，他是不会把积木让出去的哟~
盾神看到这么和谐的小朋友们感到非常开心，于是想帮助他们所有人都完成他们各自的作品。盾神现在在想，这个理想有没有可能实现呢？于是把这个问题交给了他最信赖的你。
//arr[i][0]拥有的 arr[i][1]需要的 arr[i][2] 记录该小朋友是否完成 //public_wood 代表公共可用的积木 //finish_num 代表拼完的小朋友的个数 //设置 此轮有小朋友拼完flag=0 // 对未完成的小朋友进行循环 // 如果 现在拥有的 加公共可用的积木 大于需要的 则该小朋友完成 flag=1, finish_num++ ,public_wood加这个小朋友有的积木 // 如果循环一轮没有小朋友完成且 完成的人数小于总人数 则不能完成任务 #include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int main() { int i,m,n,public_wood,finish_num; //arr[i][2] 记录该小朋友是否完成 //public_wood 代表公共可用的积木 //finish_num 代表拼完的小朋友的个数 int arr[10000][3]; scanf("%d",&m); while(m--) { public_wood=0; finish_num=0; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d%d",&arr[i][0],&arr[i][1]); if(arr[i][0]+public_wood>=arr[i][1]) { arr[i][2]=1; public_wood+=arr[i][0]; finish_num++; } else arr[i][2]=0; } int flag=1; while(flag) { flag=0; for(i=0;i<n;i++) { if(!arr[i][2]) { if(arr[i][0]+public_wood>=arr[i][1]) { arr[i][2]=1; public_wood+=arr[i][0]; finish_num++; flag=1; } } } } if(finish_num==n)printf("YES\n"); else printf("NO\n"); } }
85、王后传说
地球人都知道，在国际象棋中，后如同太阳，光芒四射，威风八面，它能控制横、竖、斜线位置。
看过清宫戏的中国人都知道，后宫乃步步惊心的险恶之地。各皇后都有自己的势力范围，但也总能找到相安无事的办法。
所有中国人都知道，皇权神圣，伴君如伴虎，触龙颜者死……
现在有一个n*n的皇宫，国王占据他所在位置及周围的共9个格子，这些格子皇后不能使用（如果国王位于王宫的边缘，占用的格子可能不到9个）。当然，皇后也不会攻击国王。
现在知道了皇宫的规模n，国王的位置（x,y）（国王位于第x行第y列，行和列号从1开始），请问，有多少种方案放置n个皇后，使她们不能互相攻击（同一横线、竖线、斜线上只能有一个皇后）。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> //8皇后问题 #include <stdio.h> int res=0; int n; int a[12][12]={0}; //检查放在此位置是否与上面的行冲突 int check(int i,int j) { int x,y; for(x=i-1;x>=0;x--)if(a[x][j]==1)return 0; for(y=j-1;y>=0;y--)if(a[i][y]==1)return 0; for(x=i-1,y=j-1;x>=0&&y>=0;x--,y--)if(a[x][y]==1)return 0; for(x=i-1,y=j+1;x>=0&&y<n;x--,y++)if(a[x][y]==1)return 0; return 1; } //按行放 每行放一个 只有赋值为0才可以放 void dfs(int row) { //每行都放完了就结束 if(row==n) { res++; return; } int col; //对于此行的每列进行dfs for(col=0;col<n;col++) { if(!a[row][col]&&check(row,col)) { a[row][col]=1; dfs(row+1); a[row][col]=0; } } } //将国王所在位置赋值为2 void initKing(int x,int y) { int op[9][2]={{1,0},{1,1},{1,-1}, {0,1},{0,-1},{0,0}, {-1,-1},{-1,0},{-1,1}}; int i; x=x-1,y=y-1; for(i=0;i<9;i++) { if(x+op[i][0]>=0&&x+op[i][0]<n&& y+op[i][1]>=0&&y+op[i][1]<n) a[x+op[i][0]][y+op[i][1]]=2; } } int main() { int x,y; scanf("%d%d%d",&n,&x,&y); initKing(x,y); dfs(0); printf("%d\n",res); return 0; }
86、瓷砖铺放
有一长度为N(1<=Ｎ<=10)的地板，给定两种不同瓷砖：一种长度为1，另一种长度为2，数目不限。要将这个长度为N的地板铺满，一共有多少种不同的铺法？
例如，长度为4的地面一共有如下5种铺法：
4=1+1+1+1
4=2+1+1
4=1+2+1
4=1+1+2
4=2+2
编程用递归的方法求解上述问题。
//深度优先搜索 n代表当前数量 i代表此次要减去的数量 //每轮搜索若还剩下瓷砖 都先-1块瓷砖 搜索到底回溯时再-2块瓷砖 枚举出所有情况 #include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int res=0; void dfs(int n,int i) { if((n-i)==0) { res++; return; } if(n>i) { dfs(n-i,1); dfs(n-i,2); } } int main() { int n; scanf("%d",&n); dfs(n,1); dfs(n,2); printf("%d\n",res); return 0; }
87、求先序排列
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。
//深度优先搜索 //后序的最后一项为根节点root //再在中序中找到root，root左边的部分是root的左子树大小为a，root右边的部分是root的右子树大小为b //先序的第一个节点为root 下一个节点从root的左子树找 // root的左子树在后序的位置为起始节点起a个大小对其进行dfs // root的右子树为后序最后的节点往前数b个大小 对其dfs #include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> char pre_order[9],in_order[9],post_order[9]; int res=0; //inorder_start 中序起点 //inorder_end 中序终点 //postorder_root 当前从后根序中 处理的根节点 //preorder_index 先序的标号 void dfs(int inorder_start,int inorder_end, int postorder_root,int preorder_index) { if(inorder_start>inorder_end)return; pre_order[preorder_index]=post_order[postorder_root]; int inorder_root,i; for(i=inorder_start;i<=inorder_end;i++) if(in_order[i]==post_order[postorder_root]) break; //右子树的长度 int right_len=inorder_end-i; //左子树的长度 int left_len=i-inorder_start; //先处理左子树 dfs(inorder_start,i-1,postorder_root-right_len-1,preorder_index+1); //再处理右子树 dfs(i+1,inorder_end,postorder_root-1,preorder_index+left_len+1); } int main() { int i; scanf("%s",&in_order[0]);getchar();//LNR scanf("%s",&post_order[0]);//LRN int len=strlen(in_order); dfs(0,len-1,len-1,0); for(i=0;i<len;i++)printf("%c",pre_order[i]); printf("\n"); return 0; }
88、FBI树
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：
1)T的根结点对应的内容为S，因此其类型与串S的类型相同；
2)若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造左子树T1，由右子串S2构造右子树T2。
现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> //相当于递归后续遍历 char ch[1026]; void fun(int start,int end) { int mid=(start+end)/2; if(start!=end) { fun(start,mid); fun(mid+1,end); } int a=0,b=0,i; for(i=start;i<=end;i++) if(ch[i]==\'0\')a++; else b++; if(a&&b) printf("F"); else if(a)printf("B"); else printf("I"); } int main() { int n; scanf("%d",&n); scanf("%s",&ch[1]); fun(1,strlen(&ch[1])); return 0; }
89 单词接龙
作者: Turbo时间限制: 1S章节: 深度优先搜索
问题描述 :
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外，相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。
样例输入
5
at
touch
cheat
choose
tact
a
样例输出
23
样例说明
连成的“龙”为atoucheatactactouchoose
输入说明 :
输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出说明 :
只需输出以此字母开头的最长的“龙”的长度
输入范例 :
5
at
touch
cheat
choose
tact
a
输出范例 :
23
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> using namespace std; const int maxn = 100; int n; int res = 0; //拼接结果 string word[maxn]; //字符串数组 存放单词 string beginn; //用来存储开头字符 int used[maxn]; // 记录dfs时每个单词使用次数 bool check(string s, string m, int k) { int lens = (int)s.length(); for (int i = 0; i < k; i++)//k为接口的长度 { if (s[lens - k + i] != m[i]) return false; } return true; } void add(string &tmp, string m, int k) { int lenm = (int)m.length(); for (int i = k; i < lenm; i++)//从k开始拼接 { tmp += m[i]; } } void dfs(string str) { int len = (int)str.length(); res = max(res, len);//每次更新当前以拼接好的字符串长度 for (int i = 1; i <= n; i++) { if (used[i] >= 2) continue; int maxlink = (int)word[i].length();//最大接口长度是当前所选单词的长度 for (int j = 1; j <= maxlink; j++) { if (check(str, word[i], j)) { string tmp = str; add(tmp, word[i], j);//将Word【i】字符拼接到tmp中 if (tmp == str) continue; used[i]++; dfs(tmp); used[i]--; } //else // break; } } } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> word[i]; } cin >> beginn; dfs(beginn); cout << res << endl; return 0; }
90 排列问题
作者: Turbo时间限制: 1S章节: 深度优先搜索
问题描述 :
求一个0～N-1的排列（即每个数只能出现一次），给出限制条件（一张N*N的表，第i行第j列的1或0，表示为j这个数能不能出现在i这个数后面，并保证表中的第i行第i列为0，i和j都从0开始），将这个排列看成一个自然数，求从小到大排序第K个排列。
样例输入
3 2
0 1 1
1 0 0
0 1 0
样例输出
1 0 2
解释：
对于N=3的没有任何限制的排列如下：
第一：0 1 2
第二：0 2 1
第三：1 0 2
第四：1 2 0
第五：2 0 1
第六：2 1 0
根据题目所给的限制条件由于2不能出现在1后面，0不能出现在2后面
第一：0 2 1
第二：1 0 2
第三：2 1 0
输入说明 :
第一行为N和K,接下来的N行，每行N个数，0表示不能，1表示能
N<=10，K<=500000
输出说明 :
所求的排列
输入范例 :
3 2
0 1 1
1 0 0
0 1 0
输出范例 :
1 0 2
#include <iostream> using namespace std; const int maxn = 11; int p[maxn], hashtable[maxn] = { 0 }; int mp[maxn][maxn] = {0}; int n, k; int num = 0; void dfs(int index) { if (index == n) { num++; if (num == k) { for (int i = 0; i < n; i++) { cout << p[i] ; if (i < n-1) { cout << " "; } } cout << endl; } return; } for (int x = 0; x <n; x++) { if (hashtable[x] == 0&&mp[p[index-1]][x]==1||index==0) { hashtable[x] = 1; p[index] = x; dfs(index + 1); hashtable[x] = 0; } } } int main() { cin >> n >> k; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> mp[i][j]; } } dfs(0); return 0; }
91、和为T
从一个大小为n的整数集中选取一些元素，使得它们的和等于给定的值T。每个元素限选一次，不能一个都不选。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> //二进制枚举 //-7 -3 -2 5 9 // 1 0 0 0 0 //此处为二进制倒着写 // 0 1 0 0 0 // 1 1 0 0 0 // 0 0 1 0 0 //位运算1<<n代表1的二进制作移n位 //s&(1<<j) ;<<优先级比&g高 此项判断二进制的s在第j位是不是1 int main() { int n; int arr[22]; int count=0; long sum=0; long target; int i,j; scanf("%d",&n); for(i=0;i<n;i++)scanf("%d",&arr[i]); scanf("%d",&target); for(i=1;i<(1<<n);i++)//枚举所有状态 { sum=0; for(j=0;j<n;j++)//枚举arr if(i&(1<<j))//代表二进制数的i的第j位为为1 sum+=(long)arr[j]; if(sum==target)//此状态符合条件 { count++; for(j=0;j<n;j++)//枚举arr if(i&(1<<j))//代表二进制数的i的第j位为为1 printf("%d ",arr[j]); printf("\n"); } } printf("%d\n",count); return 0; }
92、母亲的牛奶
农民约翰有三个容量分别是A,B,C升的桶，A,B,C分别是三个从1到20的整数，最初，A和B桶都是空的，而C桶是装满牛奶的。有时，约翰把牛奶从一个桶倒到另一个桶中，直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约，牛奶不会有丢失。写一个程序去帮助约翰找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。
//使用深度优先搜索 记录出现过的状态 //对于为出现的状态 分别从三个桶向另外两个桶的一个倒牛奶 分为倒满和倒完两种情况 //一共有12种可能 依次深度优先搜索 #include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #define MAX 21 int a,b,c; int visit[MAX][MAX][MAX]={0};//标记此状态是否出现过 int res[MAX]={0};//标记答案 void dfs(int x,int y,int z) { //printf("%d %d %d\n",x,y,z); if(visit[x][y][z])return;//状态出现过 if(!x)res[z]=1;//A桶为空 此时C桶的值为答案 visit[x][y][z]=1; //z->y z+y>b?dfs(x,b,z-(b-y)):dfs(x,z+y,0); //z->x z+x>a?dfs(a,y,z-(a-x)):dfs(x+z,y,0); //y->z y+z>c?dfs(x,y-(c-z),c):dfs(x,0,y+z); //y->x y+x>a?dfs(a,y-(a-x),z):dfs(y+x,0,z); //x->y x+y>b?dfs(x-(b-y),b,z):dfs(0,x+y,z); //x->z x+z>c?dfs(x-(c-z),y,c):dfs(0,y,x+z); return; } int main() { scanf("%d%d%d",&a,&b,&c); dfs(0,0,c); int i,first=0; for(i=0;i<MAX;i++) { if(res[i]&&!first) { printf("%d",i); first=1; } else if(first&&res[i]) printf(" %d",i); } printf("\n"); return 0; }
93、魔板
在成功地发明了魔方之后，鲁比克先生发明了它的二维版本，称作魔板。这是一张有8个大小相同的格子的魔板：
1 2 3 4
8 7 6 5
我们知道魔板的每一个方格都有一种颜色。这8种颜色用前8个正整数来表示。可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个颜色序列。对于上图的魔板状态，我们用序列（1，2，3，4，5，6，7，8）来表示。这是基本状态。
这里提供三种基本操作，分别用大写字母“A”，“B”，“C”来表示（可以通过这些操作改变魔板的状态）：
“A”：交换上下两行；
“B”：将最右边的一列插入最左边；
“C”：魔板中央四格作顺时针旋转。
下面是对基本状态进行操作的示范：
A: 8 7 6 5
1 2 3 4
B: 4 1 2 3
5 8 7 6
C: 1 7 2 4
8 6 3 5
对于每种可能的状态，这三种基本操作都可以使用。 你要编程计算用最少的基本操作完成基本状态到目标状态的转换，输出基本操作序列。
//使用广度优先搜索 每次都从队列中拿出一个对象进行三种操作并入队 并记录其变更方式 //直到出现目标状态为止 #include<bits/stdc++.h> using namespace std; string target;//目标状态 map<string,string> my_map;//用于判重复加存路径 key等于出现过的序列 val变换方法路径 queue<string> que;//广搜队列 //A方法 上下两行互换 void fun_a(string str){ string origin_str=str; for(int i=0;i<4;i++){ char ch=str[i]; str[i]=str[7-i]; str[7-i]=ch; } if(!my_map.count(str)){//没有出现过 que.push(str);//入队 my_map[str]=my_map[origin_str]+\'A\';//在map中记录方法路径 } } //最后一列与第一列互换 void fun_b(string str){ string origin_str=str; str[0]=origin_str[3],str[1]=origin_str[0],str[2]=origin_str[1],str[3]=origin_str[2], str[4]=origin_str[5],str[5]=origin_str[6],str[6]=origin_str[7],str[7]=origin_str[4]; if(!my_map.count(str)){ que.push(str); my_map[str]=my_map[origin_str]+\'B\'; } } //中间四个 顺时针旋转 void fun_c(string str){ string origin_str=str; str[1]=origin_str[6],str[2]=origin_str[1], str[5]=origin_str[2],str[6]=origin_str[5]; if(!my_map.count(str)){ que.push(str); my_map[str]=my_map[origin_str]+\'C\'; } } void bfs(){ //先存入初始状态 que.push("12345678"); my_map["12345678"]="";//初始状态的 路径转化序列为空 while(!que.empty()){ string p=que.front(); fun_a(p); fun_b(p); fun_c(p); if(my_map.count(target)){//当出现目标序列 printf("%d\n",my_map[target].size()); cout<<my_map[target]<<endl; return; } que.pop(); } } int main(){ int i; char ch; for(i=0;i<8;i++){ scanf("%c",&ch); getchar(); target+=ch; } bfs(); return 0; }
94、计算器
王小二的计算器上面的LED显示屏坏掉了，于是他找到了在计算器维修与应用系学习的你来为他修计算器。
屏幕上可以显示0~9的数字，其中每个数字由7个小二极管组成，各个数字对应的表示方式如图所示：
为了排除电路故障，现在你需要计算，将数字A变为数字B需要经过多少次变换？
注意：现在将其中每段小二极管的开和关都定义为一次变换。例如数字1变为2是5次操作。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> //直接写出某数字变换到另一个数字所需的步数 形成的矩阵 //利用上述矩阵求解答案 int main() { int arr[10][10]={ {0,4,3,3,4,3,2,3,1,2}, {4,0,5,3,2,5,6,1,5,4}, {3,5,0,2,5,4,3,4,2,3}, {3,3,2,0,3,2,3,2,2,1}, {4,2,5,3,0,3,4,3,3,2}, {3,5,4,2,3,0,1,4,2,1}, {2,6,3,3,4,1,0,5,1,2}, {3,1,4,2,3,4,5,0,4,3}, {1,5,2,2,3,2,1,4,0,1}, {2,4,3,1,2,1,2,3,1,0}, }; //arr[i,j]代表从i变换到j需要几次操作 int i,n; char a[101],b[101]; scanf("%d",&n); scanf("%s",a);getchar(); scanf("%s",b); int sum=0; for(i=0;i<n;i++)sum+=arr[a[i]-\'0\'][b[i]-\'0\']; printf("%d\n",sum); return 0; }
95、学霸的迷宫 wa
// OJ.cpp : Defines the entry point for the console application. #include "stdafx.h" /*#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h>*/ //使用dfs超时 因为要搜索最短路径 bfs第一次找到的路径即为最短路径 /*int m,n; char arr[500][500]; //D L R U int op[4][2]={{1,0},{0,-1},{0,1},{-1,0}}; char opch[4]={\'D\',\'L\',\'R\',\'U\'}; int max=0; char res[500]; int res_size=0; int flag=0; void dfs(int i,int j,int depth) { //printf("%d %d %d %c\n",i,j,depth,arr[i][j]); arr[i][j]=\'1\'; if(flag)return; if(i==n-1&&j==m-1) { flag=1; printf("%d\n",depth); res[depth]=\'\0\'; printf("%s\n",res); return; } int k; for(k=0;k<4;k++) { if(arr[i+op[k][0]][j+op[k][1]]==\'0\') { res[depth]=opch[k]; dfs(i+op[k][0],j+op[k][1],depth+1); } } arr[i][j]=\'0\'; } int main() { int i,j; scanf("%d%d",&n,&m); getchar(); memset(arr,\'1\',sizeof(char)*500*500); for(i=0;i<n;i++) { for(j=0;j<m;j++) scanf("%c",&arr[i][j]); getchar(); } dfs(0,0,0); return 0; }*/ //后3个wa
#include<iostream> #include<string> #include<queue> #include<cstring> using namespace std; //D L R U int op[4][2]={{1,0},{0,-1},{0,1},{-1,0}}; char opch[4]={\'D\',\'L\',\'R\',\'U\'}; char map[500][500]; int n,m; struct Point { int x,y,len; string path; Point(int a,int b){x=a;y=b;} }; void bfs(int n,int m) { int k,flag=0; queue<Point> que; Point p0(0,0); p0.len=0; p0.path=""; map[0][0]=\'1\'; que.push(p0); while(!que.empty()&&!flag) { Point p=que.front();que.pop(); for(k=0;k<4;k++) { int tx=p.x+op[k][0]; int ty=p.y+op[k][1]; if(tx>=n||ty>=m||tx<0||ty<0)continue; if(map[tx][ty]==\'0\') { map[tx][ty]=\'1\'; Point next_p(tx,ty); next_p.len=p.len+1; next_p.path=p.path+opch[k]; que.push(next_p); if(tx==n-1&&ty==m-1) { cout<<next_p.len<<endl; cout<<next_p.path<<endl; flag=1; break; } } } } } int main() { int i,j; scanf("%d%d",&n,&m); getchar(); memset(map,\'1\',sizeof(char)*500*500); for(i=0;i<n;i++) { for(j=0;j<m;j++) scanf("%c",&map[i][j]); getchar(); } bfs(n,m); return 0; }
96、矩阵中最长递增路径
给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> int m,n; int res[50][50][2]={0}; int op[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; int max=0; //使用深度优先搜索 // res[i][j][1] 作为标记此节点已经走过 // 然后四个方向依次进行深度优先搜索 // 若不超边界且大于当前节点的值 则前进 // 若无符合条件的 标记节点为未走过 void dfs(int i,int j,int depth) { res[i][j][1]=1; if(depth>max)max=depth; int k; for(k=0;k<4;k++) if(res[i+op[k][0]][j+op[k][1]][1]==0&& res[i+op[k][0]][j+op[k][1]][0]>res[i][j][0]) dfs(i+op[k][0],j+op[k][1],depth+1); res[i][j][1]=0; } int main() { int i,j; scanf("%d%d",&m,&n); for(i=0;i<m;i++) for(j=0;j<n;j++)scanf("%d",&res[i][j][0]); for(i=0;i<m;i++) for(j=0;j<n;j++) dfs(i,j,1); printf("%d\n",max); }
97、 乘积最大
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：
设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串：312， 当N=3，K=1时会有以下两种分法：
3*12=36
31*2=62
这时，符合题目要求的结果是：31*2=62
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> //对于 长度为i的数字 分为j项 //dp[i][j]=max(dp[i][j],dp[w][j-1]*num[w+1][i]) //代表了以某个w分割 出的值最大 //dp[i][j] 代表长度为i的数字分为j项 //num[w+1][i] 代表从w+1到第i位数字的大小 #define MAX 42 int main() { int n,k; long temp; char arr[MAX]; long dp[MAX][MAX]; scanf("%d%d",&n,&k); scanf("%s",&arr[1]);//从第一项开始存 int i,j,w,r; temp=0; //初始化分成0项的值 for(i=1;i<=n;i++) { temp=temp*10+arr[i]-\'0\'; dp[i][0]=temp; } for(i=1;i<=n;i++)//枚举需要计算的长度 { for(j=1;j<=k;j++)//枚举分成的项 { for(w=1;w<i;w++)//从第w项断开 { temp=0; for(r=w+1;r<=i;r++)//计算num[w+1][i] temp=temp*10+arr[r]-\'0\'; dp[i][j]=dp[i][j]>dp[w][j-1]*temp?dp[i][j]:dp[w][j-1]*temp; } } } printf("%ld\n",dp[n][k]); }
98、数的划分
将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1，1，5; 1，5，1; 5，1，1;
问有多少种不同的分法。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> //深度优先搜索超时 /*int res=0; int n,k;*/ //当进行深度优先搜索时 下一个数要大于前一个数 这样就不会重复了 /*void dfs(int left,int cur,int cur_depth) { int i; if(left-cur-(k-cur_depth-1)<0)return ; if(cur_depth==k-1) { if(left-cur==0) res++; return; } for(i=cur;i<=left/(k-cur_depth-1);i++) dfs(left-cur,i,cur_depth+1); } int main() { int i; scanf("%d%d",&n,&k); for(i=1;i<=n-k+1;i++) dfs(n,i,0); printf("%d\n",res); return 0; }*/ //动态规划 //f(i,i)=1 ,f(i,j)=0(i<j) //f(x,k)代表将x分为k份 //状态转移方程f(x,k)=f(x-1,k-1)+f(x-k,k); //f(x-1,k-1)代表有1的情况 直接把1分好 并去除 //f(x-k,k) 代表没1的情况 先把1分到k份 然后再将x-k分成k份 那么每份就不包含1 int main() { int res[201][7]; int i,j; for(i=1;i<=200;i++) { for(j=1;j<=6;j++) { if(i==j) res[i][j]=1; else if(i<j) res[i][j]=0; else { res[i][j]=0; if(i-1>0&&j-1>0) res[i][j]+=res[i-1][j-1]; if(i-j>0) res[i][j]+=res[i-j][j]; } } } int n,k; scanf("%d%d",&n,&k); printf("%d\n",res[n][k]); }
99、最长字符序列
设x(i), y(i), z(i)表示单个字符，则X={x(1)x(2)……x(m)}，Y={y(1)y(2)……y(n)}，Z={z(1)z(2)……z(k)},我们称其为字符序列，其中m,n和k分别是字符序列X，Y，Z的长度，括号()中的数字被称作字符序列的下标。
如果存在一个严格递增而且长度大于0的下标序列{i1,i2……ik}，使得对所有的j=1,2,……k，有x(ij)=z(j)，那么我们称Z是X的字符子序列。而且，如果Z既是X的字符子序列又是Y的字符子序列，那么我们称Z为X和Y的公共字符序列。
在我们今天的问题中，我们希望计算两个给定字符序列X和Y的最大长度的公共字符序列，这里我们只要求输出这个最大长度公共子序列对应的长度值。
举例来说，字符序列X=abcd，Y=acde，那么它们的最大长度为3，相应的公共字符序列为acd。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> //LCS 最长公共子序列 //dp[i][j]代表序列a的前i项 序列b的前j项的公共子序列 //dp[i][j]=max(dp[i-1][j],dp[i][j-1])//继承最大的一个 // 若a[i]=b[j] dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1); int main() { char a[102],b[102]; scanf("%s",&a[1]);getchar(); scanf("%s",&b[1]);getchar(); int alen=strlen(&a[1]),blen=strlen(&b[1]); int dp[102][102]={0}; int i,j; for(i=1;i<=alen;i++) { for(j=1;j<=blen;j++) { dp[i][j]=dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1]; if(a[i]==b[j]) dp[i][j]=dp[i][j]>(dp[i-1][j-1]+1)?dp[i][j]:(dp[i-1][j-1]+1); } } printf("%d\n",dp[alen][blen]); return 0; }
100 邮票
作者: Turbo时间限制: 1S章节: 动态规划
问题描述 :
已知一个 N 枚邮票的面值集合（如，{1 分，3 分}）和一个上限 K ,表示信封上能够贴 K 张邮票。计算从 1 到 M 的最大连续可贴出的邮资。 例如，假设有 1 分和 3 分的邮票；你最多可以贴 5 张邮票。很容易贴出 1 到 5 分的邮资（用 1 分邮票贴就行了），接下来的邮资也不难：
6 = 3 + 3
7 = 3 + 3 + 1
8 = 3 + 3 + 1 + 1
9 = 3 + 3 + 3
10 = 3 + 3 + 3 + 1
11 = 3 + 3 + 3 + 1 + 1
12 = 3 + 3 + 3 + 3
13 = 3 + 3 + 3 + 3 + 1。
然而，使用 5 枚 1 分或者 3 分的邮票根本不可能贴出 14 分的邮资。因此，对于这两种邮票的集合和上限 K=5，答案是 M=13。
输入说明 :
第 1 行： 两个整数，K 和 N。
K（1 <= K <= 200）是可用的邮票总数。N（1 <= N <= 50）是邮票面值的数量。
第 2 行 到最后： N 个整数，每行 最多15 个，列出所有的 N 个邮票的面值，面值不超过 10000。
输出说明 :
第 1 行： 一个整数，从 1 分开始连续的可用集合中不多于 K 张邮票贴出的邮资数。
输入范例 :
5 2
1 3
输出范例 :
13
#include <iostream> #include <algorithm> using namespace std; int dp[2000001]; int k, n; int p[51]; int main() { cin >> k >> n; for (int i = 0; i < n; i++) { cin>>p[i]; } sort(p,p+n); dp[0]=0; int index = 0; while (dp[index] <= k) { int min = 10000000; index++; for (int i = 0; i < n&&p[i]<=index; i++) { if (dp[index-p[i]] + 1 < min) min = dp[index-p[i]] + 1; } dp[index] = min; } cout << index - 1 << endl; return 0; }
//%02d代表宽度为两位 不足以0补齐
给定一个十进制整数，返回其对应的二进制数的位数。例如，输入十进制数9，其对应的二进制数是1001，因此位数是4。