/*****************************2000题**********************************/
#include <iostream>
#include <algorithm>使用C++中的库函数，实现字符位置调整
using namespace std;
int main(void)
{
char n[4];
while (cin >> n)
{
if (n[0] > n[1]) swap(n[0], n[1]);
if (n[1] > n[2]) swap(n[1], n[2]);
if (n[0] > n[1]) swap(n[0], n[1]);
<< n[0] << ' ' << n[1] << ' ' << n[2] << endl;
}
return 0;
}思路：
1 要让三个数从小到大排，顺序就是：比较1，2两个数。如果第一个数比第二数大，把这两个数交换，来保证前面两个数按升序排列。
2 比较2，3两个数。如果第二个数比第三数大，把这两个数交换，来保证后面两个数按升序排列。
3 经过上面两步，最大的数已经被移到最后。再重复一次第一步。保证三个数都是按升序来排列。
/*****************************2001题**********************************/
#include <math.h>
#include <stdio.h>
int main(void)
{
double x[2], y[2];
while(scanf("%lf%lf%lf%lf", x, y, x+1, y+1) != EOF)
("%.2f\n",sqrt((x[1]-x[0])*(x[1]-x[0])+(y[1]-y[0])*(y[1]-y[0])));
return 0;
}思路：
直接用勾股定理做。
/*****************************2002题**********************************/
#include <math.h>
#include <stdio.h>
#define PI 3.1415927
int main(void)
{
double r;
while (scanf("%lf", &r) != EOF)
("%.3lf\n", 4.0*PI*r*r*r/3.0);
return 0;
}
思路：
球体的体积公式:V = 4пr3/3
/*****************************2003题**********************************/
#include <math.h>
#include <stdio.h>
int main(void)
{
double r;
while (scanf("%lf", &r) != EOF)
("%.2lf\n", fabs(r));
return 0;
}
思路：
直接调用库函数。
/*****************************2004题**********************************/
#include <math.h>
#include <stdio.h>
int main(void)
{
int r;
while (scanf("%d", &r) != EOF)
{
if (r < 0)
("Score is error!");
else if (r < 60)
("E");
else if (r < 70)
("D");
else if (r < 80)
("C");
else if (r < 90)
("B");
else if (r < 101)
("A");
else
("Score is error!");
}
return 0;
}思路：
4 接受数据Score，直到读入失败
5 如果 Score 小于 0，为错误数据，输出“Score is error!”，返回第1步，否则进入第3步。
6 如果 Score 小于 60，输出“E”，返回第1步，否则进入第3步。
7 如果 Score 小于 70，输出“D”，返回第1步，否则进入第4步。
8 如果 Score 小于 80，输出“C”，返回第1步，否则进入第5步。
9 如果 Score 小于 90，输出“B”，返回第1步，否则进入第6步。
10 如果 Score 小于 101，输出“A”，返回第1步，否则进入第7步。
11 Score为错误数据，输出“Score is error!”，返回第1步。
/*****************************2005题**********************************/
#include <math.h>
#include <stdio.h>
#define lev(n) (n % 4 == 0 && (n % 100 != 0 || n % 400 == 0))
int main(void)
{
int y, m, d, i, s;
int month[2][13] = {
{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
{0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};
while (scanf("%d/%d/%d", &y, &m, &d) != EOF)
{
for (s = 0, i = 1 ; i < m ; i++)
+= month[lev(y)][i];
+= d;
("%d\n", s);
}
return 0;
}思路：
判断N是否为闰年的方法是：N能4整数但不能被100整除 或者 N能被400整除
算出第N年的每个月的天数后就从一月开始累加，不要忘了最后要加天数
/*****************************2006题**********************************/
#include <stdio.h>
int main(void)
{
int n, i, s, t;
while (scanf("%d", &n) != EOF)
{
for (s = 1, i = 0 ; i < n ; i++)
{
("%d", &t);
if (t & 1) s *= t;
}
("%d\n", s);
}
return 0;
}
思路：
循环+条件判断
/*****************************2007题**********************************/
#include <stdio.h>
int main(void)
{
unsigned int m, n, i, x, y;
while (scanf("%u%u", &m, &n) != EOF)
{
if (m > n)
{
= n;
= m;
m = i;
}
= y = 0;
for (i = m ; i <= n ; i++)
(i & 1) ? (y += i*i*i) : (x += i*i);
("%u %u\n", x, y);
}
return 0;
}
思路：
简单的循环+判断。
按题目的意思数据类型用unsigned int型就可以了。
但这个问题有个容易遗漏的地方:输入的m、n有可能m > n!
/*****************************2008题**********************************/
#include <stdio.h>
int main(void)
{
int n, i, a, b, c;
double x;
while (scanf("%d", &n) , n)
{
= b = c = 0;
for (i = 0 ; i < n ; i++)
{
("%lf", &x);
if (x > 0) c++;
else if (x < 0)
++;
else b++;
}
("%d %d %d\n", a, b, c);
}
return 0;
}
思路：
算法与2004题雷同，但要注意这里上以0作为结束符，而不是EOF
/*****************************2009题**********************************/
#include <math.h>
#include <stdio.h>
int main(void)
{
int n;
double x, s;
while (scanf("%lf%d", &x, &n) != EOF)
{
for(s = 0.0; n--; x = sqrt(x))
+= x;
("%.2lf\n", s);
}
return 0;
}
思路：
循环
/*****************************2010题**********************************/
#include<stdio.h>
int main()
{
int b, l, c, i;
int a[] = {1, 153, 370, 371, 407};
while (scanf("%d%d", &b, &l) != EOF)
{
= 0;
for (i = 0 ; i < 5 ; i++)
{
if (a[i] >= b && a[i] <= l)
(c++ ? " %d" : "%d", a[i]);
}
(c ? "\n" : "no\n");
}
return 0;
}
思路：
12 这里讨论给出一个整数n，如何判断它是否为水仙花数的算法。
而判断一组数只要在外面加层循环就可以了。sum ← 0(0 赋值给 sum)
13 n ← m
14 判断n是否为0，不是则进入下一步，否则跳到第7步
15 sum += (n % 10)3
16 n /= 10
17 重复第3步
18 m 等于 sum 则返回1，否则返回0
至于输出的问题，完全可以再加个变量c，初始为0，每输出一个水仙花数 都自增一次c++。
然后在c > 0时就在数字前输出一个空格。
最后判断 c > 0就只输出一个回车，否则还要输出no。
/*****************************2011题**********************************/
#include<stdio.h>
int n;
double rev(int c)
{
return c <= n ?( ((c & 1) ? 1.0 : -1.0) / c + rev(c + 1) ): 0 ;
}
int main()
{
int t;
scanf("%d", &t);
while (t-- && scanf("%d", &n))
("%.2lf\n", rev(1));
return 0;
}
思路：
本题的算法依然是迭代。
初始sum=0， i从1开始到n，如果1是奇数，sum += 1.0 / i; 否则 sum -= 1.0 / i;
当然，迭代是可以换成递归的。本题的递归定义为:
┌ 0 (n = 0)
f(n)┼ f(n-1)+1/n (n为奇数)
└ f(n-1)-1/n (n为偶数)
当然，你也可以顺着递归，这就随你喜欢了。
┌ 0 (i > n)
f(i)┼ f(n+1)+1/n (n为奇数)
└ f(n+1)-
/*****************************2012题**********************************/
#include <stdio.h>
int main(void)
{
int m, n;
int x[] = {
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1
};
while (scanf("%d%d", &m, &n), m || n)
{
for (m += 39, n += 39; x[m] && m <= n ; m++);
(m > n ? "OK" : "Sorry");
}
return 0;
}
思路： 还记得第2010题的算法吧？本题也一样:打表
/*****************************2013题**********************************/
#include <math.h>
#include <stdio.h>
int main(void)
{
int n;
while (scanf("%d", &n) != EOF)
("%.0f\n", 3 * pow(2, n - 1) - 2);
return 0;}思路： 直接用循环迭代过关
/*****************************2014题**********************************/
#include <stdio.h>
int main(void)
{
int n, i;
double min, max;
double x, y;
while (scanf("%d", &n) != EOF)
{
("%lf", &x);
= max = x;
for (i = 1 ; i < n ; i++)
{
("%lf", &y);
+= y;
if (y > max) max = y;
if (y < min) min = y;
}
("%.2lf\n", (x - min - max) / (n - 2));
}
return 0;
}
思路：
要实现的算法是:求整个数组的和、在数组中找最值。
找最值，可以先把第一个元素赋给max、min变量，做一次遍历，一一比较，把最大值存入max，最小值存入min。
也可以直接对数组进行排序，然后从第二个加到倒数第二个，这样就可以了，省去减两个最值。
/*****************************2015题**********************************/
#include <stdio.h>
int main(void)
{
int i, n, m, b, c;
while (scanf("%d%d", &n, &m) != EOF)
{
= 2;
= 0;
for (i = 0 ; i < n / m ; i++)
{
(c++ ? " %d" : "%d", b + m - 1);
+= m * 2;
}
(n % m ? " %d\n" : "\n", b + n % m - 1);
}
return 0;
}
思路：
解决这个问题，关键是要解决给出一个偶数X，求出从它开始连续的m个偶数的和
而这个问题只要用等差数列求和公式就可以了。
/*****************************2016题**********************************/
#include <stdio.h>
#include <algorithm>库函数的使用，交换两个元素
using namespace std;
int main(void)
{
int i, n;
int f[100], m;
while (scanf("%d", &n), n)
{
= 0;
for (i = 0 ; i < n ; i++)
{
("%d", f + i);
if (f[i] < f[m]) m = i;
}
swap(f[m], f[0]);
for (i = 0 ; i < n ; i++)
("%d%c", f[i], (i < n - 1 ? ' ' : '\n'));
}
return 0;
}
思路：
这题涉及交换，所以在寻找最小值的时候不需要记录它的值，只要记录下它的下标就可以。
/*****************************2017题**********************************/
#include <ctype.h>
#include <stdio.h>
int main(void)
{
int n, d;
char c;
scanf("%d%*c", &n);
while (n--)
{
for (d = 0 ; (c = getchar()) != '\n' ;)
{
if (isdigit(c))
++;
}
("%d\n", d);
}
return 0;
}思路：
因为本题只要求输出每一行数字的个数。所以不需要把那些字符记录下来。
因此不需要开个字符数组去记录。而且如果你想开也不知道该开多大，因为题目中没有提示一行最多有几个。
而判断行末就判断是否为'\n'就可以。
/*****************************2018题**********************************/
#include <ctype.h>
#include <stdio.h>
int main(void)
{
int n, i;
int fab[55] = {1, 2, 3, 4, 6};
for (i = 5 ; i < 55 ; i++)
[i] = fab[i - 1] + fab[i - 3];
while (scanf("%d", &n), n)
{
("%d\n", fab[n - 1]);
}
return 0;
}思路：
本题中，第n年的牛的来源有2中:
第n-1年的牛
第n-3年的牛所生的小牛
而递推的出口是第1年为1头，第2年为2头，第3年为3头。
/*****************************2019题**********************************/
#include <stdio.h>
int main(void)
{
int n, i, m, x[101];
while (scanf("%d%d", &n, &m), n || m)
{
for (i = 0 ; i < n ; i++)
("%d", x + i);
for (i = n ; i && x[i - 1] > m ; i--)
[i] = x[i - 1];
x[i] = m;
for (i = 0 ; i < n + 1 ; i++)
("%d%c", x[i], (i - n ? ' ' : '\n'));
}
return 0;
}
思路：
本题目其实就是让你实现一次插入排序。
插入排序的工作机理与很多人打牌时，整理手中牌时的做法差不多。在开始摸牌时，我们的左手是空的，牌面朝下放在桌上。
接这，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的每一张牌从右到左地进行比较。
无论在什么时候，左手中的牌都是排好序的，而这些牌原先都是桌上那副牌里最顶上的有一些牌。
下面是插入排序的伪代码：
INSERTION-SORT(A)
1 for j←2 to length[A]
2 do key←A[j]
3 /*Insert A[j]into the sorted sequence A[1..j-1].*/
4 i←j - 1
5 while i>0 and A[j]>key
6 do A[i+1]←A[i]
7 i←i - 1
8 A[i+1]←key
/*****************************2020题**********************************/
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
int cmp(const int *a, const int *b)
{
return abs(*b) - abs(*a);
}
int main(void)
{
int n, i, x[101];
while (scanf("%d", &n), n)输入条件不为0，则继续执行
{
for (i = 0 ; i < n ; i++)
("%d", x + i);
(x, n, sizeof(int), cmp);
for (i = 0 ; i < n ; i++)
("%d%c", x[i], (i != n - 1 ? ' ' : '\n'));
}
return 0;
}
思路：
这题的考点就是排序。
对初学者来说，比较熟悉的排序是“冒泡排序”和“选择排序”。
在排升序的时候，元素比较用'<'，降序用'>'。
对于整数等基本数据类型，这样的比较符号很容易理解。但换了其他比较规则，你是不是还能很好地理解呢？呵呵。
就像本题的规则：比较数的绝对值的大小，在这里-3 > 1，所以就不能直接用'>'，而是要自己制定一套大小规则。
刚开始可能不习惯看到 -3 > 1这样的规则，熟悉后就好了。
/*****************************2021题**********************************/
#include <stdio.h>
int main(void)
{
int n, i, x, sum;
while (scanf("%d", &n), n)
{
= 0;
for (i = 0 ; i < n ; i++)
{
("%d", &x);
+= x / 100;
%= 100;
+= x / 50;
%= 50;
+= x / 10;
%= 10;
+= x / 5;
%= 5;
+= x / 2;
%= 2;
+= x;
}
printf("%d\n", sum);
}
return 0;
}
思路：
这道题可以简化为给定面额，求需要的人民币的张数。
用的方法是贪心。这不难理解，用的人民币的面值越大，当然张数就越少。
/*****************************2022题**********************************/
#include <math.h>
#include <stdio.h>
int main(void)
{
int i, j;
int n, m;
int x, y;
double a, t;
while (scanf("%d%d", &n, &m) != EOF)
{
= x = y = 0;
for (i = 0 ; i < n ; i++)
{
for (j = 0 ; j < m ; j++)
{
("%lf", &t);
if (fabs(t) > fabs(a))
{
= t;
= i;
= j;
}
}
}
("%d %d %.0f\n", x + 1, y + 1, a);
}
return 0;
}
思路：
从以前的在一维数组里找最值扩大到二维数组而已。
/*****************************2023题**********************************/
#include <stdio.h>
#include <string.h>
int main(void)
{
int n, m;
int i, j;
int t, d;
int s[50];
int c[5];
int sc[50][5];
while (scanf("%d%d", &n, &m) != EOF)
{
(s, 0, sizeof(s));
(c, 0, sizeof(c));
(sc, 0, sizeof(sc));
for (i = 0 ; i < n ; i++)
{
for (j = 0 ; j < m ; j++)
{
("%d", &sc[i][j]);
[j] += sc[i][j];
[i] += sc[i][j];
}
}
for (i = 0 ; i < n ; i++)
printf("%.2lf%c", s[i] * 1.0 / m, i < n - 1 ? ' ' : ' \n');
for (i = 0 ; i < m ; i++)
printf("%.2lf%c", c[i] * 1.0 / n, i < m - 1 ? ' ' : ' \n');
for (t = i = 0 ; i < n ; i++)
{
for (d = 1, j = 0 ; j < m ; j++)
{
if (sc[i][j] < 1.0 * c[j] / n)
{
= 0;
break;
}
}
if (d)
++;
}
("%d\n\n", t);
} return 0;
}思路：
简单的循环+条件判断。
/*****************************2024题**********************************/
#include <ctype.h>
#include <stdio.h>
int main(void)
{
int n, d, i;
char sym[64];
scanf("%d%*c", &n);
while (n--)
{
(sym);
if (sym[0] != '_' && !isalpha(sym[0]))使用头文件包含的库文件源程序
{
("no");
continue;
}
for (d = i = 1 ; sym[i] ; i++)
{
if (!isalnum(sym[i]) && sym[i] != '_')
{
= 0;
break;
}
}
(d ? "yes" : "no");
}
return 0;
}
思路：
直接按题目的描述来做就可以了。
先判断是不是以下划线或字母开头，然后依次判断后面的字符是不是都为数字或字母。
/*****************************2025题**********************************/
#include <stdio.h>
int main(void)
{
char t[128];
char max;
int i;
while (gets(t))
{
for (max = i = 0 ; t[i] ; i++)
{
if (t[i] > max)
= t[i];
}
for (i = 0 ; t[i] ; i++)
{
(t[i]);
if (t[i] == max)
("%s", "(max)");
}
('\n');
}
return 0;
}思路：找最大值
/*****************************2026题**********************************/
#include <ctype.h>
#include <stdio.h>
int main(void)
{ char t[128] = {' '};
int i;
while (gets(t + 1))
{
for (i = 1 ; t[i] ; i++)
((isalpha(t[i]) && t[i-1] == ' ') ? toupper(t[i]) : t[i]);
('\n');
}
return 0;
}思路：
问题的关键在于如何判断为单词的首字母。
方法也不难，只要你判断当前字符为字母，而前一个为空格就可以了。
为了简单处理整个字符串的第一个字符。你可以让保存前一个字符的变量初始为空格。
这样就可以把判断规则统一起来了，不用特殊处理字符串的第一个字符。
/*****************************2027题**********************************/
#include <ctype.h>
#include <stdio.h>
int main(void)
{
int n;
int y[5];
char c;
("%d%*c", &n);
while (n--)
{
[0] = y[1] = y[2] = y[3] = y[4] = 0;
while ((c = getchar()) != '\n')
{
switch (tolower(c))
{
case 'a':
[0]++; break;
case 'e':
[1]++; break;
case 'i':
[2]++; break;
case 'o':
[3]++;break;
case 'u': y[4]++;break;
default : break;
}
}
printf("a:%d\n", y[0]);
printf("e:%d\n", y[1]);
printf("i:%d\n", y[2]);
printf("o:%d\n", y[3]);
printf("u:%d\n", y[4]);
if (n) putchar('\n');
}
return 0;
}思路：
这一题，只要懂得switch语法就可以了。 当然，用if嵌套也没问题
/*****************************2028题**********************************/
#include<stdio.h>
typedef unsigned long ulong;
ulong gcd(ulong u, ulong v)
{
int remainder;
= u % v;
while(remainder)
{
= v;
= remainder;
= u % v;
}
return v;
}
ulong lcm(ulong u, ulong v)
{
return u * v / gcd(u, v);
}
int main(void)
{
int n;
ulong u;
ulong res;
while (scanf("%d", &n) != EOF)
{
= 1;
while (n--)
{
("%lu", &u);
= lcm(res, u);
}
("%lu\n", res);
}
return 0;
}思路：
最小公倍数lcm(x, y) = x * y / gcd(x, y) (其中gcd()求最大公约数)
所以这题的关键的关键是求最大公约数。
/*****************************2029题**********************************/
#include <stdio.h>
#include <string.h>
int main(void)
{
int n;
char s[1024];
char t[1024];
("%d%*c", &n);
while (n--)
{
(s);
(t, s);
(s); //strrev用于反转字符串.
(strcmp(t, s) ? "no" : "yes");
}
return 0;
}思路：
得到字符串长度len
i从0循环到len / 2;
比较string[i] 与 string[len - i - 1] 是否相同;
/*****************************2030题**********************************/
#include <stdio.h>
#include <string.h>
int main(void)
{
int n;
int count;
char c;
scanf("%d%*c", &n);
while (n--)
{
= 0;
while ((c = getchar()) != '\n')
{
if (c < 0)
++;
}
("%d\n", count / 2);
}
return 0;
}思路：
汉字占双字节，高位的字节里都是 < 0,所以只要统计小于0的字符的个数。
/*****************************2031题**********************************/
#include <stdio.h>
#include <string.h>
void ttor(int n, int r)
{
if (n)
{
(n / r, r);
("%c", n % r > 9 ? n % r - 10 + 'A' : n % r + '0');
}
}
int main(void)
{
int n;
int r;
while (scanf("%d%d", &n, &r) != EOF)
{
if (n > 0)
(n, r);
else if (!n)
('0');
else
{
('-');
(-n, r);
}
('\n');
}
return 0;
}
思路：
1、把r进数转换成十进制数，只要把r进制数写成r的各次幂的和的形式。然后按十进制计算结果。(这里r是大于1的自然数)；
2、把十进制换成r进制，可以把十进制化成r的各次幂(各次幂的系数小于r而大于或等于0的整数)的和，从最高次幂起各次幂的系数就是依次的r进制从左到右各个数位上的数字。
/*****************************2032题**********************************/
#include <stdio.h>
#include <string.h>
int main(void)
{
int i, j, n;
int YanHui[32];
while (scanf("%d", &n) != EOF)
{
(YanHui, 0, sizeof(YanHui));
[0] = 1;
for (i = 0 ; i < n ; i++)
{
("%d", 1);
for (j = i ; j ; j--)
[j] += YanHui[j - 1];
for (j = 1 ; j <= i ; j++)
(" %d", YanHui[j]);
('\n');
}
('\n');
}
return 0;
}
思路：
把杨辉三角压缩进数组中，就会发现它的规律:f(i, i) = f(i, 1) = 1 (i > 0)
f(i, j) = f(i-1, j) + f(i-1, j-1) (j < i)
/*****************************2033题**********************************/
#include <stdio.h>
int main(void)
{
int n, i;
int t[6];
("%d", &n);
while (n--)
{
for (i = 0 ; i < 6 ; i++)
("%d", t + i);
[1] += (t[2] + t[5]) / 60;
[2] = (t[2] + t[5]) % 60;
[0] += (t[1] + t[4]) / 60;
[1] = (t[1] + t[4]) % 60;
[0] += t[3];
("%d %d %d\n", t[0], t[1], t[2]);
}
return 0;
}
思路：
平时用的是十进制，规则是逢10进1，而时间是六十进制，就是逢60进1位。本题就是让你做一个60进制的加法运算。
/*****************************2034题**********************************/
#pragma warning(disable : 4786)
#include <set>
#include <cstdio>
using namespace std;
int main(void)
{
int n, m, t;
set <int> s;
set <int>::iterator it;
while (scanf("%d%d", &n, &m), n + m)
{
while (n--)
{
("%d", &t);
.insert(t);
}
while (m--)
{
("%d", &t);
if (s.count(t)) s.erase(t);
}
for (it = s.begin(); it != s.end(); it++)
("%d ", *it);
(s.size() ? "\n" : "NULL\n");
.clear();
}
return 0;
}
思路：
集合的减法 A-B的意义是:在集合A中去掉所有与集合B中相同的元素，剩下的内容就是结果。
/*****************************2035题**********************************/
#include <stdio.h>
int mi(int n, int m)
{
Return m?(m%2?(mi(n,m/2)*mi(n, m/2)*(n%1000))%1000:(mi(n,m/2)*mi(n,m/2))%1000):1;
}
int main(void)
{
int n, m;
while(scanf("%d%d", &n, &m), n+m)
("%d\n", mi(n, m));
return 0;
}思路：
mn就是把m连乘n次，虽然效率低，但应付本题也可以0MS 0K AC了
如果你也想得到一个更有效率的算法，可以看看下面公式，有灵感吗？ 1 n = 0
mn = (mk)2 n = 2k
m·m2k n = 2k + 1
/*****************************2036题**********************************/
#include <math.h>
#include <stdio.h>
int main(void)
{
int x[3], y[3], n;
double sum;
while (scanf("%d", &n), n)
{
("%d%d", x, y);
[2] = x[0]; y[2] = y[0];
= 0.0;
while (--n)
{
scanf("%d%d", x+1, y+1);
+= x[0]*y[1] - x[1]*y[0];
[0] = x[1]; y[0] = y[1];
}
+= x[0]*y[2] - x[2]*y[0];
printf("%.1f\n", sum / 2.0);
}
return 0;
}
思路：
可以利用多边形求面积公式：
S = 0.5 * ( (x0*y1-x1*y0) + (x1*y2-x2*y1) + ... + (xn*y0-x0*yn) )
其中点(x0, y0), (x1, y1), ... , (xn, yn)为多边形上按逆时针顺序的顶点。
/*****************************2037题**********************************/
#include <stdio.h>
#include <stdlib.h>
struct c{ int x; int y; int ord;
}d[100];
int cmp(const struct c *a, const struct c *b)
{ if ((*a).x == (*b).x) return (*a).y - (*b).y; else
return (*a).x - (*b).x;
}
int main(void)
{ int i, j, n, max;
while (scanf("%d", &n), n)
{ for (max = i = 0; i < n; i++)
{
("%d%d", &d[i].x, &d[i].y);
[i].ord = 1;
}
(d, n, sizeof(struct c), cmp);
[n-1].ord = 1; for (i = n - 2; i >= 0; i--)
{ for (j = i + 1; j < n; j++)
{ if (d[i].y <= d[j].x && d[i].ord < d[j].ord + 1)
[i].ord = d[j].ord + 1;
} if (max < d[i].ord)
= d[i].ord;
}
("%d\n", max);
}
return 0;
}思路：
说是动态规划，其实也有点贪心的思想。
一维数组里保存的的就是以当前节目作为开始，最多能完整地看多少个不同的节目。
很明显，播出时间最晚的节目只是能1。
我采取从后往前的规划方法。
这样，当循环到i时，能保证数组里 D[i+1] -> D[n-1] 保存的都是最优解。
所以让j 从 i+1 到 n-1 循环，找出看完第i个节目后最多还能看的节目数max。(不要忘了判断能否完整收看哦)
把max+1 保存到 D[i]里。如此下去直到结束。
/*****************************2038题**********************************/
#include <stdio.h>
int main(void)
{
int n;
double a, b, c;
scanf("%d", &n);
while (n-- && scanf("%lf%lf%lf", &a, &b, &c))
puts(a + b > c && a + c > b && b + c > a ? "YES" : "NO");
return 0;
}思路：
如果a, b, c三条边能组成三角形，则
a + b > c
a + c > b
b + c > a
/*****************************2039题**********************************/
#include <stdio.h>
int A(int n)
{
int i,sum = 1;
for (i = 2; i <= n / 2; i++)
if (n % i == 0)
+= i;
return sum;
}
int main(void)
{
int n, a, b;
("%d", &n);
while (n-- && scanf("%d%d", &a, &b))
(A(a) == b && A(b) == a ? "YES" : "NO");
return 0;
}思路：
得到数据n后，只要循环1->n/2，找出所有的因子累加就可以了。
/*****************************2040题**********************************/
#include <stdio.h>
int main(void)
{
int i, n;
int m[41] = {0, 1};
for (i = 2; i < 41; i++)
[i] = m[i-1] + m[i-2];
scanf("%d", &n);
while (n-- && scanf("%d", &i))
("%I64d\n", m[i]);
return 0;
}
思路：
由题目可知，每次只能走一级或两级。
因此从第一级走上第二级只能走一步，只有1种走法。
从第一级走上第三级，可以从第一级直接走两步，也可以从第二级走一步。有2种走法
走上第n级，可以从第n-1级走一步上来，也可以从第n-2级走两步上来。
即:
f(2) = 1
f(3) = 2
f(n) = f(n-1) + f(n-2) (n > 3)
是一个斐波那契函数。
/*****************************2041题**********************************/
#include <math.h>
#include <stdio.h>
int main(void)
{
int n, t;
scanf("%d", &t);
while(t-- && scanf("%d", &n))
("%.0f\n", pow(2, n) + 2);
return 0;
}
思路：
本题用循环迭代能0MS 0K过。当然，也同样可以有更神奇的方法
/*****************************2042题**********************************/
#include <ctype.h>
#include <stdio.h>
int main(void)
{
int n, a[6];
char c;
("%d%*c", &n);
while (n--)
{
[0] = a[1] = a[2] = a[3] = a[4] = a[5] = 0;
while ((c = getchar()) != '\n')
{
if (isupper(c))
a[0] = a[5]++; else if (islower(c))
[1] = a[5]++;
else if (isdigit(c))
[2] = a[5]++;
else
[3] = a[5]++;
}
if (a[0]) a[4]++;
if (a[1]) a[4]++;
if (a[2]) a[4]++;
if (a[3]) a[4]++;
(a[4] > 2 && a[5] > 7 && a[5] <17 ? "YES" : "NO");
}
return 0;
}思路：
按照题目的意思做就可以
/*****************************2043题**********************************/
#include <stdio.h>
int main(void)
{
int i, j, n;
int d[51] = {1, 1, 2,};
for (i = 3; i < 51; i++)
[i] = d[i-1] + d[i-2];
scanf("%d", &n);
while (n-- && scanf("%d%d", &i, &j) != EOF)
("%I64d\n", i > j ? 0 : d[j-i]);
return 0;
}
思路：
刚开始我看不懂这一题，因为我不清楚对于六边形的蜂房来说，哪一边算右边。
后来明白了，原来它所谓的右，是那张图的右边。一只蜜蜂可以往下一格走，也可以往图的右边走。 比如:蜜蜂在1格里，它可以往2、3两格里爬。蜜蜂在6格里，它可以往7、8两格里爬。 所以在第n格里蜜蜂可以爬到第n+1, n+2格子里。因此，这又是一个斐波那契数。
/*****************************2044题**********************************/
#include <math.h>
#include <stdio.h>
int main(void)
{
int i;
Int d[51] = {0, 3, 6, 6};
for (i = 4; i < 51; i++)
[i] = d[i-1] + 2*d[i-2];
while (scanf("%d", &i) != EOF)
("%I64d\n", d[i]);
return 0;
}思路：
数组F[i]保存i个方格有多少种填涂方法。
n个方格可以由n-1个方格和n-2个方格填充得到。
比如，在一涂好的n-1个格子里最后再插入一个格子，就得到了n个格子了。
因为已经填好n-1的格子中，每两个格子的颜色都不相同。
所以只能插入一种颜色。而n-1个格子一共有F[n-1]种填涂方法。所以从n-1格扩充到n格共有F(n-1)种方法。
若前n-1不合法，而添加一个后变成合法，即前n-2个合法，而第n-1个与第1个相同。
这时候有两种填法。
所以
f[n] = f[n-1] + 2 * f[n-2];
f[1] = 3;
f[2] = 6;
f[3] = 6
/*****************************2045题**********************************/
#include <math.h>
#include <stdio.h>
int main(void)
{
int i;
Int d[51] = {1, 1, 2,};
for (i = 3; i < 51; i++)
[i] = d[i-1] + d[i-2];
while (scanf("%d", &i) != EOF)
("%I64d\n", d[i]);
return 0;
}
思路：
从图中也可以观察出来，第N张牌的排列可以又N-1张牌的排列再在末尾加上一张竖的牌。 这样依然合法。
也可以在N-2张合法排列的牌后面加上两张横着放的牌(如果竖着放就和上面一种重复了)。
所以f(n) = f(n-1) + f(n-2)
即又是一个斐波那契数列。
/*****************************2046题**********************************/
#include <math.h>
#include <stdio.h>
int main(void)
{
int i;
int d[41][2] = {{0,0}, {1, 2}};
for (i = 2; i < 41; i++)
{
d[i][0] = d[i-1][1];
[i][1] = 2 * (d[i-1][0] + d[i-1][1]);
}
while (scanf("%d", &i) != EOF)
("%I64d\n", d[i][0] + d[i][1]);
return 0;
}思路：
这一题比起其他题稍微高级一点，它需要两路同时进行梯推。
我们每次都在原来合法的字符串的最后面再加一个字符，让它仍然是合法的字符串。
这就会出现最后一个字符是O和不是O两种情况，把末尾是O的字符串的个数保存在D[I][0]里，而不是O的保存在D[I][1]里。
在原来的字符串上再加个O，让它依然合法，则原来的字符串末尾必须不为O，即D[n][0] = D[n-1][1]
而在原来的字符串上再加非O，则它对前面字符串的末尾没有要求，而且它还有E、F两种。因此D[n][1] = 2 * (D[n-1][0] + D[n-1][1])
初始D[1][0] = 1; D[1][1] = 2;
/*****************************2047题**********************************/
#include <math.h>
#include <stdio.h>
int main(void)
{
int i, n;
int d[21][2] = {{1,0},{1,0},{2,1},{6,2}};
for (i = 4; i < 21; i++)
{
[i][0] = i * d[i-1][0];
[i][1] = (i - 1) * (d[i-1][1] + d[i-2][1]);
}
scanf("%d", &n);
while (n-- && scanf("%d", &i))
("%.2f%%\n", d[i][1]*100.0/d[i][0]);
return 0;
}
思路：
神、上帝以及老天爷啊！就为了张Twins的签名照就这么大费周章的。唉~现在的年轻人啊。
N张票的所有排列可能自然是Ann = N!种排列方式
现在的问题就是N张票的错排方式有几种。
首先我们考虑，如果前面N-1个人拿的都不是自己的票，即前N-1个人满足错排，现在又来了一个人，他手里拿的是自己的票。
只要他把自己的票与其他N-1个人中的任意一个交换，就可以满足N个人的错排。这时有N-1种方法。
另外，我们考虑，如果前N-1个人不满足错排，而第N个人把自己的票与其中一个人交换后恰好满足错排。
这种情况发生在原先N-1人中，N-2个人满足错排，有且仅有一个人拿的是自己的票，而第N个人恰好与他做了交换，这时候就满足了错排。
因为前N-1个人中，每个人都有机会拿着自己的票。所以有N-1种交换的可能。
综上所述：f(n) = (i - 1) * [f(n - 1) + f(n - 2)]
/*****************************2048题**********************************/
#include <stdio.h>
int main(void)
{
int i, m, n;
int a[21][2] = {{1,0},{1,0},{2,1},{6,2}};
for (i = 4; i < 21; i++)
{
[i][0] = i * a[i-1][0];
[i][1] = (i-1) * (a[i-1][1] + a[i-2][1]);
}
("%d", &i);
while (i-- && scanf("%d%d", &n, &m))
("%I64d\n", a[n][0]/a[m][0]/a[n-m][0]*a[m][1]);
return 0;
}思路：
是错排问题，方法见2048题。但这里还要从N个新郎中找出M个冤大头。
方法就不用多讲了，就是求组合Cmn
/*****************************2049题**********************************/
#include <stdio.h>
int main(void)
{
int n, i;
scanf("%d", &i);
while (i-- && scanf("%d", &n))
("%d\n", 2*n*n-n+1);
return 0;
}思路：
N条相交的直线最多能把平面分割成几块。---->递推~
/*****************************2050题**********************************/
#include <stdio.h>
void TtoB(int n)
{
if (n)
{
TtoB(n >> 1);
printf("%d", n & 1);
}
}
int main(void)
{
int n;
while (scanf("%d", &n) != EOF)
{
(n);
('\n');
}
return 0;
}思路：数制的转换
资源连接：
标签：2050,main,int,void,while,ACM,++,2000,include From： https://blog.51cto.com/chenfenglove/7023704