[差分][前缀和][细节] codeforces 1452E Two Editorials

codeforces 1452E Two Editorials

题目链接:https://codeforces.com/problemset/problem/1452/E

题意:一次比赛中 2 个dalao来讲题,总共有 $m$ 个选手来听讲,题目总数为 $n$ ,编号从 $1$ 开始到 $n$ 。每个dalao都只会选择连续的 $k$ 个题目进行讲解,两个人可以交叉。而每一个听讲的人都只会选择听一个dalao的讲题,这是由哪个dalao讲的题目中覆盖的他感兴趣的题目数量较多决定的,第 $i$ 个人想听的题目范围是 $[l_i,r_i]$ . 问两个大佬怎么选可以使得两个人所获得的得分加一块最多,其中得分是他们讲的每个题目收听的人数。

数据范围:$1 \leq n, m \leq 2000,1 \leq k \leq n$, $1 \leq l_{i} \leq r_{i} \leq n$

输出:两个人采取某种讲题方案后加一块能获得的最大分数

题解:

把每个听讲的人看成一条线段,问题可以抽象成在数轴上找到两个长度为k的区间使得上述分数最大。从数据范围来看,可以 $O(n^2)$ 枚举两个人讲题的起点,之后如果能使用滑动窗口动态维护, $O(1)$ 更新答案这题就做完了。那么自然可以想到枚举第一个人讲题的范围之后,第二个人的范围在遍历的过程中动态维护。如果我们使用前缀和来做的话,是可以 O1 得到两个人各自的和的,但是题目要求两个人之间如果有均覆盖到的听讲者,那么只有覆盖的较多的讲题人才有得分。这是一个对每个听众来说取max的操作,但是我们要在数轴的维度来说要做到 O1 动态维护就是比较难的。我们假设第一个人对于自己内部的的得分和为sum1.第二个人的得分为sum2.先不考虑取max的情况,此时sum1和sum2都可以通过简单的积分前缀和得到。我们考虑把这个max操作转化成几个不同数组的差分和求和操作。简单的画一下第二个样例,就可以意识到当枚举到第一个人的讲课区间 [i,iend] 的时候,听众对应的线段可以分为三类:(1)在iend之前结束的;(2)在iend之后开始的;(3)在iend之前开始,在iend之后结束的。
继续阅读“[差分][前缀和][细节] codeforces 1452E Two Editorials”

[娱乐][代理][CF] 使用cloudflare worker反向代理codeforces,支持登录和提交代码评测

作为一个退役的ACM选 (蒟)手(蒻),偶尔也会回codeforces上做做题娱乐娱乐。。

但是codeforces作为一个外国网站,在国内访问的话速度十分感人,你懂的。

虽然绝大多数 业内人士 都有不可描述的方法让自己访问到国外的网站,但是还是有一些刚接触比赛的同学需要一个比较快的访问途径。当然国内之前也有一些dalao自制的codeforces镜像,例如 https://codeforc.es/ 等。

我这里提供一种免费自行搭建codeforces反向代理的方法,借用了cloudflare免费提供的serveless服务:workers。关于workers的简单介绍可以参见官方的blog:

Cloudflare Workers的名称来自Web Workers,更具体地说是Service Workers,一个用于在web浏览器后台运行并拦截HTTP请求的脚本的W3C标准API。Cloudflare Workers是针对相同的标准API编写的,但是是在Cloudflare的服务器上运行,而不是在浏览器中运行。
以下是您可以使用的工具:
– 使用最新的标准语言功能执行任意JavaScript代码。
– 拦截和修改HTTP请求和响应URL,状态,标头和正文内容。
– 直接从您的Worker响应请求,或将其转发到其他地方。
– 将HTTP请求发送到第三方服务器。
– 以串行或并行方式发送多个请求,并使用响应组成对原始请求的最终响应。
– 在响应已经返回到客户端之后发送异步请求(例如,用于记录或分析)。
– 控制其他Cloudflare功能,例如缓存行为。
– 显然我们要达到反向代理的目的只需要处理两件事:
– 处理客户端的请求,修改参数之后发送给真正的服务端(codeforces.com)
– 处理codeforces.com返回的响应,修改参数后发给客户端
继续阅读“[娱乐][代理][CF] 使用cloudflare worker反向代理codeforces,支持登录和提交代码评测”

