5588葡京线路《简约至上》读书简摘

一.明确认识

  • 叙述要点的有数种方式:
    1.于是相同句子话将她形容出来,要统筹啊,遵循哪几久设计规则。(简单而迅速)
    2.讲述用户的行使状况,以及自己之计划而什么满足用户在该场景下的需。(重用户体验)

  • 活动有办公室
    软件的使环境,是考察用户之特等地点,使软件可环境需要。

  • 着眼什么
    举手投足上前现实环境,你会意识影响用户体验的因素如此的多。

办公室:
某有意思的话题传遍耳朵,有人会竖起耳朵听,因此打断工作。
来电话,短信,新邮件。。
也某个会议打印文档,他们一般最后一分钟去打印。

家里头:
限用画速记本边看电视。
宽带速度不若公司线路那么平稳。
在孩子看卡通片时候购物。

户外:
打电话时或许坐在几只确保,手机按键不够大会特别辛苦。
略知一二的日光或吃人口拘禁不根本屏幕。

公的用户体验应该简单到非深受这些干扰的熏陶,能够以众人为从断的空闲生存。

  • 其三种植用户
    1.专家型,花时间体验有的功用。
    2.随意型用户,有趣味使用高级复杂的出品,却非甘于碰全新的事物,学习意愿不显著。
    3.主流用户,使用你的活光为完成任务。
    值得注意的是:他们的签并无见面趁机年华升级

  • 主流用户想使什么

主流用户以及大家用户需区别

【SinGuLaRiTy-1013】 Copyright (c) SinGuLaRiTy 2017. All Rights
Reserved.

二.删除

  • 简化设计极端显眼的方,就是去除不必要的机能。
  • 以及新增功能相比,客户更关心基本功能的改善。
  • 名列功能优先级,看看产品能否充分满足用户最高优先级
  • 夺丢可发生可管的挑选项,分散人们注意力的玩具。让用户专心去做和好的作业。
  • 选料简单,用户反而又爱。减少用户的取舍,加速决策过程。
  • 散错误的发源是简化体验的基本点思路。
  • 减少视觉混乱
  • 因而空白和微小的背景色来划分页面。不要以线条。
  • 尽可能少使用强调,加多少就足足了,不用加粗,放大,又成为红色
  • 变更以粗黑线,匀称,浅色的线还好。
  • 操纵信息层次。最好不跳三单层次:标题,子标题,正文。
  • 压缩元素大小的成形。

这是 三道 USACO 的题……

三.组织

  • 分块。将起组织及”7加减1”个块中。分块越少,选择更加少,用户承担进一步轻。
  • 围绕行为开展集体。画来用户作为有助于了解你的软件出品。
  • 网格。利用不可见的网格来针对齐页面元素。网格越是简单,效果越来越明显。
  • 旁。可以用颜色,灰色阴影,大小缩放,形状变化,来给用户感知分层。

第一挥毫:奶牛飞盘

四.隐藏

  • 藏匿不常因此而切莫能够少的成效。
  • 及时出现。如字典功能只有以挑单词之后才会来得。
  • 被职能容易找到。当用户专注于有平码任务时,他的关注点会聚焦。遇到问题之后,他们过分专注屏幕上问题区域。就算标签还杀,如果身处了用户关注点之外,用户为看不到。
  • 设非设于丁找最老,隐藏就是水到渠成之。

题材叙述

有n(2<=n<=20)头奶牛在戏飞盘,可是飞盘飞至了高处。现在他俩一旦惦记方叠在一道,去取飞盘。飞盘的万丈为H(1
<= H <=
1,000,000,000)。给出各头奶牛的重、高度、强壮度(能够接受之轻重),问他们是否足够得到,如果能获取到,求其额外还会承受极度多小重量。(要包每头奶牛所接受之分量都未超越其的强壮度)。

