1、$A_{1}=2,A_{2}=3,A_{n}=A_{n-2}+A_{n-1}-1$。给出数字$n$，将其表示成若干个$A$中的不同元素的和。
思路：设$B_{n}=A_{n}-1$，那么有$B_{n}=B_{n-2}+B_{n-1},B_{1}=1,B_{2}=2$。那么$B$其实是斐波那契数列。设将$n$表示成$k$个$A$中的元素，那么就等同于将$n-k$表示成$k$个$B$中不同的元素。这个分两步进行：（1）将$n-k$表示成最少的$B$中元素的和，（2）如果这个个数大于$k$那么无解。若小于$k$，可以将某个数字$x=B_{t}$替换为$B_{t-2}+B_{t-1}$以增加一个数字。
#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <stack>
using namespace std; long long f[100];
int n; void init(long long x)
{
f[1]=1;
f[2]=2;
for(int i=3;i<100;++i)
{
f[i]=f[i-1]+f[i-2];
if(f[i]>x)
{
n=i-1; break;
}
}
} vector<int> ans; int check(int k,long long x)
{
if(x<=0) return 0;
ans.clear();
while(x>0)
{
for(int i=n;i>=1;--i) if(x>=f[i])
{
ans.push_back(i);
x-=f[i];
break;
}
}
if((int)ans.size()>k) return 0;
while((int)ans.size()<k)
{
sort(ans.begin(),ans.end());
int ok=0;
for(int i=0;i<(int)ans.size();++i)
{
if((i==0&&ans[0]>=3)||(i!=0&&ans[i]-ans[i-1]>=3))
{
ans.push_back(ans[i]-1);
ans[i]-=2;
ok=1;
break;
}
}
if(!ok) return 0;
}
return 1;
} class AlmostFibonacciKnapsack
{
public:
vector<int> getIndices(long long x)
{
init(x);
for(int i=1;i<=n;++i) if(check(i,x-i)) return ans;
return vector<int>{-1};
}
};
2、给出一个二维整数数组$A[n][n]$。构造一个$n$个顶点的带权无向图$G$，使得对于$G$中任意两点$i,j$,它们之间的最小割等于$A[i][j]$。
思路：最小割的一个性质是：对于由一个割$C$将$G$分成的两个点集$P,Q$，对于$P,Q$内任意一点$p,q$，它们之间的最小割小于等于$|C|$。所以，初始化所有顶点是一个集合$S$。然后每一步重复下面操作：
（1）若$S$的大小小于2结束；否则找到最小的$t=A[i][j],i\in S,j\in S$
（2）初始化集合$S_{0},S_{1}$为空，将$S$中第一个元素$x_{0}$放入$S_{0}$.然后对于$S$中任意一个其他元素$x_{i}$，若$A[x_{0}][x_{i}]>t$则将$x_{i}$放入$S_{0}$,否则将其放入$S_{1}$
（3）对于$S_{0},S_{1}$中的元素$x,y$，若$A[x][y]!=t$，则无解。
（4）递归判断$S_{0},S_{1}$
#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <stack>
using namespace std; const int N=2005;
const int INF=1000000005; class AllGraphCuts
{
int n;
int g[55][55];
vector<int> ans; void add(int u,int v,int w)
{
ans.push_back(w*n*n+u*n+v);
} int dfs(vector<int> S)
{
if(S.size()<=1) return 1;
int tmp=INF;
for(int i=0;i<(int)S.size();++i) for(int j=0;j<(int)S.size();++j)
{
if(i!=j&&g[S[i]][S[j]]<tmp) tmp=g[S[i]][S[j]];
}
vector<int> S0,S1;
S0.push_back(S[0]);
for(int i=1;i<(int)S.size();++i)
{
if(g[S[0]][S[i]]>tmp) S0.push_back(S[i]);
else S1.push_back(S[i]);
}
if(S0.empty()||S1.empty()) return 0;
for(int i=0;i<(int)S0.size();++i) for(int j=0;j<(int)S1.size();++j)
{
if(g[S0[i]][S1[j]]!=tmp) return 0;
}
add(S0[0],S1[0],tmp);
return dfs(S0)&&dfs(S1);
} public:
vector<int> findGraph(vector<int> x)
{
n=1;
while(n*n!=(int)x.size()) ++n;
for(int i=0;i<n;++i) for(int j=0;j<n;++j) g[i][j]=x[i*n+j];
for(int i=0;i<n;++i) for(int j=0;j<n;++j)
{
if((i==j&&g[i][j]!=0)||(g[i][j]!=g[j][i])) return vector<int>{-1};
}
vector<int> S;
for(int i=0;i<n;++i) S.push_back(i);
if(dfs(S)) return ans;
return vector<int>{-1};
}
};