Codeforces Round #766 (Div. 2)

\(\color{Green}{★}\) 表示赛时做出。
\(\color{Yellow}{★}\) 表示赛后已补。
\(\color{Red}{★}\) 表示 \(\text{To\ be\ solved}\)。

VP

A. Not Shading

\(\color{Gray}{800}\) \(\color{Green}{★}\)

Description

给定一个 01 矩阵，每次能将有 1 的一列或一行全染成 1。

求问让给定位置变为 1 的最小操作次数。

Solution

分类讨论。

• 所求位置本来就是 1，输出 0.
• 所求位置所在行或列有 1，输出 1.
• 矩阵中有 1，输出 2.
• 输出 -1。

思路不难出，码量对于 A 略大。

void work(){
  int n,m,x,y;cin>>n>>m>>x>>y;
  vector<string>a(n);
  for(auto &i:a) cin>>i;
  if(a[x-1][y-1]=='B') return cout<<"0\n",void();
  bool f1=0,f2=0;
  L(i,0,m-1) f1|=(a[x-1][i]=='B');
  L(i,0,n-1) f1|=(a[i][y-1]=='B');
  if(f1) return cout<<"1\n",void();
  L(i,0,n-1) L(j,0,m-1) f2|=(a[i][j]=='B');
  cout<<(f2?2:-1)<<'\n';
}

B. Not Sitting

\(\color{Green}{1300}\) \(\color{Green}{★}\)

Description

有大小为 \(n \times m\) 的网格图，A 可以先将 \(k\) 个位置涂上色，\(B,A\) 先后选择一个位置，要求 \(B\) 选择的位置未上色。

\(B\) 希望尽可能接近 \(A\)，\(A\) 希望尽可能远离 \(B\)，对于 \(k \in [0,n \cdot m -1]\)，求 \(A,B\) 之间的曼哈顿距离。

Solution

• \(B\) 要接近 \(A\)，显然最优策略就是坐中心；
• \(A\) 要远离 \(B\)，显然最优策略就是坐四角。

问题转化为每个点到四角的距离最大值。
全部压入一个数组，排序后输出即可。

void work(){
  cin>>n>>m;a.clear();L(i,1,n) L(j,1,m) 
    a.pb(max({i+j-2,i-1+m-j,n-i+j-1,n-i+m-j}));
  a.resize(n*m);sort(all(a));
  for(int i:a) cout<<i<<' ';cout<<'\n';
}

C. Not Assigning

\(\color{Cyan}{1400}\) \(\color{Green}{★}\)

Description

给定一棵 \(n\) 个节点的树，要求构造树上所有边和相邻边对的权值和都是质数或输出无解。

Solution

首先，如果两个质数的和仍是质数，则其中之一必然是 \(2\)。

所以，如果一个节点的度数超过 \(2\)，必然无解，因为肯定会出现奇数相加的情况。

否则，dfs 遍历整棵树，对于每条边，分别用类似黑白染色的方式，赋值为 \(2,x\)(\(x\) 是质数，且 \(x+2\) 也是质数)

一开始看错题，以为质数不能重复，白亏了两个 dfs。

void dfs(int u,int fa,int x){
  for(pi v:g[u]) if(F(v)^fa)
      ans[S(v)]=x,dfs(F(v),u,x^1);
}void work(){
  cin>>n;L(i,1,n) g[i].clear();
  int rt,x,y,m=0;
  L(i,2,n) cin>>u>>v,g[u].pb({v,i}),g[v].pb({u,i});
  L(i,1,n){
    if(si(g[i])==1) rt=i;
    if(si(g[i])>2) return cout<<"-1\n",void();
  }dfs(rt,0,2);L(i,2,n) cout<<ans[i]<<" \n"[i==n];
}

D. Not Adding

\(\color{Purple}{1900}\) \(\color{Green}{★}\)

Description

给定一个长度为 \(n\) 的序列 \(\left\{ a_1,a_2,\dots,a_n \right\}\)。

