发表于

2551 竹青遍野

Problem Description

“临流揽镜曳双魂 落红逐青裙 依稀往梦幻如真 泪湿千里云”
在MCA山上,除了住着众多武林豪侠之外,还生活着一个低调的世外高人,他本名逐青裙,因为经常被人叫做”竹蜻蜓”,终改名逐青,常年隐居于山中,不再见外人.根据山上附近居民所流传的说法,逐青有一个很奇怪的癖好,从他住进来那天开始,他就开始在他的院子周围种竹子,第1个月种1根竹子,第2个月种8根竹子,第3个月种27根竹子…第N个月就种(N^3)根竹子.他说当他种下第X根竹子那一刻,就是他重出江湖之时!告诉你X的值,你能算出逐青的复出会是在第几个月吗?

Input

首先输入一个t,表示有t组数据，跟着t行.每行是一个整数X,X < 1000000000

Output

输出一个整数n,表示在第n个月复出

Sample Input

3
1
2
10

Sample Output

1
2
3

Solution:

当某个月种的竹子数+已经种的竹子数 >= 付出需要的竹子数时, 打印当前这个月月份.
我怕直接用i,3溢出, 就先开了个立方根, pow(n, 1.0/3); pow的两个参数都需要是double类型.

我自己要注意double判断小于等于的情况, 包含判等的情况, 需要考虑误差, 独立写了一个double判断相等函数.

#include <cstdio>
#include <cmath>
using namespace std;

int db_equal(double db1, double db2) {
   return -0.0005 < (db1 - db2) && (db1 - db2) < 0.0005;
}

int main() {
  int t; scanf("%d", &t);
  while (t--) {
    int x, sum = 0; scanf("%d", &x);
    for (int i = 1; ; i++) {
      double db1 = i,
        db2 = pow((double)(x-sum), 1.0/3);
      if (db1 > db2 || (db_equal(db1, db2))) {
        printf("%d\n", i);
        break;
      }
      sum += pow((double)i, 3);
    }
  }
  return 0;
}

发表于

2550 百步穿杨

Problem Description

时维九月,序属三秋,辽军大举进攻MCA山,战场上两军正交锋.辽军统帅是名噪一时的耶律-James,而MCA方则是派出了传统武将中草药123.双方经过协商,约定在十一月八日正午十分进行射箭对攻战.中草药123早早就开始准备,但是他是武将而不是铁匠,造弓箭的活就交给聪明能干的你了,现在告诉你每种弓箭规格,即箭身的长度,以及每种规格弓箭所需要的数目,要求你把需要的弓箭都输出.
弓箭的基本样子为 “>+—+>”,其中”+—+”为箭身,数据保证箭身长度 > 2

Input

首先输入一个t,表示有t组数据，跟着t行：
每行一个N (N < 50 ),接下去有N行,第i行两个整数Ai , Bi,分别代表需要箭身长度为Ai的弓箭Bi枝. (Ai < 30 , Bi < 10 )
输入数据保证每一个Ai都是不同的.

Output

按照箭身的长度从小到大的顺序依次输出所有需要的弓箭,”每一种”弓箭后输出一个空行.

Sample Input

1
4
3 4
4 5
5 6
6 7

Sample Output

>+-+>
>+-+>
>+-+>
>+-+>

>+--+>
>+--+>
>+--+>
>+--+>
>+--+>

>+---+>
>+---+>
>+---+>
>+---+>
>+---+>
>+---+>

>+----+>
>+----+>
>+----+>
>+----+>
>+----+>
>+----+>
>+----+>

Solution:

字符串的s.insert(int pos, string substr);因此在insert前, 先用循环构造好需要插入的子串.

坑点:

  • 需要对每个case的箭按照长度从小到大排序, 刚开始题目没有读清楚.
  • 打印根本不需要特别注意格式, 是我想多了。
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct Node {
  int a, b;
};

bool cmp(Node n1, Node n2) {
  return n1.a < n2.a;
}

