那些严重拖慢做题进度的题以及遇到的坑

那些严重拖慢做题进度的题以及遇到的坑

杭电204X

进制转换

这一题的关键是用字符数组来捕捉每一位的数,因为存在十进制以上的数,还要捕捉特定的那些字母,对于其他的就可以用数字和字符的关系来进行转换。

还有一个细节就是负号,取余的时候用正数会比较方便,因此最后不要忘记负号。

关键代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
switch (n % r)
{
case 10:
a[i] = 'A';
break;
case 11:
a[i] = 'B';
break;
case 12:
a[i] = 'C';
break;
case 13:
a[i] = 'D';
break;
case 14:
a[i] = 'E';
break;
case 15:
a[i] = 'F';
break;
default:
a[i] = '0' + n % r;
}

遇到的坑:

  • 一开始没有加default,为了图方便最后一个case没加break,后来加了default之后没意识到…狠狠坑了我一把
  • 做题的时候思路要清晰,需要对余数大于小于10进行分类讨论,一个default就直接包含其中一种情况了
  • 当感觉难以下手的时候不妨在纸上写下自己的思路!!!

一张桌子吃饭的并查集问题

并查集这个其实不是很难,只要把模板套上去就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int fa[maxn];  // fa是father的简写

void init(int n)
{
for (int i = 0; i < n; ++i)
{
fa[i] = i;
}
}

int find(int n)
{
if (fa[n] == n)
return n;
return fa[n] = find(fa[n]); // 赋值语句的前半句可以减少递归次数从而提高程序的效率
}

void connect(int x, int y)
{
x = fa[x];
y = fa[y];
if (x != y)
fa[x] = y; // 连接的是头头
}

遇到的坑:

  • 要注意的是实际问题的编号很可能不是从0开始的,所以init函数循环可能要改一下才符合实际情况,今天就是这个地方一直WA

输出杨辉三角

这一题其实并不难,我是用杨辉三角的每个数的公式做的,也就是用到了排列组合的性质,然而排列组合的公式挖了个大坑

组合数公式:Cn,m = An,m / m!

1
2
3
4
5
6
7
if (n - m < m)
m = n - m;
for (int i = 0; i < m; ++i)
rst *= (m - i);
for (int j = 2; j <= m; ++j)
rst /= m;
retrurn rst;

遇到的坑:

  • 主要是忘记公式了,再加上思维很混乱于是就一直都有问题

求集合中的A-B

其实挺简单的,多来几个循环进行判断就可以了

遇到的坑:

  • 初始化的两个输入值中可以有一个为零的,所以在输入的判断中就不能直接while (scanf("%d %d", &n, &m) != EOF && m && n)了,而是要在while中进行break:if (n == 0 && m == 0) break;

最后

今天做题的效率十分低下,就是因为出现了这些大大小小的问题,希望以后做题的时候思路可以更清晰一点,不要再在这些坑爹的问题上耽误时间了,吃一堑长一智!