五.转移

  • 于装置中转换
  • 当动平台及桌面平台中间变
  • 往用户更换。例如旅游路计划软件。对模棱两可是情况的拍卖,简单的界面,将复杂的办事留给用户。
  • 用户擅长啊。计算机擅长精确保存信息,人欣赏控制结果。基本型旅行行程计划软件将指定目标和社记录的劳作留给用户,对计算机来说复杂的任务,对人而言轻而易举。让用户觉得简单的首要前提是:先将懂把生忙碌工作授计算机,将什么工作留给用户。

输入

先是行包含N和H。

紧接下N行,每行三只数,分别表示她的冲天、重量与强壮度。所有的高频都也刚刚整数。

六.末尾的嘱咐

  • 拿复杂放到哪里。设计用户体验的末段,往往是咨询,把复杂在哪里。
  • 夫任务应是自动化,还是用户来支配?
  • 界面中应当是含多力量特定按钮,还是只放通用按钮。
  • 职责是一次性完成,还是细分几段子时间得。
  • 任务是吃用户有意识去好(例如用屏幕上之控件来罗搜索结果),还是应该在无意完成(如查看伦敦地形图中之绿色线路)。
  • 被简答发生在用户之血汗中
    毫无吃您的计划性干扰了用户的思绪。简单的筹划能也用户留起足够的长空,他们见面因此自己之生存来填充这些空中,从而开创有更增长,更有意义的体验。

产品新人求职中持续更新《PM成长路》专题集。欢迎关注,欢迎大家来与我多多交流

输出

如奶牛的师可够到飞盘,输出还能够经受之无比要命额外重量;否则输出“Mark is
too tall”.

样例数据

样例输入 样例输出

4 10         

9 4 1         

3 3 5         

5 5 10        

4 4 5

2

 

 

 

 

 

 

 

样例解释

选择:(1)3 3 5 (2)4 4 5 (3)5 5 10

STD Code

#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#define INF 20+5
#define MAXN 0x3f3f3f3f
using namespace std;
struct node
{
    long long int w;
    long long int s;
    long long int h;
    long long int infor;
};
node cow[INF];
long long int tot_height=0;
long long int height,num;
bool cmp(node a,node b)
{
    return a.infor>b.infor;
}
long long minn=MAXN,ans=-1;
bool visited[30];
long long int min(long long int a,long long int b)
{
    if(a<b)
        return a;
    else
        return b;
}
void dfs(int i,int now_height)
{
    int j;
    if(now_height>=height)
    {
        minn=MAXN;
        for(int ii=0;ii<num;ii++)
            if(visited[ii])
                minn=min(minn-cow[ii].w,cow[ii].s);
        if(minn>ans)
            ans=minn;
        return ;
    }
    else
        for(j=i;j<num;j++)
        {
            visited[j]=1;
            dfs(j+1,now_height+cow[j].h);
            visited[j]=0;
        }
}
int main()
{
    int tot_weight=0;
    scanf("%I64d%I64d",&num,&height);
    for(int i=0;i<num;i++)
    {
        scanf("%I64d%I64d%I64d",&cow[i].h,&cow[i].w,&cow[i].s);
        tot_weight+=cow[i].w;
    }
    for(int i=0;i<num;i++)
        cow[i].infor=cow[i].s-(tot_weight-cow[i].w);
    sort(cow,cow+num,cmp);
    dfs(0,0);
    if(ans==-1)
        printf("Mark is too tall\n");
    else
        printf("%lld\n",ans);
    return 0;
}

题材分析

瞧问题,首先想到的当是DP或者是贪心。尝试写起DP方程式的早晚,猛然察觉似乎写不起单所以然来,DP无法以确保高度最好精良和重量(也就算是强壮度的分配)最优秀。于是毅然放弃DP,尝试贪心。看看样例,似乎发觉了好几头脑:这像就是于强壮度贪心嘛,水题呀!再望题目,怎么当这样例有硌次……这明确不是正解好不好?

咱俩来探视下面就组数据:

5 10

10 20 5

4 4 6

3 3 5

3 1 7

2 1 8

