P8121 题解

yzy1 · 2022-02-09 18:25:59 · 题解

这里是出题人官方题解。

Task 1

只有一颗子弹，所以向右或者向上移动一步就可以，但是由于题目限制 k=100，指令会重复 100 次，机器人会移动到画面之外而爆炸，所以我们需要在躲避子弹后回到原来的位置。

if(n==1)cout<<"401";
else cout<<"302";

Task 2

我们可以写一个子弹可视化的程序来辅助分析，下面是一个示例：

const int N = 2e6 + 9;
int n, m, b, d, k, maxc, p[5], X, Y, tp, cost;
struct B {
  int l, r, x, y, p, q;
} a[N];
list<B> now;

signed main() {
  ifstream fin("0.in");
  fin.tie(0);
  fin >> n >> m >> b >> d >> k >> maxc;
  char mp[n + 3][m + 3];
  rep (i, 0, 4)
    fin >> p[i];
  re (i, b)
    fin >> a[i].l >> a[i].r >> a[i].x >> a[i].y >> a[i].p >> a[i].q;
  cerr<<"end\n";
  char c;
  do c = getchar();
  while (c != '\n');
  sort(a + 1, a + b + 1, [](const B &a, const B &b) { return a.l < b.l; });
  re (t, d) {
    each (x, now)
      x.x += x.p, x.y += x.q;
    while (a[tp + 1].l == t) now.push_back(a[++tp]);
    memset(mp, '.', sizeof mp);
    each (x, now)
      if (0 <= x.x && x.x <= n && 0 <= x.y && x.y <= m) mp[x.x][x.y] = 'x';
    cerr << "time: " << t << '\n';
    per (i, min(m,100), 0) {
      rep (j, 0, min(n,100))
        putchar(mp[j][i]);
      putchar('\n');
    }
    for (auto it = now.begin(); it != now.end();) {
      if (it->r <= t || it->x < 0 || it->x > n || it->y < 0 || it->y > m)
        it = now.erase(it);
      else
        ++it;
    }
    char c;
    do c = getchar();
    while (c != '\n');
  }
  return 0;
}

通过可视化程序，我们发现一些子弹墙组成了一个空心矩形，而有一颗子弹一直在赶着机器人跑。且转动为顺时针或者逆时针。分别判断这两种情况，写一个沿着边缘转的程序即可。

注意数据中的 k \le 我们需要转的圈数。也就是我们需要手动循环多次，注意不要让代价超过 maxc。

Task 3

发现这个点 n,m 很小，且让我们输出的是最优方案，直接考虑 dp，设 dp(t,i,j) 为在 t 时刻走到 (i,j) 的最少代价，转移即可。复杂度看你的实现，可以是 O(n^2bd)，或者 O(nbd)。

re(t,d){
  memset(vis,0,sizeof vis);
  each (x, now){
    rep(i,0,n)rep(j,0,m)if(Ck(x.x,x.y,x.x+x.p,x.y+x.q,i,j))vis[i][j]=1;
    x.x += x.p, x.y += x.q;
  }
  while (a[tp + 1].l == t) now.push_back(a[++tp]),vis[now.back().x][now.back().y]=1;
  rep(i,0,n)rep(j,0,m)if(!vis[i][j])
    rep(di,0,4)if(Ck(i-DX[di],j-DY[di])){
      int nw=dp[t-1][i-DX[di]][j-DY[di]]+p[di];
      if(nw<dp[t][i][j])dp[t][i][j]=nw,lst[t][i][j]=di;
    }
  for (auto it = now.begin(); it != now.end();) {
    if (it->r <= t || it->x < 0 || it->x > n || it->y < 0 || it->y > m)
      it = now.erase(it);
    else
      ++it;
  }
}

Task 4

这些子弹数据全部都是随机的，且子弹比较稀疏。写个暴搜即可，一旦找到一种小于等于 maxc 的方案就输出。

我们发现静止的代价远低于移动的代价，所以暴搜的逻辑里要优先静止。

void Dfs(int t,int c,int X,int Y,vector<int>res){
  if(c>maxc)return;
  if(X<0||Y<0||X>n||Y>m)return;
  if(t==d){
    if(c<=maxc){
      ans=res,maxc=c;
      each(x,ans)cout<<x;
      cout<<'\n';
    }
    exit(0);
  }
  re(i,b)
    if(a[i].l==t&&a[i].x==X&&a[i].y==Y)return;
    else if(a[i].l<t&&t<=a[i].r&&
        Ck(a[i].x+(t-a[i].l-1)*a[i].p,
          a[i].y+(t-a[i].l-1)*a[i].q,
          a[i].x+(t-a[i].l)*a[i].p,
          a[i].y+(t-a[i].l)*a[i].q,X,Y))return;
  int rnk[]={0,1,2,3,4};
  sort(rnk,rnk+5,[](int a,int b){return p[a]<p[b];});
  shuffle(rnk+1,rnk+5,rnd);
  rep(ii,0,4){
    int i=rnk[ii];
    auto ress=res;ress.push_back(i);
    Dfs(t+1,c+p[i],X+dx[i],Y+dy[i],ress);
  }
}

