Luogu 1248 加工生产调度

题目

题目链接: https://www.luogu.org/problemnew/show/P1248

这道题目暴力显然不可取$ 1000!$ , DP 的状态不太容易定义,只能贪心大法

分析贪心

我们可以先假设只有两个物品$ A $ 和$ B $,则存在以下两种情况($ x $代表物品在 A 工厂加工所需时间,$ y $ 代表 B 工厂,以下同理)

  1. 先加工$ A $后加工$ B $,则时间为$ A.x + B.y + \max(A.y, B.x) $
  2. 先加工$ B $后加工$ A $,则时间为$ A.y + B.x + \max(A.x, B.y) $

则若先加工 A 比先加工 B 优,应满足
$$
A.x + B.y + \max(A.y, B.x) < A.y + B.x + \max(A.x, B.y) \\
\begin{align}
&= \max(A.y, B.x) – A.y – B.x < \max(A.x, B.y) – A.y – B.x \\
&= -\min(A.y, B.x) < -\min(A.x, B.y) \\
&= \min(A.x, B.y) < \min(A.y, B.x)
\end{align}
$$
然后放到cmp里,A 了?

等一下,这个方法……是错误的

继续阅读“Luogu 1248 加工生产调度”

BUPT 网安杯 游记

Day 0

早上迷迷糊糊的醒来,然后收拾东西一出门…

看不见任何东西,起大雾了

然后迟到了五分钟,虽然大家都迟到了

本来以为航班会延误的…然后它平安无事

通过交易和 StudyingFather 大爷坐在一起,因为各种东西心情复杂,进入睡眠状态

下飞机后坐机场大巴……老师成功的把站名读错了

到达后,服务人员告诉我们可以住两天,但是原来一人一间得变成两人一间,这当然是滋瓷的啦

老师通知完注意事项后,我和 StudyingFather 大爷讨论起午饭的问题,最终决定吃点带北京味道的东西,于是吃了饼子卷菜…

北京消费水平好高啊qwq

吃完饭后依旧心情复杂,继续睡觉=_=

继续阅读“BUPT 网安杯 游记”

随笔 && 公告

因为各种各样的原因,服务器被重做

或许有意或许无意,没有备份主题,而所有友情链接都是存于主题之中的

就这样凭空消失了许多友情链接,我凭借这自己几乎无用的记忆,挽救回了一些友接,其他的就随缘吧

主题终究也是丢了,多多少少算是记录了自己了成长历程的一份代码,说可惜也挺可惜的,但是不抛弃过往终究没有未来

既然博客里有回忆OI路程的,这次,也就回忆一下自己在前端方面的脚印吧

本博客于 2017.01 开始在网上有了自己的身影,随着网站稳定性的不断提高,我开始尝试不断去做一些前端的小东西

最开始写的必应壁纸,当时还打扰了一些比较厉害的人,中间还偷过别人的东西,被别人发现,给自己上了版权这一课

后面逐渐又认识了一些比我年龄稍大的人,自己有了一些越发大胆的想法,写出一个WordPress 主题

再那之后,我总喜欢将自己的闲暇时间用于研究别人的代码,那阵时间是我代码风格最多变的时候,当然,程序里也有不少从他人那里「借鉴」过来的东西,在那之后,我去学习了信息学竞赛,在学习信息学竞赛的空闲时间,将主题的初版写了出来

在那之后,一旦有什么新鲜想法就往主题里面加,直到后来自己也不知道里面都有什么东西,终究不再做大改,转头信息学竞赛,在闲暇时间写一点小东西

到了去年,NOIP 前,完全将自己投入了信息学竞赛当中,利用自己曾经努力的结果,主题也成功被打造的非常适合OI

随着自己代码能力的不断增强,使自己开始能够理解在刚搭建博客时,在 WordPress 官网上所看到那句「代码如诗」的含义

但越是理解,越是不想去学习信息学竞赛中的模板

我不喜欢信息学竞赛中的数学题,因为通常这类题目只能用于解决一个问题–题目中所给予的式子,我们只能将其通过一个个定理化简,一个个到最后都给人一股与原题目无关的感觉

