专栏首页机器学习入门挑战程序竞赛系列(33):POJ 2991 Crane

挑战程序竞赛系列(33):POJ 2991 Crane

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/77046799

挑战程序竞赛系列(33):POJ 2991 Crane*

详细代码可以fork下Github上leetcode项目,不定期更新。

练习题如下:

POJ 2991: Crane

一道线段树题,在《挑战》中刷到了,就和之前理解的线段树拿来对比下,关于线段树可以参看【算法细节系列(28):线段树】。

先来分析下题目,对于每个线段的更新,我们的目的在于记录终点的位置,此题的一个trick在于能否想到更新中的相对不变量【向量】,何以理解?

首先,旋转位置s,那么必然终点的位置会发生变化,所带来的结果是s后续的每个顶点都会发生相对变化,而s之间的顶点则没有改变。这种更新模式就特别符合线段树的性质了,因为线段树的提出就是基于对更新的优化,使得它在O(logn)O(\log n)的时间复杂度内完成。当然最幼稚的做法是,从s->终点,每旋转一次更新后续所有坐标。

这种模拟的做法必然会超时。那么问题来了,如何让这些更新规则去符合线段树的构造规则呢?

就拿上述方案来说,如果每个顶点维护一个坐标变量,那么就无法用区间来表示,因为每个顶点相互独立,它们的信息无法共享,所以区间合并所带来的问题是并不知道选谁作为该区间的代表。理论上来说,是终点坐标,可是却无法从几个孩子结点得到终点坐标的信息,得换换思路了。

向量,每个区间[l,r]维护一个起点指向终点r的向量,这和题目有关,因为我们只需要维护终点信息,而无需关注其它顶点的位置,那么我们就把问题抽象成了区间,每个区间维护一个向量,由此,区间与区间就能根据向量来合并了,合并规则为:当前向量加上右区间向量和所需旋转的角度。

这样一来,根结点必然永远都是从起点指向终点的向量,也就是答案x和y。

具体更新规则为:

x′=xchl+(cos(α)⋅xchr−sin(α)⋅ychr)

x' = x_{chl} + (\cos (\alpha) \cdot x_{chr} - \sin(\alpha) \cdot y_{chr})

y′=ychl+(sin(α)⋅xchr+cos(α)⋅ychr)

y' = y_{chl} + (\sin (\alpha) \cdot x_{chr} + \cos(\alpha) \cdot y_{chr})

代码如下:

import java.util.Scanner;

public class Main{

    static class SegementTree{
        int size;
        double[] vx;
        double[] vy;
        double[] angle;

        public SegementTree(int n){
            this.size = (1 << n) - 1;
            vx = new double[size];
            vy = new double[size];
            angle = new double[size];
        }

        public void init(int s, int l, int r){ //对应的区间为[l,r)
            angle[s] = vx[s] = 0;

            //叶子结点 和非叶子结点
            if (r - l == 1){
                vy[s] = len[l]; //表示区间叶子结点与下一段的向量 
            }
            else{
                int chl = s * 2 + 1;
                int chr = s * 2 + 2;
                init(chl, l, (l + r) / 2); //天然的划分所有区间
                init(chr, (l + r) / 2, r);
                vy[s] = vy[chl] + vy[chr]; //对于非叶子结点,vy表示合并后,终点向量距离原点的(x,y)
            }
        }

        //从s开始,更新与s+1的角度,逆时针旋转角度a,当前线段树的结点为v,对应的区间为l和r
        //由题意得,线段树中的每个左区间的向量需要变换,但右区间作为整体不需要做任何计算。
        public void change(int s, double a, int v, int l, int r){
            if (s <= l) return; // 如果需要旋转的s,对应当前的区间为右孩子,则不需要更新,因为它们隶属于一个整体
            else if (s < r){
                int chl = v * 2 + 1, chr = v * 2 + 2;
                int m = (l + r) / 2;
                //分治求解
                change(s, a, chl, l, m);
                change(s, a, chr, m, r);
                //区间合并
                if (s <= m) angle[v] += a; // 右儿子需要转动的角度,如果s 在右侧,则只需要更新当前状态ang[v]
                double sin = Math.sin(angle[v]);
                double cos = Math.cos(angle[v]);
                vx[v] = vx[chl] + (cos * vx[chr] - sin * vy[chr]);
                vy[v] = vy[chl] + (sin * vx[chr] + cos * vy[chr]);
            }
        }
    }

    static int[] len;
    static double[] prv;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int n = in.nextInt();
            int c = in.nextInt();

            len = new int[n];
            prv = new double[n];
            for (int i = 0; i < n; ++i){
                len[i] = in.nextInt();
                prv[i] = Math.PI;
            }

            SegementTree tree = new SegementTree(15);
            tree.init(0, 0, n);

            for (int i = 0; i < c; ++i){
                int s = in.nextInt();
                int A = in.nextInt();
                double a = A / 360.0 * 2 * Math.PI;
                tree.change(s, a - prv[s], 0, 0, n);
                prv[s] = a;
                System.out.println(String.format("%.2f %.2f", tree.vx[0], tree.vy[0]));
            }
        }
        in.close();
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ 刷题系列:3299. Humidex

    POJ 刷题系列:3299. Humidex 传送门:POJ 3299. Humidex 题意: 给定T, D, H中的任意两个数,求另外一个。 思路: ...

    用户1147447
  • 4.6平面上的分治法(1)

    利用分治后左平面和右平面的最小d来限制第二种情况的查询,绝了。关于第二种情形的算法采用平面扫描法,但前提y需要排序。

    用户1147447
  • LWC 52:688. Knight Probability in Chessboard

    LWC 52:688. Knight Probability in Chessboard 传送门:688. Knight Probability in Ches...

    用户1147447
  • 超级碗大秀无人机背后,是英特尔在体育圈内的巨大野心

    镁客网
  • perf-让CPU消耗无处遁形

    前几天我在看一篇公众号文章《DBA接招:一次因PAUSE指令变化引发的MySQL性能危机》 文章写得很棒,分析地也很彻底,但是更吸引我的是文中的几张图,例如

    jeanron100
  • MySQL 计算两个日期之间相差的秒数 SQL

    一个会写诗的程序员
  • 终于学会后空翻!历经多次NG,波士顿动力机器人再get新技能

    原作 Natt Garun Root 发自 凹非寺 量子位 出品 | 公众号 QbitAI 不知道谷歌爸爸怎么想的(・(ェ)・) ,今年6月把大好前途的波士顿...

    量子位
  • linux网络编程之socket(十四):基于UDP协议的网络程序

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/...

    s1mba
  • [置顶] linux网络编程之socket(十四):基于UDP协议的网络程序

    一、下图是典型的UDP客户端/服务器通讯过程 ? 下面依照通信流程,我们来实现一个UDP回射客户/服务器 ?   #include <sys/types.h> ...

    s1mba
  • 安服神器 | FuzzScanner

    一个用来进行信息搜集的工具集,主要是用于对网站子域名、开放端口、端口指纹、c段地址、敏感目录、链接爬取等信息进行批量搜集。

    HACK学习

扫码关注云+社区

领取腾讯云代金券