int main() {
  int T, flag = 0; cin >> T;
  while (T--) {
    vector<Node> v;
    int N; cin >> N;
    for (int i = 0; i < N; i++) {
      Node node;
      int a, b; cin >> node.a >> node.b;
      v.push_back(node);
    }

    sort(v.begin(), v.end(), cmp);

    for (int i = 0; i < N; i++) {
      string s = ">++>", add = "";
      for (int j = 0; j < v[i].a-2; j++) {
        add += '-';
      }
      s.insert(2, add);
      for (int j = 0; j < v[i].b; j++) {
        cout << s << endl;
      }
      cout << endl;
    }
  }
  return 0;
}

发表于

2549 壮志难酬

Problem Description

问题是这样的：给你一个小数x，让你算出小数点后第n位是什么，(1 <= n <= 6)

Input

首先输入一个t,表示有t组数据，跟着t行：
每行输入一个小数（输入数据保证一定是a.b的形式,为了简单化问题，没有循环小数的情况）
然后跟一个n,表示小数点后第几位

Output

输出一个数表示小数点后第n位的数

Sample Input

3
1.234 1
2.345 2
3.456 3

Sample Output

2
4
6

Solution:

坑点:
n的范围在[1,6]闭区间内, 如果小数点不满6位的话, 应该输出0

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

int main() {
  int T, d; string s;
  cin >> T;
  while (T--) {
    cin >> s >> d;
    int pos = s.find('.');
    // int len = s.length();    // 不要通过长度来判断小数后是否有6位
    // if (len < 8) {           // 比较麻烦
    //   for (int i = 0; i < 8 - len; i++) {
    //     s += '0';
    //   }
    // }
    s += "000000";              // 直接添6位就好
    
    printf("%c\n", s[pos+d]);
  }
  return 0;
}

发表于

2548 两军交锋

Problem Description

话说辽军与MCA相峙多年,终于在一个秋日的早晨爆发了一次大规模的冲突.情况是这样子的,当天上午,由耶律-Pacision领军的辽军忽然带领数万人马浩浩荡荡向MCA山杀来,而这时候驻扎在MCA防守前线的是久经沙场的老将纪哥.纪哥得知这个消息,立刻召集手下精英,前往阻击辽军.现已知辽军前进速度 U 米/秒 ,纪哥 速度 V 米 /秒 ,两军一开始相距L米,战地记者从两军刚开始进军就立刻开始以 W 米/秒的速度马不停蹄地往返于两军之间作第一时间的报道,即一到达一方,立刻返回前往另一方.问,当两军交锋之时,战地记者总共走的路程.

Input

首先输入一个t,表示有t组数据，跟着t行：
每行有四个实数 u ,v , w , l 分别表示辽军速度,纪哥速度,记者速度,以及起始的距离.

Output

输出一行实数表示总的路程.精确到小数点后3位.

Sample Input

1
10 20 30 100

Sample Output

100.000

Solution:

根据公式化简得到

(u+v) * t = L;
w * t = x

#include <cstdio>

int main() {
  int T; scanf("%d", &T);
  double u, v, w, l;
  while (T--) {
    scanf("%lf %lf %lf %lf", &u, &v, &w, &l);
    printf("%.3lf\n", w*(l/(u+v)));
  }
  return 0;
}

发表于

1062 最简分数(20)

一个分数一般写成两个整数相除的形式：N/M，其中 M 不为0。最简分数是指分子和分母没有公约数的分数表示形式。

现给定两个不相等的正分数 N1/M1和 N2/M2，要求你按从小到大的顺序列出它们之间分母为 K 的最简分数。

输入格式：

输入在一行中按 N/M 的格式给出两个正分数，随后是一个正整数分母 K，其间以空格分隔。题目保证给出的所有整数都不超过 1000。

输出格式：

在一行中按 N/M 的格式列出两个给定分数之间分母为 K 的所有最简分数，按从小到大的顺序，其间以 1 个空格分隔。行首尾不得有多余空格。题目保证至少有 1 个输出。