我喜欢像写后端,因为他们可以在现实中有对应,每一行代码从未多余,连起来如诗一般美好,你不知道你的代码会遇到什么,但是你知道你的程序在如何解决问题,你会让你的程序尽力面对所有可能

或许我写下这一段话会被许多Oi大佬们喷,什么我不懂得数学之美,万物基于数学,只是我不理解定理的美妙之处什么诸如此类的话语,我也知道,但这只是一个菜鸡的碎碎念而已

Oi 肯定是要学的,我也喜欢各式各样的算法,在经过一句句代码后,图上的风云变化,一句句代码后,变得有理可循的字符,但是我也真的累了,不想再去分析一句句代码背后的运行速度了

既然服务器坏了,一切重头开始,就让我稍微,回到梦最开始的地方,做一小会的梦吧

Educational Codeforces Round 60 (Rated for Div. 2) 解题报告

A. Best Subsegment

给定一串数列, 求区间最大平均值

显然,最大的区间平均值可以就是数列中最大的那个,然后基于最大的点想两边枚举区间长度

#include <cstdio>
#include <algorithm>
inline int Max(int a, int b){return a > b? a: b;}
const int N = 1e5 + 1e4;
int n, max, max_id, len, rig, max_len;
int a[N];
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        if(a[i] > max)
            max = a[i];
    }
    for(int i = 1; i <= n; i++){
        if(a[i] == max && ( a[i - 1] != max || i == 1 ) ){
            rig = i; len = 0;
            while( a[rig] == a[i] && rig <= n ){
                rig++; len++;
            }
            max_len = Max(len, max_len);
        }
    }
    printf("%d", max_len);
}
继续阅读“Educational Codeforces Round 60 (Rated for Div. 2) 解题报告”

Codeforces Round #538 (Div. 2) 解题报告

A Got Any Grapes?

顺序判断即

比赛的时候忘记写 else 既然 PP 了,然后就 FST

#include <cstdio>
int an,dm,mi;
int gr,pu,bl;
int main(){
    scanf("%d%d%d", &an, &dm, &mi);
    scanf("%d%d%d", &gr, &pu, &bl);
    if(an > gr) {
        printf("NO\n");
        return 0;
    }
    else gr -= an;
    if(pu + gr < dm){
        printf("NO\n");
        return 0;
    }
    else {
        if(pu <= dm) {dm -= pu; pu = 0;}
        else {pu -= dm; dm = 0;}
        if(gr < dm) {
            printf("NO\n");
            return 0;
        }
        else gr -= dm;
    }
    if(gr + pu + bl < mi) printf("NO\n");
    else printf("YES\n");
}
继续阅读“Codeforces Round #538 (Div. 2) 解题报告”

CCF WC 2019 游记

Day -1

上午起来收拾了一下就前往乌鲁木齐市机场了

在机场里面互相定位是一件困难的事情,我们最终通过奇迹淫巧和瞎挥手聚在了一起

然后是漫长的安检和候机….

在经历各种各样奇怪的娱乐过后,飞机终于落地

飞机上拍的云朵

下去坐地铁,站了一个多小时后有疯狂转圈终于吃上了人生中第一顿麦当劳并到达了宾馆

发现电视有 HDML 口,接之

一顿瞎嗨,用电视看了看鬼畜和老番

继续阅读“CCF WC 2019 游记”

DoH && EDNS 的配置

DoH

Dns over Https 一说 Dns over Http/2

虽然有一些差别,但本质上都是为了解决一个问题

使用 dnsforwarder 建立本地 DNS 服务器避免 DNS 问题 一文中,我们讲述了通过了tcp查询代替udp查询来提高污染的难度以避免污染

但是即便是tcp查询,依然使用明文,中间攻击会导致你可以想到的任何不好情况发生

而随着技术发展,https连接的延迟已经越来越低,已经在用户可以接受的范围内——70-600 ms,在http2的情况下,延迟甚至有可能比udp要低

在去年IETF与谷歌实验室分别发布了两套标准

继续阅读“DoH && EDNS 的配置”