acmer之路（3）四月第一周日志
2018-04-08 本文已影响87人
跌跌撞撞小红豆
这一周加入了院足球队，好久都没有感受到在赛场上奔腾的感觉了。不过正好赶上清明，因此也算有充足的时间来码代码。这个月一共码了20题，排名终于冲进了四万名。
四月第一周（1）.png
四月第一周（2）.png
ID 2015 偶数求和
#include<stdio.h>
int main()
{
int n, m, k;
int i,j;
int a[101];
a[0] = 0;
int sum, sum1;
int count;
while (scanf("%d", &n) != EOF)
{
for (i = 1; i <= n; i++)
{
a[i] = 2 * i;
}
scanf("%d", &m);
count = 0;
for (i = 1; i <= n; i = i + m)
{
sum = 0;
for (j = 0; j < m; j++)
{
sum = sum + a[i + j];
}
sum = sum / m;
printf("%d", sum);
if ((i + j - 1) < n)
{
printf(" ");
}
if ((i + j - 1) == n)
{
printf("\n");
}
count++;
if ((n - m * count) < m) break;
}
sum1 = 0;
if ((n - m * count) < m && (n - m * count) > 0)
{
k = n - m * count;
for (i = 0; i < k; i++)
{
sum1 = sum1 + a[m*count + i + 1];
}
sum1 = sum1 / k;
printf("%d\n", sum1);
}
}
}
ID 2016 数据的交换输出
#include<stdio.h>
#define N 100
int main() {
int arr[N];
int i,x,n;
while(scanf("%d",&n),n!=0) {
for(i=0; i<n; i++)
scanf("%d",&arr[i]);
int k=0,j=arr[0];
for(i=1; i<n; i++) {
if(j>arr[i]) {
j=arr[i];
k=i;
}
}
x=arr[0];
arr[0]=j;
arr[k]=x;
for(i=0; i<n; i++) {
if(i==n-1)
printf("%d",arr[i]);
else
printf("%d ",arr[i]);
}
printf("\n");
}
return 0;
}
ID 2017 字符串统计
#include<stdio.h>
#include<string.h>
main()
{
int n,num;
char str;
scanf("%d",&n);
getchar();
while(n--)
{ num=0;
while(scanf("%c",&str),str!='\n')//
{
if(str>='0'&&str<='9') num++;
}
printf("%d\n",num);
}
return 0;
}
ID 2019 数列有序
#include<stdio.h>
int main() {
int i,j,k,m,n;
while(scanf("%d %d",&n,&m),n!=0||m!=0) {
int a[120];
for(i=0; i<n; i++)
scanf("%d",&a[i]);
a[n]=m;
for(j=n-1; j>=0; j--) {
if(a[j]>a[j+1]) {
k=a[j];
a[j]=a[j+1];
a[j+1]=k;
} else
break;
}
for(i=0; i<=n; i++) {
if(i==0)
printf("%d",a[i]);
else
printf(" %d",a[i]);
}
printf("\n");
}
return 0;
}
这一题我一开始采取的方法是找到它的位置，然后插入，并在此之前将它位置之后的所有元素向后挪一个来给它空出位置。跟现在的这个方法相比，我那样处理明显是麻烦了。而且我用前者也确实超时了。
ID 2021 发工资喽
#include<stdio.h>
int main()
{
int n;
int a[101], b[101];
int i;
int hundreds, tens, nums;
int money;
int sum;
while (scanf("%d", &n), n != 0)
{
sum = 0;
for (i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
for (i = 0; i < n; i++)
{
money = 0;
b[i] = 0;
hundreds = a[i] / 100;
tens = (a[i] % 100) / 10;
nums = (a[i] % 100) % 10;
if (hundreds > 0)
{
money = money + hundreds;
}
if (tens >= 5)
{
money++;
tens = tens - 5;
money = money + tens;
}
else
{
money = money + tens;
}
if (nums >= 5)
{
money++;
nums = nums - 5;
money = money + nums / 2;
money = money + nums % 2;
}
else
{
money = money + nums / 2;
money = money + nums % 2;
}
b[i] = money;
}
for (i = 0; i < n; i++)
{
sum = sum + b[i];
}
printf("%d\n", sum);
}
return 0;
}
我这题的思路是这样的，将每个老师的工资看成一个个体，储存在一个数组中。然后将每个老师的工资分成三部分，分别是百位以前的数字（因为人民币最大面额100），十位上的数字，个位上的数字。然后再做处理，最后相加。
ID 2022 海选女主角
#include <stdio.h>
#include <math.h>
int main() {
int n, m, i, j, a, b;
double d, max;
while(~scanf("%d%d", &m, &n)) {
max = 0;
a = 0;
b = 0;
for(i=0; i<m; i++)
for(j=0; j<n; j++) {
scanf("%lf", &d);
if(fabs(d) > fabs(max)) {
a = i;
b = j;
max = d;
}
}
printf("%d %d %.0lf\n", a+1, b+1, max);
}
return 0;
}
这题用到了一个求绝对值的函数，并且注意分数使用浮点型数据表示。
ID 2023 求平均成绩
#include<stdio.h>
int main() {
int n,m;
double a1[50][5],av1[50],av2[5],k;
while(scanf("%d %d",&n,&m)==2) {
int x,y=0;
for(int pe=0; pe<n; pe++) {
for(int su=0; su<m; su++)
scanf("%lf",&a1[pe][su]);
}
for(int i=0; i<n; i++) {
k=0;
for(int j=0; j<m; j++)
k+=a1[i][j];
av1[i]=k/m;
}
for(int i=0; i<m; i++) {
k=0;
for(int j=0; j<n; j++)
k+=a1[j][i];
av2[i]=k/n;
}
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(a1[i][j]>=av2[j])
x=1;
else {
x=0;
break;
}
}
if(x==1)
y++;
}
for(int i=0; i<n; i++) {
if(i==n-1)
printf("%.2lf\n",av1[i]);
else
printf("%.2lf ",av1[i]);
}
for(int j=0; j<m; j++) {
if(j==m-1)
printf("%.2lf\n",av2[j]);
else
printf("%.2lf ",av2[j]);
}
printf("%d\n",y);
printf("\n");
}
return 0;
}
ID 2024 合法标识符
#include<stdio.h>
#include<string.h>
int main()
{
char a[50];
int t;
scanf("%d\n",&t);
while(t--)
{
gets(a);
if(!isalpha(a[0])&&a[0]!='_')
{
printf("no\n");
continue;
}
int flag=1;
int l=strlen(a);
for(int i=1;i<l;i++)
{
if(a[i]!='_'&&!isalnum(a[i]))
{
flag=0;
break;
}
else
{
flag=1;
}
}
if(flag==1)
{
printf("yes\n");
}
else if(flag==0)
{
printf("no\n");
}
}
return 0;
}
ID 2026 首字母变大写
#include<stdio.h>
#include<string.h>
int main()
{
char a[120];
int k, i;
while (gets_s(a,120) != NULL)
{
k = strlen(a);
a[0] = a[0] - 32;
for (i = 0; i < k; i++)
{
if (a[i] == ' ')
{
a[i + 1] = a[i + 1] - 32;
}
}
puts(a);
}
return 0;
}
get_s()函数是新标准里面的一个函数，它避免了get()函数数据溢出导致覆盖堆栈中原有数据的问题。
ID 2027 统计元音
#include<stdio.h>
#include<string.h>
int main()
{
char a[120];
int n, i, k;
int count1, count2, count3, count4, count5;
scanf("%d", &n);
getchar();
while (n--)
{
count1 = count2 = count3 = count4 = count5 = 0;
gets_s(a, 120);
k = strlen(a);
for (i = 0; i < k; i++)
{
if (a[i] == 'a')
{
count1++;
}
if (a[i] == 'e')
{
count2++;
}
if (a[i] == 'i')
{
count3++;
}
if (a[i] == 'o')
{
count4++;
}
if (a[i] == 'u')
{
count5++;
}
}
printf("a:%d\ne:%d\ni:%d\no:%d\nu:%d\n", count1, count2, count3, count4, count5);
if (n)
{
printf("\n");
}
}
return 0;
}
我做这题的时候呢，提交了很多次都无法AC，这里我得到了一些宝贵的教训，分享给大家。首先，WA(wrong answer)和PE(Presentation Error)是完全不同的两个意思。不少人出现了WA就在格式上看了一遍又一遍，我告诉大家，WA基本不是格式错误，PE一定是格式错误。这题我犯了两个低级错误，第一个我把getchar()放在了循环里面，第二个他说最后一个输出后没有空行，并不意味着不用换行，只是说不用换行后再空一行。
ID 2028 求最小公倍数
#include<stdio.h>
#include<string.h>
int main()
{
long long n;
long long i;
long long a[10001];
long long num1, num2;
long long remainder;
long long temp;
long long lcm;
long long x, y;
while (scanf("%d", &n) != EOF)
{
num1 = num2 = 0;
for (i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
lcm = a[0];
for (i = 1; i < n; i++)
{
num1 = lcm;
num2 = a[i];
if (num1 < num2)
{
temp = num2;
num2 = num1;
num1 = temp;
}
x = num1;
y = num2;
while (y != 0)
{
temp = x % y;
x = y;
y = temp;
}
lcm = num1 * num2 / x;
}
printf("%d\n", lcm);
}
return 0;
}
我求多个数的最小公倍数的方法是，先求两个数的最小公倍数，然后将这个求得的数再与第三个数求最小公倍数。注意int类型数据不够存。
ID 2030 汉字统计
#include<stdio.h>
#include<string.h>
int main()
{
int n;
scanf("%d", &n);
getchar();
while (n--)
{
char a[110000];
gets_s(a,110000);
int l, num = 0;
l = strlen(a);
for (int i = 0; i<l; i++)
{
if (a[i]<' ')
num++;
}
printf("%d\n", num / 2);
}
return 0;
}
不少人拿到这题不知道该怎么做，其实很简单。汉字在unicode编码中首位都是1，而在数据存储中首位是1的数字表示是负数，又因为汉字占两个字符，所以要除以二。
ID 2032 杨辉三角
#include <stdio.h>
int main() {
int s = 1, n;
int i, j;
while(scanf("%d", &n)!=EOF) {
printf("1\n");
for (i = 2; i <= n; s = 1, i++) {
printf("1 ");
for (j = 1; j <= i - 2; j++)
printf("%d ", (s = (i - j) * s / j));
printf("1\n");
}
printf("\n");
}
return 0;
}
用数组的方式来打印杨辉三角大家肯定都会，可是我们也可以通过发现它们数据间的关系，找出递推公式直接输出，这样是不是更符合ACM的精神呢？
ID 2033 时间相加
#include<stdio.h>
#include<string.h>
int main()
{
int n;
int a[100][6];
int i;
int hour, minute, second;
while (scanf("%d", &n) != EOF)
{
for (i = 0; i < n; i++)
{
scanf("%d %d %d %d %d %d", &a[i][0], &a[i][1], &a[i][2], &a[i][3], &a[i][4], &a[i][5]);
}
for (i = 0; i < n; i++)
{
hour = minute = second = 0;
hour = a[i][0] + a[i][3];
if (a[i][1] + a[i][4] > 59)
{
hour = hour + 1;
minute = a[i][1] + a[i][4] - 60;
}
else
{
minute = a[i][1] + a[i][4];
}
if (a[i][2] + a[i][5] > 59)
{
minute = minute + 1;
second = a[i][2] + a[i][5] - 60;
}
else
{
second = a[i][2] + a[i][5];
}
printf("%d %d %d\n", hour, minute, second);
}
}
return 0;
}
so easy!!!
ID 2035 求数后三位
#include<stdio.h>
int main()
{
int m, n;
int temp;
int i;
while (scanf("%d %d", &m, &n), m != 0, n != 0)
{
temp = 1;
for (i = 0; i < n; i++)
{
temp = (temp * m) % 1000;
}
printf("%d\n", temp);
}
return 0;
}
这一题思路很简单，可是如果直接相乘最后得出结果，数据太大，会输出超时。这里需要用到一个数学技巧，就是每次得到的数都对一千除余，只要保留了这个数的后三位就能保证最后得到的数的后三位是正确的。
ID 2039 三角形
#include<stdio.h>
int main()
{
int n;
int i, j;
float a[3];
float max;
int index;
float temp;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
max = 0;
for (j = 0; j < 3; j++)
{
scanf("%f", &a[j]);
if (a[j] > max)
{
max = a[j];
index = j;
}
}
temp = a[0];
a[0] = a[index];
a[index] = temp;
if (a[1] + a[2] > a[0])
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
输入要注意是浮点型才能AC!
ID 2040 亲和数
#include<stdio.h>
#include<math.h>
int main()
{
int n;
long num1, num2;
int i;
long sum1, sum2;
while (scanf("%d", &n) != EOF)
{
while (n--)
{
sum1 = sum2 = 0;
scanf("%d %d", &num1, &num2);
for (i = 2; i <= sqrt(num1); i++)
{
if (num1%i == 0)
{
sum1 = sum1 + i + num1/i;
}
}
sum1++;
for (i = 2; i <= sqrt(num2); i++)
{
if (num2%i == 0)
{
sum2 = sum2 + i + num2 / i;
}
}
sum2++;
if ((sum1 == num2) && (sum2 == num1))
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
}
return 0;
}
ID 2041 超级楼梯
#include<stdio.h>
#include<math.h>
int main()
{
int n,m;
int a[50];
int i;
while (scanf("%d", &n) != EOF)
{
while (n--)
{
a[0] = 1;
a[1] = 1;
scanf("%d", &m);
for (i = 2; i <= 40; i++)
{
a[i] = a[i - 1] + a[i - 2];
}
printf("%d\n", a[m-1]);
}
}
return 0;
}
这题看着没头绪，其实它背后的数学知识是斐波那契数列。知道怎么做了吧，这个数列可是ACM最喜欢考的知识点了。给大家科普一下，知道这个数列为什么这么出名嘛？因为它的递推公式的一个比值是黄金分割点。
ID 2042 过路费
#include<stdio.h>
#include<math.h>
int main()
{
int n,m;
int i;
int initial_value, final_value;
while (scanf("%d", &n) != EOF)
{
while (n--)
{
scanf("%d", &m);
initial_value = 3;
for (i = 0; i < m; i++)
{
final_value = 2 * (initial_value - 1);
initial_value = final_value;
}
printf("%d\n", final_value);
}
}
return 0;
}
水题。
ID 2045 着色问题
#include<stdio.h>
int main()
{
int n;
int i;
__int64 coefficient1, coefficient2;
__int64 count;
__int64 temp;
while (scanf("%d", &n)!=EOF)
{
if (n == 1)
{
printf("3\n");
}
else if (n == 2||n == 3)
{
printf("6\n");
}
else
{
coefficient1 = coefficient2 = 2;
count = 0;
for (i = 4; i <= n; i++)
{
count = (coefficient1 * 2 + coefficient2) * 3;
temp = coefficient1;
coefficient1 = coefficient2;
coefficient2 = 2 * temp + coefficient2;
}
printf("%I64d\n", count);
}
}
return 0;
}
这题需要找到背后的一个数学规律。我实在不知道如何形容，给大家看看我的做题笔记吧。。。也是够蠢的，写了这么多才发现规律。
思路笔记