输入样例：

7/18 13/20 12

输出样例：

5/12 7/12

Solution:

先实现分数的四则运算, 在运算中不处理分母为0时, 表示成Inf的情况。
单独写一个show()函数用于打印, 进入show()之前分数已经被化简.
1, 先处理分母为0的情况, 再处理分子为0的情况,
2, 符号单独处理, 分子小于0, 打印”(-“这样分数部分可只运算整数
3, 特别要主要的是分子表示既有整数又有分数的情况。

main函数中, 约分后调用打印函数即可.

坑点:

  • 如果int不声明成long long 的话, case34凉, 估计是相加会溢出的原因把。

写四则运算一定要仔细..

实际代码:

#include <cstdio>
struct Fraction {
  long long up, down;
};

long long gcd(long long a, long long b) {
  return !b ? a : gcd(b, a % b);
}

void reduction(Fraction &f) {
  if (!f.down) return;  // Inf
  // if (!f.up) f.down = 1; return;  // 0      // debug01
  if (!f.up) {
    f.down = 1; return;
  }
  if (f.down < 0) {   // down<0
    f.up *= -1;
    f.down *= -1;
  }
  long long up_t = f.up, g = 0;
  if (f.up < 0) up_t = -1 * f.up;
  g = gcd(up_t, f.down);
  if (g > 1) {
    f.up /= g;
    f.down /= g;
  }
  // g == 1 ok
}

Fraction add(Fraction a, Fraction b) {
  Fraction f;
  f.up = a.up * b.down + b.up * a.down;
  f.down = a.down * b.down;
  reduction(f);
  return f;
}

Fraction minus(Fraction a, Fraction b) {
  Fraction f;
  f.up = a.up * b.down - b.up * a.down;
  f.down = a.down * b.down;
  reduction(f);
  return f;
}

Fraction multi(Fraction a, Fraction b) {
  Fraction f;
  f.up = a.up * b.up;
  f.down = a.down * b.down;
  reduction(f);
  return f;
}

Fraction divide(Fraction a, Fraction b) {
  Fraction f;
  f.up = a.up * b.down;
  f.down = a.down * b.up;
  reduction(f);
  return f;
}


long long rabs(long long n) {
  return n < 0 ? -n : n;
}

void show(Fraction f) {
  if (!f.down) {
    printf("Inf"); return;
  }
  if (!f.up) {
    printf("0"); return;
  }

  if (f.up < 0) printf("(-");   // (-

  if (f.down == 1) {  // ok->int
    printf("%lld", rabs(f.up));
    if (f.up < 0) printf(")");   // )
    return;
  }

  if (rabs(f.up) < f.down) {     // no int, attetion
    printf("%lld/%lld", rabs(f.up), f.down);
  } else {
    long long a = rabs(f.up) / f.down;
    long long b = rabs(f.up) - a*f.down;
    printf("%lld %lld/%lld", a, b, f.down);
  }
  if (f.up < 0) printf(")");     // )
}

int main() {
  Fraction a, b;
  scanf("%lld/%lld %lld/%lld", &a.up, &a.down, &b.up, &b.down);
  reduction(a); reduction(b);
  show(a); printf(" + "); show(b); printf(" = "); show(add(a, b)); printf("\n");
  show(a); printf(" - "); show(b); printf(" = "); show(minus(a, b)); printf("\n");
  show(a); printf(" * "); show(b); printf(" = "); show(multi(a, b)); printf("\n");
  show(a); printf(" / "); show(b); printf(" = "); show(divide(a, b)); printf("\n");
  return 0;
}

发表于

2097 Sky数

Problem Description

Sky从小喜欢奇特的东西，而且天生对数字特别敏感，一次偶然的机会，他发现了一个有趣的四位数2992，这个数，它的十进制数表示，其四位数字之和为2+9+9+2=22，它的十六进制数BB0，其四位数字之和也为22，同时它的十二进制数表示1894，其四位数字之和也为22，啊哈，真是巧啊。Sky非常喜欢这种四位数，由于他的发现，所以这里我们命名其为Sky数。但是要判断这样的数还是有点麻烦啊，那么现在请你帮忙来判断任何一个十进制的四位数，是不是Sky数吧。

Input

输入含有一些四位正整数，如果为0，则输入结束。

Output

若n为Sky数，则输出“#n is a Sky Number.”，否则输出“#n is not a Sky Number.”。每个结果占一行。注意：#n表示所读入的n值。

Sample Input

2992
1234
0

Sample Output

2992 is a Sky Number.
1234 is not a Sky Number.

Solution:

16进制中B在转换中, 被当作11来计算.
可以只用sum一个临时变量来做进制的转换.

坑点:

  • 这个相同的数不一定是22, 只要是三种结果一致都满足

实际代码:

#include <cstdio>
using namespace std;

int main() {
  int n = 0;
  while (scanf("%d", &n) && n) {
    int sum = n, a = 0, b = 0, c = 0;
    while (sum) {
      a += sum % 10;
      sum /= 10;
    }
    sum = n;
    while (sum) {
      b += sum % 16;
      sum /= 16;
    }
    sum = n;
    while (sum) {
      c += sum % 12;
      sum /= 12;
    }
    (a == b && b == c) ? printf("%d is a Sky Number.\n", n) :
        printf("%d is not a Sky Number.\n", n);
  }
  return 0;
}

发表于

2096 小明A+B

Problem Description

小明今年3岁了, 现在他已经能够认识100以内的非负整数, 并且能够进行100以内的非负整数的加法计算.
对于大于等于100的整数, 小明仅保留该数的最后两位进行计算, 如果计算结果大于等于100, 那么小明也仅保留计算结果的最后两位.

例如, 对于小明来说:
1) 1234和34是相等的
2) 35+80=15

