D1T1 季风

将位移拆成两类考虑：一类是风被动产生的，一类是人主动产生的。

前者我们以 \((x,y)\) 为起点考虑位移，后者以 \((0,0)\) 为起点考虑位移。

枚举 \(m\bmod n\)，记 \(N=\lfloor\frac mn\rfloor\)。

若存在余数为 \(i\) 的合法步数，等价于存在正整数 \(N\) 使得 \(|Fx(N)| + |Fy(N)| \le Fn(N)\) ，其中 \(Fx,Fy,Fn\) 均为关于 \(N\) 的一次函数。具体地，记前 \(i\) 步位移为 \(s\)，一轮 \(n\) 步位移为 \(S\)，\(Fx(N) = S_xN + s_x + T_x\)，\(Fy(N) = S_yN + s_y + T_y\)，\(Fn(N) = knN + ki\)。

将绝对值拆开解一元一次不等式即可求出 \(N\) 的范围，从而得到余数为 \(i\) 时的最小 \(m\)。

代码很短很好写。

#define int long long
using pii=pair<int,int>;
il pii operator+(pii x,pii y){return pii(x.x+y.x,x.y+y.y);}
il pii operator+=(pii&x,pii y){return x=x+y;}
il pii operator-(pii x,pii y){return pii(x.x-y.x,x.y-y.y);}
il pii operator-=(pii&x,pii y){return x=x-y;}
il pii operator*(pii x,pii y){return pii(max(x.x,y.x),min(x.y,y.y));} // cap
il pii operator*=(pii&x,pii y){return x=x*y;}
const int inf=1LL<<60;
il void Solve()
{
  int n,k,X,Y;
  rd(n),rd(k),rd(X),rd(Y);
  pii d(X,Y),ds{};
  ve<pii>a(n);
  for(int i=0;i<n;++i) rd(a[i].x),rd(a[i].y),ds-=a[i];
  int ans=inf;
  for(int i=0;i<=n;++i) {
    pii fx(ds.x,d.x),fy(ds.y,d.y),fn(n*k,i*k),rag(0,inf);
    // |fx(N)| + |fy(N)| \le fn(N)
    auto F=[&](pii x)->pii // g(x) \ge 0 => x \in [l,r]
    {
      if(x.x) {
        if(x.x>0) return pii(ceil((db)-x.y/x.x),inf);
        else return pii(-inf,floor((db)-x.y/x.x));
      }
      else return x.y<0?pii(inf,-inf):pii(-inf,inf);
    };
    for(pii g:{fn-fx-fy,fn-fx+fy,fn+fx-fy,fn+fx+fy}) rag*=F(g);
    if(rag.x<=rag.y) {
      cn(ans,rag.x*n+i);
    }
    if(i<n) d-=a[i];
  }
  wrt(ans<inf?ans:-1,'\n');
  return;
}

\(\color{green}{\checkmark}\)

D1T2 魔法手杖

显然可以二分答案，然后在 Trie 树上贪心地 check，有一个 \(O(nk^2)\) 的暴力。

优化就是把二分改成倍增状物，或者是建压位 Trie 均可做到 \(O(nk)\)。

代码运营代写。

D1T3 虫洞

\(m=1,k=1\) 就是 \(l^c\)，\(l\) 为环长，\(c\) 为其出现次数。

\(k=1\)，可以将同构的连通分量视为等价类，缩等价类后即为 \(m=1\)。

对于一个等价类考虑，最终一定形如若干等价类被缩在一起。只需计算 \(f(i)\) 为 \(i\) 个等价类 \(k\) 次后缩在一起的方案数，转移是个背包状物。

然后矩快优化转移即可。

代码运营代写。

D2T1 迷宫守卫

考虑第一位怎么确定。

\(f_{u,i}\) 表示 \(u\) 子树中，让最小字典序 \(\ge i\) 的最小代价。
转移类似归并排序是容易的。

然后在 \(f_1\) 数组上二分即可知道首位取值。

取完首位后，原树会被割成若干个规模更小的满二叉树。递归求解即可。

具体地，贪心地，我们找到首位对应的叶子，先扣去最小代价，然后不断跳父亲，如果从左子树到达父亲，就考虑一下父亲是否必须被点亮，然后求解自己兄弟的子问题即可。

记得及时更新代价。

复杂度 \(O(n2^n)\)。

const LL infll=1ll<<60;
il void Solve()
{
  int n;rd(n);
  int m=1<<n,M=m<<1;
  ve<int>p(m|1);
  ve<LL>a(M);
  ve<ve<int>>b(M);
  for(LL&x:a) rd(x);
  for(int i=m;i<M;++i) p[--a[i]]=i;
  ve<ve<LL>>f(M);
  #define ls (u<<1)
  #define rs (ls|1)
  function<void(int)>dfs=[&](int u)
  {
    if(u>=m) {
      f[u]=ve<LL>{0,infll},b[u].pb(a[u]);
      return;
    }
    dfs(ls),dfs(rs),b[u].resize(b[ls].size()+b[rs].size());
    f[u].assign(b[u].size()+1,infll);
    auto _=[&]
    {
      int p=0;
      ve<pii>a(b[u].size());
      for(int i=0;i<b[ls].size();++i) a[p++]=pii(b[ls][i],i);
      for(int i=0;i<b[rs].size();++i) a[p++]=pii(b[rs][i],~i);
      return sort(all(a)),a;
    }();
    int c[3]{};
    for(auto[w,id]:_) {
      if(id>=0) {
        cn(f[u][c[2]],f[ls][c[0]]+min(a[u],f[rs][c[1]]));
      }
      else {
        cn(f[u][c[2]],f[ls][c[0]]+f[rs][c[1]]);
      }
      ++c[id<0],b[u][c[2]++]=w;
    }
    for(int i=f[u].size()-1;i;--i) cn(f[u][i-1],f[u][i]);
    return;
  };
  dfs(1);
  #undef ls
  #undef rs
  function<ve<int>(int,LL&)>solve=[&](int u,LL&K)
  {
    if(u>=m) return ve<int>{a[u]};
    int it=upper_bound(all(f[u]),K)-begin(f[u]);
    ve<int>ans{b[u][--it]};
    K-=f[u][it];
    for(int v=p[ans[0]];v^u;v>>=1) {
      LL c=f[v^1][upper_bound(all(b[v^1]),ans[0])-begin(b[v^1])];
      if(v&1) K+=c;
      else {
        K+=min(a[v>>1],c);
        if(c>K) K-=a[v>>1];
      }
      for(int x:solve(v^1,K)) ans.pb(x);
    }
    return ans;
  };
  for(int x:solve(1,a[0])) wrt(x+1,' ');
  wrt('\n');
  return;
}

\(\color{green}{\checkmark}\)

D2T2 重塑时光

咕。

D2T3 最长待机

咕。

标签：pii,return,省选,2024,int,解题,il,operator,ls
From： https://www.cnblogs.com/BK0717/p/18061794

联合省选 2024 解题报告