收入计划

问题描述

高考结束后,同学们大都找到了一份临时工作,渴望挣得一些零用钱。从今天起,Matrix67将连续工作N天(1<=N<=100 000)。每一天末他可以领取当天及前面若干天里没有领取的工资,但他总共只有M(1<=M<=N)次领取工资的机会。Matrix67已经知道了在接下来的这N天里每一天他可以赚多少钱。为了避免自己滥用零花钱,他希望知道如何安排领取工资的时间才能使得领到工资最多的那一次工资数额最小。注意Matrix67必须恰好领工资M次,且需要将所有的工资全部领走(即最后一天末需要领一次工资)。

输入

第一行输入两个用空格隔开的正整数N和M
以下N行每行一个不超过10000正整数,依次表示每一天的薪水。

输出

输出领取到的工资的最大值最小是多少。

样例输入

1
2
3
4
5
6
7
8
7 5
100
400
300
100
500
101
400

样例输出

1
500

样例说明

采取下面的方案可以使每次领到的工资不会多于500。这个答案不能再少了。
100 400 300 100 500 101 400 每一天的薪水
<——1 <——-2 <—3 <—4 <—5 领取工资的时间
500 400 500 101 400 领取到的工资

分析

最小值最大/最大值最小类问题 -> 二分答案典型问题

二分答案模板,对于 l 与 r 的理解,不要仅仅用「二分法解方程」的思想理解,此类题 可把 l 看作不可行域, r 看作可行域

此题需要二分工资最大值(单次领取的最高工资必定在 [单日工资最大值,全部工资] 的区间内)利用贪心(从左到右能取就取),判断是否可行。

二分答案模板

1
2
3
4
5
6
7
8
9
10
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# include<iostream>
using namespace std;
int n,m,sum=0,maximum=-1,ans;
int a[101000];
int check(int x)
{
int i;
int times=0,tot=0;
for(i=1;i<=n;i++)
{
tot=tot+a[i];
if(tot>x)
{
tot=a[i];
times++;
}
if(times+1>m)//判断是否恰好领 m 次,注意是 times+1
return 0;
}
return 1;
}
int main()
{
int i;
cin >>n>>m;
for(i=1;i<=n;i++)
{
cin >>a[i];
maximum=max(maximum,a[i]);
sum=sum+a[i];
}
int l=maximum,r=sum;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
cout <<ans<<endl;
return 0;
}
分享到

最短路径问题

问题描述

平面上有 n 个点(n<=100),每个点的坐标均在-10000~10000 之间。其中的一些点之间有连线 。若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离 。现在的任务是找出从一点到另一点之间的最短路径 。

输入

输入共 n+m+3 行,其中:
第一行为整数 n。
第 2 行到第 n+1 行 (共 n 行 ),每行两个整数 x 和 y,描述了一个点的坐标。
第 n+2 行为一个整数 m,表示图中连线 的个数。
此后的 m 行(m<=1000),每行描述一条连线,由两个整数 i和 j 组成,表示第 i个点和第 j 个点之
间有连线 。
最后一行 :两个整数 s 和 t,分别表示源点和目标点。

输出

输出仅一行,一个实数(保留两位小数),表示从 s 到 t 的最短路径长度 。

样例输入

1
5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5

样例输出

1
3.41

分析