若我们坐强壮度为贪婪策略,那么即便会见优先选项后四头牛,而强烈的,只选择第一头牛就是极度优解。也就是说,若一峰牛生重复,强壮度很粗,高度也很高,在是种植思路被即使见面WA。同理可证明按高度排序是行不通的。

这就是说,我们就算如寻思一下犬牙交错一点之唯利是图了。出于偶然,我想到了以描述奶牛的结构体中定义一个值infor=cow.strong+cow.weight,越想进一步觉得这猜测靠谱(其实是就是正解,具体证法见后),但连接下自己就犯了一个致命的错误:用同叠for循环把奶牛一个个准免好的顺序叠上去——最后就WA了(看来样例与自我自己的样例还是于水qwq)正确的解法是:由于匪是各个一样峰奶牛都好吃选中,即各级一样条奶牛都生“被入选”与“未选中”两种情景,对于这种线性查找最优解的问题,我们可以展开DFS,不断更新ans,最后收获答案(若到结尾还无更新到ans,就说明无解)。

<对于infor=cow.strong+cow.weight贪心策略的证明-反证法>

率先我们来设想一下:面前有同一折牛,infor最要命之以无比下面,越为上,牛的infor越小。我们对当下叠牛自生为上编号123。下面,就是核心了:

俺们看看第i头牛和第i-1头牛(也就是说cow[i]在cow[i-1]的地方):其中,设第i头牛还能够经受的重量也cow[i].strong-W,第i-1条牛还会接受的重也cow[i-1].strong-(cow[i].weight+W),这半独价值的min就是拖欠限量外之答案了;

而今,我们来“扭转乾坤”,把第i头牛和第i-1峰牛对调动一下职位(现在,cow[i-1]在cow[i]的上面):此时,cow[i-1]尚能够接受的份额为cow[i-1].strong-W,而cow[i]尚会承受之份量也cow[i].strong-(cow[i-1].weight+W),同样的,这点儿个值取min也是目前限制外的答案。

由起“infor最酷之以最好下面,越向上,牛之infor越聊”这同样极,即cow[i].strong+cow[i].weight<cow[i-1].strong+cow[i-1].weight,我们得窥见于轮换前的min一定比调换后底min更完美。以此类推,就只是证出该结论。

次挥毫:马拉松比赛

问题叙述

奶牛贝西为他的伴侣设计了同等修老比赛的线路。这长达线路上总共有n(n<=100000)个点,它们分布于一个平面坐标系受。它的同伙毅力不够,所以无可知走了全程,于是贝西深受他们配备了相同便条线路(它是千篇一律段连接的触及,比如要定子线路吧【i,j】,表示奶牛需要由点i开始,经过点i+1,点i+2,……,最后交点j)。即使如此,奶牛们依然可能过了中某个点坐节约路程,当然者点不可知是分路的起点要终点。现在,有Q(Q<100000)个操作:操作分为两栽,第一栽也”U
I X Y”,表示以点I的职位要于坐标(X,Y)处;第二种乎Q I J,表示如定子线路也点i到点j,需要查询奶牛们从i跑至j的无限短路程。(路程是因曼哈顿相差计算的)他们得以跨了中有点。

不无的坐标值x,y均以[-1000,+1000]区间。

输入

第一实行包含N和Q。接下来N行,每行两个数(X,Y),表示每个点的坐标,按照号码从小至很之一一为出。

连下Q行,每行表示一个操作。操作如上所述。

输出

对各级一样次等查询,输出一个整数,表示该子线路的无比短缺里程(曼哈顿距离)。

样例数据

样例输入 样例输出

5 5

-4 4

-5 -3

-1 5

-3 4

0 5

Q 1 5

U 4 0 1

U 4 -1 1

Q 2 4

Q 1 4

11

8

8

 

 

 

 

 

 

 

 

 

 

 

 

 

STD Code

