《简约至上》读书简摘

六.结尾的叮嘱

  • 将复杂放到哪里。设计用户体验的最后,往往是问,把纷纭放在何地。
  • 本条义务应该是自动化,照旧用户来控制?
  • 界面中应有是富含众多职能特定按钮,依然只放通用按钮。
  • 职分是一回性落成,如故分几段时光成功。
  • 义务是让用户有意识去做到(例如用屏幕上的控件来筛选搜索结果),照旧应该在无意已毕(如查看London地图中的深黄线路)。
  • 让简答发生在用户的脑子中
    不用让您的设计干扰了用户的思绪。简单的宏图能为用户留出充分的空中,他们会用本人的生活来填充那么些空间,从而成立出更增进,更有意义的体会。

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

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;
}

二.删除

  • 简化设计最明显的章程,就是剔除不要求的法力。
  • 与新增功效相比较,客户更关怀基本作用的改革。
  • 名列功用优先级,看看产品能仍然不能充裕满意用户最高优先级
  • 去掉可有可无的选项,分散人们注意力的玩具。让用户专心去做本人的事情。
  • 慎选个别,用户反而更欣赏。减弱用户的选料,加速决策进程。
  • 清除错误的来源于是简化体验的显要思路。
  • 调减视觉混乱
  • 用空白和微小的背景观来划分页面。不要采纳线条。
  • 尽只怕少使用强调,加粗就足足了,不用加粗,放大,又改成金红
  • 别使用粗黑线,匀称,浅色的线更好。
  • 控制音信层次。最好不当先多个层次:标题,子标题,正文。
  • 减去成分大小的变化。

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

首先大家来设想一下:面前有一叠牛,infor最大的在最上面,越往上,牛的infor越小。大家对那叠牛从下往上编号123。下边,就是核心了:

咱俩看来第i头牛和第i-二只牛(也等于说cow[i]在cow[i-1]的方面):其中,设第i头牛还可以承受的分量为cow[i].strong-W,第i-3头牛还能承受的份量为cow[i-1].strong-(cow[i].weight+W),那多个值的min就是该限量内的答案了;

如今,我们来“翻盘”,把第i头牛和第i-三头牛对调一下岗位(以后,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更优。以此类推,就可证出该结论。

五.转移

  • 在配备之间转移
  • 在运动平台和桌面平武汉间转移
  • 向用户更换。例如旅游行程陈设软件。对举棋不定情况的处理,简单的界面,将复杂的劳作留给用户。
  • 用户擅长什么。计算机擅长精确保存消息,人欣赏控制结果。基本型旅行行程布置软件把内定目标和集体记录的做事留给用户,对电脑来说复杂的职分,对人而言易如反掌。让用户觉得不难的主要前提是:先搞领会把很忙工作付出统计机,将何以工作留给用户。

样例数据

样例输入 样例输出

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

 

 

 

 

 

 

 

 

 

 

 

 

 

一.醒目认识

  • 叙述要点的两种艺术:
    1.用一句话把它写出来,要统筹怎样,遵从哪几条规划规则。(不难而神速)
    2.描述用户的行使处境,以及作者的规划要怎么着满意用户在本场景下的必要。(重用户体验)

  • 走出办公室
    软件的施用环境,是着眼用户的极品地方,使软件符合环境须求。

  • 着眼什么
    走进现实环境,你会意识影响用户体验的因素如此之多。

办公室:
有些有意思的话题传遍耳朵,有人会竖起耳朵听,因而打断工作。
来电话,短信,新邮件。。
为有些会议打印文档,他们常备最终一分钟去打印。

家里头:
边用台式机边看TV。
宽带速度不如公司线路那么平稳。
在儿女看卡通时候购物。

户外:
通话时可能背着几个包,手机按键不够大会很麻烦。
知晓的太阳或许令人看不清显示屏。

您的用户体验应该简单到不受这几个苦恼的影响,可以在人们被打断的空闲生存。

  • 两种用户
    1.专家型,花时间体验有所的成效。
    2.随意型用户,有趣味使用高级复杂的制品,却不乐意接触全新的事物,学习意愿不显明。
    3.主流用户,使用你的制品只为完毕职责。
    值得注意的是:他们的标签并不会趁着岁月升级

  • 主流用户想要什么

主流用户和学者用户需求差别

第①题:马拉松竞技

四.隐藏

  • 暗藏不常用但不可以少的作用。
  • 及时出现。如字典功能唯有在选拔单词之后才会来得。
  • 让职能简单找到。当用户专注于某一项任务时,他的关注点汇聚焦。蒙受标题今后,他们过度专注显示器上难题区域。固然标签再大,尽管身处了用户关心点之外,用户也看不到。
  • 借使不要令人找太久,隐藏就是水到渠成的。

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;
}

三.组织

  • 分块。将项社团到”7加减1”个块中。分块越少,采用越少,用户承担越轻。
  • 围绕行为展开团队。画出用户作为有助于精晓您的软件出品。
  • 网格。利用不可见的网格来对齐页面成分。网格越是不难,效果越来越显著。
  • 分段。可以利用颜色,海军蓝阴影,大小缩放,形状变化,来让用户感知分层。

这是 三道 USACO 的题……

其三题:奶牛慢跑

输出

若果奶牛的武装部队得以够到飞盘,输出还能接受的最大额外重量;否则输出“马克 is
too tall”.

题材叙述

有n(n<=一千00)头奶牛在一个无穷长的小道上慢跑。每头奶牛的源点不一样,速度也不相同。小道能够被分为多条跑到。奶牛只可以在属于自个儿的跑道上慢跑,不容许更换跑道,也不容许改变速度。如若要慢跑t(t<=一千000000)分钟,要保证在其它时候不会有同样跑道上的奶牛相遇,请问最少须要多少条跑道。奶牛起首在哪条跑道是足以随心所欲安装的。

