White

            今天下午14：00小组举行了第一次磨合赛，总体配合的感觉还可以，相信还有很多问题没暴露出来，还有不到两个月，把握好每次练习的机会，争取这方面不会有太大失分点。

           在此特意感谢熬夜为我们准备题目的超哥，还有两位带我飞的队友。然后，先定个小目标——坐上山师4队的位置。

推荐题目：A、E

A - A

HDU - 1131 

卡特兰数的应用。

在不考虑顺序的前提下，将节点编号为0~n-1，任取一个节点k作为根节点，从而衍生出两个子问题f(k-1)和f(n-k)，有f(k-1)*f(n-k)棵树，则——f(n) = f(0)*f(n-1) + f(1)*f(n-2) + …… + f(n-1)*f(0)，符合卡特兰数的递推公式。由该递推公式可以推出f(n) = f(n-1)*(4n-2)/(n+1)。至此，卡特兰数的问题已经解决。

加入字母顺序以后，这可以看成已经准备好了n个位置，现在来安排座位，排序总数为n!种。    所以数的数量就等于f(n)*n!

这里如果分别计算再相乘的话会很麻烦，所以直接令答案h(n) = h(n-1)*n*(4n-2)/(n+1)

卡特兰数：

#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> 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("d",katelan[n][i--]); } cout << endl; } return 0; }

AC代码：

#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> 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("d",katelan[n][i--]); //d 表示在输出一个小于4位的数值时 //将在前面补0使其总宽度为4位 } cout << endl; } return 0; }

B - B

HDU - 1087                    

最长上升子序列。之前的博客也写过。

（队友及）AC代码：

#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> 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代码：

#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> 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代码：

#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> 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 * 10^x ，同时取对数，移项，化简，得a = 10^(N*lgN - x)，而这里的x就是lg(N^N)向下取整（别问我为什么）。

到这里答案就可以得出来了，注意一下强制类型转换。

（队友瑕）AC代码：

#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> 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代码：

#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> 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代码：

#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> using namespace std; int main() { long long a,b; while(~scanf("%lld%lld",&a,&b)) { if(a==0) a=0; else if(a==1) a=1; else if(a==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==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==4) { switch(b%2) { case 1:a=4;break; case 0:a=6;break; } } else if(a==5) { a=5; } else if(a==6) { a=6; } else if(a==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==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==9) { switch(b%2) { case 1:a=9;break; case 0:a=1;break; } } cout<<a<<endl; } return 0; }

AC代码：

#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int INF = 0x3f3f3f3f; const int MAX = 1005; long long quickpow(long long a, long long b, long long c) { long long ans = 1; a = a % c; while(b) { if(b & 1) ans = ans * a % c; b >>= 1; a = a*a%c; } return ans; } int main() { long long n, m; while(~scanf("%lld%lld",&n,&m)) { long long ans = quickpow(n, m, 10); cout << ans << endl; } return 0; }