部门网站建设整改,关键词seo优化,小型企业网络营销方案,广州平面设计招聘1.数字三角形#xff08;方向次数限制#xff0c;动态规划#xff09; //如果n为奇数时#xff0c;最后必然走到最后行最中间的数#xff0c;如果为偶数#xff0c;则取中间两个数的最大值#xff0c; //因为向左下走的次数与向右下走的次数相差不能超过 1
#include …1.数字三角形方向次数限制动态规划 //如果n为奇数时最后必然走到最后行最中间的数如果为偶数则取中间两个数的最大值 //因为向左下走的次数与向右下走的次数相差不能超过 1
#include iostream
using namespace std;
const int N110;
int g[N][N];
int f[N][N];
int n;
int ans;
int main()
{cinn;for(int i1;in;i){for(int j1;ji;j){cing[i][j];}}for(int i1;in;i){for(int j1;ji;j){f[i][j]max(f[i-1][j],f[i-1][j-1])g[i][j];}}//如果n为奇数时最后必然走到最后行最中间的数如果为偶数则取中间两个数的最大值//因为向左下走的次数与向右下走的次数相差不能超过 1if(n%2)coutf[n][n/21];else coutmax(f[n][n/2],f[n][n/21]);return 0;
}
2.作物杂交DFS递归 #include iostream
#include map
#include vector
using namespace std;
const int N2000100;
int n,m,k,t;
vectorpairint,int fa[N];
int tim[N];
int f[N];//f[i]表示得到i需要花费的时间
mapint,intmp;
int ans;
int dfs(int t)//倒着推
{for(int i0;ifa[t].size();i){int afa[t][i].first;int bfa[t][i].second;if(!mp[a])dfs(a);if(!mp[b])dfs(b);if(mp[a]mp[b]){mp[t]1;f[t]min(f[t],max(tim[a],tim[b])max(f[a],f[b]));}}return f[t];
}
int main()
{cinnmkt;for(int i1;in;i){cintim[i];f[i]1e9;//初始都是得不到的}for(int i1;im;i){int x;cinx;mp[x]1;f[x]0;//已经有了得到的时间为0}for(int i1;ik;i){int a,b,c;cinabc;fa[c].push_back({a,b});}coutdfs(t);return 0;
}
3.Excel地址思维 #include iostream
#include vector
using namespace std;
int main()
{long long n;cinn;vectorcharv;while(n){n--;//0-25表示A-Z所以先减一v.push_back(n%26A);//贡献当前位的表示n/26;//贡献当前位的权}for(int iv.size()-1;i0;i--)coutv[i];return 0;
}
4.k倍区间思维
组合求法假设%k值相等的区间有n个根据得出的结论发现任何两个前缀区间的和对k取模的值相等则由大的前缀区间减掉小的前缀区间所形成的区间的必定是K倍区间。那n个中取任何两个区间都可以组成k倍区间问有多少k倍区间就转换成n个区间取两个的情况有多少个就是Cn2n*(n-1)/2所以对于每个%k值相等的区间都添加一次组合就可以算出总共有多少k倍区间了 #include iostream
using namespace std;
const int N1e510;
#define ll long long
ll sum;
ll cnt[N];//cnt[i]表示与k取模后余i的个数
int a[N];
int n,k;
ll ans;
int main()
{cinnk;for(int i1;in;i){cina[i];sumsuma[i];//计算前缀和cnt[sum%k];//统计所有前缀和%k后的余数相同个数}//余数为0直接就是k的倍数lanscnt[0];//剩下的余数相同的前缀和选2个相同的进行相减//即可得到一个子区间且和是k的倍数for(int i0;ik;i){//组合数cnt[i]个数选两个C(n,2)n*(n-1)/2//求得的组合数即所有组合即可贡献答案anscnt[i]*(cnt[i]-1)/2;}coutansendl;return 0;
}
思路来自Moon 5.包子凑数动态规划 #include iostream
using namespace std;
const int N110;
const int M1e4;
int n;
int a[N];
int f[M];//f[i]0表示i个包子凑不出来f[i]1表示i个包子凑得出来
int gcd(int a,int b)//用来判断是否互质若全不互质那肯定凑不出来无限个
{return b?gcd(b,a%b):a;
}
int main()
{cinn;for(int i0;in;i){cina[i];} //求出数组a的最大公因数int ggcd(a[0],a[1]);for(int i2;in;i){ggcd(g,a[i]);}//如果最大公因数大于1肯定无法表示的有无限if(g1){coutINFendl;}else{int ans0;f[0]1;//0个包子肯定可以for(int i0;in;i){for(int j0;ja[i]M;j){if(f[j]){f[ja[i]]1;}}}for(int i0;iM;i){if(!f[i]){ans;}}coutansendl;}return 0;
}
7.分巧克力二分
以下是错误代码注意切巧克力是有边的限制的不能使用面积面积满足但是形状不满足的巧克力是不合法的
#include iostream
#include cmath
using namespace std;
const int N1e510;
#define ll long long
int n,k;
int b1e9;
int cnt0;
ll sum[N];
int main()
{cinnk;for(int i1;in;i){int h,w;cinhw;int kk(int)sqrt(h*w);bmin(b,kk);sum[i](ll)h*w;}for(int i1;in;i){cnt(sum[i]/(b*b));}if(cntk)coutbendl;else{while(cntk){b--;cnt0;for(int i1;in;i){cnt(sum[i]/(b*b));}}coutbendl;}return 0;
} #include iostream
#include cmath
using namespace std;
const int N1e510;
#define ll long long
int n,k;
int ans;
int h[N],w[N];
bool check(int x)
{int cnt0;for(int i1;in;i){cnt(h[i]/x)*(w[i]/x);//有多少个x的高多少个x的宽这样才能切出巧克力}return cntk;
}
int main()
{cinnk;for(int i1;in;i){cinh[i]w[i];}int l1;int rN;while(lr){int mid(lr)/2;if(check(mid)){ansmid;//ans是符合要求的不断取大的lmid1;}else{rmid-1;}}coutansendl;return 0;
}
8.九宫幻方DFS #include iostream
#include map
using namespace std;
int a[4][4];
int ans[4][4];
int n,cnt;
pairint,intp[10];
mapint,intmp;
bool check()
{int suma[1][1]a[2][2]a[3][3];if(sum!a[1][3]a[2][2]a[3][1])return 0;for(int i1;i3;i){int temp10,temp20;for(int j1;j3;j){temp1a[i][j];temp2a[j][i];}if(temp1!sum||temp2!sum)return 0;}return 1;
}
void dfs(int now)
{if(nown)//也就是所有为0的点都已经遍历完了{if(check()){cnt;for(int i1;i3;i){for(int j1;j3;j){ans[i][j]a[i][j];}}}return;} //x和y表示可以填数的点int xp[now].first,yp[now].second;for(int i1;i9;i){if(mp[i])continue;//填过的不可以再填a[x][y]i;mp[i]1;dfs(now1);a[x][y]0;mp[i]0;}
}
int main()
{for(int i1;i3;i){for(int j1;j3;j){cina[i][j];if(!a[i][j])p[n]make_pair(i,j);mp[a[i][j]]1;}}dfs(1);if(cnt1){for(int i1;i3;i){for(int j1;j3;j){coutans[i][j] \n[j3];}}}else coutToo Many\n;return 0;
}