[数论][图论][思维] codeforces 1325 E Ehab’s REAL Number Theory Problem

codeforces 1325 E

题意:给定一个长度1e5的数组$a$, $1 \le a_i \le 10^6$ ,满足 $a_i$的因子数量不超过7. 求 $a$ 的最短的满足所有元素相乘结果为完全平方数的子序列的长度。

这个题目做的时候。。一直在想怎么dp。。。完全没往图的方向想。太久没做题了就是这样,丢掉了很多东西,sigh
继续阅读“[数论][图论][思维] codeforces 1325 E Ehab’s REAL Number Theory Problem”

MIT 6.858: Computer Systems Security 计算机系统安全 #Lab1

MIT 6.858: Computer Systems Security 计算机系统安全 #Lab1

本文同步发布于本人知乎文章https://zhuanlan.zhihu.com/p/258405554

1. Introduction

MIT 6.858 是麻省理工学院一门著名的计算机安全系列课程。跟其相类似的其他名校的安全类课程还有Standford CS155OSU 系统安全与软件安全等。虽然是比较硬核的大学课程,其实验环境对于现实生活中的安全攻防来说也还是相对较为理想的。不过对于想尽快地熟悉基础的系统安全攻防知识的新手来说,这些实验的容量已经足够了。整个课程有4次实验和一个最终的Final Project,其中所有的实验都围绕一个由课程教师构建的一个名为zoobar的web application来展开。四次实验的主要内容是:

  • Lab 1: you will explore the zoobar web application, and use buffer overflow attacks to break its security properties.
  • Lab 2: you will improve the zoobar web application by using privilege separation, so that if one component is compromised, the adversary doesn’t get control over the whole web application.
  • Lab 3: you will build a program analysis tool based on symbolic execution to find bugs in Python code such as the zoobar web application.
  • Lab 4: you will improve the zoobar application against browser attacks.

即分别围绕缓存区溢出攻击、权限分离、符号执行和浏览器攻击四个主题来展开。我将在blog里陆续更新之后的内容。这一次我们先来看第一次实验,Buffer Oveflows
继续阅读“MIT 6.858: Computer Systems Security 计算机系统安全 #Lab1”

麻省理工学院(MIT)研究生学习指导–怎样做研究生 [转载]

麻省理工学院(MIT)研究生学习指导
怎样做研究生
本文的主旨是解释如何做研究。我们提供的这些建议,对于研究本身(阅读、写作和程序设计)、理解研究过程以及开始研究(方法论、选题、选导师和情感因素),都是极具价值的。

  1. 简介

这是什么?
并没有什么神丹妙药可以保证在研究中取得成功,本文只是列举了一些可能会对研究有所帮助的非正式意见。

目标读者是谁?
本文主要是为新入学的研究生而写。

如何使用?
要精读完本文,太长了一些,最好是采用浏览的方式。很多人觉得下面的方法很有效:先快速通读一遍,然后选取其中与自己当前研究项目有关的部分仔细研究。
本文被粗略地分为两部分。第一部分涉及研究者所需具备的各种技能:如阅读,写作和程序设计等等。第二部分讨论研究过程本身:即研究究竟是怎么回事,如何做研究,如何选题和选导师,如何考虑研究中的情感因素。很多读者反映,从长远看,第二部分比第一部分更有价值,也更让人感兴趣。

本文的主要内容包括: 继续阅读“麻省理工学院(MIT)研究生学习指导–怎样做研究生 [转载]”

图片转latex/word代码在线工具,mathpix的在线替代,完全免费,避免重复劳动

使用示例

使用方法