给定非负整数A和B, 你的任务是代表小明计算出A+B的值.

Input

输入数据的第一行为一个正整数T, 表示测试数据的组数. 然后是T组测试数据. 每组测试数据包含两个非负整数A和B(A和B均在int型可表示的范围内).

Output

对于每组测试数据, 输出小明A+B的结果.

Sample Input

2
35 80
15 1152

Sample Output

15
67

Solution:

首先想到的思路是, 将a+b之后的值, 用求余的方法得到最后两位, 并且计算出值.

#include <cstdio>

int main() {
  int T; scanf("%d", &T);
  while (T--) {
    int a, b; scanf("%d %d", &a, &b);
    int sum, ans = 0;
    sum = a + b;
    if (sum >= 100) {
      ans += sum % 10;
      ans += (sum/10%10) * 10;
    } else {
      ans = sum;
    }
    printf("%02d\n", ans);   // 改了也没ac
  }
  return 0;
}

// WA

题目中说最后a, b都在int范围内, 但a+b没说, 刚开始觉得应该不会考这个吧, 但现在没其他选择.
修改思路, 只相加最后两位, 需要自己实现整数相加的过程, 有点像大整数.

坑点:

  • 一个是上述说的整数溢出.
  • 如果是个位数的话, 前面不需要加0

代码:

// 推测溢出, 只加后两位
#include <cstdio>
#include <cstring>

int arr_a[1005], arr_b[1005], len_a, len_b;

int K = 2;

int main() {
  int T; scanf("%d", &T);
  while (T--) {
    int a, b; scanf("%d %d", &a, &b);
    memset(arr_a, 0, sizeof(arr_a));
    memset(arr_b, 0, sizeof(arr_b));
    len_a = 0, len_b = 0;

    while (a && len_a < K) {
      arr_a[len_a++] = a % 10;
      a /= 10;
    }

    while (b && len_b < K) {
      arr_b[len_b++] = b % 10;
      b /= 10;
    }

    int ans = 0, carry = 0, temp = 0, s = 1;
    for (int i = 0; i < K; i++) {
      temp = arr_a[i] + arr_b[i] + carry;
      ans += (temp % 10) * s;
      s *= 10;
      carry = temp/10;
    }
    printf("%d\n", ans);
  }
  return 0;
}