顶点数较小,不加优化的 Dijkstra 即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
const int INF=1<<29;
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int x[110],y[110];
double dist[110][110];
// dist 数组即用作存边权的边集数组,若两点间有边则存其边权,没有则赋为 ∞
bool flag[110];// flag 用作标记每个端点是否已访问
double getdist(int x1,int x2,int y1,int y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
memset(flag,0,sizeof(flag));
int n,m,s,t;
int i,j,k,pos;
for(i=0;i<110;i++)
{
flag[i]=0;
for(j=0;j<110;j++)
dist[i][j]=INF;
}
cin >>n;
for(i=1;i<=n;i++)
{
dist[i][i]=0;
cin >>x[i]>>y[i];
}
cin >>m;
for(i=1;i<=m;i++)
{
int a,b;
cin >>a>>b;
dist[a][b]=dist[b][a]=getdist(x[a],x[b],y[a],y[b]);
}
cin >>s>>t;
flag[s]=1;
for(i=1;i<=n;i++)
{
int minimum=INF;
for(j=1;j<=n;j++)//找离 s 最近点 j
{
if(!flag[j] && dist[s][j]<minimum)
{
pos=j;
minimum=dist[s][j];
}
}
flag[pos]=1;
for(j=1;j<=n;j++)
if(!flag[j] && dist[s][pos]+dist[pos][j]<dist[s][j])
//以找到的点为中间点,更新 s 到各顶点的最短距离
dist[s][j]=dist[s][pos]+dist[pos][j];
}
printf("%.2lf\n",dist[s][t]);
return 0;
}
分享到

如何在 VPS 上搭建 Hexo 博客并使用 Git Hooks 更新?

几个你或许会问我的问题

为什么是 Hexo ?

A fast, simple & powerful blog framework, powered by Node.js.

- @tommy351 ( Hexo 作者 )

现在是 2015 年,身在开发者圈里,如果想开始写一个 Blog ,使用静态网站生成器搭建无疑是最好的选择,而最热门的三款生成器 Jekyll / Octopress / Hexo 中,对于不懂前端的我们, Hexo 有着质量最高的主题,几乎可以说是唯一的选择,相比 Jekyll / Octopress ,安装简便,生成页面效率有质的区别(可以想象某一天积累到 100 篇 Blog , Jekyll / Octopress 生成需要花费数分钟,而 Hexo 仍仅需几秒的血泪对比)。

为什么是在 VPS 上?

因为种种原因,如 GitHub 的 CDN 提供商是 fastly ,而 fastly 同时为 Twitter 提供服务; GitHub 上有许多并不和谐的项目…… GitHub 在国内多次被墙。使用 VPS 相比于 GitHub Pages 更为自由,比如可以为博客 配置 SSL ,无论是 从前面进还是从后面进 的你,最终目标都是把自己补全为一个 full-stack developer ,更早地向 Dev-Ops 方向迈进对你没有任何坏处。我始终认为,每一位 梦想成为魔法师的男孩 都应该有一个 VPS ,无论在你学习的哪个阶段,它总是可以用来做许多有趣抑或有用的事。

为什么通过 Git Hooks 更新?

其实你也可以本地什么都不做,每次都把文章的 *.md 通过 sftp 上传到 VPS 上,然后在 VPS 的网站目录中执行 hexo d -fg 更新博客,至于这个过程感受如何,请自行品味。

我还没有 VPS ?

/*以下提及的两款 VPS 同时均可搭建个人独享的代理服务*/

  • 如果可以接受每 5 的价格 -> DigitalOcean /*通过链接注册赠送 10 ,在开发者社区中有很好的声誉,是这个行业中为数不多的靠谱提供商之一,堪称最优性价比。*/
  • 如果可以接受每 4.5 的价格 -> 123Systems /*需要输入优惠码 LABOR 才可以以 4.5 的价格购买。机房一定要选择 Los Angeles 。如果缺货,属于正常情况,请耐心等待。 越便宜的东西,很可能就越容易出问题,因为商家不可能在卖给你那么便宜的同时还用足好料。而且如果出了问题,因为本身就是没有利润的东西,商家很可能也就不会当回事了。 作为练手可以,但是请一定做好数据备份,并在资金充裕时及时迁移到更好的服务。*/
  • 不愿意/不能为 VPS 付费?请使用 GitHub Pages 和免费代理服务,关于是免费代理服务,一句话忠告:免费的是最贵的。既然总还是需要购买代理服务的,为什么不自己搭建呢?

域名如何注册、配置?

