1. 竖式填空

CA6EFF0F-51E7-4A9C-97D0-8E270D8AD912.png

[编程|100分] 竖式填空
时间限制：1秒
空间限制：65536K
题目描述
小Q是名小学生，他最喜欢数学中的加法竖式填空了。例如下面的填空题，每个空格表示1…9中的一个数字。

有时候这种竖式题不一定只有唯一解，小Q很想知道，给定一个这样的竖式，总共可能的解有多少个。
被加数和加数的位数不会超过3位。和的位数不会超过4位。空格只可能存在于被加数和加数中。

输入描述:
每个输入数据包含多个测试点。
第一行为测试点的个数T(T<=30)。
每个测试点包含一行，包含了三个长度大于0的字符串，分别表示被加数，加数和结果。每个字符串之间有一个空格。每个字符串只会包含“X”和“1”…“9”，其中“X”表示竖式中的空格。保证竖式至少有一个解。

输出描述:
对于每个测试点，输出一行，表示一共可能的解的个数。

输入例子:
2
X7 9X 123
X X 4

输出例子:
1
3
（样例解释：样例1的解为27+96，样例2的解为1+3,2+2,3+1。）

#include <cstdio>

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>



using namespace std;



int getNum (string &numA, string &numB, string &sum, int pos, int carry)

{

  if (pos == -1)

  {

    if (carry)

      return 0;

    else

      return 1;

  }

  else

  {

    int digitA = numA[pos] - '0', digitB = numB[pos] - '0', digitSum = sum[pos] - '0';

    if (numA[pos] != 'X' && numB[pos] != 'X')

    {

      if ((digitA + digitB + carry) % 10 != digitSum)

        return 0;

      else

      {

        int newCarry = 0;

        if (digitA + digitB + carry >= 10)

          newCarry = 1;



        return getNum (numA, numB, sum, pos - 1, newCarry);

      }

    }

    else if (numA[pos] == 'X' && numB[pos] == 'X')

    {

      int cnt = 0;

      for (int j = 1; j <= 9; ++j)

        for (int k = 1; k <= 9; ++k)

        {

          int tmp = j + k + carry;

          int newCarry = 0;



          if (tmp >= 10)

            newCarry = 1;



          if (tmp % 10 == digitSum)

            cnt += getNum (numA, numB, sum, pos - 1, newCarry);

        }



      return cnt;

    }

    else

    {

      int digit = digitA;

      if (numB[pos] != 'X')

        digit = digitB;



      int cnt = 0;

      for (int i = 1; i <= 9; ++i)

      {

        int tmp = i + digit + carry;

        int newCarry = 0;



        if (tmp >= 10)

          newCarry = 1;



        if (tmp % 10 == digitSum)

          cnt += getNum (numA, numB, sum, pos - 1, newCarry);

      }



      return cnt;

    }

  }

}



int main ()

{

  int testNum;

  scanf ("%d", &testNum);

 

  for (int i = 0; i < testNum; ++i)

  {

    string numA, numB, sum;

    cin >> numA >> numB >> sum;



    while (numA.size () != sum.size ())

      numA.insert (numA.begin (), '0');



    while (numB.size () != sum.size ())

      numB.insert (numB.begin (), '0');



    printf ("%d\n", getNum (numA, numB, sum, (int)sum.size () - 1, 0));

  }



  return 0;

}

2.NTES

79F5A525-9438-4AF4-A98F-763AACF917A7.png

题目描述
NTES是网易在纳斯达克股票市场的代号，在财报公布后，NTES的股价接连大涨，创下了历史新高。 下面，我们用四个5x7的点阵来描述NTES这代号。

....#

.#...#

..#..#

...#.#

....##

#######
...#...
...#...
...#...
...#...

#######

......

#######

......

#######

#######

......

#######
......#
#######
假设我们认为每个点的周围的8个方向的点都和它是相连的，并且相连在一起的符号“#”我们可以认为在同一个联通分量，则上述四个点阵分别都包含了一个“#”的联通分量。

给定N * M的点阵，点阵只包含“.”和“#”两种符号。在点阵中可能包含了很多的联通分量。那么，在这点阵当中，你能找到多少个和标准的“N”,“T”,“E”,“S”一样的联通分量呢？
下面是点阵中NTES对应的联通分量的一些限制：
❖ N、T、E、S可能被顺时针旋转90度、180度或270度。例如以下的7x11的点阵中，包含了两个完整的T（两个联通分量），一个与前文提到的T方向一致，另一个是顺时针旋转了270度。

