A FZU-2054
水题，比较A,B双方的最大值即可。
B FZU-2055
string，截取‘.’之前和之后然后和给出的文件夹名和拓展名比较就好了啊，不明白为什么那么多人错。
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = ;
string path[maxn], type[maxn];
int main()
{
int T; scanf("%d", &T);
while(T--)
{
int n, m; scanf("%d%d", &n, &m);
string str;
for(int i = ; i < n; i++)
{
cin >> str;
int pos = str.find_last_of('.');
path[i] = str.substr(, pos);
type[i] = str.substr(pos);
}
string t1, t2;
for(int i = ; i < m; i++)
{
cin >> t1 >> t2;
for(int j = ; j < n; j++)
{
if(t2 != type[j]) continue;
if(t1.length() > path[j].length()) continue;
string tmp = path[j].substr(, t1.length());
if(tmp == t1) {cout << path[j] << type[j] << endl;}
}
} }
return ;
}
C FZU-2056
题意：现在有一个n*m的矩阵A，在A中找一个H*H的正方形，使得其面积最大且该正方形元素的和不大于 limit。
分析：开始以为是DP或者二维RMQ，其实用二分就可以做出来；
在输入时构造元素和矩阵dp[][]（即dp[i][j]为从(1,1)到(i,j)的矩形范围元素和）;再在(0，min(m,n))范围内二分查找满足条件的最优解H；
计算正方形内元素和的方法要掌握;
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxn = ;
int m, n, lim;
int dp[maxn][maxn];
bool solve(int h)
{
// if(h == 1) return
for(int i = h; i <= n; i++)
{
for(int j = h; j <= m; j++)
{
if(dp[i][j]-dp[i-h][j]-dp[i][j-h]+dp[i-h][j-h] > lim) continue;
return true;
}
}
return false;
}
int main()
{
int T; scanf("%d", &T);
while(T--)
{
scanf("%d%d%d", &n, &m, &lim);
memset(dp, , sizeof(dp));
for(int i = ; i <= n; i++)
{
int tmp = ;
for(int j = ; j <= m; j++)
{
int x; scanf("%d", &x);
tmp += x;
dp[i][j] = dp[i-][j]+tmp;
}
} int H = min(n, m);
int L = , R = H;
int M;
while(L < R)
{
M = L+(R-L)/;
if(M == L) M++;
if(solve(M)) L = M;
else R = M-;
}
cout << L*L << endl;
}
return ;
}
D FZU-2057
题意：给出一树状家谱图，再给出两个人，问两人什么关系；
分析：又想复杂了，只要在输入时记录下父子母子关系，性别，然后由长辈往下搜就行，如果是男的就输出'F'，女的输出‘M’，搜不到时注意改变长幼关系再搜一次，如果还搜不到就输出Relative；
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
const int maxn = ;
int vis[maxn], child[maxn], sex[maxn];
stack<int> vv;
struct Node
{
int f, m, sex;
bool operator == (const Node& rhs) const
{
return f==rhs.f && m == rhs.m;
}
}nodes[maxn];
void print()
{
while(!vv.empty()){
int t = vv.top(); vv.pop();
if(t == ) printf("F");
else if(t == )printf("M");
}
printf("\n");
}
bool dfs(int u, int v)
{
while(!vv.empty()) vv.pop();
while(u != v)
{
if(sex[u] == )
vv.push();
else if(sex[u] == )
vv.push();
else
break;
u = child[u];
}
if(u == v)
return true;
else return false;
} int main()
{
int T; scanf("%d", &T);
while(T--)
{
memset(sex, , sizeof(sex));
int n; scanf("%d", &n);
int a, b, c;
for(int i = ; i<n/; i++)
{
scanf("%d%d%d", &a, &b, &c);
// nodes[a].f = b, nodes[a].m = c;
sex[b] = , sex[c] = ;
child[b] = child[c] = a;
}
int m; scanf("%d", &m);
while(m--)
{
int x, y; scanf("%d%d", &x, &y);
if(dfs(x, y))
{
printf("0 ");
print();
}
else if(dfs(y, x))
{
printf("1 ");
print();
}
else
printf("Relative\n");
}
}
return ;
}
E FZU-2058
题意：给出N个元素，问有多少对元素的和是M;
分析：一种常见的简单思路题；二层循环不用想肯定超时，dp当然也用不上，对于其中一个元素x，排序后用二分或者lower_bound/upper_bound函数搜索M-x的个数就好啦。
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = ;
LL a[maxn];
LL n, m; LL solve()
{
LL cnt = ;
for(int i = ; i < n; i++)
{
LL t = m-a[i];
int pos1 = upper_bound(a+i+, a+n, t)-a-i-;
int pos2 = lower_bound(a+i+, a+n, t)-a-i-;
cnt += pos1-pos2;
}
return cnt;
} int main()
{ while(~scanf("%I64d%I64d", &n, &m))
{
for(int i = ; i < n; i++)
{
scanf("%I64d", &a[i]);
}
sort(a, a+n);
printf("%I64d\n", solve());
} return ;
}
F FZU-2059
G FZU-2060
心好累，我再想想T ^ T；
I FZU-2062
题意：要想得到1~n之间的所有数，最少需要多少个数。
分析：确实是个有点意思的水题，前提是要想到十进制可以用二进制转换啊！愚蠢！不行得多练练位运算...
以n=5为例：
5 = 1+2+2;
4 = 2+2;
3 = 1+2；
2 = 2；
1 = 1；
答案：log2(n)
J FZU-1859
题意：画图题，HDU2083的简化，递归画图就行；当然也有找规律画出来的，且待我研究研究...
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = ; int pic[maxn][maxn]; void print(int x, int y, int n)
{
if(n == ) {pic[x][y] = ''; return;}
print(x, y, n-);
print(x+(<<(n-)), y, n-);
print(x+(<<(n-)), y+(<<(n-)), n-);
} int main()
{
int T; scanf("%d", &T);
while(T--)
{
memset(pic, , sizeof(pic));
int n; scanf("%d", &n);
print(, , n);
for(int i = ; i <= (<<(n-)); i++)
{
for(int j = ; j <= i; j++)
if(pic[i][j]) printf("@"); else printf(" ");
printf("\n");
}
} return ;
}
K FZU-1862
题意：给出一个环，按顺时针的顺序求出下标为L,R之间的最大的数；
分析：这题感觉时间上自己是水过去的，把环变成数组先打表求出各区间的最大值，然后输出即可。灰常简单的转化技巧。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = ;
int m[maxn], Max[maxn][maxn];
int main()
{
int n;
int kase = ;
while(~scanf("%d", &n))
{
printf("Case #%d:\n", ++kase);
for(int i = ; i <= n; i++) scanf("%d", &m[i]);
for(int i = ; i <= n; i++) m[n+i] = m[i];
memset(Max, -, sizeof(Max));
for(int i = ; i <= n; i++)
{
for(int j = i; j <= n+i; j++)
{
Max[i][j] = max(Max[i][j-], m[j]);
}
}
int q; scanf("%d", &q);
for(int i = ; i < q; i++)
{
int a, b; scanf("%d%d", &a, &b);
if(a <= b) printf("%d\n", Max[a][b]);
else printf("%d\n", Max[a][b+n]);
}
printf("\n");
}
return ;
}