#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#define MAXN 100010
#define INF 0x3f3f3f3f
#define get_mid (tree[root].l+tree[root].r)/2
using namespace std;
char ask[5];
int num_point,num_ask;
struct node
{
    int X;
    int Y;
};
node point[MAXN];
int Max(int a,int b)
{
    return (a>b ? a : b);
}
//Distance Function
int Abs(int target)
{
    if(target>0)
        return target;
    return (-(target));
}
int Manhattan(int a,int b)
{
    return Abs(point[a].X-point[b].X)+Abs(point[a].Y-point[b].Y);
}

//Segment Tree Function
struct segment
{
    int l;
    int r;
    int sum;
    int dis;
};
segment tree[3*MAXN];
void update(int root)
{
    int mid=get_mid;
    tree[root].dis=Max(tree[root*2].dis,tree[root*2+1].dis);
    tree[root].sum=tree[root*2].sum+tree[root*2+1].sum+Manhattan(mid,mid+1);
}
void change(int root,int pos)
{
    if(tree[root].l==tree[root].r)
    {
        if(1<tree[root].l&&tree[root].r<num_point)
            tree[root].dis=Manhattan(pos-1,pos)+Manhattan(pos,pos+1)-Manhattan(pos-1,pos+1);
        return;
    }
    int mid=get_mid;
    if(pos<=mid)
        change(root*2,pos);
    else
        change(root*2+1,pos);
    update(root);
}
void build(int root,int l,int r)
{
    tree[root].l=l;
    tree[root].r=r;
    tree[root].sum=0;
    tree[root].dis=-INF;
    if(l==r)
        return;
    int mid=(l+r)/2;
    build(root*2,l,mid);
    build(root*2+1,mid+1,r);
}

//Ans Calculation
int get_sum(int root,int l,int r)
{
    if(r<tree[root].l||tree[root].r<l)
        return 0;
    if(l<=tree[root].l&&tree[root].r<=r)
        return tree[root].sum;
    int mid=get_mid;
    int addition=0;
    if(l<=mid&&mid<r)
        addition=Manhattan(mid,mid+1);
    return get_sum(root*2,l,r)+get_sum(root*2+1,l,r)+addition;
}
int get_dis(int root,int l,int r)
{
    if(r<tree[root].l||tree[root].r<l)
        return 0;
    if(l<=tree[root].l&&tree[root].r<=r)
        return tree[root].dis;
    return max(get_dis(root*2,l,r),get_dis(root*2+1,l,r));
}

//Main Function
int main()
{
    scanf("%d%d",&num_point,&num_ask);
    build(1,1,num_point);
    for(int i=1;i<=num_point;i++)
    {
        scanf("%d%d",&point[i].X,&point[i].Y);
        change(1,i);
        if(i>1)
            change(1,i-1);
        if(i<num_point)
            change(1,i+1);
    }
    for(int i=1;i<=num_ask;i++)
    {
        scanf("%s",ask);
        if(ask[0]=='U')
        {
            int I,new_X,new_Y;
            scanf("%d%d%d",&I,&new_X,&new_Y);
            point[I].X=new_X;
            point[I].Y=new_Y;
            change(1,I);
            if(I>1)
                change(1,I-1);
            if(I<num_point)
                change(1,I+1);
        }
        else
        {
            int Start,End;
            scanf("%d%d",&Start,&End);
            int Sum_ans,Dis_ans=0;
            Sum_ans=get_sum(1,Start,End);
            if(End-Start>1)
                Dis_ans=get_dis(1,Start+1,End-1);
            printf("%d\n",Sum_ans-Dis_ans);
        }
    }
    return 0;
}

问题分析

代表考试的时光接触都并未点——看到此神奇之题材还有查询操作就发头那个。上网搜了了原题,发现原题实际上并从未U操作与Q操作,因此原题的解法就是一个DP。不过,对于这道经过改动的书来说,显然不是DP就能迎刃而解的了:O(n)的DP套上O(n)的询问,总时间复杂度初步估计至少为O(n^2),对于这100000之多少就是只有“嘿嘿嘿”。

