第七届省赛题目
注意
- 简单的题目，只是写了一个函数实现功能，对于复杂的题目，会给出全部代码
1
-
题目
网友年龄
某君新认识一网友。
当问及年龄时，他的网友说：
“我的年龄是个2位数，我比儿子大27岁,
如果把我的年龄的两位数字交换位置，刚好就是我儿子的年龄”
请你计算：网友的年龄一共有多少种可能情况？
提示：30岁就是其中一种可能哦. -
代码
void test01()
{
int num = 0;
for(int i=0;i<=9;i++)
{
for(int j=0;j<i;j++)
{
if( 9*(i-j) == 27 )
{
num++;
//printf("%d, %d\n", 10*i+j, 10*j+i);
}
}
}
printf("num : %d\n", num);
}
2
-
题目
生日蜡烛
某君从某年开始每年都举办一次生日party，并且每次都要吹熄与年龄相同根数的蜡烛。
现在算起来，他一共吹熄了236根蜡烛。
请问，他从多少岁开始过生日party的？ 注意：这道题不需要进行两层循环即可。
-
代码
void test02()
{
int sum = 0;
int si = 0, ei = 0;
int goal = 236;
while( sum != goal )
{
if( sum < goal )
{
ei++;
sum += ei;
}
else if( sum > goal )
{
sum -= si;
si++;
}
}
printf("si : %d, ei : %d\n", si, ei);
}
3
-
题目
方格填数
如下的10个格子
+--+--+--+
| | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | |
+--+--+--+
（如果显示有问题，也可以参看【图1.jpg】）
填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？ 思路：DFS
-
代码
#include <stdio.h>
int num[3][4];
int sum = 0;
bool isFilled[10];
int abs(int n)
{
return n >= 0 ? n : -n;
}
// 在num[r][c]处防止i符合规则则返回true
bool isLegal(int r, int c, int val)
{
if( r == 0 && c == 0 )
return true;
else if( r == 0 )
return abs(val-num[r][c-1]) > 1;
else if( c == 0 )
return abs(val-num[r-1][c]) > 1 && abs(val-num[r-1][c+1])>1;
else if( c != 3 )
return abs(val-num[r][c-1]) > 1 && abs(val-num[r-1][c]) > 1 && abs(val-num[r-1][c-1])>1 && abs(val-num[r-1][c+1])>1;
else
return abs(val-num[r][c-1]) > 1 && abs(val-num[r-1][c]) > 1 && abs(val-num[r-1][c-1])>1;
}
void dfs(int r, int c)
{
if( r == 2 && c == 3 )
{
sum++;
return;
}
for(int i=0;i<=9;i++)
{
if( !isFilled[i] && isLegal(r, c, i) )
{
num[r][c] = i;
isFilled[i] = true;
dfs( r + (c+1)/4, (c+1)%4 );
isFilled[i] = false;
}
}
}
int main()
{
num[0][0] = -10;
num[2][3] = -10;
for(int i=0;i<10;i++)
isFilled[i] = false;
dfs( 0, 1 );
printf("%d\n", sum);
return 0;
}
4
-
题目
快排的填空实现 -
代码
#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;
}
5
-
题目
消除尾一
下面的代码把一个整数的二进制表示的最右边的连续的1全部变成0
如果最后一位是0，则原数字保持不变。
如果采用代码中的测试数据，应该输出：
00000000000000000000000001100111 00000000000000000000000001100000
00000000000000000000000000001100 00000000000000000000000000001100 -
代码
#include <stdio.h>
void f(int x)
{
int i;
for(i=0; i<32; i++) printf("%d", (x>>(31-i))&1);
printf(" ");
x = x&(x+1);
for(i=0; i<32; i++) printf("%d", (x>>(31-i))&1);
printf("\n");
}
int main()
{
f(103);
f(12);
return 0;
}
6
-
题目
寒假作业
现在小学的数学题目也不是那么好玩的。
看看这个寒假作业：
□ + □ = □
□ - □ = □
□ × □ = □
□ ÷ □ = □
(如果显示不出来，可以参见【图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 <stdio.h>
bool isUsed[14];
int num[4][3];
int sum = 0;
// 判断第几行最后一个值填入这个是否正确
bool right( int r, int val )
{
switch(r)
{
case 0:
return num[r][0] + num[r][1] == val;
break;
case 1:
return num[r][0] - num[r][1] == val;
break;
case 2:
return num[r][0] * num[r][1] == val;
break;
case 3:
return val * num[r][1] == num[r][0];
break;
default:
return false;
}
}
void dfs( int r, int c )
{
if( r == 4 )
{
sum++;
if( sum <= 3 )
{
for(int i=0;i<4;i++)
{
for(int j=0;j<3;j++)
printf("%4d", num[i][j]);
printf("\n");
}
}
printf("\n");
return;
}
for(int i=1;i<=13;i++)
{
// 该数没有被使用
if( !isUsed[i] )
{
isUsed[i] = true;
// 是计算的结果，则需要判断一下
if( c != 2 || right(r, i) )
{
num[r][c] = i;
dfs( r+(c+1)/3, (c+1)%3 );
}
isUsed[i] = false;
}
}
}
int main()
{
for(int i=1;i<14;i++)
isUsed[i] = false;
dfs( 0, 0 );
printf("%d\n", sum);
}
7
-
题目
剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。 注：有人用dfs求解，我没怎么看懂23333，参考链接在这：http://blog.csdn.net/kavu1/article/details/51130029
-
代码
#include <stdio.h>
bool map[3][4];
int sum = 0;
int idx[5];
int abs( int a )
{
return a >= 0 ? a : -a;
}
bool connect(int a, int b)
{
int r1 = a/4, c1 = a%4;
int r2 = b/4, c2 = b%4;
return abs(r1-r2)+abs(c1-c2) == 1;
}
bool match()
{
bool ret = false;
for(int i=0;i<5;i++)
{
ret = false;
for(int j=0;j<5;j++)
{
if( connect(idx[i],idx[j]) )
{
ret = true;
break;
}
}
if( !ret ) // 如果无法连接，则退出并返回
break;
}
return ret;
}
int main()
{
// 随机选取5个点，看是否能够
for(int i1=0;i1<12;i1++)
{
idx[0] = i1;
for(int i2=i1+1;i2<12;i2++)
{
idx[1] = i2;
for( int i3=i2+1;i3<12;i3++ )
{
idx[2] = i3;
for(int i4=i3+1;i4<12;i4++)
{
idx[3] = i4;
for(int i5=i4+1;i5<12;i5++)
{
idx[4] = i5;
if( match() )
{
sum++;
}
}
}
}
}
}
printf("ans : %d\n", sum);
return 0;
}
8
-
题目
四平方和
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多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 -
代码
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int num[5];
int goal = 0;
int number = 0;
void dfs(int n, int sum)
{
if( number != 0 )
exit(0);
if( sum > goal || n > 5 )
return;
if( n == 5 )
{
if( sum == goal )
{
number++;
for( int i=1;i<5;i++ )
printf("%d ", num[i]);
printf("\n");
}
return;
}
// 这是不等于5的情况
if( sum == goal )
return;
num[n] = num[n-1];
int tmp = sum;
while( tmp < goal )
while( tmp < goal )
{
tmp = sum+num[n]*num[n];
dfs( n+1, tmp );
num[n]++;
}
}
int main()
{
scanf("%d", &goal);
dfs(1, 0);
return 0;
}
9
-
题目
密码脱落
X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。
输入一行，表示现在看到的密码串（长度不大于1000）
要求输出一个正整数，表示至少脱落了多少个种子。
例如，输入：
ABCBA
则程序应该输出：
0
再例如，输入：
ABDCDCBABC
则程序应该输出：
3 -
代码
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
char s[1020];
int min_len = 9999;
int s_len = 0;
void dfs(int l, int r, int len)
{
if( l>=r )
{
if( min_len > len )
min_len = len;
return;
}
// 对称则继续检测
if( s[l] == s[r] )
dfs( l+1, r-1, len );
// 2种情况
else
{
dfs(l+1, r, len+1);
dfs(l, r-1, len+1);
}
}
int main()
{
gets( s );
s_len = strlen( s );
dfs( 0, s_len-1, 0 );
printf("min len : %d\n", min_len);
return 0;
}
10
-
题目
最大比例
X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。
并且，相邻的两个级别间的比例是个固定值。
也就是说：所有级别的奖金数构成了一个等比数列。比如：
16,24,36,54
其等比值为：3/2
现在，我们随机调查了一些获奖者的奖金数。
请你据此推算可能的最大的等比值。
输入格式：
第一行为数字 N (0<N<100)，表示接下的一行包含N个正整数
第二行N个正整数Xi(Xi<1 000 000 000 000)，用空格分开。每个整数表示调查到的某人的奖金数额
要求输出：
一个形如A/B的分数，要求A、B互质。表示可能的最大比例系数
测试数据保证了输入格式正确，并且最大比例是存在的。
例如，输入：
3
1250 200 32
程序应该输出：
25/4
再例如，输入：
4
3125 32 32 200
程序应该输出：
5/2
再例如，输入：
3
549755813888 524288 2
程序应该输出：
4/1 - 参考链接：http://www.aichengxu.com/cyvyan/6607933.htm
- 思路：这道题其实是找出所有相邻数的最大公约数的最大公约数，首先对数据进行排序，然后去除重复的数字，最后求出相邻数据被的最大公约数除过之后的数。原文的链接中的做法无法对
16,24,81的测试数据正确求解（我认为正确的解为3/2，原文链接代码得到的是9/4） - 注意：long long的数据输入与输出需要使用%lld，否则在输出时，会影响后面数据的输出，在输入时，对于很大的数据，无法读取。
-
代码
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int N;
long long bonus[100];
long long res[100], p1[100], p2[100];
long long num1, num2;
void sort()
{
long long tmp;
for(int i=0;i<N;i++)
{
for(int j=i+1;j<N;j++)
{
if( bonus[j] < bonus[i] )
{
tmp = bonus[j];
bonus[j] = bonus[i];
bonus[i] = tmp;
}
}
}
}
void removeSame()
{
int k = 1;
res[0] = bonus[0];
for(int i=1;i<N;i++)
{
if( bonus[i] == bonus[i-1] )
continue;
res[k++] = bonus[i];
}
N = k;
}
long long gcd(long long a, long long b)
{
long long t;
if( b == 0 )
return a;
else
return gcd( b, a%b );
}
long long max(long long a, long long b)
{
return a >= b ? a : b;
}
long long min(long long a, long long b)
{
return a <= b ? a : b;
}
void solve()
{
int tmp;
int k;
if( N == 1 )
{
num1 = 1;
num2 = 1;
return;
}
else if( N == 2 )
{
tmp = gcd( res[1], res[0] );
num1 = res[1] / tmp;
num2 = res[0] / tmp;
return;
}
else
{
k = 0;
long long g,g1,g2;
for(int i=1;i<N;i++)
{
tmp = gcd( res[i], res[i-1] );
p1[k] = res[i] / tmp;
p2[k] = res[i-1] / tmp;
k++;
}
}
double t = 999999; // 存储最小的公约数
long long t1, t2, tt1, tt2, max_tmp, min_tmp;
long long max_p1, max_p2, min_p1, min_p2;
for(int i=0;i<N-1;i++)
{
for(int j=i+1;j<N-1;j++)
{
if( p1[i]*p2[j] == p1[j]*p2[i] )
{
t1 = p1[i];
t2 = p2[i];
}
else
{
max_p1 = max( p1[i], p1[j] );
max_p2 = max( p2[i], p2[j] );
min_p1 = min( p1[i], p1[j] );
min_p2 = min( p2[i], p2[j] );
max_tmp = max_p1;
min_tmp = min_p1;
max_p1 = max( min_tmp, max_tmp/min_tmp );
min_p1 = min( min_tmp, max_tmp/min_tmp );
max_tmp = max_p2;
min_tmp = min_p2;
max_p2 = max( min_tmp, max_tmp/min_tmp );
min_p2 = min( min_tmp, max_tmp/min_tmp );
t1 = gcd( max_p1, min_p1 );
t2 = gcd( max_p2, min_p2 );
}
// 在之前的程序中可知p1>p2
if( 1.0*t1/t2 < t )
{
t = 1.0*t1/t2;
tt1 = t1;
tt2 = t2;
}
}
}
tmp = gcd(tt1, tt2);
num1 = tt1 / tmp;
num2 = tt2 / tmp;
}
int main()
{
scanf("%d", &N);
for(int i=0;i<N;i++)
scanf("%lld", &bonus[i]);
sort();
removeSame();
solve();
printf("%lld/%lld\n", num1, num2);
return 0;
}