Task 5

一些静止的子弹形成了一些迷宫，而且在最后一秒会给除了一个点外其他所有点来一个「全屏秒杀」。所以这几个 task 的目标就变成了「最少的移动步数移动到指定的目标点」。跑一个最短路就可以。注意开 long long。

bool vis[N];
bool ban[3333][3333];
int dis[N];
vector<pair<int,int>>e[N];

inline bool Ck(int x,int y){return 0 <= x && x <= n && 0 <= y && y <= m && !ban[x][y];}
inline int Id(int x,int y){return x*(m+1)+y;}

void Spfa(int s) {
  memset(dis,0x3f,sizeof dis);
  dis[s] = 0;
  queue<int> q;
  q.push(s);
  vis[s] = false;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = 0;
    each(i,e[u]){
      int v=i.first;
      if (dis[u] + i.second < dis[v]) {
        dis[v] = dis[u] + i.second;
        if (!vis[v]) q.push(v),vis[v] = true;
      }
    }
  }
}

signed main(){
  ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  cin>>n>>m>>b>>d>>k>>maxc;
  rep(i,0,4)cin>>p[i];
  re(i,b)cin>>a[i].l>>a[i].r>>a[i].x>>a[i].y>>a[i].p>>a[i].q;
  re(i,b)if(a[i].l==1)ban[a[i].x][a[i].y]=1;
  rep(i,0,n)rep(j,0,m)re(dir,4)if(Ck(i+DX[dir],j+DY[dir]))e[Id(i,j)].push_back({Id(i+DX[dir],j+DY[dir]),p[dir]});
  Spfa(0);
  memset(ban,0,sizeof ban);
  re(i,b)if(a[i].l==inf)ban[a[i].x][a[i].y]=1;
  int X=0,Y=0;
  rep(i,0,n)rep(j,0,m)if(!ban[i][j]){X=i,Y=j;break;}
  cout<<dis[Id(X,Y)]<<'\n';
  return 0;
}

Task 6

容易发现对于 i \in [1,b - 1]，第 i 个子弹一直会定格在 x_i 位置，在 r_i 时刻消失。又因为 k 很大，最优解显然是先定格一段时间，再向右走一格。经过缜密的计算，可以发现答案就是：\max_{i=1}^m\{\lfloor \dfrac{r_i}{x_i} \rfloor\}。

注意要开高精度。

Task 7

还是一堆静止的子弹，但是你发现这个 n,m 都特别大，而且这次的 k 不是 1 了，这东西好像没有什么好方法能做。实际上出题人也没有根据数据直接做的解法。解决这个 Task 需要从 gen 本身入手。

使用反编译软件进行破解，用 32 位以 PD 格式打开可执行文件，找到 main 函数进入，按下 F5 生成伪代码：

int __cdecl main(int argc, const char **argv, const char **envp)
{
  int result; // eax
  __main();
  freopen("0.in", "w", &__iob[1]);
  scanf("%d", &seed);
  if ( (unsigned int)(seed - 1) > 0x3FFFFFFE )
  {
    fprintf(&__iob[2], "Invalid seed\n");
    result = -1;
  }
  else
  {
    puts("100000 100000 300000 1000000000 100 1000");
    puts("999999999 1 1 1 1");
    GenAns();
    GenHintData();
    GenData();
    result = 0;
  }
  return result;
}

main 中调用了 GenAns（生成答案）、GenHintData（生成提示数据）、GenData（生成其它数据）三个函数。你会发现这个程序是先生成答案，再根据答案生成数据的。

再来看看 GenHintData：

int GenHintData(void)
{
  unsigned int v0; // ebx
  v0 = rnd();
  printf("1 1 ");
  printf("%d ", v0 >> 24);
  printf("%d ", BYTE2(v0));
  printf("%d ", BYTE1(v0));
  return printf("%d\n", (unsigned __int8)v0);
}

可以发现，该函数所做的就是生成一个随机数，然后分四段打印出来。

接着来看 GenAns：

int GenAns(void)
{
  signed int v0; // ebx
  int result; // eax
  int v2; // edx
  int v3; // edi
  v0 = 1;
  do
  {
    result = (rnd() & 3) + 1; // 生成 [1,4] 随机数
    ans[v0] = result;
    v2 = dword_84397C[v0] + dx[result]; // 移动后的 x 坐标
    X[v0] = v2;
    v3 = dword_47303C[v0] + dy[result]; // 移动后的 y 坐标
    Y[v0] = v3;
    if ( v2 < 0 || v3 < 0 ) // 检查是否超出画面
    {
      ans[v0] = 5 - result; // 取反方向（左下上右）->（右上下左）
      X[v0] = dword_84397C[v0] + dx[5 - result];
      result = dword_47303C[v0] + dy[5 - result];
      Y[v0] = result;
    }
    ++v0;
  }
  while ( v0 != 1001 ); // 循环 1000 次
  return result;
}