于圈正解之前,先来大一下:什么是“曼哈顿离”,我们用一个姿势来代表(设同一平面上起有限沾:A(X1,Y1),B(X2,Y2)):Manhattan(A,B)=|X1-X2|+|Y1-Y2|。

下面,我们来拘禁一样拘留正解:我们事先忽小掉所谓的“跳了有一个碰”的情景,也就是说,先考虑走了事所有点的曼哈顿距离,由于触及是准路线的相继为出底,我们挺容易取得总路程的表达式(M表示Manhattan距离):

Distance_All=M(A1,A2)+M(A2,A3)+M(A3,A4)+……+M(An-2,An-1)+M(An-1,An)

跟着,我们重新借用而要跨越了第k (1<k<n) 个点,那么:

Distance_Skip(k)=M(A1,A2)+M(A2,A3)+M(A3,A4)+……+M(Ak-2,Ak-1)+M(Ak-1,Ak+1)+M(Ak+1,Ak+2)+……+M(An-2,An-1)+M(An-1,An)

我们将Distance_All与Distance_Skip(k)作差,就足以获过了第k个点时奶牛们丢运动的距离(暂且将那称为Benifit(k))了。由于要求最好短距离,那么题目就转账为要所被闹区间当中Benifit(k)的太充分价值。到了这里,我们发现,线段树就可化解这题目嘛:建立一个线段树来储存Benifit(k),每次找就搜该距离的不过酷价值就是行了。然而,在形容代码的当儿你见面发觉,由于发生加点的操作,而且Ans=Distance_Origin-max(Benifit(k)),其中求Distance_Origin要为此前缀和来求,所以,我们尚亟需建立一个线段树来储存从A[Start]到A[End]本来应运动的路程(你呢得以拿一个线段树的结构体开大一点,将Distance_Origin及Benifit的值存到同)。这样勾画下去,就从来不毛病5588葡京线路了。

老三开:奶牛慢跑

题目叙述

有n(n<=100000)头奶牛在一个无穷长的小道上减缓跑。每头奶牛的起点不同,速度也不同。小道可以叫分成多漫长跑至。奶牛只会以属自己的跑道上冉冉跑,不容许更换跑道,也非容许改变速度。如果如舒缓跑t(t<=1000000000)分钟,要保管在其他时候不见面生同等跑道上之奶牛相遇,请问最少需要有些条跑道。奶牛开始以哪条跑道是足以随意安装的。

输入

率先执两只整数n,t。

通下去的n行,每行包含两只整数,表示奶牛的职及快。位置是勿因整数,速度是刚刚整数。所有的奶牛的起点都非同等,按起点递增的各个为闹。

输出

极端少之跑道数。

样例数据

样例输入 样例输出

5 3

0 1

1 2

2 3

3 2

6 1

3

 

 

 

 

 

 

 

 

STD Code

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<iostream>
typedef long long LL;
#define INF 100010
using namespace std;
struct node
{
    LL start;
    LL speed;
    LL range;
    int th;
};
node cow[INF];
int data[INF];
int f[INF];
int ans;
int p=1;
int pa[INF];
bool cmp_start(node a,node b)
{
    return a.start<b.start;
}
bool cmp_range(node a,node b)
{
    if(a.range==b.range)
        return a.th>b.th;
    return a.range<b.range;
}

