
日记
聪明的人已经发现了(不聪明的人也该发现了),上一篇日记是12月12日的,但是这一篇是12月16日的。一不小心鸽了 天。
至于前三天,你只需要知道我在打 usaco
和 bf-v
。其他没甚讲的。那个 usaco
也是,第一道就来一道贪心(一生之敌)。然后第二道又是一道差分约束。也是打的来。其实是有原题的,但是我忘了。有讲头的也只有 usaco
的银组T3。
Silver_C 2D Conveyer BeltLink to
看不着题面的点这里
说句闲话:其实我的大号是没打过银组的,但是我有小号。
我们发现,每一个建了传送带的格子,就相当于向传送带指向的点建了一条边。而没有建的,就相当于向四个方向都建了边。而指向外面或者最外层的没有建边的点就统一连到一个点: 上面。还有最重要的结论:当且仅当形成环的时候,环上的点和最终要走到环上的点是走不出去的。于是乎我们考虑从每一个点开始搜。搜到环了就标成出不去。但是这么做的时间复杂度是 ,就算是剪枝以后也有 这么做明显不现实。
我们先考虑简单版:只查询一次。现在的做法是枚举每一个点,从它开始搜。但是,我们想,能不能把它变成从一个点搜呢?我们发现,能出去的点一定形成一颗以 为根的内向树(就是子节点指向父亲节点的树)。我们都知道,内向树很麻烦,几乎不可处理。所以我们考虑建反图,那样子,环还是环,但是内向树却变成了外向树,我们便可以直接从 开始搜,搜到的点就是能出去的点。
然后我们就得到了一个 的做法。但是总共不是只有一次询问,于是我们考虑如何处理询问。我们发现:每次多加一个新的传送带就是将 条边删成 条边。但是,我们知道,删边十分的麻烦,即使是链表也一样。于是我们考虑离线,倒序枚举。那样子每次就是加边,这就十分的简单了。我们考虑加边后,每次从 开始搜,搜出来有多少个点就是上一个请求的答案(这个自己想想)。于是,我们发现,还是 。还是不可以。我们考虑剪枝:每次搜过的,计数并打上标记,以后不再搜。但是我们发现,第一次搜就把 和所有能出去的点都标记了。这些点现在就想墙一样挡着。于是我们只能考虑寻找新的起点。还是那句话:第一次搜就把 和所有能出去的点都标记了。于是我们压根就不用再从 开始搜,能影响答案的也就只有加边的那个点。于是我们直接考虑从这个点开始搜,搜到的点计数,那样总点数减累计的能出去的点数就是上一个请求的答案。但是,如果能这个点能影响答案,当且仅当之前不能到但现在能到,也就是说,它当前不能到但是它周围四个点有一个能到,它才能作为新的起点。这样,我们就真正的把他优化到了 。
因为有些恶心的细节所以还是放下代码:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384
#include<bits/extc++.h>
#define int long long
using namespace std;
const int maxq = 2e5 + 5;
const int maxn = 1e6 + 5;
const int dir[4][2] = {-1,0,1,0,0,-1,0,1};
int n,q;
int x[maxq],y[maxq],d[maxq];
int ans[maxn],cnt = -1;
bool vis[maxn],mp[maxn];
struct edge {
int v;
edge *nxt;
}*head[maxn];
int toint(int x,int y) {
if (x < 1 || x > n || y < 1 || y > n)//这里的意思是出去了就是0点
return 0;
return (x - 1) * n + y;
}
void adde(int u,int v) {
auto tmp = new edge;
tmp->v = v;
tmp->nxt = head[u];
head[u] = tmp;
}
void dfs(int u) {//搜索并计数
if (vis[u])
return;
vis[u] = 1;
cnt ++;
for (auto i = head[u]; i; i = i->nxt)
dfs(i->v);
}
signed main() {
scanf("%lld%lld",&n,&q);
for (int i = 1; i <= q; i++) {
scanf("%lld%lld",x + i,y + i);
char ch;
cin >> ch;
mp[toint(x[i],y[i])] = 1;
switch (ch) {
case 'U':
d[i] = 0;
break;
case 'D':
d[i] = 1;
break;
case 'L':
d[i] = 2;
break;
default:
d[i] = 3;
break;
}
adde(toint(x[i] + dir[d[i]][0],y[i] + dir[d[i]][1]),toint(x[i],y[i]));//建反图
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (!mp[toint(i,j)])
for (int k = 0; k < 4; k++)
adde(toint(i + dir[k][0],j + dir[k][1]),toint(i,j));//没有标记的点就四个方向都建边
for (int i = q; i >= 1; i--) {
static int st = 0;//如果是第一次就从0开始搜
static bool fl = 1;//标记它能不能成为新的起点
if (fl)
dfs(st);
ans[i] = n * n - cnt;//记录答案
st = toint(x[i],y[i]);
fl = 0;
for (int j = 0; j < 4; j++)
{
if (j == d[i])
continue;
int tx = x[i] + dir[j][0];
int ty = y[i] + dir[j][1];
fl |= vis[toint(tx,ty)];//旁边四个点能到
adde(toint(tx,ty),st);//加边
}
fl &= (!vis[st]);//当前不能到,就作为新的起点
}
for (int i = 1; i <= q; i++)
printf("%lld\n",ans[i]);
return 0;
}
日记
© 伊埃斯 | CC BY-NC-SA 4.0