可以看到，反编译后的函数还是比较易读的，它用 rnd 函数生成了一个长度为 1000 的答案序列。

再来看看 rnd：

unsigned int rnd(void)
{
  unsigned int v0; // edx
  unsigned int result; // eax
  v0 = 32 * ((((seed << 13) ^ (unsigned int)seed) >> 17) ^ (seed << 13) ^ seed);
  result = v0 ^ (((seed << 13) ^ (unsigned int)seed) >> 17) ^ (seed << 13) ^ seed;
  seed ^= v0 ^ (((seed << 13) ^ (unsigned int)seed) >> 17) ^ (seed << 13);
  return result;
}

发现这就是个 Xorshift，其等同于 x^=x<<13,x^=x>>17,x^=x<<5。

现在问题变成了，根据一个生成的随机数，推算出一开始的 seed，进而推算出最开始生成的 1000 个随机数是什么。我们可以把每一个二进制位当成一个未知数，用高斯消元解异或方程组来根据下一个随机数解出上一个随机数。重复跑 1000 次即可得到最开始的 seed，然后模拟数据生成即可。

signed main(){
  ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  cin>>n>>m>>b>>d>>k>>maxc;
  rep(i,0,4)cin>>p[i];
  re(i,b)cin>>a[i].l>>a[i].r>>a[i].x>>a[i].y>>a[i].p>>a[i].q;
  seed=(a[1].x<<24)|(a[1].y<<16)|(a[1].p<<8)|a[1].q;
  per(i,1000,1)ans[i]=Rev()%4+1;
  re(i,1000){
    X[i]=X[i-1]+dx[ans[i]],Y[i]=Y[i-1]+dy[ans[i]];
    if(X[i]<0||Y[i]<0)ans[i]=5-ans[i],X[i]=X[i-1]+dx[ans[i]],Y[i]=Y[i-1]+dy[ans[i]];
    cout<<ans[i];
  }
  cout<<'\n';
  return 0;
}

Task 8

我们发现所有的子弹全都是从最右面往正左方发射且速度相同。而且我们只能向上走、向下走和静止不动。

我们可以认为子弹不动，而是相对的机器人在动。

那么问题就转化为了机器人每次可以从 (x,y) 开始移动，有 3 种移动方案：

移动到 (x+k,y)，前提是 (x,y)\sim(x+k) 之间没有子弹。
移动到 (x+k,y+1)，前提是 (x,y+1)\sim(x+k,y+1) 之间没有子弹。
移动到 (x+k,y-1)，前提是 (x,y-1)\sim(x+k,y-1) 之间没有子弹。

设 f(i,j) 为到达 (i,j) 的最小代价，那么转移就很显然了。

一共 O(nm) 个状态，每次转移前缀和判断合法，总时间复杂度为 O(nm)

#include <bits/stdc++.h>
#define fi first
#define sc second
using namespace std;
typedef pair<int,int> pi;
const int maxn=1205,inf=0x3f3f3f3f;
int f[2][maxn],n,m,b,d,p0,p1,p4,cnt,ans=inf,ls[maxn];
pi p[maxn*20];
bool book[maxn];
int main() {
    int x,y,z;
    scanf("%d%d%d%d%*d%*d",&n,&m,&b,&d);
    scanf("%d%d%*d%*d%d",&p0,&p1,&p4);
    for(int i=1; i<=b; i++) {
        scanf("%*d%*d%d%d%*d%d",&x,&y,&z),z=-z;
        if((y+z-1)/z<=d)p[++cnt]=pi((y+z-1)/z,x),ls[x]=max(ls[x],(y+z-1)/z);
        if(y%z==0&&y/z+1<=d)p[++cnt]=pi(y/z+1,x),ls[x]=max(ls[x],y/z+1);
    }
    sort(p+1,p+cnt+1),memset(f,0x3f,sizeof(f)),f[0][0]=0;
    int lst=1;
    for(int i=0; i<=n; i++)cout<<ls[i]<<" \n"[i==n];
    for(int i=1; i<=d; i++) {
        memset(book,0,sizeof(book));
        while(lst<=cnt&&p[lst].fi<=i)book[p[lst].sc]=1,lst++;
        int now=i&1,lst=now^1;
        memset(f[now],0x3f,sizeof(f[now]));
        for(int j=0; j<=n; j++) {
            if(book[j])continue;
            f[now][j]=min(inf,f[lst][j]+p0);
            if(j)f[now][j]=min(f[now][j],f[lst][j-1]+p4);
            if(j<n)f[now][j]=min(f[now][j],f[lst][j+1]+p1);
        }
        for(int j=0; j<=n; j++)if(ls[j]<i)ans=min(ans,f[now][j]);
        if(lst>cnt)break;
    }
    printf("%d",ans);
    return 0;
}