标题分析

代表考试的时候碰都未曾碰——看到那些神奇的难题还有查询操作就感到头大。上网搜过了原题,发现原题实际上并不曾U操作与Q操作,因而原题的解法就是1个DP。然而,对于那道经过改动的题来说,显著不是DP就能消除的了:O(n)的DP套上O(n)的查询,总时间复杂度初叶估价最少为O(n^2),对于那一千00的数据就唯有“嘿嘿嘿”。

在看正解此前,先来科普一下:什么是“曼哈顿相距”,大家用二个姿势来表示(设一平面上有两点: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)的最大值。到了那边,大家发现,线段树就足以化解这几个标题嘛:建立2个线段树来存储Benifit(k),每回搜寻就寻找该区间的最大值就行了。然则,在写代码的时候你会意识,由于有加点的操作,而且Ans=Distance_Origin-max(Benifit(k)),其中求Distance_Origin要用前缀和来求,所以,我们还索要树立1个线段树来存储从A[Start]到A[End]原本应走的路途(你也可以把一个线段树的结构体开大一点,将Distance_Origin与Benifit的值存到一块儿)。那样写下来,就没毛病了。

输入

第二行包罗N和H。

接下去N行,每行七个数,分别代表它的惊人、重量和强壮度。全数的数都为正整数。

输入

第二行包罗N和Q。接下来N行,每行多少个数(X,Y),表示逐个点的坐标,根据号码从小到大的次第给出。

接下去Q行,每行表示三个操作。操作如上所述。

样例数据

样例输入 样例输出

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

标题叙述

奶牛Bessie给她的同伙设计了一条马拉松竞技的路线。那条路线上一共有n(n<=一千00)个点,它们分布在1个平面坐标系中。它的同伴毅力不够,所以不大概跑完全程,于是Bessie给他俩配备了一条子线路(它是一段连接的点,比如设定子线路为【i,j】,表示奶牛必要从点i初叶,经过点i+1,点i+2,……,最终到点j)。即便如此,奶牛们依然大概跳过中间有个别点以节约路程,当然这一个点不或许是子线路的起点或极端。未来,有Q(Q<一千00)个操作:操作分为二种,第3种为”U
I X Y”,表示将点I的职分设在坐标(X,Y)处;第2种为Q I J,表示设定子线路为点i到点j,要求查询奶牛们从i跑到j的最短里程。(路程是以曼哈顿相距总结的)他们可以跳过中间有些点。

全体的坐标值x,y均在[-1000,+1000]区间。

<最长不下降子系列-树状数组解法小结>

不降子系列求的是1个成分的值单调不降的行列。

传统的状态统筹便是使用f[n] 表示到达第n位时的最长不降子连串。

那就是说转移就是:

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

个中须要:a[i]<=a[n] && i<=n

举个例证:

图片 1

这就是说想要使得复杂度比较优,就不能透过枚举全数满意条件的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

样例数据

样例输入 样例输出

5 3

0 1

1 2

2 3

3 2

6 1

3

 

 

 

 

 

 

 

 

输入

首先行五个整数n,t。

接下去的n行,每行包括多少个整数,表示奶牛的地方和进度。地点是非负整数,速度是正整数。全数的奶牛的源点都不均等,按起源递增的依次给出。

输出

最少的跑道数。

标题分析

 考试的时候,只写到了按起源地方排序就写不下来了(其实,最开首自作者还以为那是一道“纯数学水题”——当然,以后也觉得那道题的思索难度确实不大)

下边,大家来画多个图:

图片 2

通过旁观图片大家得以窥见:当奶牛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中只要属于3个回涨子连串,就足以共用一条跑道。那时想到了怎么?拦截导弹!也等于说,那时的最长下落子系列的尺寸就是内需跑道的数额。

只是,难点来了:近日大家所学的求最长下落子连串的光阴复杂度是O(n^2)的,对于一千00的数额肯定会晚点,那时,大家就要用到另一种更美妙的算法了。

在上边的代码中,小编用的是线段树(当然,树状数组也是足以的);而网上有一种更加“高级”的【lower_bound解法】,可以上网去寻觅自学一下。上边,作者来讲讲笔者的笔触:

大家设置二个数组来分别存储数组中以各种数为最终的最长上涨子连串(若有多少个,取结尾最小的),那样一来,就可以通过判断新增的数是或不是比在此之前的最终大,若比以前的终极大,就可以立异当前最长上涨子序列的值。当然,倘诺直白for循环暴力,时间复杂度依旧O(n^2)的,那时,大家即将用线段树或树状数组来开展优化,那样时间复杂度就会变为O(n
logn)了。本题中的最长下跌子体系也是相同的。

首先题:奶牛飞盘

题材叙述

有n(2<=n<=20)头奶牛在玩飞盘,然则飞盘飞到了高处。以后她们要想艺术叠在一块,去取飞盘。飞盘的可观为H(1
<= H <=
1,000,000,000)。给出每头奶牛的分量、中度、强壮度(可以接受的轻重),问她们是否够得到,即便可以取到,求它们额外还能经受最多多少重量。(要保障每头奶牛所收受的分量都不当先它的强壮度)。

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循环把奶牛3个个按排好的逐条叠上去——最终就WA了(看来样例与本身要好的样例仍旧比较水qwq)正确的解法是:由于不是每一只奶牛都得以被选中,即每三只奶牛都有“被入选”与“未选中”三种景况,对于这种线性查找最优解的题目,大家可以展开DFS,不断更新ans,最后收获答案(若到结尾都没更新到ans,就认证无解)。

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

输出

对于每一回查询,输出二个平头,表示该子线路的最短路程(曼哈顿距离)。