20180927NOIP模拟赛

20180927.pdf

T1 maze

ポジションゼロが私の定位置 
お呼びですか? 天堂真矢です 
見てなさい 今にその座を奪ってあげる 
西條クロディーヌ Allez, on y va! 

「よろしく九九組」

咳咳走错片场了,这里没迷宫组

正经说题,一看到什么“最小值刚好等于xxx”就可以知道这个要二分答案了,这个题过于套路了,根本不给选手思考空间,我才不会说我读完题就开始码了

二分一个$k$,代入用dijstra跑一遍最短路验证即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>

struct Data{
	int x, y;
	double dis;
	bool friend operator <(const Data &_, const Data &__){
		return __.dis<_.dis;
	}
}now, top;
const double esp=0.00000001;
int map[110][110], n, m, sx, sy, tx, ty;
int dir[4][2]={{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
double s, tim[2], dis[110][110];
bool vis[110][110];

void dij(){
	std::priority_queue<Data>q;
	memset(dis, 0x7f, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	dis[sx][sy]=0;
	now.x=sx, now.y=sy, now.dis=0;
	q.push(now);
	while(!q.empty()){
		top=q.top();
		q.pop();
		if(vis[top.x][top.y])	
			continue;
		vis[top.x][top.y]=true;
		for(int i=0; i<4; i++){
			now.x=top.x+dir[i][0];
			now.y=top.y+dir[i][1];
			now.dis=top.dis+tim[i/2];
			if(map[now.x][now.y]==1 || now.x<1 || now.x>n || now.y<1 || now.y>m)
				continue;
			if(now.dis<dis[now.x][now.y]){
				dis[now.x][now.y]=now.dis;
				q.push(now);
			}
		}
	}
}

bool check(){
	dij();
	return dis[tx][ty]-s<=esp;
}

int main(){
	freopen("maze.in", "r", stdin);
	freopen("maze.out", "w", stdout);
	tim[0]=1.0;
	scanf("%d%d%d%d%d%d", &n, &m, &sx, &sy, &tx, &ty);
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			scanf("%d", &map[i][j]);
	scanf("%lf", &s);
	double l=0.0, r=100000.0;
	while(r-l>=esp){
		double mid=(l+r)/2.0;
		tim[1]=mid;
		if(check())
			l=mid;
		else
			r=mid-esp;
	}
	printf("%.3lf", l);
	return 0;
}

T2 bird

读题之后,自然而然想到,可以统计一下每个时刻有几只鸟在直线$x=0$上,然后再dp计算一下

设$f[i]$为第$i$秒时开枪,累计打中的鸟的数量。设$p_{i, j}$为第$i$秒和第$j$秒都在直线$x=0$上的鸟的数量。设$c_{i}$为第$i$秒直线$x=0$上的鸟的数量。

$$f[i]=\max\limits_{j=0}^{\max\{0, i-k\}}\{f[j]-p_{i, j}\}+c_{i}$$

考场上我就写了个这样的dp交上去了,只有80分QAQ

我们其实可以用线段树优化一下这个DP,一只鸟$i$在第$j$秒时,若$r_{i}<j$,则这只鸟从今以后都无法被打到了。所以我们可以将所有鸟按$r_{i}$排个序,初始先将每只鸟$i$入队,$f[l_{i}]\sim f[r_{i}]$都$-1$。计算$f[i]$的时候,将所有满足$r_{x}<i$的鸟$x$出队,$f[l_{x}]\sim f[r_{x}]$都$+1$。这时候的$f[j]$就都是$f[j]-p_{i, j}$了,直接线段树查询区间最大值即可。

#include <iostream>
#include <cstdio>
#include <algorithm>

struct Data{int l, r;}a[100010];
int N, K, cnt[500010];
bool cmp1(const Data &_, const Data &__){return _.r<__.r;}

class SegTree{
private:
    struct Node{
        int l, r, mx, laz;
        Node *lch, *rch;
        Node(int l, int r, Node *lch, Node *rch)
            :lch(lch), rch(rch), l(l), r(r), mx(0), laz(0){}
        
        void push_up(){
            mx=std::max(lch->mx, rch->mx);
        }
        
        void push_down(){
            lch->laz+=laz, rch->laz+=laz;
            lch->mx+=laz, rch->mx+=laz;
            laz=0;
        }
    }*root;
    
    Node *build(int l, int r){
        if(l==r)	return new Node(l, r, NULL, NULL);
        return new Node(l, r, build(l, (l+r)/2), build((l+r)/2+1, r));
    }
    
    void add(Node *v, int l, int r, int val){
        if(l<=v->l && v->r<=r){
            v->mx+=val, v->laz+=val;
            return;
        }
        v->push_down();
        if(2*l<=v->l+v->r)
            add(v->lch, l, r, val);
        if(2*r>v->l+v->r)
            add(v->rch, l, r, val);
        v->push_up();
    }
    
    int query(Node *v, int l, int r){
        if(l<=v->l && v->r<=r)
            return v->mx;
        int ans=-2333;
        v->push_down();
        if(2*l<=v->l+v->r)
            ans=std::max(ans, query(v->lch, l, r));
        if(2*r>v->l+v->r)
            ans=std::max(ans, query(v->rch, l, r));
        return ans;
    }
    
public:
    SegTree(){
        root=build(1, 500001);
    }
    
    void add(int l, int r, int val){
        add(root, l+1, r+1, val);
    }
    
    int query(int l, int r){
        return query(root, l+1, r+1);
    }
};

int main(){
    int l, r, tot=0, ans=0;
    SegTree *T=new SegTree;
    scanf("%d%d", &N, &K);
    for(int i=1; i<=N; i++){
        scanf("%d%d", &l, &r);
        if(r<0)	continue;
        l=std::max(l, 0);
        a[++tot].l=l, a[tot].r=r;
        cnt[l]++, cnt[r+1]--;
        T->add(l, r, -1);
    }
    std::sort(a+1, a+tot+1, cmp1);
    for(int i=1; i<=500000; i++)	cnt[i]+=cnt[i-1];
    for(int i=0, j=1, now; i<=500000; i++){
        while(j<=tot && a[j].r<i){
            T->add(a[j].l, a[j].r, 1);
            j++;
        }
        now=(i>=K ? T->query(0, i-K) : 0)+cnt[i];
        T->add(i, i, now);
        ans=std::max(ans, now);
    }
    printf("%d", ans);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注