ZJT's Blog

大変に気分がいい~

集训队作业之ARC065-E

2017-10-13 12:552017-10-13 12:55
集训队作业AtCoderBFSset

传送门

作死直接看日语题面做题,不过竟然看懂题意了23333

大概就是先算出每个点跟几个点距离符合条件,以及从初始点开始搜出所有能到达的点。这两个东西都能直接旋转45度之后维护行和列来做,我懒就直接用了set,复杂度是$O(n\log n)$,其实应该可以$O(n)$做。

#include <cstdio>
#include <cstring>
#include <cassert>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#define MAXN 100010
#define LL long long
using namespace std;

struct Point{
    int id; 
    Point(const int &_id):id(_id){}
    bool operator < (Point x) const;
};

int n,size,x1,x2;
int p[MAXN][2],d;
map<int,int> T1,T2;
set<Point> S[MAXN<<1];
int rk[3][MAXN],st[MAXN];
bool visit[MAXN];
int cnt[MAXN];
queue<int> Q;

bool Point::operator < (Point x) const{
    if(p[id][0]==p[x.id][0]) return id<x.id;
    return p[id][0]<p[x.id][0];
}

int dis(int x,int y){
    return abs(p[x][0]-p[y][0])+abs(p[x][1]-p[y][1]);
}

void pre_gao(int x){
    int temp=0;
    for(set<Point>::iterator it=S[x].begin();it!=S[x].end();it++)
        rk[st[x]][it->id]=++temp;
}

int cnt_set(int x,int type,int l,int r){
    if(!x) return 0;
    p[0][0]=r+1;
    set<Point>::iterator it2=S[x].upper_bound(0);
    p[0][0]=l;
    set<Point>::iterator it1=S[x].upper_bound(0);
    if(it1!=S[x].end())
        return (it2==S[x].end()?S[x].size()+1:rk[type][it2->id])-rk[type][it1->id];
    else return 0;
}

void gay(int x,int l,int r){
    if(!x) return;
    p[0][0]=r+1;
    set<Point>::iterator it2=S[x].upper_bound(0);
    p[0][0]=l;
    set<Point>::iterator it1=S[x].upper_bound(0);
    while(it1!=it2){
        if(!visit[it1->id]){
            visit[it1->id]=1;
            Q.push(it1->id);
        }
        set<Point>::iterator it3=it1;
        it3++;
        S[x].erase(it1);
        it1=it3;
    }
}

int calc_cnt(int x){
    int res=0;
    res+=cnt_set(T1[p[x][0]+p[x][1]+d],1,p[x][0]+1,p[x][0]+d);
    res+=cnt_set(T2[p[x][0]-p[x][1]+d],2,p[x][0],p[x][0]+d-1);
    res+=cnt_set(T1[p[x][0]+p[x][1]-d],1,p[x][0]-d,p[x][0]-1);
    res+=cnt_set(T2[p[x][0]-p[x][1]-d],2,p[x][0]-d+1,p[x][0]);
    return res;
}

void bfs(){
    Q.push(x1); Q.push(x2);
    visit[x1]=visit[x2]=1;
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        gay(T1[p[x][0]+p[x][1]+d],p[x][0],p[x][0]+d);
        gay(T2[p[x][0]-p[x][1]+d],p[x][0],p[x][0]+d);
        gay(T1[p[x][0]+p[x][1]-d],p[x][0]-d,p[x][0]);
        gay(T2[p[x][0]-p[x][1]-d],p[x][0]-d,p[x][0]);
    }
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    scanf("%d%d%d",&n,&x1,&x2);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&p[i][0],&p[i][1]);
        int t1=p[i][0]+p[i][1],t2=p[i][0]-p[i][1];
        if(!T1.count(t1)) st[T1[t1]=++size]=1;
        if(!T2.count(t2)) st[T2[t2]=++size]=2;
        S[T1[t1]].insert(i);
        S[T2[t2]].insert(i);
    }
    d=dis(x1,x2);
    for(int i=1;i<=size;i++) pre_gao(i);
    for(int i=1;i<=n;i++) cnt[i]=calc_cnt(i);
    bfs();
    LL ans=0;
    for(int i=1;i<=n;i++)
        if(visit[i]) ans+=cnt[i];
    ans/=2;
    printf("%lld\n",ans);
    return 0;
}

查看详细内容

集训队作业之AGC014-C

2017-10-13 10:122017-10-13 10:12
集训队作业AtCoderBFS

传送门

考虑从第二次开始,就可以无视障碍了,因为可以把这些障碍在上一次消掉。所以直接BFS一下看哪些点是第一次就能走到的,然后瞎处理一下就做完了。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN 1010
using namespace std;

int n,m,k,sx,sy;
int a[MAXN][MAXN];
bool visit[MAXN][MAXN];
int d[MAXN][MAXN];

void bfs(){
    static queue< pair<int,int> > Q;
    Q.push(make_pair(sx,sy));
    d[sx][sy]=0;
    visit[sx][sy]=1;
    while(!Q.empty()){
        int tx=Q.front().first,ty=Q.front().second;
        Q.pop();
        if(tx>1 && !visit[tx-1][ty] && !a[tx-1][ty]){
            Q.push(make_pair(tx-1,ty));
            visit[tx-1][ty]=1;
            d[tx-1][ty]=d[tx][ty]+1;
        }
        if(ty>1 && !visit[tx][ty-1] && !a[tx][ty-1]){
            Q.push(make_pair(tx,ty-1));
            visit[tx][ty-1]=1;
            d[tx][ty-1]=d[tx][ty]+1;
        }
        if(tx<n && !visit[tx+1][ty] && !a[tx+1][ty]){
            Q.push(make_pair(tx+1,ty));
            visit[tx+1][ty]=1;
            d[tx+1][ty]=d[tx][ty]+1;
        }
        if(ty<m && !visit[tx][ty+1] && !a[tx][ty+1]){
            Q.push(make_pair(tx,ty+1));
            visit[tx][ty+1]=1;
            d[tx][ty+1]=d[tx][ty]+1;
        }
    }
}

int dis(int x,int y){
    int res=min(min(x-1,n-x),min(y-1,m-y));
    if(!res) return 0;
    return (res-1)/k+1;
}

int main(){
#ifdef DEBUG
    freopen("C.in","r",stdin);
#endif
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){
        static char str[MAXN];
        scanf("%s",str+1);
        for(int j=1;j<=m;j++){
            if(str[j]=='#') a[i][j]=1;
            if(str[j]=='S') sx=i,sy=j;
        }
    }
    bfs();
    int ans=0x7FFFFFFF;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(visit[i][j] && d[i][j]<=k)
                ans=min(ans,dis(i,j)+1);
    printf("%d\n",ans);
    return 0;
}

查看详细内容