如果还没有注册域名,推荐使用 namesilo ,这是目前在国外注册域名的最廉价注册商(各种数年一遇的活动不计),在这里注册的所有域名都 免费赠送域名保护 ,至于为什么不在国内注册?你懂的。使用优惠码 EscapeFromChina 可以获得 1 美元优惠(即每年 8.99 - 1 ≈ ¥50 ),可以使用 支付宝 付款。

配置即在域名注册商(如 namesilo )的管理台将域名的 NS 服务器设置为 DNSPod / CloudXNS 的,并在 DNSPod / CloudXNS 上为域名配置一条 A 记录和一条 @ 记录,记录值为你的 VPS IP ,配置较为基础,如果你不知道具体如何配置,请自行搜索。


搭建过程

搭建过程分为两部分,一部分在本机进行,另一部分则在服务端进行,大致需要完成的工作是在本机和 VPS 各安装一次 Hexo 和 Git ,并在 VPS 上安装 Nginx 服务器、配置 Git Hooks 以实现更新。

本机1

Linux Desktop

Linux Desktop 用户一定都是 Power User ,此处略。

Windows

以下下载 强烈 建议在 代理 下进行,或者自行寻找国内源。

安装 Node.js

Node.js 官网下载最新版,一路默认安装。

安装 Git

下载 Git for Windows ,一路默认安装。

Mac

安装 Homebrew

安装 Node.js

使用 Homebrew 安装 Node.js
brew install node

安装 Git

系统自带,无需手工安装。

Windows && Mac

/*以下操作, Windows 涉及 Node.js 、 Hexo 的操作都在 cmd 中输入 node 后执行,涉及 Git 的都在 Git Bash 中执行。 Mac 所有操作都在 Terminal 中执行。*/

创建网站目录

在任意位置创建一个文件夹,作为网站目录,并通过 cd 命令进入文件夹。

本地安装 Hexo

1
2
3
4
5
npm install -g hexo-cli
hexo init
npm install
hexo d -fg
hexo serve

打开 http://localhost:4000 即可看到你的站点(当然还没有发布到网络)。

本地 Git 配置

同样通过 cd 命令进入文件夹,之后执行

1
2
3
git init
git add .
git commit -m "Initial commit"

VPS

此处为 Debian / Ubuntu 在 root 用户下的操作,使用其他发行版本的一定是 Power User ,略。

关于连接 VPS , Windows 用户请使用 Putty (提示: Putty 中使用粘贴仅需鼠标右键), Mac 则直接在 Terminal 中输入 ssh root@IP

关于 vi 操作,不会用 vi 可以将下列命令中的 vi 全部替换为 nano (可能需执行 apt-get install nano -y ),如果觉得 nano 使用还是相对复杂,请使用 SFTP 工具, Windows 用户可使用 WinSCP , Mac 可使用 Cyberduck

1
2
3
4
5
6
7
8
9
apt-get update && apt-get upgrade -y
apt-get install git-core -y
curl -sL https://deb.nodesource.com/setup | bash
apt-get install nodejs -y
apt-get install nginx -y
cd /etc/nginx/sites-available
rm -rf default
touch example.com
vi example.com

在其中输入如下内容并保存,注意 IPexample 需替换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
server {
listen IP:80 ;
root /var/www/example.com/public;
server_name example.com;
access_log /var/log/nginx/example_access.log;
error_log /var/log/nginx/example_error.log;
location ~* ^.+\.(ico|gif|jpg|jpeg|png) {
root /var/www/example.com/public;
access_log off;
expires 1d;
}
location ~* ^.+\.(css|js|txt|xml|swf|wav) {
root /var/www/example.com/public;
access_log off;
expires 10m;
}
location / {
root /var/www/example.com/public;
if (-f request_filename) {
rewrite ^/(.*) /1 break;
}
}
}

之后执行

1
2
3
4
5
6
7
8
ln -s /etc/nginx/sites-available/example.com /etc/nginx/sites-enabled/
cd ~
mkdir repos && cd repos
mkdir example.com.git && cd example.com.git
git init --bare
cd hooks
touch post-receive
vi post-receive