用截图工具(QQ 微信等的截图或者Windows自带的截图)截图或将图片复制到剪切板后在本页面按Ctrl+V粘贴即可在文本框内获取latex代码。注意Word的代码复制出来之后再Word里粘贴要用 右键-> 粘贴 -> 仅粘贴文本 的方式

地址: https://mathcode.herokuapp.com/ 建议加入书签。由于是部署在heroku美国上(买不起服务器和域名)所以国内直连会比较卡。

新地址:https://mathf.itewqq.cn/ 建议加入书签。为了方便国内连接我迁移到了自己的国内学生机上。网页打开速度变快了,但是腾讯云的学生机总带宽只有1M所以人多的时候用可能还是会卡(贫穷.jpg)

继续阅读“图片转latex/word代码在线工具,mathpix的在线替代,完全免费,避免重复劳动”

BUUOJ Web #1 [HCTF 2018]WarmUp [强网杯 2019] 随便注 [SUCTF 2019]EasySQL [RoarCTF 2019]Easy Calc

0x01 [HCTF 2018] WarmUp [PHP][代码审计]

题目链接

简单题。打开网页后一张滑稽,按F12寻找信息,发现代码注释里有一行
“`“`,在url后加上/source.php刷线页面,得到一段PHP代码。

<?php
    highlight_file(__FILE__);
    class emmm
    {
        public static function checkFile(&$page)
        {
            $whitelist = ["source"=>"source.php","hint"=>"hint.php"];
            if (! isset($page) || !is_string($page)) {
                echo "you can't see it";
                return false;
            }

            if (in_array($page, $whitelist)) {
                return true;
            }

            $_page = mb_substr(
                $page,
                0,
                mb_strpos($page . '?', '?')
            );
            if (in_array($_page, $whitelist)) {
                return true;
            }

            $_page = urldecode($page);
            $_page = mb_substr(
                $_page,
                0,
                mb_strpos($_page . '?', '?')
            );
            if (in_array($_page, $whitelist)) {
                return true;
            }
            echo "you can't see it";
            return false;
        }
    }

    if (! empty($_REQUEST['file'])
        && is_string($_REQUEST['file'])
        && emmm::checkFile($_REQUEST['file'])
    ) {
        include $_REQUEST['file'];
        exit;
    } else {
        echo "<br><img src=\"https://i.loli.net/2018/11/01/5bdb0d93dc794.jpg\" />";
    }  
?>

看这个判断语句

if (! empty($_REQUEST['file'])
        && is_string($_REQUEST['file'])
        && emmm::checkFile($_REQUEST['file'])
    )

说明是在请求中包含有文件,以及文件是一个string,这两个都好说,看第三个是进入checkFile函数。

看代码逻辑的话,有三种情况会返回true
继续阅读“BUUOJ Web #1 [HCTF 2018]WarmUp [强网杯 2019] 随便注 [SUCTF 2019]EasySQL [RoarCTF 2019]Easy Calc”

关于近期遭受一些网络攻击的声明

最近吧,偶然看日志,发现很多莫名其妙的对我这破站的攻击。。。有暴力ssh密码的,爆破admin后台的,xdebug攻击面的,莫名其妙。这只是我的个人网站,90%的文章都是acm算法题的题解,想不明白有什么好玩的。

