The Bakery 解题报告(cf833b dp 带优化的dp 线段树)

http://codeforces.com/contest/833/problem/B

NOTICE

推荐在写这道题前看看 HH 的项链 解题报告(SDOI 2009 线段树 排序 离线处理)

算法设计

拿到题,3分钟,这是一道动态规划。写码,调试,提交,一气呵成,最后发现在第4个点超时。转过头来看,发现在处理每一个状态的时候套着一个循环,导致整体算法复杂度 O(n ^ 3) 遂放弃。

最近学习了线段树,然后再看这道题,发现了这道题在求不同数字的个数的时候进行了很多不必要的重复运算,可以用线段树解决。

由于本人的描述实在不行,具体解决方案请直接看下面代码以及其注释,先粗略看一遍全局变量的定义,然后再看一下main函数。

配合这张图食用更佳。

示例代码

#include <cstdio>
#include <cstring>

const int N = 38500; // 35000 * 1.1 

int n, k, a[N]; // 题目中提供的数据 

int last[N]; // 记录该位置的数上一次出现的位置,last[i] 代表 a[i] 位置上的数在 a 数组中上一次出现的位置,如果没有出现过,则为 0 
int index[N]; // 用于辅助建立 last 数组 

int d[N]; // 动态规划中用于保留结果的数组, d[i] 代表在一次切割中(阶段),最后一个切割点(或者说是最后一个箱子装的最后一个蛋糕的坐标)的结果 

struct node {
    int l, r;
    int f;
    int max;
    node *lc, *rc;
} mem[2 * N];
node *memp;
node *root; // 线段树中第 i 个位置的数 为 上一个阶段 d[i] 以及 i + 1 ~ j 中不同数字的个数 的和,其中 j 为当前推进到的位置,详见下方解释 

inline void push_down(node *p) {
    if (p->f) {
        p->lc->max += p->f;
        p->lc->f += p->f; // mistake: 就像傻子一般,线段树这里给写错了 
        p->rc->max += p->f;
        p->rc->f += p->f;
        p->f = 0;
    }
}

inline void pull_up(node *p) {
    if (p->lc->max > p->rc->max) p->max = p->lc->max; else p->max = p->rc->max;
}

node *init(int a[], int l, int r) {
    node *p = memp++;
    p->l = l;
    p->r = r;
    p->f = 0;
    if (l == r) {
        p->lc = p->rc = NULL;
        p->max = a[l];
    } else {
        int mid = (l + r) >> 1;
//      printf("%d %d %d\n", l, mid, r);
        p->lc = init(a, l, mid);
        p->rc = init(a, mid + 1, r);
        pull_up(p);
    }
    return p;
}

