HDOJ 2504 又见GCD

题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2504

看了一下午的线段树,迷糊了,弄个水题来放松下。
思路:
a=b*k1
c=b*k2
又知道a,b,求c
a/b=k1,
c/b=k2;
k1,k2互质,所以只要找到最小的k2,使k2与k1互质就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cstring>
#include <ctype.h>
#include <stdlib.h>
#include <string>
using namespace std;
 
__int64 gcd(__int64 a, __int64 b)
{
    if(a<b)
    {
        a ^= b;
        b ^= a;
        a ^= b;
    }
    if(b == 0)
        return a;
    return gcd(b, a%b);
}
 
__int64 a, b, c;
int nCases;
int main()
{
    scanf("%d", &nCases);
    while(nCases--)
    {
        scanf("%I64d %I64d", &a, &b);
        __int64 k=a/b;
        for(int i=2; ; ++i)
            if(gcd(k, i) == 1)
            {
                printf("%I64d\n", i*b);
                break;
            }
    }
    return 0;
}

HDOJ 2042 不容易系列之二

题目地址:

http://acm.hdu.edu.cn/showproblem.php?pid=2042

标准的递推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 // Author: Tanky Woo
// HDOJ 2042
 
#include <iostream>
using namespace std;
int f[35];
int main()
{
    f[0] = 3;
    for(int i=1; i<31; ++i)
    {
        f[i] = (f[i-1]-1)*2;
    }
    int nCases, num;
    scanf("%d", &nCases);
    while(nCases--)
    {
        scanf("%d", &num);
        printf("%d\n", f[num]);
    }
    return 0;
}

当然,这里还有其他办法,这是MiYu的:

1
2
3
4
5
6
7
8
9
10
11
12
13
 #include <stdio.h>
int main ()
{
    int T;          
    int N;
    scanf ( "%d",&T );
    while ( T -- )
    {
          scanf ( "%d",&N );
          printf ( "%d\n" ,(1 << N )+ 2 );
    }
    return 0; 
}

HDOJ 1058 Humble Numbers

题目地址:

http://acm.hdu.edu.cn/showproblem.php?pid=1058

表示这题不太好理解,但是理解了就好了。

不好说,这题还是分析代码好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 // Author: Tanky Woo
// HDOJ 1058
#include <iostream>
using namespace std;
 
__int64 humble[6000];
int _min(int a, int b, int c, int d)
{
    int m;
    if(a < b)
        m = a;
    else
        m = b;
    if(m > c)
        m = c;
    if(m > d)
        m = d;
    return m;
}
 
int main()
{
    int e1=1, e2=1, e3=1, e4=1;
    __int64 a1, a2, a3, a4;
    humble[1] = 1;
    for(int i=2; i<6000; ++i)
    {
        a1 = 2*humble[e1];
        a2 = 3*humble[e2];
        a3 = 5*humble[e3];
        a4 = 7*humble[e4];
        humble[i] =  _min(a1, a2, a3, a4);
        if(humble[i] == a1)
            e1++;
        if(humble[i] == a2)
            e2++;
        if(humble[i] == a3)
            e3++;
        if(humble[i] == a4)
            e4++;
    }
 
    int n;
    while(scanf("%d", &n) && n)
    {
        if(n%100==11 || n%100==12 || n%100==13)
            printf("The %dth humble number is %d.\n", n, humble[n]);
        else if(n % 10 == 1)
            printf("The %dst humble number is %d.\n", n, humble[n]);
        else if(n % 10 == 2)
            printf("The %dnd humble number is %d.\n", n, humble[n]);
        else if(n % 10 == 3)
            printf("The %drd humble number is %d.\n", n, humble[n]);
        else
            printf("The %dth humble number is %d.\n", n, humble[n]);
    }
    return 0;
}

HDOJ 1159 Common Subsequence

题目地址:

http://acm.hdu.edu.cn/showproblem.php?pid=1159

这题不好说啊~~~~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 #include <iostream>
using namespace std;
char a[1003], b[1003];
int table[1003][1003];
int _max(int a, int b)
{
    return a>b? a:b;
}
int main()
{
    while(scanf("%s %s", a, b) != EOF)
    {
        int len1 = strlen(a);
        int len2 = strlen(b);
        int flag = 0;
        for(int i=0; i<len1; ++i)    //把第0行初始化
        {
            if(b[0] == a[i])
                flag = 1;
            if(flag == 0)
                table[0][i] = 0;
            else
                table[0][i] = 1;
        }
        flag = 0;
        for(int i=0; i<len2; ++i)   //把第0列初始化
        {
            if(a[0] == b[i])
                flag = 1;
            if(flag == 0)
                table[i][0] = 0;
            else
                table[i][0] = 1;
        }
        for(int i=1; i<len2; ++i)
            for(int j=1; j<len1; ++j)
                if(b[i] == a[j])
                    table[i][j] = table[i-1][j-1]+1;
                else
                    table[i][j] = _max(table[i-1][j], table[i][j-1]);
        /*
        for(int i=0; i<len1; ++i)
        {
            for(int j=0; j<len2; ++j)
                printf("%d ", table[i][j]);
            printf("\n");
        }
        */
        printf("%d\n", table[len2-1][len1-1]);
    }
    return 0;
}

HDOJ 1081 To The Max

题目地址:

http://acm.hdu.edu.cn/showproblem.php?pid=1081

汗,这题求最长子序列我居然忘了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int LS(int *line)     // 正确
{
	int i;
	int temp = line[0], sum = line[0];
	for(i = 1; i<nNum; ++i)
	{
		if(temp > 0)
			temp += line[i];
		else
			temp = line[i];
		if(temp > sum)
			sum = temp;
	}
	return sum;
}

我居然记成了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 int LS(int *line)   // 错误!
{
	int i;
	int temp = line[0], sum = line[0];
	for(i = 1; i<nNum; ++i)
	{
		if(sum > 0)
			temp += line[i];
		else
			temp = line[i];
		if(temp > sum)
			sum = temp;
	}
	return sum;
}

上面这个错误的随便给组数据就行了,如:
1 -2 3
按错误的是输出2~~~
结果一直WA。
而之前做过2题居然都忘了~~~~
HDOJ 1003 Max Sum
HDOJ 1231 最大连续子序列
大家可以一起做了。
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 // Author: Tanky Woo
// HDOJ 1081
// Accepted 1081 15MS 224K 891B C++ Tanky Woo 
#include <iostream>
using namespace std;
 
int aMatrix[103][103];
int aLine[103];
#define INF -100000
int nNum;
 
int LS(int *line);
int main()
{
    //freopen("input.txt", "r", stdin);
    while(scanf("%d", &nNum) != EOF)
    {
        memset(aMatrix, 0, sizeof(aMatrix));
        int maxSum = INF;
        for(int i=0; i<nNum; ++i)
            for(int j=0; j<nNum; ++j)
                scanf("%d", &aMatrix[i][j]);
        for(int i=0; i<nNum; ++i)
        {
            memset(aLine, 0, sizeof(aLine));
            for(int j=i; j<nNum; ++j)
            {
                for(int k=0; k<nNum; ++k)
                    aLine[k] += aMatrix[j][k];
                int sum = LS(aLine);
                if(sum > maxSum)
                    maxSum = sum;
            }
        }
        printf("%d\n", maxSum);
    }
    return 0;
}
 
int LS(int *line)
{
    int i;
    int temp = line[0], sum = line[0];
    for(i = 1; i<nNum; ++i)
    {
        if(temp > 0)
            temp += line[i];
        else
            temp = line[i];
        if(temp > sum)
            sum = temp;
    }
    return sum;
}