AGC004 做题记录
A
边长中有偶数就可以平分输出 \(0\) ，否则输出最小的一面的方块数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | #include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int main(){
ll a=read(),b=read(),c=read();
if(a&1&&b&1&&c&1){
printf("%lld\n",min(a*min(b,c),b*c));
}else puts("0");
return 0;
}
|
B
妙贪心（.
假设我们吟唱了 \(k\) 次魔法后完成收集，那么 \(i\) 色史莱姆有可能为 \([i-k,i]\) （下标对 \(N\) 取模）的任意一个史莱姆变化而来，最小代价即为区间中 \(a_j\) 的最小值。
时间复杂度：\(O(N^2)\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | #include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N=2e3+5;
ll n,x,a[N],M[N][N];
ll ans;
int main(){
n=read(),x=read();
rep(i,1,n)M[i][i]=a[i]=read();
rep(i,1,n)rep(j,i+1,n){
M[i][j]=min(M[i][j-1],a[j]);
}
ans=9e18;
rep(i,0,n){
ll cost=i*x;
rep(j,1,n){
int last=j-i;
if(last<=0)cost+=min(M[last+n][n],M[1][j]);
else cost+=M[last][j];
}
ans=min(ans,cost);
}
printf("%lld\n",ans);
return 0;
}
|
C
构造题通常需要用上给定的玄学条件。比如这道题中的「保证边界上不会被涂色」。因为我们想找通解，并不能依赖于紫色格子的位置。所以想到先构造没有交集的红色和蓝色格子，并且要保证四连通且与紫色格子连通。最上面一行和所有奇数列填红色，最下面一行和所有偶数列填蓝色（像两把梳子上下卡在一起）。这种构造显然满足四连通，最后取颜色集合与紫色格子的并集即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 | #include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m;
char s[505][505];
int main(){
n=read(),m=read();
rep(i,1,n)scanf("%s",s[i]+1);
rep(i,1,n){
rep(j,1,m){
if(i==n)printf(".");
else if(i==1||j&1||s[i][j]=='#')printf("#");
else printf(".");
}
puts("");
}
puts("");
rep(i,1,n){
rep(j,1,m){
if(i==1)printf(".");
else if(i==n||j%2==0||s[i][j]=='#')printf("#");
else printf(".");
}
puts("");
}
return 0;
}
|
D
给了一个基环内向树，并且保证 \(1\) 号节点在环上。如果环长不为 \(1\) （即不是 \(1\) 号节点的自环），那么不难发现环上的点到达 \(1\) 号点的次数无法都恰好为 \(K\) 。于是必须断掉原边改成自环。
剩下 \(N-1\) 条边构成一棵树，我们想选一些边把它连向 \(1\) ，这个操作会把原树分成几颗树，且要满足深度不超过 \(K-1\) 。注意到距离不到 \(K\) 的节点可以提前到达 \(1\) 之后绕自环跑，满足要求。贪心统计答案即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | #include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N=1e5+5;
int n,k,ans,a[N];
vector<int> G[N];
int dfs(int u,int dep){
int ret=dep;//当前深度
for(int v:G[u]){
ret=max(ret,dfs(v,dep+1));//子树中节点最深的深度
}
if(a[u]!=1&&ret-dep==k-1)return ++ans,0;//如果为k-1则断边并且新深度为0
return ret;
}
int main(){
n=read(),k=read();
rep(i,1,n)a[i]=read();
if(a[1]!=1)ans=a[1]=1;
rep(i,2,n)G[a[i]].push_back(i);
dfs(1,0);printf("%d\n",ans);
return 0;
}
|
E
dp神题。
首先观察到出口在棋盘上的相对位置不变，不妨把机器人的运动转化成出口带着棋盘的运动，掉下棋盘的棋子就没了。不妨观察一下出口第一次移动带来的影响，向上走一步会把最下面一行的机器人消除，同时有可能救到当前位置的机器人。其他方向移动的结果也是类似的。
第二个重要的观察是我们并不需要知道出口运动的全过程，只需要知道四个方向分别走到过多远。具体地，我们设四个方向分别走了 \(l,r,u,d\) 距离。在出口仍在这个范围活动，不改变这个状态的情况下，并不会有新的机器人掉下棋盘。而出口每走一步，最多将 \(l,r,u,d\) 中的任意一个 \(+1\) 来改变状态，而这可以 \(dp\) ！
定义 \(f_{l,r,u,d}\) 为四个方向分别走了 \(l,r,u,d\) 距离后救到机器人的最大值。如果某个方向还有机器人，那么就可以朝这个方向扩展。由于 \(l,r,u,d\) 本质上是框柱了一个矩形，每次扩展也一定是行或列上连续的一段，我们可以用前缀和优化。最后注意到本题卡空间，而答案值很小，我们可以用 \(short\) 存。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 | #include <bits/stdc++.h>
#define rep(i,a,b) for(i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m,x,y,i,j,l,r,u,d;
short f[105][105][105][105],s[105][105][2],ans;
char a[105];
inline void Max(short &x,const short &y){if(y>x)x=y;}
inline short Sum(int i,int j,int x,bool op){
if(!op)return s[i][x][op]-s[j][x][op];
return s[x][i][op]-s[x][j][op];
}
int main(){
n=read(),m=read();
rep(i,1,n){
scanf("%s",a+1);
rep(j,1,m){
if(a[j]=='E')x=i,y=j;
s[i][j][0]=s[i-1][j][0]+(a[j]=='o');
s[i][j][1]=s[i][j-1][1]+(a[j]=='o');
}
}
rep(l,0,y-1)rep(r,0,m-y)rep(u,0,x-1)rep(d,0,n-x){
ans=max(ans,f[l][r][u][d]);
if(l+r<y-1)Max(f[l+1][r][u][d],f[l][r][u][d]+Sum(min(x+d,n-u),max(x-u-1,d),y-l-1,0));
if(l+r<m-y)Max(f[l][r+1][u][d],f[l][r][u][d]+Sum(min(x+d,n-u),max(x-u-1,d),y+r+1,0));
if(u+d<x-1)Max(f[l][r][u+1][d],f[l][r][u][d]+Sum(min(y+r,m-l),max(y-l-1,r),x-u-1,1));
if(u+d<n-x)Max(f[l][r][u][d+1],f[l][r][u][d]+Sum(min(y+r,m-l),max(y-l-1,r),x+d+1,1));
}
printf("%d\n",(int)ans);
return 0;
}
|