邯山网站制作,百度收录网站之后又怎么做,网站开发一般有那些语言,下店拓客团队前言 FFF不会做#xff0c;正解好神仙#xff0c;爬了
正题 AT2041 [AGC004A] Divide a Cuboid
https://www.luogu.com.cn/problem/AT2041
题目大意
一个A∗B∗CA*B*CA∗B∗C的立方体#xff0c;分成两个长方体使得边长都是整数而且体积差最小。 1≤A,B,C≤1091\leq A,B…前言
FFF不会做正解好神仙爬了
正题 AT2041 [AGC004A] Divide a Cuboid
https://www.luogu.com.cn/problem/AT2041
题目大意
一个A∗B∗CA*B*CA∗B∗C的立方体分成两个长方体使得边长都是整数而且体积差最小。
1≤A,B,C≤1091\leq A,B,C\leq 10^91≤A,B,C≤109
解题思路
如果有一边是偶数之间这边开始分不然就找一边分的最小就好了。
code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
ll a,b,c;
signed main()
{scanf(%lld%lld%lld,a,b,c);if((a1)(b1)(c1))printf(%lld\n,min(a*b,min(b*c,a*c)));else puts(0);return 0;
}AT2042 [AGC004B] Colorful Slimes
https://www.luogu.com.cn/problem/AT2042
题目大意
nnn个颜色的史莱姆第iii只可以花费aia_iai获得或者花费kkk使得所有获得的史莱姆颜色加一后模nnn求最少花费多少能获得所有颜色的史莱姆。
1≤n≤2000,1≤ai,k≤1091\leq n\leq 2000,1\leq a_i,k\leq 10^91≤n≤2000,1≤ai,k≤109
解题思路
显然我们可以通过控制获得的顺序使得加一的次数就是次数最多的那个史莱姆所以处理出最多加iii次的情况下每个史莱姆的最少获得费用。 然后枚举就好了。时间复杂度O(n2)O(n^2)O(n2)。
code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2100;
ll n,k,ans,a[N],f[N][N];
signed main()
{scanf(%lld%lld,n,k);for(ll i0;in;i)scanf(%lld,a[i]);for(ll i0;in;i){f[i][0]a[i];for(ll j1;jn;j)f[i][j]min(f[i][j-1],a[(i-jn)%n]);}ans1e18;for(ll i0;in;i){ll sum0;for(ll j0;jn;j)sumf[j][i];ansmin(ans,sumi*k);}printf(%lld\n,ans);return 0;
}AT2043 [AGC004C] AND Grid
https://www.luogu.com.cn/problem/AT2043
题目大意
给出一个n×mn\times mn×m的网格图满足四边上都没有’#’现在要求求出两个n×mn\times mn×m的网格图使得上面的’#‘四联通且两张图上’#的并恰好是给出的网格图。
1≤n,m≤5001\leq n,m\leq 5001≤n,m≤500
解题思路
突破口应该是四周没有’#’所以我们可以用四周来保证四联通然后从四周延伸’#过来。
对于第一张图我们左边铺满’#’奇数行除了最右边铺满’#’偶数行只在有原图有’#的位置铺。
第二张图相反的右边铺满’#’偶数行处理最左边铺满’#’奇数行在原图有’#的位置铺。
就好了。
code
#includebits/stdc.h
using namespace std;
const int N510;
int n,m;char s[N][N];
int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%s,s[i]1);for(int i1;in;i){putchar(#);if(i1||in)for(int j2;jm;j)putchar(.);else if(i1)for(int j2;jm;j)putchar((jm)?.:#);else for(int j2;jm;j)putchar(s[i][j]);putchar(\n);}putchar(\n);for(int i1;in;i){if(i1||in)for(int j1;jm;j)putchar(.);else if(!(i1))for(int j1;jm;j)putchar((j1)?.:#);else for(int j1;jm;j)putchar(s[i][j]);putchar(#);putchar(\n);}return 0;
}AT2044 [AGC004D] Teleporter
https://www.luogu.com.cn/problem/AT2044
题目大意
给出nnn个点的一棵基环外向树保证一号点在环上每次可以修改一个点的父亲可以是自己求最少修改次使得所有点的kkk级祖先都是111号点。
1≤n≤105,1≤k≤1091\leq n\leq 10^5,1\leq k\leq 10^91≤n≤105,1≤k≤109
解题思路
显然一号点一定要连自己因为环上必然只有一个点满足kkk级祖先是111所以改其他节点还不如改一号点。
然后问题就变成树上的了之间贪心到必须改的时候再改就好了。
时间复杂度O(n)O(n)O(n)
code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e510;
struct node{int to,next;
}a[N1];
int n,k,tot,ans,fa[N],ls[N],f[N];
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x){f[x]0;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa[x])continue;dfs(y);f[x]max(f[x],f[y]1);}if(fa[x]!1f[x]1k)ans,f[x]-1;return;
}
int main()
{scanf(%d%d,n,k);scanf(%d,fa[1]);if(fa[1]!1)ans;fa[1]1;for(int i2;in;i){scanf(%d,fa[i]);addl(fa[i],i);}dfs(1);printf(%d\n,ans);return 0;
}AT2045 [AGC004E] Salvage Robots
题目大意
n×mn\times mn×m的网格上有一些机器人和一个出口每次你可以让所有的机器人上/左/下/右移动出界的机器人算为死亡到达出口的机器人算为出逃求最多能救走多少个机器人。
1≤n,m≤1001\leq n,m\leq 1001≤n,m≤100
解题思路
设fu,d,l,rf_{u,d,l,r}fu,d,l,r表示所有机器人最多往上/下/左/右走了u/d/l/ru/d/l/ru/d/l/r步时最多能救多少机器人然后暴力转移即可。
时间复杂度O(n4)O(n^4)O(n4)
code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N105;
int n,m,rx,ry,ans,w[N][N],h[N][N];
short f[N][N][N][N];char s[N];
signed main()
{scanf(%d%d,n,m);for(int i1;in;i){scanf(%s,s1);for(int j1;jm;j){w[i][j]w[i-1][j](s[j]o);h[i][j]h[i][j-1](s[j]o);if(s[j]E)rxi,ryj;}}for(int u0;urx;u)for(int d0;dn-rx;d)for(int l0;lry;l)for(int r0;rm-ry;r){ansmax(ans,(int)f[u][d][l][r]);if(lrry-1)f[u][d][l1][r]max((int)f[u][d][l1][r],f[u][d][l][r]w[min(rxd,n-u)][ry-l-1]-w[max(rx-u-1,d)][ry-l-1]);if(lrm-ry)f[u][d][l][r1]max((int)f[u][d][l][r1],f[u][d][l][r]w[min(rxd,n-u)][ryr1]-w[max(rx-u-1,d)][ryr1]);if(udrx-1)f[u1][d][l][r]max((int)f[u1][d][l][r],f[u][d][l][r]h[rx-u-1][min(ryr,m-l)]-h[rx-u-1][max(ry-l-1,r)]);if(udn-rx)f[u][d1][l][r]max((int)f[u][d1][l][r],f[u][d][l][r]h[rxd1][min(ryr,m-l)]-h[rxd1][max(ry-l-1,r)]);}printf(%d\n,ans);return 0;
}