每次操作可以选择两个数 \(a_i,a_j\)，满足 \(\gcd(a_i,a_j)\) 不在序列中，将 \(\gcd(a_i,a_j)\) 加入序列。

求问最多的操作次数。

\(n \le 10^6,a_i \le 10^6\)

Solution

注意到 \(a_i\) 的值域范围很小，而且加入的数不会比原先的数大，所以完全可以枚举每个数是否在 \(a\) 中出现。

因为有 \(\gcd(\gcd(a_i,a_j),a_k) = \gcd(a_i,a_j,a_k)\)，所以该问题的本质是求：从原序列中选出一个子序列，能够产生的 \(\gcd\) 有多少种。

对于每个值，直接枚举所有可能的倍数，并检查这些倍数的 \(\gcd\) 是否为当前数即可。

bool vis[N];int ans,f[N];
signed main(){
  FST;int n;cin>>n;int a;
  L(i,1,n) cin>>a,vis[a]=1,f[a]=a;
  L(i,1,1e6){
    ll(j,i,1e6,i) f[i]=__gcd(f[i],f[j]);
    if(f[i]==i&&!vis[i]) ans++;
  }cout<<ans;
}

E. Not Escaping

\(\color{Gold}{2200}\) \(\color{Yellow}{★}\)

Description

有一个 \(n \times m\) 的网络，要求从 \((1,1)\) 移动到 \((n,m)\)。

无法直接在竖直方向移动，在第 \(i\) 行横向移动每个单位扣除 \(x_i\) 的生命。

另有 \(k\) 个梯子，两端分别在 \((a,b),(c,d)\)，攀爬可以恢复 \(h\) 的生命，不能回溯。

求问最小扣除的生命，或报告无解。

\(n,m,k \le 10^5\)

Solution

本题有一个很显然的思路，就是直接建图跑最短路，并且忽略掉那些平凡的节点。

因为有负权边，所以得用 SPFA，但是朴素的 SPFA 过不去，要加一些奇技淫巧去优化。详见 CF 讨论区和 Luogu 题解区。

考虑 DP。

还是像最短路那样，忽略掉除了起点、终点和所有梯子的端点之外的平凡点，这样就只剩下最多 \(2\cdot k+2\) 个点。

设 \(f_i\) 表示到达编号为 \(i\) 的节点时的最大生命。

因为题目要求不走回头路，所以可以按楼层递增，逐层进行 DP。

然后考虑 DP 的转移： (赛时就蚌在这)

对于某个点，显然有两种到达的方式，一种是同一层内的其他节点，另一种是通向这个节点的梯子。

• 通过同层其他节点转移

此时可以采用填表法进行 DP，转移方程为 \(f_i =\max\left( f_i,f_j-dis_{i,j}\times x_{c} \right)\)。

因为有左右两个转移方向，所以要正反扫两遍进行转移。

• 通过梯子转移

此时可以采用 刷表法进行 DP，转移方程为 \(f_{v_i} = \max\left( f_{v_i},f_i + h \right)\)。

因为题目要求最小损失，所以最后输出 \(-f_{ed}\) 即可。

int n,m,k,pd,a,b,c,d,h;
vector<pi>g[N];pi nt[N];
int x[N],f[N];
void work(){
  rd(n,m,k);pd=0;
  L(i,1,n) rd(x[i]),g[i].clear();
  g[1].pb({1,++pd});
  L(i,1,k){
    rd(a,b,c,d,h);
    g[a].pb({b,++pd});nt[pd]={pd+1,h};
    g[c].pb({d,++pd});nt[pd]={0,0};
  }g[n].pb({m,++pd});
  L(i,1,pd) f[i]=-INF;f[1]=0;
  L(i,1,n){
    sort(all(g[i]));
    L(j,1,si(g[i])-1) f[S(g[i][j])]=max(f[S(g[i][j])],
      f[S(g[i][j-1])]-(F(g[i][j])-F(g[i][j-1]))*x[i]);
    R(j,si(g[i])-2,0) f[S(g[i][j])]=max(f[S(g[i][j])],
      f[S(g[i][j+1])]-(F(g[i][j+1])-F(g[i][j]))*x[i]);
    for(pi x:g[i]) if(f[S(x)]!=-INF&&F(nt[S(x)])!=0)
      f[F(nt[S(x)])]=max(f[F(nt[S(x)])],f[S(x)]+S(nt[S(x)]));
  }if(f[pd]==-INF) wr("NO ESCAPE\n");else wr(-f[pd],'\n');
}

