前言
\(F\)不會做，正解好神仙，爬了
正題
AT2041 [AGC004A] Divide a Cuboid
https://www.luogu.com.cn/problem/AT2041
題目大意
一個\(A*B*C\)的立方體，分成兩個長方體使得邊長都是整數而且體積差最小。
\(1\leq A,B,C\leq 10^9\)
解題思路
如果有一邊是偶數之間這邊開始分，不然就找一邊分的最小就好了。
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll a,b,c;
signed main()
{
scanf("%lld%lld%lld",&a,&b,&c);
if((a&1)&&(b&1)&&(c&1))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
\(n\)個顔色的史萊姆，第\(i\)隻可以花費\(a_i\)獲得，或者花費\(k\)使得所有獲得的史萊姆顔色加一後模\(n\)，求最少花費多少能獲得所有顔色的史萊姆。
\(1\leq n\leq 2000,1\leq a_i,k\leq 10^9\)
顯然我們可以通過控制獲得的順序使得加一的次數就是次數最多的那個史萊姆，是以處理出最多加\(i\)次的情況下每個史萊姆的最少獲得費用。
然後枚舉就好了。時間複雜度：\(O(n^2)\)。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=2100;
ll n,k,ans,a[N],f[N][N];
signed main()
{
scanf("%lld%lld",&n,&k);
for(ll i=0;i<n;i++)
scanf("%lld",&a[i]);
for(ll i=0;i<n;i++){
f[i][0]=a[i];
for(ll j=1;j<n;j++)
f[i][j]=min(f[i][j-1],a[(i-j+n)%n]);
}
ans=1e18;
for(ll i=0;i<n;i++){
ll sum=0;
for(ll j=0;j<n;j++)
sum+=f[j][i];
ans=min(ans,sum+i*k);
}
printf("%lld\n",ans);
return 0;
}
AT2043 [AGC004C] AND Grid
https://www.luogu.com.cn/problem/AT2043
給出一個\(n\times m\)的網格圖，滿足四邊上都沒有'#'，現在要求求出兩個\(n\times m\)的網格圖使得上面的'#'四聯通且兩張圖上'#'的并恰好是給出的網格圖。
\(1\leq n,m\leq 500\)
突破口應該是四周沒有'#'，是以我們可以用四周來保證四聯通，然後從四周延伸'#'過來。
對于第一張圖我們左邊鋪滿'#'，奇數行除了最右邊鋪滿'#'，偶數行隻在有原圖有'#'的位置鋪。
第二張圖相反的右邊鋪滿'#'，偶數行處理最左邊鋪滿'#'，奇數行在原圖有'#'的位置鋪。
就好了。
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m;char s[N][N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
for(int i=1;i<=n;i++){
putchar('#');
if(i==1||i==n)
for(int j=2;j<=m;j++)putchar('.');
else if(i&1)
for(int j=2;j<=m;j++)putchar((j==m)?'.':'#');
else
for(int j=2;j<=m;j++)putchar(s[i][j]);
putchar('\n');
}
putchar('\n');
for(int i=1;i<=n;i++){
if(i==1||i==n)
for(int j=1;j<m;j++)putchar('.');
else if(!(i&1))
for(int j=1;j<m;j++)putchar((j==1)?'.':'#');
else
for(int j=1;j<m;j++)putchar(s[i][j]);
putchar('#');putchar('\n');
}
return 0;
}
AT2044 [AGC004D] Teleporter
https://www.luogu.com.cn/problem/AT2044
給出\(n\)個點的一棵基環外向樹，保證一号點在環上，每次可以修改一個點的父親（可以是自己），求最少修改次使得所有點的\(k\)級祖先都是\(1\)号點。
\(1\leq n\leq 10^5,1\leq k\leq 10^9\)
顯然一号點一定要連自己，因為環上必然隻有一個點滿足\(k\)級祖先是\(1\)，是以改其他節點還不如改一号點。
然後問題就變成樹上的了，之間貪心到必須改的時候再改就好了。
時間複雜度：\(O(n)\)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct node{
int to,next;
}a[N<<1];
int n,k,tot,ans,fa[N],ls[N],f[N];
void addl(int x,int y){
a[++tot].to=y;
a[tot].next=ls[x];
ls[x]=tot;return;
}
void dfs(int x){
f[x]=0;
for(int i=ls[x];i;i=a[i].next){
int y=a[i].to;
if(y==fa[x])continue;
dfs(y);f[x]=max(f[x],f[y]+1);
}
if(fa[x]!=1&&f[x]+1>=k)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 i=2;i<=n;i++){
scanf("%d",&fa[i]);
addl(fa[i],i);
}
dfs(1);
printf("%d\n",ans);
return 0;
}
AT2045 [AGC004E] Salvage Robots
\(n\times m\)的網格上有一些機器人和一個出口，每次你可以讓所有的機器人上/左/下/右移動，出界的機器人算為死亡，到達出口的機器人算為出逃，求最多能救走多少個機器人。
\(1\leq n,m\leq 100\)
設\(f_{u,d,l,r}\)表示所有機器人最多往上/下/左/右走了\(u/d/l/r\)步時最多能救多少機器人，然後暴力轉移即可。
時間複雜度：\(O(n^4)\)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=105;
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 i=1;i<=n;i++){
scanf("%s",s+1);
for(int j=1;j<=m;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')rx=i,ry=j;
}
}
for(int u=0;u<rx;u++)
for(int d=0;d<=n-rx;d++)
for(int l=0;l<ry;l++)
for(int r=0;r<=m-ry;r++){
ans=max(ans,(int)f[u][d][l][r]);
if(l+r<ry-1)f[u][d][l+1][r]=max((int)f[u][d][l+1][r],f[u][d][l][r]+w[min(rx+d,n-u)][ry-l-1]-w[max(rx-u-1,d)][ry-l-1]);
if(l+r<m-ry)f[u][d][l][r+1]=max((int)f[u][d][l][r+1],f[u][d][l][r]+w[min(rx+d,n-u)][ry+r+1]-w[max(rx-u-1,d)][ry+r+1]);
if(u+d<rx-1)f[u+1][d][l][r]=max((int)f[u+1][d][l][r],f[u][d][l][r]+h[rx-u-1][min(ry+r,m-l)]-h[rx-u-1][max(ry-l-1,r)]);
if(u+d<n-rx)f[u][d+1][l][r]=max((int)f[u][d+1][l][r],f[u][d][l][r]+h[rx+d+1][min(ry+r,m-l)]-h[rx+d+1][max(ry-l-1,r)]);
}
printf("%d\n",ans);
return 0;
}