1.最长公共子序列
#include<bits/stdc++.h>
using namespace std;
const int N=105;
char a[N],b[N],c[N];
string f[N][N][N];
int main(){
scanf("%s%s%s",a+1,b+1,c+1);
int n = strlen(a+1);
int m = strlen(b+1);
int k = strlen(c+1);
//初始化
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int l = 1;l<=k; l++)
f[i][j][l]="";
// cout << n << m << k <<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
for(int l = 1;l<=k; l++){
int s1 = f[i-1][j][l].size();
int s2 = f[i][j-1][l].size();
int s3 = f[i][j][l-1].size();
if(s1>s2&&s1>s3) f[i][j][l] = f[i-1][j][l];
else if(s2>s1&&s2>s3) f[i][j][l] = f[i][j-1][l];
else f[i][j][l] = f[i][j][l-1];
if(a[i]==b[j]&&b[j]==c[l]) f[i][j][l]=f[i-1][j-1][l-1]+a[i];
}
}
cout << f[n][m][k] <<endl;
// printf("%s\n",f[n][m][k]);
return 0;
}
2.AFamousICPCTeam
给出四个正方体箱子的边长，问能装下这四个正方体箱子
的大正方体边长最小要多大，要求边长最小且必须能装下四个箱子。
这道题并不难，要模拟自己手动推的过程，虽然不能一下得出结论
多举几个例子，从一般到极端，就出来了
自己模拟的时候都会从最大的开始放，所以先排个序
然后发现a一定大于a1+a2（最大的两个正方体）
又通过画图，a1+a2一定可以满足放下四个正方体---->答案就是a1+a2
3.A Famous Grid
经典bfs+筛质数
3.树的先中后序遍历
这里特别注意：孩子兄弟表示法不适合这种区分左右孩子顺序的问题，遇到这种问题还是老实建树
由于这里插入一条边 void add(int a,int b){
e[idx] = b,ne[idx] = h[a], h[a] = idx++;
} 是链表的头插法，在先序和后序遍历的时候，把右子树先插，左子树后插，还是能用这种方法的，但不建议。中序遍历不可以用，因为当当前节点只有一个孩子时候无法区分它是左孩子还是右孩子（除非加个额外的变量标记一下）
void PreOrdered(int u){
cout<<u<<' ';
for(int i = h[u];i!=-1;i = ne[i]){
int j = e[i];
PreOrdered(j);
}
}
void BackOrdered(int u){
for(int i = h[u];i!=-1;i = ne[i]){
int j = e[i];
PreOrdered(j);
}
cout<<u<<' ';
}
//输入时候，先插入r后l
for(int i=0;i<n;i++){
int f,l,r;
cin>>f>>l>>r;
if(r!=-1) add(f,r);
if(l!=-1) add(f,l);
}
4.汉诺塔问题
这里移动次数可以通过递推来实现，移动n个块需要$ 2^n-1$次移动，正常递推后100次输出的话，画一个递归树，n=64时总递归次数3*2^(64)-1会严重超时
void dfs(int from,int to,int helper,int n){
if(n==1){
//输出
return 1;
}
dfs(from,helper,to,n-1);
dfs(from,to,helper,1);
dfs(helper,to,from,n-1);
}
考虑剪枝，n=6的时候，移动次数63，n=7的时候，移动次数127，只要输出后100次操作即可
所以当n>7时候 都不用考虑前两个dfs
FDU2015
3. 实现一个优先队列
和算法基础课中的模拟堆类似， 模拟堆
FDU2016
1.求最大公共子串长度
子串！=子序列（子串是连续的）
方法：
1）暴力枚举$O(n^3)$
2）后缀数组$O(nlogn)$
3）二分长度+字符串哈希+哈希表$O(nlogn)$
这里用第三种方法
#include<bits/stdc++.h>
using namespace std;
string a,b;
int main(){
cin>>a>>b;
int len = min(a.size(),b.size());
int l = 0, r = len;
int max_len = 0;
string tmp;
while(l<=r){
unordered_set<string> h;
bool flag = false;
int mid = l+r>>1;
for(int i=0; i<b.size()-mid+1;i++){//枚举a中长度为mid的所有子串
string s = b.substr(i,mid);
//cout<<"s="<<s<<endl;
h.insert(s);
}
for(int i=0; i<a.size()-mid+1;i++){//枚举b中长度为mid的所有子串
string s = a.substr(i,mid);
// cout<<"s2="<<s<<endl;
if(h.count(s)){
flag = true;
max_len = max(max_len,mid);
l = mid+1;
tmp = s;
}
}
if(!flag) r = mid-1;
}
cout << max_len<<endl<<tmp;
return 0;
}
3.求字符串的哈夫曼编码长度
先统计所有字符的出现次数，（建立哈夫曼树，发现求哈夫曼编码长度就是求所有节点的带权路径长度WPL==非叶节点权值之和），找最小的两两push进小根堆，在push的时候加上该节点的权值
FDU2017
3.无向图
找权值之和最小的边，让图连通—最小生成树问题kruskal算法， 详情见
FDU2018
3.骨牌
简单思路：类似斐波那契数列，f(n) = f(n-1)+f(n-2)，其中fi表示前i列确定的方案数
其他思路：是 蒙德里安的梦想 的简化版
4.如何保留两位小数
cout<<fixed<<setprecision(2)<<x<<y<<endl; 或者
printf(%.2f %.2f\n,x,y);
6.约数求和
思路：1~n这n个数里有几个i * i===和
一些约数的结论
FDU2019
3.有向树形态
先举几个简单的例子试试，发现大问题可以化成小问题，这棵树的形态=左子树形态*右子树形态，同时为防止sfs中的重复操作，用数组记下来每个答案，如果记过了就不用重复算了
int dfs(int n){//求n个节点的树的可能性个数
if(dp[n]!=-1) return dp[n];
dp[n] = 0;
for(int i=0;i<n;i++){
dp[n]=dfs(i)*dfs(n-i-1);
}
return dp[n];
}
FDU2020
3.打地鼠
n个整数从小到大，挑尽可能多个差不小于d的数—如果我能选，我前面那个也能选—贪心
4.序列
典型的动态规划，注意：只开一个一维数组f[i]代表1~i在b中已经确定是哪个数字，此时最小代价记在f中。这种方式记录的信息太少了，长度为i确定了，长度i+1未必选长度为i时的那些数------>所以开一个二维数组dp[N][10]，枚举每一位分别是0~9中的数时候的代价，用记录在数组中降低题目的复杂。
//错误思路
memset(f,0x3f3f3f3f,sizeof f);
f[1] = 0, b[1] = a[1];
for(int i=2;i<=n;i++){//枚举当前位的位置
for(int j=0;j<10;j++){//枚举b的当前位的可能数字
f[i] = min(f[i],f[i-1]+abs(a[i]-j)+(j-b[i-1])*(j-b[i-1]));
}
}
cout<<f[n]<<endl;
//正确思路
for(int i=2;i<=n;i++){
for(int j=0; j<10; j++){//枚举第i-1位上的数字
int w_min=0x3f3f3f3f;
int w_ab=abs(a[i]-j);
for(int k=0; k<10; k++){//第i位上的数字
int w_bb=(k-j)*(k-j);
int total=dp[i-1][j]+w_bb;
w_min=min(total,w_min);
}
dp[i][j]=w_ab+w_min;
}
}
int ans=0x3f3f3f3f;
for(int i=0;i<10;i++) ans = min(ans,dp[n][i]);
5.二叉搜索树
FDU2021
3.目标和
题目
思路一：
用dp数组表示这n个数的状态,每个状态对每位进行判断$O((1<<N)*N)$,(但是会超时)
int findTargetSumWays(vector<int>& nums, int target) {
int res=0;
int dp[1<<20]={0};//10000B 表示二进制，第5个数的符号为1负，剩下都是0正
int n = nums.size();
for(int i=0;i<1<<n;i++){
//i是一个状态
int st=i,cnt=n,sum=0;
while(cnt--){//循环n次，每次处理1位
if(st&1) sum+=nums[cnt];
else sum-=nums[cnt];
st>>=1;
}
if(sum==target) res++;
}
return res;
}
思路二：
背包问题，准备两个背包，一个背包package_a存放标记为正的元素，另一个背包package_b存放标记为负的元素。package_a - package_b = target。
package_a - package_b = target;
package_a + package_b = sum;
则 package_a = (target + sum)/2。
所以根据题意给的target和sum，可以求出package_a的值。
转化为：给定一个大小为package_a的背包，有多少种组合方式能把背包装满？ 0-1背包。