F. Not Splitting

\(\color{Red}{2700}\) \(\color{Yellow}{★}\)

Description

定义一个元素是由方格图中相邻方格组成的二元组。

称一个由若干元素组成的数组是强的，当且仅当存在一种方案，可以沿方格纸上的格线将方格纸分为两个全等的部分，使得数组中的每一个元素中包含的两个方格都处于同一部分。

给定一个 \(k\times k\) 的方格纸和 \(n\) 个元素，请求出至少需要删除多少个元素，才能使得剩余的元素组成的数组是强的。

\(n \le 10^5,k\le 500,k|2\)

Solution

Claim

所有满足条件的切割线都满足关于 \([\dfrac{k}{2},\dfrac{k}{2}]\) 即方格图中心点中心对称。

Proof

考虑从中心点出发，随便找一条到达边缘的路线。

此时可以发现，要想构造出另外半条切割线并且满足题目中所述的条件，就一定要关于中心点进行中心对称来找。

严谨的证明请移步官方题解

Q.E.D

由此，我们可以转化题意，转变为求解 被切割的元素的最小值。

考虑一手图论，把网格图里的交点看成点，每条边分割的元素个数看成边的权值，从中点出发跑最短路，只要到达边界处，就说明此时产生了最优的解。

因为最边缘一圈的边是不可能有贡献的，所以对边的编号和对点的编号并不完全相同，要加一点转化，具体看代码。

实现上，因为每条边有五个参数(其实可以只有四个)，所以直接用 std::map<std::tuple<int,int,int,int>,int> 无脑解决即可。

关于 std::tuple，可以当成拓展的 std::pair，需要 C++11 以上的版本。

因为路线是关于中心点中心对称的，所以在更新 \((i,j)\) 的答案同时还要把 \((k-i,k-j)\) 一起带上。

int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int n,k,a,b,c,d;
map<tuple<int,int,int,int>,int>mp;/*same as edge value*/
bool vis[510][510];
struct nd{int w,x,y;friend bool operator<(nd a,nd b){return a.w>b.w;}};
void work(){
  cin>>n>>k;me(vis,0);mp.clear();
  priority_queue<nd>q;
  L(i,1,n){
    cin>>a>>b>>c>>d;if(a>c) swap(a,c);if(b>d) swap(b,d);
    if(a^c) mp[{a,b-1,a,b}]++,mp[{a,b,a,b-1}]++;
    else mp[{a-1,b,a,b}]++,mp[{a,b,a-1,b}]++;
  }
  //only edges in the middle can make value,
  //because if got border,then return.
  //the id should change.
  q.push({0,k/2,k/2});
  while(!q.empty()){
    auto u=q.top();q.pop();if(vis[u.x][u.y]) continue;
    vis[u.x][u.y]=vis[k-u.x][k-u.y]=1;
    if(!u.x||!u.y||u.x==k||u.y==k) 
      return cout<<n-u.w<<'\n',void();
    L(i,0,3){
      nd v={0,u.x+dx[i],u.y+dy[i]};
      v.w=u.w+mp[{u.x,u.y,v.x,v.y}]+
        mp[{k-u.x,k-u.y,k-v.x,k-v.y}];
      q.push(v);
    }
  }
  //and why this can work as an dijstra?
  //regard it as two points run on graph.
}