发表于

2099 整除的尾数

Problem Description

一个整数，只知道前几位，不知道末二位，被另一个整数除尽了，那么该数的末二位该是什么呢？

Input

输入数据有若干组，每组数据包含二个整数a，b（0<a<10000, 10<b<100），若遇到0 0则处理结束。

Output

对应每组数据，将满足条件的所有尾数在一行内输出，格式见样本输出。同组数据的输出，其每个尾数之间空一格，行末没有空格。

Sample Input

200 40
1992 95
0 0

Sample Output

00 40 80
15

Source

2007省赛集训队练习赛（2）

Recommend

lcy | We have carefully selected several similar problems for you: 2098 2096 2091 2081 2017

Solution:

找到0~99之间的第一个满足的条件的末尾两个数, 然后用一个等差数列寻找其他符合条件的值, 不用遍历100个数.

坑点:

  • debug01把区间扩大成了[0, 100], 这样子的话, 造成100成为尾数, 不可能的。

代码:

#include <cstdio>

int main() {
  int a, b, cnt = 0;
  while (scanf("%d %d", &a, &b) != EOF && a && b) {
    int sum = a * 100;
    int i = 0, find = 0;
    for ( ; i < 100; i++) {
      if ((sum + i) % b == 0) {
        find = 1;
        break;
      }
    }
    if (!find) {
      printf("\n");
    } else {   // find
      int start = i, k = (99-start) / b;   // debug01:
      printf("%02d", start);
      for (int i  = 0; i < k; i++) {
        printf(" %02d", start + (i+1) * b);
      }
      printf("\n");
    }
  }
  return 0;
}

发表于

2095 find your present(2)

Problem Description

In the new year party, everybody will get a “special present”.Now it’s your turn to get your special present, a lot of presents now putting on the desk, and only one of them will be yours.Each present has a card number on it, and your present’s card number will be the one that different from all the others, and you can assume that only one number appear odd times.For example, there are 5 present, and their card numbers are 1, 2, 3, 2, 1.so your present will be the one with the card number of 3, because 3 is the number that different from all the others.

Input

The input file will consist of several cases.
Each case will be presented by an integer n (1<=n<1000000, and n is odd) at first. Following that, n positive integers will be given in a line, all integers will smaller than 2^31. These numbers indicate the card numbers of the presents.n = 0 ends the input.

Output

For each case, output an integer in a line, which is the card number of your present.

Sample Input

5
1 1 3 2 2
3
1 2 1
0

Sample Output

3
2

Hint:

use scanf to avoid Time Limit Exceeded

Author

8600

Source

HDU 2007-Spring Programming Contest - Warm Up （1）

Recommend

8600 | We have carefully selected several similar problems for you: 2097 2099 2096 2094 1008

Solution:

在所有奇数中, 找出不同的那个数, 用^异或运算累计, 初始值为0, 全相等为0; 若有唯一一个不等, ans就是那个值。

#include <cstdio>
int main() {
  int n = 0;
  while (scanf("%d", &n) != EOF && n) {
    int ans = 0, temp = 0;
    while (n--) {
      scanf("%d", &temp);
      ans ^= temp;
    }
    printf("%d\n", ans);
  }
  return 0;
}

发表于

1065 A+B and C (64bit)(20)

Given three integers A, B and C in [−2^63,2^63], you are supposed to tell whether A+B>C.

Input Specification:

The first line of the input gives the positive number of test cases, T (≤10). Then T test cases follow, each consists of a single line containing three integers A, B and C, separated by single spaces.

Output Specification:

For each test case, output in one line Case #X: true if A+B>C, or Case #X: false otherwise, where X is the case number (starting from 1).

Sample Input:

3
1 2 3
2 3 4
9223372036854775807 -9223372036854775808 0

Sample Output:

Case #1: false
Case #2: true
Case #3: false

Solution:

case2 wrong error, 手误.

实现大整数的加减, 符号另外算。

要解释一下的是符号,
对于A+B, 如果AB是同号的, 大整数相加后, 符号记成A或B的符号; 如果AB异号, 比较AB大小, 计算结果是 较大数-较小数(sub), 符号是较大数的符号.
比较A+B结果和C, 若rst和C异号, 符号为负的一定小; 若rst和C同号, 负号的话谁大整数小, 谁实际更大, 正号大整数大的结果更大.

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

struct Bign {
  int d[1005];
  int len;
  Bign() {
    memset(d, 0, sizeof(d));
    len = 0;
  }
};

Bign change(string s) {
  Bign a;
  a.len = s.length();
  for (int i = 0; i < a.len; i++) {
    a.d[i] = s[a.len-1-i] - '0';
  }
  return a;
}

Bign add(Bign a, Bign b) {
  Bign ans;
  int carry = 0;
  // for (int i = 0; i < a.len || i < a.len; i++) {
  for (int i = 0; i < a.len || i < b.len; i++) {      // case2, debug:01
    int temp = a.d[i] + b.d[i] + carry;
    ans.d[ans.len++] = temp % 10;
    carry = temp / 10;
  }
  if (carry) {
    ans.d[ans.len++] = carry;
  }
  return ans;
}

Bign sub(Bign a, Bign b) {
  Bign ans;

  for (int i = 0; i < a.len || i < b.len; i++) {
    if (a.d[i] < b.d[i]) {
      a.d[i+1]--;
      a.d[i] += 10;
    }
    ans.d[ans.len++] = a.d[i] - b.d[i];
  }
  while (ans.len - 1 >= 1 && ans.d[ans.len-1] == 0) {
    ans.len--;
  }
  return ans;
}

int compare(Bign a, Bign b) {
  if (a.len < b.len) return -1;
  else if (a.len > b.len) return 1;
  else {
    for (int i = 0; i < a.len; i++) {
      if (a.d[i] < b.d[i]) {
        return -1;
      } else if (a.d[i] > b.d[i]) {
        return 1;
      }
    }
    return 0;
  }
}

int main() {
  int T; cin >> T;
  for (int i = 0 ; i < T; i++) {
    // ..
    string a, b, c; cin >> a >> b >> c;
    int flag_a = 1, flag_b = 1, flag_c = 1, flag_add = 1;
    if (a[0] == '-') {
      flag_a = -1;
      a = a.substr(1, b.length()-1);
    }  // else flag_a = 1;
    if (b[0] == '-') {
      flag_b = -1;
      b = b.substr(1, b.length()-1);
    }
    if (c[0] == '-') {
      flag_c = -1;
      c = c.substr(1, c.length()-1);
    }
    Bign ba = change(a), bb = change(b), bc = change(c), rst_add;
    if (flag_a * flag_b == 1) {
      flag_add = flag_a;
      rst_add = add(ba, bb);
    } else {   // diff flag, compare
      int cmp_ab = compare(ba, bb);
      if (cmp_ab > 0) {
        flag_add = flag_a;
        rst_add = sub(ba, bb);
      } else if (cmp_ab < 0) {
        flag_add = flag_b;
        rst_add = sub(bb, ba);
      } else {  // -5 + 5 = 0
        flag_add = 1;
        rst_add = sub(ba, bb);
      }
    }
    string ans = "";
    if (flag_add < 0 && flag_c > 0) {
      ans = "false";
    } else if (flag_add > 0 && flag_c < 0) {
      ans = "true";
    } else if (flag_add < 0 && flag_c < 0) {
      ans = compare(rst_add, bc) < 0 ? "true" : "false";
    } else if (flag_add > 0 && flag_c > 0) {
      ans = compare(rst_add, bc) > 0 ? "true" : "false";
    }
    cout << "Case #" << i+1 << ": " << ans << endl;
  }
  return 0;
}