void change(node *p, int l, int r) {
    if (l <= p->l && p->r <= r) {
        ++p->max;
        ++p->f;
        return;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    if (l <= mid) change(p->lc, l, r);
    if (mid < r) change(p->rc, l, r);
    pull_up(p);
}

int query(node *p, int l, int r) {
    if (l <= p->l && p->r <= r) {
        return p->max;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    int max = 0, tmp;
    if (l <= mid) {
        max = query(p->lc, l, r);
    }
    if (mid < r) {
        tmp = query(p->rc, l, r);
        if (tmp > max) max = tmp;
    }
    pull_up(p); // mistake:这里的pull_up是不可或缺的 

    return max;
}
//
//void debug2() {
//  for (int i = 1; i <= n; ++i) printf("%d ", last[i]);
//  printf("\n\n");
//}
//
//void debug1() {
//  for (int i = 0; i <= n; ++i) printf("%d ", d[i]);
//  printf("\n");
//} 

int main() {
//  freopen("input.txt", "r", stdin);

    scanf("%d%d", &n, &k);
    memset(index, 0, sizeof index);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        last[i] = index[a[i]]; // 读取输入的过程中同时填充一下 last 数组,last 数组的含义见上定义 
        index[a[i]] = i;
    }
//  
//  debug2();

    // 动态规划,为了能够对动态规划中的一个阶段中的不同状态下的求解能够快速进行,我们使用了递推,这样求解的顺序可以利用线段树进行优化 
    memset(d, 0, sizeof d); // 不难发现最开始的结果都是 0 的 
    for (int i = 1; i <= k; ++i) { // 阶段,即切割或者说是箱子的个数 
        memp = mem;
        root = init(d, 0, n); // 线段树是可以从 0 开始建立的,详见下方解释 
        for (int j = i; j <= n; ++j) { // 枚举当前阶段切割点的位置 
            // 诚然,我们对于每一个切割点而言,我们都可以跑一次如下的循环 
            /* 
            int max = 0, tmp;
            for (int k = i - 1; k <= j - 1; ++k) { // 很明显 i - 1 之前的是不可能满足题意的 
                tmp = last_d[k] + different_num_between(k, j);
                if (tmp > max) max = tmp;
            }
            */
            // 但是这样太慢了,我们发现,计算从 k 到 j 的有多少个不同的数字这个函数被调用了很多遍,并且发现貌似每次都进行了许多无用的计算
            // 我们建立一棵线段树,定义为当推进到 j 位置的时候,线段树中第 k 个数为从 k + 1(加一是为了初始化方便) 到 j 中不同数字的个数
            // 我们可以发现,last[j] + 1 到 j 中间是没有 a[j] 这个数的(一句废话)
            // 那也就是说,如果我们的进度推进到了 j 的话,对于所有的 在 last[j] + 1 ~ j 中的位置到 j 的不同数字种类应该会多出一个 j ,反映到数量上,就是个数 +1 
            // 映射到线段树的时候别忘了位置 -1 
            //  
            // 我们还可以发现,如果说按照上述定义,求最大值仍然需要扫描整个线段树,因为在原始的线段树上我们还需要增加上一个阶段的结果
            // 那么我们索性就在线段初始化的时候,将 d 数组作为线段树最开始的初始化用数组,这样求最大值就可以用线段树舒服的求出来了(当然线段树写错了当我没说) 
            // 
            // 被绕晕了?可以翻上去看看定义那里的注释,并且根据代码理解一下 
            change(root, last[j] + 1 - 1, j - 1); 
            d[j] = query(root, i - 1, j - 1); // mistake: 请注意,这里必须是 i - 1 而不是 i 
        }
//      debug1();
    }
//  
//  // 哦,我的老伙计,这一坨被注释的代码是彻头彻底的错误 
//  int max = 0;
//  for (int i = 1; i <= n; ++i) if (d[i] > max) max = d[i];
//  printf("%d", max);
//  for (int i = 1; i <= n; ++i) printf("%d ", d[i]);
//  printf("%d", d[n]); 

    printf("%d", d[n]);

    return 0;
}

Load Balancing 解题报告(USACO 2016 February Contest, Silver. Problem 2. 排序 树状数组 离散化)

USACO(W) (滑稽

题目解析

题目在线详情(提交地址):http://www.usaco.org/index.php?page=viewproblem2&cpid=619

题目意思其实很简单,给定一个二维矩阵(农场),其中放置着许多点(牛),求在一个恰当的地方切水平竖直两刀,使得所切的四个区域中点最多的那个区域中的点最少。(啥,还没看懂?回到题目详情继续啃英文)

算法设计

且不考虑什么 k-d tree 这种特别高级的算法,我们先想一想暴力怎么做?枚举每一个切割点(水平竖直切割线的交点)!但是,我们可以发现,由于x,y都特别大,这样会导致程序最后时间非常慢…

Wait!为啥点才1000多个?对,我们可以简单的在大脑中想,这么一个大矩阵,一大堆空间都是0,也就是说我们枚举了很多没用的位置点,我们可以对x,y单独(想一想为什么单独做是可以的)做一次离散化,这样可以迅速让枚举范围减小。离成功进了一步!

但是,依然很慢 O(n^3) ,原因其实蛮简单的,因为统计区域内的点非常的慢,每一次统计我们都统计了上次统计过的点。那为什么我们不想想办法解决这个问题呢?首先,我们可以让这些牛 有序 (其实这是我最开始的想法,比离散化的想法还要早一些),我们按行往下推进,然后我们对水平切割线的上下分别建立一个树状数组。(其实最开始我的想法是对每一行都建立一棵线段树的,但是发现其实没有必要每一行都建立一棵的),然后枚举每一个垂直切割线,这样我们的复杂度降低到了 O(n ^ 2 * logn)

实例代码

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 1100;

int n;
struct cd {
    int x, y;
} c[N];

bool cmp(cd a, cd b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

int *d[N];

bool cmp_d(int *a, int *b) {
    return *a < *b;
}

int t[N], b[N]; // 水平轴切开的上下两部分,top bottom 

void change(int t[], int k, int x) {
    while (k <= n) {
        t[k] += x;
        k += k & (-k); 
    }
}

int sum(int t[], int k) {
    int x = 0;
    while (k > 0) {
        x += t[k];
        k -= k & (-k);
    }
    return x;
}

int main() {
//  freopen("input.txt", "r", stdin);
    freopen("balancing.in", "r", stdin);
    freopen("balancing.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", &c[i].x, &c[i].y);

    // 对x进行排序,便于下方移动水平轴 
    std::sort(c + 1, c + n + 1, cmp); 
//  for (int i = 1; i <= n; i++) printf("%d %d\n", c[i].x, c[i].y); printf("\n");

    // 对y进行离散化,便于下方移动垂直轴
    for (int i = 1; i <= n; i++) d[i] = &c[i].y;
    std::sort(d + 1, d + n + 1, cmp_d); 
    int last = 0, count = 0;
    for (int i = 1; i <= n; i++) {
        if (*d[i] != last) {
            count++;
            last = *d[i];
        }
        *d[i] = count;
    }
//  for (int i = 1; i <= n; i++) printf("%d %d\n", c[i].x, c[i].y); printf("\n");

    // 移动水平轴,并且枚举垂直轴 
    memset(t, 0, sizeof t);
    memset(b, 0, sizeof b);
    for (int i = 1; i <= n; i++) change(b, c[i].y, 1); // 先填充水平轴下方的内容
    int ans = 0x7fffffff;
    int i = 1;
    while (i <= n) {
        int row = c[i].x; 
        // 从水平轴下方删除,并且添加到水平轴上方
        while (i <= n && c[i].x == row) {
            change(t, c[i].y, 1);
            change(b, c[i].y, -1);
            i++;
        }

        for (int j = 1; j <= n; j++) { 
            int tmp, stage_ans = 0;
            tmp = sum(t, j); // 上左 
            if (tmp > stage_ans) stage_ans = tmp;
            tmp = sum(t, n) - tmp; // 上右 
            if (tmp > stage_ans) stage_ans = tmp;
            tmp = sum(b, j); // 下左 
            if (tmp > stage_ans) stage_ans = tmp;
            tmp = sum(b, n) - tmp; // 下右 
            if (tmp > stage_ans) stage_ans = tmp;
            if (stage_ans < ans) ans = stage_ans; 
        }
    }
    printf("%d", ans); 

    return 0;
} 

使用CamStream配合OBS低成本实现功能强大的现场直播

你是否经常去户外直播?你是否苦恼各大直播平台的直播软件不够强大?你是否在犹豫是否购买价格高昂的直播设备?

来试试CamStream+OBS直播方案,低成本,功能强大!

请注意,技术更新非常迅速,本文章可能在发布后一段时间后不再可用。

需要

在下面的教程中,我们需要:

  • 一台手机(Android系统)
  • 一台笔记本电脑(MacOS系统或者其他)
  • 50元人民币(银行卡,不是现金)
  • 不限制流量的流量卡(日租也可以,土豪无视)
  • 合理的梯子(由于相关法律法规,部分asdfasdfasdfadsfsafads)
  • 以及一个愿意折腾的心(其实不是特别麻烦啦)

配置网络

打开你的手机,设置你的手机上网卡为直播用的流量卡。

打开你的手机热点,设置连接密码,并且取消对流量的限制,以及没有连接一段时间后自动关闭的功能,保证你的直播网络稳定性。

配置自动待机

打开你的手机、电脑,找到自动待机的设置,全部取消,保证直播稳定性

安装 CamStream

CamStream 是本篇文章的主角,其开发商同时也开发了另外一个广受好评的应用 Screen Stream Mirroring 推荐有需要的朋友们可以去play上搜索购买。

过梯子,访问 https://play.google.com/store/apps/details?id=com.mobzapp.camstream ,下载,安装。

配置 CamStream

CamStream的功能非常丰富,建议各位有时间可以去看看配置选项,自己调整成为自己最喜欢的选项

点击左上角菜单,点击购买专业版,去除广告以及最长直播时间限制(间隔一段时间自动停止直播),等待应用重启。

点击左上角菜单,选择串流到VLC播放器/OBS

横过来屏幕(别忘了解除屏幕锁定),记住串流地址。

安装 OBS

建议用梯子,访问 https://obsproject.com/ ,下载,安装。如果很早之前已经安装过OBS,这里仍然推荐安装一下新版。

配置 OBS

OBS也有非常丰富的功能,也欢迎各位自行发掘。

首次打开后,同意一下GPL协议。

跳过首次配置向导。

找到场景的位置,点击左下角或者右键空白,添加场景。

点击你所需要的场景,点击左下角或者右键空白,添加来源

找到媒体源,点击。

起个好听的名字。

取消选择本地文件,然后在输入那里填入之前所找到的串流地址,输入格式填入HLC。

后面,如果需要修改该来源的属性,点击相应来源后点击下方齿轮即可修改。

前往设置,找到配置串流的地方,把在直播平台上看到的串流地址以及串流参数复制到相应位置。

返回主界面,点击开始推流。

如果想同时录制直播,可以点击开始录制,文件会保存到设置里所填写的位置,一般为“家”目录下的影片(影视)目录。

如果想要录制原始素材,可以使用VLC直接录制信号,不过这里又是坑(比如录制完没有声音啦,视频格式有问题啥的),故不再多述。

对于音频的混音方式,OBS的行为会比较怪异,另外还有码率的高低以及分辨率会导致效果变化很大,建议各位用另外一台手机或者电脑实时监控直播网站上的直播画面。

另外,OBS的坑很大,所以建议各位在正式直播前先预先直播一下。

如果发现了文章错误或者有些地方文章介绍不够完整,欢迎各位在下方评论区跟我留言互动。欢迎关注我的b站直播间:https://live.bilibili.com/71261,我的新浪微博:https://weibo.com/lookas2001,另外,都翻墙了,关注下Twitter以及Facebook也不是难事嘛:https://twitter.com/lookas20011 https://www.facebook.com/lookas2001

本文章由lookas2001创作,保留所有版权权利,如需转载,请在评论区中说明。

南开体创热传递——我的第一个基于Vue.js的公开作品

废话不多说,先上项目页面:http://d.nktry.com

(如果这个域名被停止解析了,可以试试备用域名:http://diffusion.nktc.ninld.com

之前总是说了,五的网要上线了,要上线了,要上线了,可惜每次都没有真正上线过,这次先做了一个小的活动页面试试手。

感谢尤大提供的如此好用的开发框架,感谢 JetBrain 提供的如此好用的编辑器(Vue Webstrom大法好~)

代码在 Github 上开源:https://github.com/lookas2001/nktc-diffusion

有兴趣的小伙伴可以来提issue或者发pull request。

对了,本项目是基于AGPL-3.0授权的哟,所以,要注意版权哦!

~(≧▽≦)/~啦啦啦

录制自己喜欢的up主的直播,VLC!

提醒:本文章有搭配视频,在文章最下方,建议配合视频一起食用。

错过直播,好伤心,不想让其他小伙伴们再次错过直播了咋办,用vlc啊!

VLC是一个功能强大的,开放源代码的,媒体处理软件,能下厨房还能上厅堂(此处划掉),录屏,转码,播放样样精通。

本文章采用b站直播作为例子,其他直播网站大同小异。

本文章经测试适用于Desktop Windows10,由于技术更新非常迅速,请注意本文章发表时间。

本文章不支持手机平台,手机浏览器不支持“找到串流地址”步骤中的开发者控制台。

下载安装Chrome(可选)

其实其他的类chrome浏览器都是可以的,但是下方例子使用的是chrome,所以建议花些时间安装一下chrome。

官网在这里 https://www.google.com/chrome ,鉴于国情,该网站在中国无法访问。

中国地区下载推荐使用下方链接,下载后运行会立刻执行安装。
https://dl.google.com/tag/s/appguid%3D%7B8A69D345-D564-463C-AFF1-A69D9E530F96%7D%26iid%3D%7B86F44AD8-1DD3-7CAD-EE93-F76347E2AB44%7D%26lang%3Dzh-CN%26browser%3D4%26usagestats%3D1%26appname%3DGoogle%2520Chrome%26needsadmin%3Dprefers%26ap%3Dx64-stable-statsdef_1%26installdataindex%3Ddefaultbrowser/chrome/install/ChromeStandaloneSetup64.exe

如果链接失效等情况无法下载,那就可以在第三方应用商店下载,但是一定要注意捆绑安装。

下载安装VLC

官网在这里 http://www.videolan.org/

中国地区下载推荐使用下方链接
https://mirrors.tuna.tsinghua.edu.cn/videolan-ftp/vlc/2.2.6/win32/vlc-2.2.6-win32.exe
(PS:感谢清华大学tuna团队提供的镜像~)

如果链接失效等情况无法下载,请访问官网下载最新版。

安装时根据自己的需要选择合适的组件

调整vlc

让vlc更加易用,点击视图,然后点击高级控制,使其在一个选中的状态。

找到串流地址

打开浏览器

打开bilibili直播

找到任意一个主播,复制下来直播地址

打开新的标签页

按F12或者在任意空白位置右键,点击检查,转到network标签页

把复制下来的直播地址粘贴在地址栏访问,在network标签页中找到最长的那个线,复制它的地址

录制

打开vlc

点击媒体,点击转换/保存,转到网络选项卡,点击转换/保存。

选择参数,比如如果想监控现在的保存进度,可以点击显示输出,选择目标文件

点击开始

等到不想再录制的时候,可以点击下方的方块进行停止

结语

一般在录制up的视频的时候,如果自行观看,倒是无所谓,如果需要转发到其他平台,最好获取一下原up的同意,在这个例子里,因为截取的是官方的视频也就无所谓咯~

感觉vlc软件不错的小伙伴们可以去官网给个捐赠。

感觉视频不错的小伙伴们点个赞;如果有什么问题,欢迎在评论内提出建议。

视频

哔哩哔哩:https://www.bilibili.com/video/av24017610

Youtube:https://youtu.be/gvpwrpXlz7w