前言：
今天下午14：00小组举行了第一次磨合赛，总体配合的感觉还可以，相信还有很多问题没暴露出来，还有不到两个月，把握好每次练习的机会，争取这方面不会有太大失分点。
感谢：
在此特意感谢熬夜为我们准备题目的超哥，还有两位带我飞的队友。然后，先定个小目标——坐上山师4队的位置。
推荐题目：A、E
A - A
HDU - 1131
卡特兰数的应用。
在不考虑顺序的前提下，将节点编号为0~n-1，任取一个节点k作为根节点，从而衍生出两个子问题$f(k-1)$和$f(n-k)$，有$f(k-1) \times f(n-k)$棵树，
则$f(n) = f(0) \times f(n-1) + f(1) \times f(n-2) + \ldots + f(n-1) \times f(0)$,符合卡特兰数的递推公式。
由该递推公式可以推出$f(n) = \frac{f(n-1) \times (4n-2)}{(n+1)}$。至此，卡特兰数的问题已经解决。
加入字母顺序以后，这可以看成已经准备好了n个位置，现在来安排座位，排序总数为$n!$种。所以数的数量就等于$f(n) \times n!$
这里如果分别计算再相乘的话会很麻烦，所以直接令答案$h(n) = \frac{h(n-1) \times n \times (4n-2)}{(n+1)}$
卡特兰数：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
using namespace std;
const int MAX = 100;
const int XX = 10000;
int katelan[MAX+5][MAX+5];
int main()
{
katelan[0][1] = 1;
for(int i = 1; i <= MAX; ++i)
{
for(int j = 1; j <= MAX; ++j)
{
katelan[i][j] += katelan[i-1][j]*(4*i-2);
katelan[i][j+1] += katelan[i][j]/XX;
katelan[i][j] %= XX;
}
int tem;
for(int j = MAX; j > 0; --j)
{
tem = katelan[i][j] % (i+1);
katelan[i][j-1] += tem*XX;
katelan[i][j] /= (i+1);
}
}
int n;
while(~scanf("%d",&n))
{
int i = MAX;
while(katelan[n][i] == 0) i--;
cout << katelan[n][i--];
while(i > 0)
{
printf("%04d",katelan[n][i--]);
}
cout << endl;
}
return 0;
}
AC代码：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
using namespace std;
const int MAX = 100;
const int XX = 10000;
int katelan[MAX+5][MAX+5];
int main()
{
katelan[0][1] = 1;
for(int i = 1; i <= MAX; ++i)
{
for(int j = 1; j <= MAX; ++j)
{
katelan[i][j] += katelan[i-1][j]*i*(4*i-2);
katelan[i][j+1] += katelan[i][j]/XX;
katelan[i][j] %= XX;
}
int tem;
for(int j = MAX; j > 0; --j)
{
tem = katelan[i][j] % (i+1);
katelan[i][j-1] += tem*XX;
katelan[i][j] /= (i+1);
}
}
int n;
while(scanf("%d",&n) && n)
{
int i = MAX;
while(katelan[n][i] == 0) i--;
cout << katelan[n][i--];
while(i > 0)
{
printf("%04d",katelan[n][i--]);
//%04d 表示在输出一个小于4位的数值时
//将在前面补0使其总宽度为4位
}
cout << endl;
}
return 0;
}
B - B
HDU - 1087
最长上升子序列。之前的博客也写过。
（队友及）AC代码：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
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX = 1005;
int a[MAX], dp[MAX];
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
int n, ans;
while(~scanf("%d",&n) && n)
{
for(int i = 0; i < n; ++i)
{
scanf("%d",&a[i]);
dp[i]=a[i];
}
for(int i = 0; i < n; ++i)
{
for(int i1=i-1; i1>=0; --i1)
{
if(a[i]>a[i1]&&dp[i]<dp[i1]+a[i])
{
dp[i]=dp[i1]+a[i];
}
}
}
sort(dp,dp+n,cmp);
cout<<dp[0]<<endl;
}
return 0;
}
C - C
HDU - 1045
DFS。
AC代码：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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
using namespace std;
char mapa[5][5];
int vis[5][5];
int n, ans;
void init()
{
ans = 0;
memset(vis, 0, sizeof(vis));
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
if(mapa[i][j] == 'X')
vis[i][j] = 2;
}
bool ok(int x, int y)
{
if(x < 0 || x >= n || y < 0 || y >= n) return false;
return true;
}
bool okok(int x, int y)
{
if(vis[x][y] == 2) return false;
for(int i = x; ok(i, y); ++i)//右
{
if(vis[i][y] == 2) break;//如果碰到X直接退出
if(vis[i][y] == 1) return false;
}
for(int i = x; ok(i, y); --i)//左
{
if(vis[i][y] == 2) break;
if(vis[i][y] == 1) return false;
}
for(int i = y; ok(x, i); ++i)//上
{
if(vis[x][i] == 2) break;
if(vis[x][i] == 1) return false;
}
for(int i = y; ok(x, i); --i)//下
{
if(vis[x][i] == 2) break;
if(vis[x][i] == 1) return false;
}
return true;
}
void dfs(int num)
{
if(num > ans) ans = num;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
{
if(okok(i, j))
{
vis[i][j] = 1;
dfs(num + 1);
vis[i][j] = 0;
}
}
}
int main()
{
while(~scanf("%d",&n) && n)
{
for(int i = 0; i < n; ++i)
scanf("%s", mapa[i]);
init();
dfs(0);
cout << ans << endl;
}
return 0;
}
D - D
HDU - 2052
额..打印图形..手速还是不够啊，交上时已经3分1秒了..
AC代码：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
using namespace std;
const int INF = 0x3f3f3f3f;
int main()
{
int n, m;
while(~scanf("%d%d",&n, &m))
{
cout << "+";
for(int i = 0; i < n; ++i)
cout << "-";
cout << "+" << endl;
for(int i = 0; i < m; ++i)
{
cout << "|";
for(int j = 0; j < n; ++j) cout << " ";
cout << "|" << endl;
}
cout << "+";
for(int i = 0; i < n; ++i)
cout << "-";
cout << "+" << endl;
cout << endl;
}
return 0;
}
E - E
HDU - 1060
给你一个数N（$0<N<1,000,000,000$）， 让你求$N^N$的最高位数字。
一开始找规律，找啊找，就是找不到。后来发现有公式。（这道题还是挺不错的）
假设最高位数字为a，则用科学计数法表示就可以表示为$N^N = a \times 10^x$，同时取对数，移项，化简，得$a = 10^{(N \times lgN - x)}$，而这里的x就是$lg(N^N)$向下取整（别问我为什么）。
到这里答案就可以得出来了，注意一下强制类型转换。
(队友瑕)AC代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using namespace std;
int main()
{
int t;
long long n;
while(~scanf("%d",&t))
{
while(t--)
{
scanf("%lld",&n);
double b = pow(10, n*log10(n) - (long long)(n * (log10(n))));
cout << (int)b << endl;
}
}
return 0;
}
F - F
HDU - 5578
两只小青蛙？呱呱呱？然而这些情景并没有什么用，主要是问给出的字符串中，找到两个相同的字符最小的距离，没有相同的字符就输出-1
（队友及）AC代码：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
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX = 1005;
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int j=1;j<=n;++j)
{
char a[1005];
scanf("%s",a);
int len=strlen(a),num=2000;
for(int i=0;i<len-1;++i)
{
for(int i1=i+1;i1<len;++i1)
{
if(a[i]==a[i1])
{
if(num>i1-i)
{
num=i1-i;
}
}
}
}
if(num!=2000) printf("Case #%d: %d\n",j,num);
else printf("Case #%d: %d\n",j,-1);
}
}
return 0;
}
G - G
HDU - 1097
这个是求$x^y$的个位数，可以用快速幂一套带走，也可以找规律，之前的博客也写过这个题..
（队友及）AC代码：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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
using namespace std;
int main()
{
long long a,b;
while(~scanf("%lld%lld",&a,&b))
{
if(a%10==0) a=0;
else if(a%10==1) a=1;
else if(a%10==2)
{
switch(b%4)
{
case 1:a=2;break;
case 2:a=4;break;
case 3:a=8;break;
case 0:a=6;break;
}
}
else if(a%10==3)
{
switch(b%4)
{
case 1:a=3;break;
case 2:a=9;break;
case 3:a=7;break;
case 0:a=1;break;
}
}
else if(a%10==4)
{
switch(b%2)
{
case 1:a=4;break;
case 0:a=6;break;
}
}
else if(a%10==5)
{
a=5;
}
else if(a%10==6)
{
a=6;
}
else if(a%10==7)
{
switch(b%4)
{
case 1:a=7;break;
case 2:a=9;break;
case 3:a=3;break;
case 0:a=1;break;
}
}
else if(a%10==8)
{
switch(b%4)
{
case 1:a=8;break;
case 2:a=4;break;
case 3:a=2;break;
case 0:a=6;break;
}
}
else if(a%10==9)
{
switch(b%2)
{
case 1:a=9;break;
case 0:a=1;break;
}
}
cout<<a<<endl;
}
return 0;
}
1 |
|