...#######

......#...

......#...

..#...

......#...

..........

..........

❖ 对于任何一个完整的N、T、E、S对应的联通分量，必须和前面给出的标准的模板一致。即除了旋转外，不多出或者缺少任何一个“#”，否则认为不匹配。例如下图中虽然只包含了一个联通分量（根据八方向相连的定义，（1,7）和（0,6）上的“#”相连），但是其多了一个“#”在位置（1,7），因此，以下点阵中没有任何一个NTES对应的联通分量。
#######.
...#...#
...#....
...#....
...#....

输入描述:
每个输入数据包含一个测试点。
第一行为点阵的大小N，M。其中1<=N<=500，1<=M<=500。
接下来N行，每行包含了M个“.”或“#”的字符，描述了给定的点阵。

输出描述:
输出包括四行，按顺序输出点阵中包含的NTES的数量。

输入例子:
输入样例1:
7 11

...#######

......#...

......#...

..#...

......#...

..........

..........

输入样例2:
12 23
#######....#....#######
...#...##....#..#......

..#...#.#...#..#######

..#...#..#..#........#

...#..#...#.#..#######

....#....##.........

.........#.............
#######....#.##.##....#
......#....#....#.#...#
#######....#....#..#..#
......#....#....#...#.#
#######.#######.#....##

输出例子:
输出样例1:
N: 0
T: 2
E: 0
S: 0

输出样例2:
N: 1
T: 1
E: 1
S: 1

// todo

3.装备强化

91522564-A74C-43F5-B6A4-8B9EE2B3832A.png

题目描述
网游中，装备强化是提升角色战力的常见方法。 现在你参与开发的游戏中也有这项功能，团队正在设计每件装备强化所能提升的战力及需要消耗的金币数。为了设计出一个合理的强化系统，决定先做一些强化模拟测试，而你现在就在是该模拟程序的开发者。 假设现在有n件可以同时穿戴的装备，对于第i件装备，最多可以强化mi 次，对于第i件装备的第j次强化，会增加fij 的战力，并需要消耗gij 个金币。现在给出所有装备的数据，以及初始拥有的金币数量，求最多可以增加多少战力。
输入描述:
输入文件的第一行为一个正整数T，表示测试数据组数。
接下来有T组数据。每组数据第1行为两个整数n和s，分别表示装备数量及初始拥有的金币数量。接下来是n行，每行表示一个装备，其中每行第一项为一个字符串，表示装备的名称，第二项为非负整数mi，表示装备最多可强化的次数，接下来为2*mi个非负整数，表示每次强化会增加的战力及消耗的金币数。

数据范围：
对于所有数据文件，1<=T<=10。装备的名称最大长度不超过32个字符，由大小写字母或数字组成。每件装备最多强化次数mi满足0<=mi<=3。所有战力数值和金币数为非负整数且不超过10,000,000。
对于其中的20%数据，满足装备数1<=n<=5；
另外有30%数据，满足装备数1<=n<=10；
另外有30%数据，满足装备数1<=n<=16；
最后剩下的20%数据，满足装备数1<=n<=20。

数据保证只有唯一的强化方案能达到最大战力。

输出描述:
对于每个测试数据，第一行为一个整数，表示最多可提升的战力。接下来是n行，表示达到这个战力时每件装备分别的强化次数，形式为“装备名称+强化次数”。输出装备的顺序要与输入数据一致。更详细的格式请参照输出样例。

输入例子:
3
4 100
Helm 1 20 30
Gloves 1 30 40
Boots 1 10 10
Sword 1 50 50
5 10
Item1 0
Item2 1 10000 100
Item3 1 10 10
Item4 3 1 0 2 1 3 2
Item5 3 0 4 1 1 5 1
6 256
1x 2 12 43 35 58
2x 2 34 54 88 31
3x 2 43 10 15 55
4x 2 32 54 19 19
5x 2 84 1 15 45
6x 2 19 40 99 12

输出例子:
90
Helm+0
Gloves+1
Boots+1
Sword+1
12
Item1+0
Item2+0
Item3+0
Item4+3
Item5+3
418
1x+0
2x+2
3x+1
4x+2
5x+1
6x+2

// todo