在其中输入如下内容并保存,同样注意前四行的替换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/bin/bash -l
GIT_REPO=HOME/repos/example.com.git
TMP_GIT_CLONE=HOME/tmp/git/example.com
PUBLIC_WWW=/var/www/example.com
rm -rf {TMP_GIT_CLONE}
git clone GIT_REPO TMP_GIT_CLONE
rm -rf {PUBLIC_WWW}/*
cp -rf {TMP_GIT_CLONE}/* {PUBLIC_WWW}
cd ~
cd {PUBLIC_WWW}
hexo d -fg
cd ~
exit

最后执行

1
2
3
chmod +x post-receive
cd ~
service nginx restart

本机2

以下操作需要先 cd 到网站目录,注意替换

1
2
git remote add example root@IP:repos/example.com.git
git push example master

此时需要输入一次 VPS 密码,稍等片刻即安装完成。打开 example.com 即可看到你的博客。


关于更新 Blog

使用一款 MarkDown 编辑器写 Blog 。写完后将文件以 *.md 的格式保存在本地 [网站目录]\source\_posts 中。 文件编码必须为 UTF-8这一点仅 Windows 用户需注意。 如果你不知道使用什么 MarkDown 编辑器,请自行搜索。

每篇 Blog 都有固定的参数必须填写,参数如下,注意每个参数的 : 后都有一个空格。

title: title
date: yyyy-mm-dd
categories: category
tags: tag
#多标签请这样写:
#tags: [tag1,tag2,tag3]
#或者这样写:
#tags:
#- tag1
#- tag2
#- tag3
---
正文

cd 网站目录后执行

1
2
3
4
hexo d -fg
git add .
git commit -m "Post A New Blog"
git push example master

最后的几句话

靡不有初,鲜克有终。坚持做下去,你生活中的每一条河流都会在这里留下痕迹,你可以一直做到你老去的那一天,让你的整个人生沉淀成一个页面丰富的 html 文件夹

感谢@Sunyanzi 在加班中抽出时间对搭建的帮助:)

分享到

Hello World

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

分享到

JSOI 2015 扬中高中春游记

在寒假开始的时候,我作为市区唯一的信息学竞赛学习者,到在扬中高中举办的 JSOI 2015 冬令营进修。

说是学习、进修其实比较牵强。这次冬令营偏数据结构(主要在讲树和图的基础),毕竟仅仅是 6 天的时间,学到的主要还在于写 demo 和学会这些数据结构的 CRUD ,冬令营只能是一个开始,如标题所说,当作春游就好。它的效果更多的还是去 push 自己花费寒假的一段时间(1/3= =) focus 在 OI 上,看一看别人的学校,认识一群靠谱/不靠谱/有趣的 Pre 神犇,被各路神犇狂虐,培养一颗强大的「有自知之明」的健全心灵。



//17:30 的扬中高中

扬中是个小县城,来时的大巴上,只有两位乘客,显得空空荡荡。 DAY0 报到结束后有在市(县级市)中心转了一圈,很像初中之前住的那个小镇 10 多年前的样子,事实上这里的建筑也大多是 10 年前的。某机智的室友想要找一家 StarBucks 上一会儿网,打开 Siri 查到的时候大喜,结果没多久发现在江对岸的泰州。


//李立新教授和他的爱徒林厚从老师

本以为这次会和 JSOI 2012 夏令营一样欢乐的,到了 DAY1 才发现高中和初中来的心态完全不同, A 班几乎完全被初(小)中(学)生占领,而自己也很难出类拔萃,前两天确确实实有些难熬,不过适应了还是不错的。

还是 JSOI ,李立新教授还会讲数学,林厚从依然睿智如故。物是、人是、人非,我不是当初那个意(中)气(二)勃(气)发(盛)的孩子了,如果最后一次 NOIp 还是跪,光靠文化课,我又该何去何从呢?

七年之后,某二本院校毕业,在北京某个地下室里敲着代码,于己于家无望,无房无车注孤身,完全可以是我的未来。


流水账式地一下这次的知识结构:

#DAY1

    • 树的概念、表示
    • 二叉树
      • 二叉树的基本概念和与初赛题的综合
      • 二叉树的存储结构
        • 顺序存储
        • 链式存储
        • 静态链表存储
      • 二叉树的建立
      • 二叉树的遍历

#DAY2

  • 哈夫曼树
    • 哈夫曼编码
    • 大根堆和小根堆
    • 堆的 CRUD
    • 堆排序
  • 二叉排序树
    • 二叉排序树的优点
    • 二叉排序树的 CRUD

#DAY3

  • 并查集
    • 并查集的优点
    • 并查集的合并操作
    • 路径压缩

#DAY4

    • 图的存储方式
      • 邻接矩阵
      • 边集数组
      • 邻接表
      • 邻接压缩表
    • 最小生成树
      • Prim
      • Kruskal

#DAY5

  • 最短路
    • Warshall
    • Floyed
    • Dijkstra
    • SPFA

#DAY6

  • 图的连通性
    • 割点、割边
      • 用 DFS 找割点、割边
    • 强连通分量
      • Kosaraju
      • Tarjan


//带排骨汤的第一餐

这 7 天,没有一天早于 00:30 入睡,白天仍然富有生机(对,生机,所以拍照手总会抖 XD),在陌生的县城的 KFC 改善过伙食,第一次见识了在食堂汤里加排骨的土豪作风,在回宾馆的路上坐过门卫大爷的电动车,在扬中高中周围的小道上散过步,认识了好几位 Pre 神犇的队友,每天基本保持 AC 25%-50% = =,在 iPad 上玩通关了正常的大冒险,智商最低降到 -3100 ,欢乐地蹭过食堂 Wi-Fi ,因为机器的原因反复装过超过 5 次 Windows 10 Preview 和 Linux Mint ,在宾馆独占过网络(路由器未设密码,限制了连接设备 MAC 地址),被 6 年级参加提高组的小学生虐过,在冬令营过半的时候,意外地从持续了半个学期的 low spirit 里慢慢的走出来。


李立新教授某天忽然课前兴起,讲到 1992 年的 NOI 中,那时候 NOI 还是不限时的,某位江苏代表队的学生写了一通暴力,程序从上午跑到晚上 12 点,那位同学只能一直在旁边等结果,到 12 点的时候被打发回去了。

从此…… NOI / NOIp 就限时了……


这里的遇到的老师都不是文化课补习班遇到的某些只是把讲课进度不断推进,几乎不对学生负责的类型。 JSOI 印象深刻的老师应该有李立新、林厚从、杨志军,或许以后还会有神龙见首不见尾的曹文。不过在 JSOI 2012 教过动规的荆晓红老师这次说的话总是戳中我的痛点,共勉。

「你学到现在如果怕难、怕烦,那就意味着你的 OI 生涯即将结束。」

「有的同学在用骗分求解,一条题似乎也能骗到 60 分,甚至 80 分,但是这对你毫无益处,你唯一可以骗分的,是在 NOIP 真的想不到思路时。」

「到你们现在的水平,应该多自己做,而不是背别人的代码。一开始写不出较优的算法或是较好的优化没关系,应该自己一步步的去改进,在这个过程中可以多看别人的代码中的思路。」

可是我的 OI 生涯真的即将结束了= =



//两位清华爷(学生教练),被机器挡住的那位一直在读佛经。

结营考试倒是异常的简单,或许是老师想到大家也都累了,一共是三条题:

  1. NOIp 2014 D1T2 联合权值,但似乎加强了数据。
  2. 找规律、随便写。另外听说使用树状数组求 lowbit 或者使用位运算。
  3. Prim ,如果用 Kruskal 会爆 0 。

One more time, one more chance. Step by step to seize everything you ever wanted.

Wherever we go, never foget we are OIers.


By Dynamicer
In Yangzhong At 20150209 DAY2 && 20150210 DAY3
On The Way Back At 20150213
In Nantong At 20150213

分享到