ZJT's Blog

大変に気分がいい~

集训队作业之AGC019-C

2017-12-16 13:462017-12-16 13:46
集训队作业AtCoderset

传送门

一开始没看到每行每列最多只有一个,想了半天特殊情况怎么处理。。。

只考虑$x_2\geq x_1,y_2\geq y_1$的情况(别的情况能转化成这种情况),容易发现最优走法一定是一直朝着$x$或者$y$的正方向走,并且要经过数量最多的喷泉。当经过的喷泉数等于$\min(x_2-x_1+1,y_2-y_1+1)$是,还要再加上$5\pi$(因为绕着一个喷泉走了$180$度)。这个随便拿个数据结构处理一下就行了,我直接用了set。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#define MAXN 200010
#define y1 zjtsb_y1
using namespace std;

int x1,y1,x2,y2;
int n;
pair<int,int> a[MAXN];
set< pair<int,int> > S;

double PI=acos(-1.0);

int main(){
#ifdef DEBUG
    freopen("C.in","r",stdin);
#endif
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    int _n;
    scanf("%d",&_n);
    while(_n--){
        int x,y;
        scanf("%d%d",&x,&y);
        if(x>=min(x1,x2) && x<=max(x1,x2) && y>=min(y1,y2) && y<=max(y1,y2))
            a[++n]=make_pair(x,y);
    }
    if(x1>x2){
        for(int i=1;i<=n;i++) a[i].first=x1+x2-a[i].first;
        swap(x1,x2);
    }
    if(y1>y2){
        for(int i=1;i<=n;i++) a[i].second=y1+y2-a[i].second;
        swap(y1,y2);
    }
    sort(a+1,a+n+1);
    int res=0;
    for(int i=n;i>=1;i--){
        set< pair<int,int> >::iterator it=S.lower_bound(make_pair(a[i].second,0));
        int temp;
        if(it==S.end()) temp=1;
        else temp=it->second+1;
        if(temp>res) res=temp;
        it=S.insert(make_pair(a[i].second,temp)).first;
        while(it!=S.begin() && (--it)->second<=temp){
            set< pair<int,int> >::iterator it2=it;
            it2++;
            S.erase(it);
            it=it2;
        }
    }
    double ans=(double)(x2-x1+y2-y1)*100;
    ans-=res*(20-5*PI);
    if(res==min(x2-x1+1,y2-y1+1)) ans+=5*PI;
    printf("%.10lf\n",ans);
}

查看详细内容

集训队作业之ARC065-E

2017-10-13 16:552017-10-13 16: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;
}

查看详细内容