如果有一些文章侵害到了哪位的利益请直接联系我, kkutis1989@gmail.com ,有话好商量(我不是1989年生的这是个伪装名字不用试密码了

[DP][扫描线][思维] Codeforces 1313D Happy New Year

题目链接

题意:

有 $m$ 个小朋友,圣诞老人有 $N$ 个咒语,第 $i$ 个咒语施展出来的话,可以给 $[Li,Ri]$ 范围内的小朋友一块糖果,对每个小朋友来说,他得到的糖如果是奇数的话就会happy,否则就会不happy。

现在要求求出当圣诞老人采取某种最优的施展咒语的策略(一些用了一些没用,具体不需要求出来)的时候,最多有多少个小朋友可以happy?

题目保证,每个小朋友最多被 k 个咒语覆盖到。

数据范围: $m \le 10^9$, $N \le 10^5$, $1 \le k \le 8$, $1 \le Li \le Ri \le m$

题解:

(先吐槽下这题竟然2600分,这可是个div2D)

用扫描线的思想来做。

假设有一根竖直的扫描线在横轴上扫过去,那么他只会在每个 $[Li,Ri]$ 段的头尾两端发生状态变化,我们设置这些点为关键点,当我们采取某种特定的策略的时候,两个关键点之间的数据是不会发生变化的。

由于每个点最多被 $k$ 个线段覆盖,我们可以暴力的枚举出来当前扫描到的点的状态,即它被多少种线段覆盖到了,这个状态显然可以用二进制位来表示。由于我们是一个一个关键点找过去的,而两个关键点之间的数据状态仅由前一个点即可确定,所以我们的dp转移只需要考虑前一个点。

具体的转移:设 $dp[i][S]$ 为考虑到了第i个关键点(按从小到大的顺序),覆盖当前点的线段状态为 $S$ 的时候,最优解是多少。

  1. 当当前点为某线段的起点时,我们考虑每个 $S$ 中是否包含了第 $i$ 条线段,如果
    • 包含了,那么 $dp[i][S]=dp[i-1][S^(1<<p)]+(i到第i+1个关键点的距离)*(S中二进制位为1的奇偶性)$ ,因为我们相当于加上了新的一段;(其中p为当前线段所应在的二进制位,下同)
    • 没包含,那么$dp[i][S]=dp[i][S]$ $+(i到第i+1个关键点的距离)*(S中二进制位为1的奇偶性)$,等于说我们的扫描线在这一段仍然是按照之前的状态在扫描。
  2. 当当前点为某线段的终点时,我们仍然考虑每个 $S$ 中是否包含了第 $i$ 条线段,如果
    • 包含了,由于这条线段到此我们认为结束了,所以这种状态根本不合法,直接设置为$-INF$
    • 没包含,那么$dp[i][S]=max(dp[i-1][S],dp[i-1][S^(1<<p)])$ $+(i到第i+1个关键点的距离)*(S中二进制位为1的奇偶性)$,因为我们前面一段可能选了大,也可能不选更大,我们需要取个最优解。

然后我们可以发现两个转移都有方向性,我们可以用滚动数组忽略掉第一维,也就是说状态数组可以只开 $dp[1<<8]$ 即可。

继续阅读“[DP][扫描线][思维] Codeforces 1313D Happy New Year”

Docker搭建Nextcloud私有云++Aria2下载器

最近需要从国外某网站下载一个大的数据集,不知道为什么总是断流,而且不能续传,非常烦人。后来想了想,可以在国外的vps上搭一个私人云盘,然后先把数据下到vps上,再下到我的本机上,曲线救国。然后搜索了下发现Nextcloud+Aria2是比较好的一个选择,而且有docker,十分的方便,就简单部署了一下。

其中docker-compose.yml如下,其中的端口映射因为我这台vps上已经有了一个网站了,占用了80和443端口,所以修改了一下外部端口。

version: '3.5'

services:
  nextcloud:
    image: nextcloud:latest
    volumes:
      - ./data/nextcloud:/var/www/html:rw # moutn nextcloud files folder
      - ./data:/data:rw # mount your personal data folder
    restart: always
  aria2:
    image: wahyd4/aria2-ui:nextcloud
    ports:
      - "2480:80"
      - "2443:443"
    volumes:
      - ./data:/data # mount your personal data folder
    environment:
      - DOMAIN=:80
    links:
      - nextcloud:file-manager
    restart: always

写好之后我们直接docker-compose up -d启动,访问http://ip:2480即可登录nextcloud,http://ip:2480/ui/ 则是Aria2NG的管理页面。
继续阅读“Docker搭建Nextcloud私有云++Aria2下载器”