int tmp[INF],cnt=0;
int maxval[INF];
int lowbit(int x){return x&-x;}
void add(int x,int val,int num)
{
    while(x<=num){
        maxval[x]=max(maxval[x],val);
        x+=lowbit(x);
    }
}
int query(int x)
{
    int rn=0;
    while(x)
    {
        rn=max(rn,maxval[x]);
        x-=lowbit(x);
    }
    return rn;
}
int main()
{
    int num,t;
    scanf("%d%d",&num,&t);
    for(int i=1;i<=num;i++)
    {
        scanf("%I64d%I64d",&cow[i].start,&cow[i].speed);
        cow[i].range=cow[i].start+cow[i].speed*t;
    }
    sort(cow+1,cow+num+1,cmp_start);
    for(int i=1;i<=num;i++)
        cow[i].th=i;
    sort(cow+1,cow+num+1,cmp_range);
    for(int i=1;i<=num;i++)
        data[i]=num-cow[i].th+1;
    int ans=0;
    for(int i=1;i<=num;++i)
    {
        t=query(data[i])+1;
        ans=max(ans,t);
        add(data[i],t,num);
    }
    printf("%d\n",ans);
    return 0;
}

问题分析

 考试的时候,只写及了遵循起点位置排序虽描写不下去了(其实,最开头自我还当马上是同样鸣“纯数学水题”——当然,现在啊道就道题的思量难度的确无生)

脚,我们来打一个贪图:

5588葡京线路 1

通过观察图片我们可发现:当奶牛A的起点(cow[A].start)小于奶牛B的起点(cow[B].start),且奶牛A的终点(cow[A].range)大于奶牛B的极端(cow[B].range)时,就判断为A在t时间内会追上B,即要一致长长的新的跑道。由于题目条件中出:“按起点递增的各个为起”,因此我们无待排序虽足以发现:对于cow[i]来说,只要cow[i].range<cow[k].range
(k>i),就说明cow[i]与cow[k]足合用相同久跑道。由此推广:在享有的cow.range中只要属于一个上升子序列,就得同用同一长条跑道。这时想到了哟?拦截导弹!也就是说,这时的极端长下降子序列的长度就是用跑道的数。

只是,问题来了:目前我们所模拟的求最好长下降子序列的时刻复杂度是O(n^2)的,对于100000底数据一定会晚点,这时,我们且用到任何一样种更精彩之算法了。

当面的代码中,我为此底是线段树(当然,树状数组也是可的);而网上有同等栽更加“高级”的【lower_bound解法】,可以上网去寻觅自学一下。下面,我来讲说我之笔触:

咱俩安一个数组来分别存储数组中因为每个数为结尾的尽丰富齐升子序列(若有多单,取结尾最小之),这样一来,就可由此判断新增的往往是否比较前的末段很,若于前的末尾很,就得创新当前最好丰富齐升子序列的值。当然,如果直白for循环暴力,时间复杂度还是O(n^2)的,这时,我们就要用线段树要树状数组来展开优化,这样时间复杂度就见面变为O(n
logn)了。本题中之极致长下降子序列也是如出一辙的。

<最丰富不生降子序列-树状数组解法小结>

不降子序列求的凡一个要素的价单调不退底队列。

风土人情的状态统筹虽是使用f[n] 表示至第n各时之卓绝丰富无降子序列。

那么换就是:

f[n]=max(f[i]+1)

中间要求:a[i]<=a[n] && i<=n

选个例证:

5588葡京线路 2

那想使使得复杂度比较漂亮,就未能够通过枚举所有满足条件的i来找到最好优解。那么树状数组在里边就好由至特别快的询问及极致妙的f[i]的作用。

此的树状数组是当桶来使的。我们好事先考虑桶的状况。我们现在起来一个桶,其下标
x 表示 a[i]=x 的f[i]的不过可怜价值。

T[x]=max(f[i]); //其中a[i]=x

这就是说得转移至f[n]的讲话,就先行找到a[n]在桶中的职位,然后查询所有a[n]前所蕴藏的顶可怜价值备受之极老价值。也即相当给是一律段子前缀着之绝酷价值。

f[n]=max(T[x]+1); //其中x<=a[n]

在枚举f[n]的同时,也将f[n]的值扔入桶中,方便之后的创新。

T[a[n]]=max(T[a[n]],f[n]);

而桶的前缀和凡可以用树状数组来优化的,那么查询同一段落前缀的不过深价值与更改某个位置的价就是可在O(n
logn)的光阴外成功了。

 

Time : 2017-03-28