【题解】CF1611G

· · 题解

CF1611G

题意简述：

给定一张 n \times m 的 01 网格图，每次选一个点 (1,x) 出发，可以从 (x,y) 到 (x+1,y+1) 或者 (x+1,y-1)，问至少出发多少次才能经过每个 1 至少一次。

n \times m \leq 10^6

赛场上的一些想法（错解）：

1.考虑相邻两行，猜想其答案为每相邻两行答案的最大值，显然错误。

2.考虑转化成数字问题，发现 x+y 要么增加 2 要么不变，考虑按奇数偶数分类，分别处理，这个可以有，然后发现仍然不会做。

思路

赛场上问题的转化出现了一些问题，没有让问题变简单，所以考虑原问题。不妨先不考虑边界，如果走出了边界，直接对称回去。

我们通过观察发现不会从同一个点出发两次。考虑从左到右加入路径，如果一个点 (1,y) 加入了两次，找到两次路径第一个不同的位置，找不到就说明第二条完全重复，可以删去，选择不同位置中靠右的一个，发现它一定可以通过 (1,y+2) 得到， (1,y+2) 得到它时可以覆盖更多未覆盖的点。

然后是路径不会穿插，如果路径穿插了，那么找到第一个公共点，交换后面的部分，这样是等价的。

答案的上界是 \lceil{\dfrac{m}{2}}\rceil \times 2，可以构造一种方案覆盖所有点。

有了这几条性质，就可以开始贪心了。我们从 (1,1) 到 (1,n+m) 分别考虑加入一条路径。什么时候加入路径暂且不提，我们考虑加入的路径应该怎么走。设当前点为 (x_0,y_0)，如果当前对角线上 （x+y = x_0+y_0 的点），存在 (x_1,y_1) 满足 x_1>x_0 ，那么就一定走 (x+1,y-1)，因为现在这条路径必须覆盖掉这条对角线上剩下的点（因为路径不会穿插，后面的路径不会与当前路径相交），否则一定走 (x+1,y+1)，这样可以让后面能选的路径更多。

然后是什么时候应该从 (1,i) 加入一条新路径，结论是当且仅当有点满足 x+y=1+i 并且没被覆盖时。必要性显然。充分性，如果使用了 (1,i)，并且对角线没有点，那么它最开始一定是走了一段无用的 (x+1,y+1)，使用更后面的点替代即可。

于是用一些 set 维护所有满足 x+y=i 的黑点，模拟刚刚的方案即可。

代码（目前 CF 最短)

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int i,j,n,t,m,ans;
string str[N];
set<int> st[N];
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;ans=0;
        for(i=1;i<=n;i++)
        {
            cin>>str[i];
            for(j=1;j<=m;j++)
            if(str[i][j-1]=='1')st[i+j].insert(i);
        }
        for(i=1;i<=n+m;i++)
        {
            if(st[i+1].size()==0)continue;
            int pos=i;ans++;
            for(j=1;j<=n;j++)
            {
                st[j+pos].erase(j);
                if(st[j+pos].rbegin()!=st[j+pos].rend()&&*st[j+pos].rbegin()>j)pos--;
                else pos++;
            }
        }
        cout<<ans<<endl;
    }
}