一、前言
6月份的“比赛荒”之后，洛谷举办了2021年07月月赛。这次我还是参加Div.2。
以下只讲我会做的题目（事实上也只会做一道，B题和C题都是暴力骗分）。
二、A：远古档案馆（Ancient Archive）
传送门：https://www.luogu.com.cn/problem/P7724?contestId=46177
首先，当空格数量为2~4时，初始方阵肯定可以经变换后与最终方阵相同，因为此时方块可以任意移动。
然后，当空格数量为0时，方块不可移动。此时，直接判定两个方阵是否相同即可。
最后是难点：当空格数量为1时的判断。
其实也不难，重复以下判断12遍：
如果空格在左上角，则将左下角的方格往上移；
如果空格在左下角，则将右下角的方格往左移；
如果空格在右下角，则将右上角的方格往下移；
如果空格在右上角，则将左上角的空格往右移。
每一步过后，判断两个方阵是否一致。如果一致，直接输出Yes。
如果移动了12次，还没有一致的情况，则输出No。
移动12次过后，方阵恰好形成一个循环。所以只用移动12次。
$AC$ 代码：
#include<cstdio>
using namespace std;
int start_graph[3][3],end_graph[3][3];
int space_count;
int space_x,space_y;
bool equal(int a[3][3],int b[3][3])
{
for(int i=1;i<=2;i++)
{
for(int j=1;j<=2;j++)
{
if(a[i][j]!=b[i][j])
{
return false;
}
}
}
return true;
}
int main()
{
for(int i=1;i<=2;i++)
{
for(int j=1;j<=2;j++)
{
scanf("%d",&start_graph[i][j]);
if(!start_graph[i][j])
{
space_count++;
space_x=i;
space_y=j;
}
}
}
for(int i=1;i<=2;i++)
{
for(int j=1;j<=2;j++)
{
scanf("%d",&end_graph[i][j]);
}
}
if(space_count<=4&&space_count>=2)
{
printf("Yes\n");
return 0;
}
else if(space_count==0)
{
if(equal(start_graph,end_graph))
{
printf("Yes\n");
}
else
{
printf("No\n");
}
return 0;
}
else
{
int oper_graph[3][3];
for(int i=1;i<=2;i++)
{
for(int j=1;j<=2;j++)
{
oper_graph[i][j]=start_graph[i][j];
}
}
for(int i=1;i<=12;i++)
{
if(space_x==1&&space_y==1)
{
oper_graph[1][1]=oper_graph[2][1];
oper_graph[2][1]=0;
if(equal(oper_graph,end_graph))
{
printf("Yes\n");
return 0;
}
space_x=2;
}
else if(space_x==2&&space_y==1)
{
oper_graph[2][1]=oper_graph[2][2];
oper_graph[2][2]=0;
if(equal(oper_graph,end_graph))
{
printf("Yes\n");
return 0;
}
space_y=2;
}
else if(space_x==2&&space_y==2)
{
oper_graph[2][2]=oper_graph[1][2];
oper_graph[1][2]=0;
if(equal(oper_graph,end_graph))
{
printf("Yes\n");
return 0;
}
space_x=1;
}
else if(space_x==1&&space_y==2)
{
oper_graph[1][2]=oper_graph[1][1];
oper_graph[1][1]=0;
if(equal(oper_graph,end_graph))
{
printf("Yes\n");
return 0;
}
space_y=1;
}
}
}
printf("No\n");
return 0;
}三、B：珍珠帝王蟹（Crab King）
对于本题，我同时使用了暴力算法和非暴力算法。
对于Subtask1，由于数据较小，可以使用 $DFS$ 暴力搜索。
对于Subtask2，由于 $v>0$，可以证明，先加后乘是最优的选择。
这就能拿 $48$ 分了。
代码：
#include<cstdio>
#include<algorithm>
using namespace std;
struct pearl_object
{
char op;
long long num;
}add_pearl[100005],mul_pearl[100005],pearl[100005];
int add_cnt,mul_cnt;
int n;
long long ans=-0x7fffffffff;
bool flag=true;
int dfs_array[100005];
bool visit[100005];
void dfs(int x)
{
if(x>n)
{
long long temp_ans=0;
for(int i=1;i<=n;i++)
{
if(pearl[dfs_array[i]].op=='+')
{
temp_ans+=pearl[dfs_array[i]].num;
}
else
{
temp_ans*=pearl[dfs_array[i]].num;
}
}
//printf("%lld\n",temp_ans);
if(temp_ans>ans)
{
ans=temp_ans;
}
}
for(int i=1;i<=n;i++)
{
if(!visit[i])
{
visit[i]=true;
dfs_array[x]=i;
dfs(x+1);
visit[i]=false;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
char op[2];
long long num;
scanf("%s%lld",&op,&num);
if(num<=0)
{
flag=false;
}
if(op[0]=='+')
{
add_cnt++;
add_pearl[add_cnt].op=op[0];
add_pearl[add_cnt].num=num;
}
else
{
mul_cnt++;
mul_pearl[mul_cnt].op=op[0];
mul_pearl[mul_cnt].num=num;
}
}
if(flag)
{
ans=0;
for(int i=1;i<=add_cnt;i++)
{
ans+=add_pearl[i].num;
}
for(int i=1;i<=mul_cnt;i++)
{
ans*=mul_pearl[i].num;
ans%=998244353;
}
if(ans<0)
{
ans=(ans+998244353)%998244353;
}
printf("%lld\n",ans);
}
else
{
for(int i=1;i<=add_cnt;i++)
{
pearl[i].op=add_pearl[i].op;
pearl[i].num=add_pearl[i].num;
}
for(int i=1;i<=mul_cnt;i++)
{
pearl[i+add_cnt].op=mul_pearl[i].op;
pearl[i+add_cnt].num=mul_pearl[i].num;
}
dfs(1);
printf("%lld\n",ans);
}
return 0;
}四、C：天体探测仪（Astral Detector）
本题我也只能用暴力算法了。
代码：
#include<cstdio>
#include<cstring>
using namespace std;
int n;
int input[805][805];
bool visit[805];
int dfs_array[805];
bool answer_flag;
int get_min(int index,int length)
{
register int minn=input[1][dfs_array[index]];
for(register int i=2;i<=length;i++)
{
if(minn>input[1][dfs_array[i+index-1]])
{
minn=input[1][dfs_array[i+index-1]];
}
}
return minn;
}
void dfs(int x)
{
if(answer_flag)
{
return;
}
if(x>n)
{
for(register int i=2;i<=n;i++)
{
bool appear[n];
memset(appear,0,sizeof(appear));
for(register int j=1;j<=n-i+1;j++)
{
int minn=get_min(j,i);
bool flag=false;
for(register int k=1;k<=n-i+1;k++)
{
if(input[i][k]==minn&&!appear[k])
{
appear[k]=true;
flag=true;
break;
}
}
if(!flag)
{
return;
}
}
}
for(register int i=1;i<=n;i++)
{
printf("%d ",input[1][dfs_array[i]]);
}
printf("\n");
answer_flag=true;
return;
}
//printf("Test\n");
for(register int i=1;i<=n;i++)
{
if(answer_flag)
{
return;
}
if(!visit[i])
{
visit[i]=true;
dfs_array[x]=i;
dfs(x+1);
visit[i]=false;
}
}
}
int main()
{
scanf("%d",&n);
for(register int i=1;i<=n;i++)
{
for(register int j=1;j<=n-i+1;j++)
{
scanf("%d",&input[i][j]);
}
}
dfs(1);
return 0;
}五、总分
本场比赛，我一共获得了 $174$ 分，排名第 $370$ 名。
