0%

新年快乐。


最近介入了身边的一些纠纷,也面临自己工作上的一些麻烦。于是不禁开始思考这些棘手的问题。

年初有一段时间里,和一些朋友一度不合,大多数涉及到了工作上的冲突。但是冷静下来之后,很快就会找到原因:从自己身上,从对方身上。渐渐就明白了,其实一场冲突从来不是一个人的事情,而是双方的错误共同导致的。

所谓朋友,并不只是聊天吃饭发自拍而已。朋友意味着能在需要时帮助对方,对对方缺点的包容,以及能在对方损害自己时表示让步。工作上的冲突追究原因的话,和双方的性格缺陷往往脱不了干系。为了同一个目的导致双方分歧可双方都彼此没有恶意,那么坚持己见并不算好的选择。坚持己见不能达到自己的所有目的,但是适当的让步可以。

那么这就可以化简为简单的选择题:自己目前所承受的损失和双方之间的关系以及其未来可能的好处,哪个更重要些?

双方关系重要于一定量的损失,这个答案就是朋友二字所代表的含义了。

那么,新的一年里希望有人愿意原谅我的错误,希望自己能够愿意原谅其他人。


说到朋友和工作的话,那也说说社团吧

我原先以为志趣相投的人聚在一起就算得上社团了。可实际上确实是这样的吗。所谓的“少数派”就是这样的一个团体。但是和社团比起来,它似乎少了些什么。

社团是一个有独立主格的实体。这意味着它并不基于某些人际关系网。因此对社团的感情和对某些人的感情是独立的两样事物。

对社团的感情,这是一样玄妙的东西。可能是一种类宗教性质的情感,包括信仰与热爱两部分。对它不知名的着迷,深陷其中的信仰,以及为之工作的热情。这就是比简单的人际小群体多出来的东西。

而自从换届之后,突然间就意识到了一点:和普通社员比起来,社干多承担了一份责任。高一时的萌新只要玩的开心就行了,天大的事情有学长学姐顶着。突然间自己就变成了这个角色。为了社团和小高一的,自己不得不担起这份责任:而这份责任要求自己牺牲很多。担起责任的动力,就是上述的情感。

那么,新的一年,希望微笙有一天能成为有台有面的大社团,希望漫研重新振作起来。


再谈谈学习。

要说过去一年里的学习的话,不得不说是一塌糊涂。

上半年里想着要好好学习文化课,先把竞赛放一放。当时为了期中考甚至放弃了去济南公费旅游。这一放就是一整个学期过去了。结果是文化课和竞赛双爆炸。

接着从期末考后开始,就重新地投入了竞赛课程。我想我大概是热爱算法的。渐渐地产生了大的野心,希望能成为厉害的选手,希望能和名校的选手同台竞技。

但是NOIp2018成为了一场可怕的灾难。我完全没有预料到会产生这样的局面。11月11日,耻辱退役。

我不知道这次失败会困扰我多久。或许再过一两个月就会忘记吧,又或许会长久地记住它。

但是更多的后悔实在无法改变什么。那么,此后的每一天,我都需要告诫自己,我已经是个文化课选手了。

另一方面,我也已经做好了最坏的心理准备。很有可能我需要裸高考了。

希望自己能找到面对文化课的热情。希望能像dalao一样积极面对文化课。


人实在是健忘的生物。

过去一年的事情,再早一些的事情,有些已经记不起来了,有些渐渐在记忆里模糊了,有些或许是自己不愿意记住。

有时候会感到很悲哀,明明是那么重要的人那么重要的事情,为什么会忘记呢怎么可以忘记呢。

不过所幸,连同这份悲哀也很容易被忘记,这倒好。


那么,新的一年,希望成为被人需要的人,成为更优秀的人。

我们设第 i 位大臣左手上的正整数为 ai,右手上的正整数为 bi,则第 i 位大臣获得的奖金数目为 ci可以表达为:

吝啬的皇后并不希望太多的奖金被发给大臣,所以她想请你来重新安排一下队伍的顺序,使得获得奖金最多的大臣,所获奖金数目尽可能的少。

注意:重新安排队伍并不意味着一定要打乱顺序,我们允许不改变任何一位大臣的位置。

悠娴之邀写的一篇题解

显然我们发现,数列$c$是一个递增数列,”获得奖金最多的大臣”实际上就是最后一位大臣.

设$a_0=b_0=0$,则第$i(i\geq 1)$位大臣获得奖金$f_1$
$$
=max(c_{i-1},\sum_{j=1}^i a_j)+b_i
$$

$$
=max(max(c_{i-2},\sum_{j=1}^{i-1}a_j)+b_{i-1},\sum_{j=1}^{i}a_j)+b_i
$$

$\sum_{i=m}^{n}a_i$意为数列$a$中从第$m$项到第$n$项的累和

若我们交换第$i$和$i-1$两位大臣的位置,则当前后面这位大臣(即原先第$i-1$位)所获奖金$f_2$
$$
=max(max(c_{i-2},\sum_{j=1}^{i-2}a_j+a_i)+b_i,\sum_{j=1}^i a_j)+b_{i-1}
$$
假定交换两人之前的排列方式是更优的,也就是说
$$
f_1<f_2
$$
展开得
$$
max(max(c_{i-2},\sum_{j=1}^{i-1}a_j)+b_{i-1},\sum_{j=1}^{i}a_j)+b_i<max(max(c_{i-2},\sum_{j=1}^{i-2}a_j+a_i)+b_i,\sum_{j=1}^i a_j)+b_{i-1}
$$
再展开得
$$
max(c_{i-2}+b_{i-1}+b_{i},\sum_{j=1}^{i-1}a_j+b_{i-1}+b_i,\sum_{j=1}^ia_j+b_i)<max(c_{i-2}+b_i+b_{i-1},\sum_{j=1}^{i-2}a_j+a_i+b_i+b_{i-1},\sum_{j=1}^{i}a_j+b_{i-1})
$$

容易证明,$max(a,b)<max(a,c)$等价于$b<c$

原不等式两边同时消去$c_{i-2}+b_{i-1}+b_{i}$
$$
max(\sum_{j=1}^{i-1}a_j+b_{i-1}+b_i,\sum_{j=1}^ia_j+b_i)<max(\sum_{j=1}^{i-2}a_j+a_i+b_i+b_{i-1},\sum_{j=1}^{i}a_j+b_{i-1})
$$
两边同时减去$\sum_{j=1}^ia_j$
$$
max(-a_i+b_{i-1}+b_i,b_i)<max(-a_{i-1}+b_i+b_{i-1},b_{i-1})
$$
两边同时减去$(b_i+b_{i-1})$
$$
max(-a_i,-b_{i-1})<max(-a_{i-1},-b_i)
$$
去负号
$$
min(a_i,b_{i-1})>min(a_{i-1},b_i)
$$
至此,我们得到了一个形式较为简单的,只与相邻两项有关的不等式.根据这个不等式进行排序即可.

完整代码如下:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#define LL long long
using namespace std;
LL n;
struct pwp{
        LL a,b;
        bool operator < (const pwp &qwq)const{
                return min(qwq.a,b) > min(a,qwq.b);
        }
}arr[40000];
//Both overloading operator function and defining a compare function are correct
bool cmp(const pwp &al,const pwp &be){
    //"al" is short for "alpha","be" is short for "beta"
    return min(be.a,al.b) > min(al.a,be.b);
}
int main (){
        LL T;
        cin >> T;
        arr[0] = (pwp){0,0};
        while(T --){
                LL ans = 0,sum_ = 0;
                cin >> n;
                for (LL i = 1;i <= n;++ i)
                        scanf("%lld%lld",&arr[i].a,&arr[i].b);
                sort(arr + 1,arr + 1 + n);
                for (LL i = 1;i <= n;++ i){
                        sum_ += arr[i].a;
                        ans = max(ans,sum_) + arr[i].b; 
                }
                printf("%lld\n",ans);
        }
        return 0;
}

考虑另一点:原式为什么不是$f_1\leq f_2$?

  1. 比较函数cmp<定义的是严格小于,不能用小于等于去定义它们
  2. $max(a,b)\leq max(a,c)$不等价于$b\leq c$

求解这类”求某方案,使某值最大/小”的贪心问题可以考虑假定一个最佳方案,然后对该方案进行略微改动,列不等式,观察不等式得到贪心策略.

这种方法称为”微调法”(似乎?),在很多贪心问题上都很实用.

文结.

暖黄色的的夕阳斜射在苍白的石砖上。堆砌成的高耸教堂式建筑被披上了一层血一样红色的薄纱。镶嵌在精致雕花石柱中间的是硕大的刻着罗马数字的轮盘,事实上是巨型的石英钟,正指向六点稍晚一些。夕阳平等地挥洒在建筑物脚下的街道上,和众神的父亲一样平等地为世间带来光明。

街道看起来并不干净。破损的报纸,各式的小物件,以及随风飘落的叶子,散乱地堆积在路边,看起来很久没有扫过了。方向各异的车辙交错,路上的人行色匆匆,都是些穿着黑衣和低檐帽的男性,却不见一个妇人或者小孩。战争时期的城市就是这样,尤其是靠近交火前线的地方。不过,细看的话,确实有一个女性的身影,罩在一袭黑袍下,跟着同样装束的男人身后。

“危险的任务,”两人转身进了教堂式建筑对面一间不起眼的小房子,男人随手取下黑袍,挂在一条破旧的木椅上。“只是你一个人的话,未免危险”。

“请交给我,少校。”女人一动不动地伫立在男人身后。准确来说该是女孩。宝蓝色的瞳孔十分清澈,类比的话像是富人家里的人工湖泊里的水,清浅而无垢。金黄色泽的短发凌乱且沾着灰尘。

“我会完成任务的”少女这样说。男人打开随身带着的手提箱,取出黑色的机械零件,熟练地组装起来。

“我会在这里为你提供保护。进入目标建筑后首先破坏所有窗户。战斗过程不准离开窗户。”男人没有停下手上的动作。

少女稍稍转头,看向了对面建筑物上五彩的窗玻璃,“是。”

男人完成了手上的动作,很显然是一把狙击枪。“尽快结束战斗,可以使用巫术战斧。”


夜幕终于逐渐拉上,太阳最后的光明也逐渐被漆黑所吞噬。没有人注意到的时候,一个身影悄悄进入了那座教堂式建筑。

“砰!”清脆的声音响起,色彩斑斓的玻璃应声碎裂,从窗台上坠落。少女手持短枪,向赶来的两个男人毫不犹豫地扣动了扳机。和刚才不一样的两声闷响,两人胸口被血染红,倒在了血泊中间。

“有刺客!”另一个身着华丽装束的大腹便便的男人惊恐地喊道。“砰!”旋即又是一声枪响,少女手中的短枪冒着青烟。

建筑里开始彻底混乱起来。

古希腊的诗人们喜欢用神明的身姿比喻英雄。少女的衣摆随着她频急的步伐晃动着,看似宽松的黑袍却并没有脱落。人群间的尖叫声,慌忙不迭的脚步声,以及凶狠的裹携着风和死亡的子弹从四面八方向少女袭来,可惜却只能惹起那身黑袍飘摇。起跳,转身,扣动扳机。少女每一步都踩在花和血上边,破损的黑袍如花神的镂花裙摆一样。

对了,花之女神。想必那个男人也是这么觉得吧。

枪托狠狠地砸在近些的敌人身上。少女又取出一抹锋芒,回身斩断了背后悄悄缠上的毒蛇。锈蚀的铁链钻进了稀疏的敌人中间,试图偷袭的家伙已然发不出惨叫。铁链回到少女的身边,雕刻着荆棘和玫瑰缠绕的精致长柄正被少女紧握手中,沾着猩红色的干涸血液的刀刃意味着它并不是什么装饰品。站在倒地的敌人的尸体上。“任务已经完成了”,把握着长斧的少女居高临下,不住地大口喘气。

“果然还是比较像战争女神啊。”当时还没成为少校的男人看着手持战斧的少女身姿感叹道。出身陆军的贵族世家,那把战斧,WitchCraft,本来和战争女神的画像一起展示在家主的书房中。当被问起想要什么礼物的时候,少女毫不犹豫地回答了战斧,“一定很适合战斗。”

更像是死神吧,如果用的是镰刀的话。躲在伙伴的尸体中间,一个少年死死地盯着喘气着的少女,紧握手中的匕首。看着她跪倒在地上,看着她靠着战斧撑住身体,看着她持枪的手臂和肩膀无力地垂下。少年已经忘了战栗,爆发了全部的力气,连带着身体和匕首向少女刺去。

宝蓝色的瞳孔骤然紧缩。

来不及慌张。但也来不及举起枪了。

“抱歉,少校。任务失败了。”

时间此刻凝滞了。

“砰”地一声巨响,连同少年的身体和时间一同凝滞。不甘,绝望,以及其它的感情尽数凝滞,在少年胸口的血洞里。

窗口对着窗口,街道那边的小屋里黝黑的枪管似乎还冒着青烟。


冠以花神名称的战争少女,无知而强大的杀戮人偶,薇尔莉特。

NOIp2018的游记

day0

早上本来还有课的,不过翘掉了去机房.

本来还天真的以为早上大家都会乖乖去上课这样机房就安静些.然而没想到全世界都翘课了.包括步冀和严林.

开了一套模拟题做,然而难度略简单了些.一个半小时写完之后就开始颓废了.大概划水了一早上.

将近12点的时候回家取了一下行李.接着就去蟹堡王子吃了午餐还聊了些反云力的话题hhh.1点乘大巴出发去福州.收行李的时候忘了带入耳式耳机,于是从机房取了头戴式就走.

中午在大巴上看见崩崩崩开了扩充就抽了六发.出了原猎和丽塔.快落.

iODzqg.jpg

iODvM8.jpg

然而更想打一顿出了火姬的林龙河.

到了住处的时候简直震惊.房间里连天花板灯都没有.昏暗,地处公交站旁边.幸好带了头戴式耳机和眼罩.

接着去农林大试机.本来和步冀安排在第一考场,结果被告知只有第六考场才有Linux环境.于是又赶到第六考场去.机子的显示屏居然是4:5的,比想象中的还要小太多了.

出考场之后跟着步冀的导航去了食堂吃了饭,吃完了得知其他人跟着严林走错了路并没有吃上晚饭hhh.

看见qduoj的开发群里居然也有FJ的OI选手吐槽旗山招待所的住宿环境,才知道原来是省里统一安排的.加了个好友,得知一个和我同龄一个才只是普及组选手(才初中就开始搞oj了?!

晚上肝了会儿崩崩崩,完了看了看b站,大约十一点半睡下了.

day1

早上六点起床,洗漱之后去大堂吃早餐.意外地还不错(wyx:说明你真的饿了)

去农林大的路上喝了一瓶咖啡.有点撑.

进考场前十分钟.紧张的心理开始发酵.脑中开始循环神明project的几首歌.在考场外的阳台上趴了一会儿,又去上了个厕所,然而心态依然没能放下来.就这样进了考场.

因为紧张的缘故,并没有意识道原来解压密码是飞雪连天.然后开始读题.

T1:卧槽这tm不是当年noip原题吗??咋又考了??首尾相连是成环的意思吗??嗯好像不是.上次我组织的那场校内模拟赛出过这题来着,我还怒斥晨辉考原题来着.妈耶可是我身为组织者没认真看过这题的解法.嗯不过好像也不难.总之轻松地写完了

T2:这啥玩意啊大凯的疑惑吗?好像判断一下有几个数能被其它数线性组合得到就行了.感觉像是筛法搞一搞?算了先打个暴力吧.结果暴力调了近一个小时.妈耶先骗点T3的分

T3:诶部分分这么多的吗?菊花图二叉树和链分类讨论一下.诶等等菊花图和二叉树的做法合起来好像就是正解了?一看时间还有一个半小时多,先上个厕所.然而惨剧发生了:我终于没调完T3,连样例都没过.凉凉.

出考场的时候心情悲凉,难过.一听T2正解就是跟完全背包类似的筛法,更难受了.开手机要看怒斥CCF.结果Claris一眼指出T2T3都是POI原题.NOIp==POI*N

总之看着全世界都拿了255就很难受.

iODxsS.png

后来反思了一下,知道是太紧张了的缘故.然而还是难受.

中午回招待所先肝了会儿崩崩崩然后睡了个午觉.

下午玩了一下午Donut County,接着去吃了个晚饭,回来到晨辉房间联机打vertix.十点左右回去把Donut County打通了.约十二点半睡下了.

day2

早上在大厅稍微吃了点早餐,又和几个可爱的小学妹去麦当劳补了点食物.点了个薯饼和一杯咖啡,打算在路上吃.然后就进考场了.

T1:这什么傻逼题面.完全没会清题意.一开始写了个魔改dijkstra,一跑连样例2都过不了.于是又写了个裸的dfs,果然还是不行.又认认真真读了五六遍题面才意识到原来只能走一次回头路(原来这样才只有一个环的吗?!

T2:一开始以为不难,dp搞一搞就可以了.没想到完全做不动!这恶心人的题目连手动模拟都做不了啊!于是写了个大暴力,先枚举所有棋盘状态再枚举路径.中途去上了个厕所,回来发现步骥也一直在怼这题.最后打了个表交了上去.

T3:不可做题.十分钟写了A类的暴力结果还错了

day2的难度完全不可做啊.day1之后觉得是太紧张了于是day2的心态好了不少.结果这一堆不可做题根本不给机会.

出考场之后心情简单,很清楚自己是凉了.

中午临行前弄了个草莓圣代吃.在颠簸的大巴上睡了一觉就到家了.

晚上买了点小零食准备去机房颓.结果校徽不知道弄哪了.回家没找到后还是借着竞赛的请假条进了校门hhh

到机房之后把暑假期间搭的mc服务器重新拿出来玩(拖着lyx.总之累到完全失去思考能力

day -1

早上上课的时候完全没精神.找前桌借了本杂志爱格(捂脸).看了一早上

下午也是大概这样过了,晚上去机房继续颓.

清醒一点之后难受的心理彻底爆炸.完全没想过NOIp居然会挂成这样.


总之NOIp2018就这样过去了.

由于本文成文的时间跨度极大,所以大概有些前言不搭后语了.

文结.

2018-11-6 NOIp2018倒计时3天.

这两天听了一些考场技巧,自己做了一些模拟赛,顺便查缺补漏一下.大概总结一下考场注意事项.


考场注意事项

考前

  1. 记得带笔,纸,身份证,准考证
  2. 早点睡
  3. 熟悉一下考场的NOI Linux环境,了解一下frc的配置和非还原分区

考场上

比赛开始前

  1. 写好.vimrc
  2. 配置好frc,比赛开始15min后frc配置将不能更改
  3. 注意建选手文件夹和子文件夹
  4. 写好头文件和两行freopen
  5. 随便敲点东西(快读啥的)找找手感?

比赛过程

  1. 写好文件名和文件读写
  2. 注意在非还原分区做好备份
  3. 使用tab补全时千万不要写出g++ a.cpp -o a.cpp
  4. 先读完所有题面
  5. 先打暴力,反正对拍还用得上,也顺便找找状态
  6. 每道题思考不超过20分钟,即使自己看起来有思路.拿分要紧
  7. 写完了记得拍一下.
  8. 即使T1写不出来心态也不能崩,参照NOIp2017 T1.T1挂了也很有机会拿200+的分
  9. 切勿进入起火的状态.也就是不能大脑发热.不能长时间处于思考调试的状态.必要时申请上厕所.
  10. 该放则放,千万不能觉得”这题挂了就要凉了”这样的思路.拿分要紧
  11. 对于有子任务的题尽量打数据分治.当然能写出正解就不用了.
  12. 想到再补

比赛临近结束时

  1. 个人对”比赛临近结束”的定义是结束前10min,也就是说结束前30min要是还有暴力分/部分分没拿到就赶紧写暴力/部分解法.
  2. 检查个人文件夹,子文件夹,准考证号,题目标题.
  3. 检查文件读写,记得自建.in文件测试一下.(我校某场场比赛挂文件的同学已经让我懒得吐槽了.
  4. 检查字符串常量输出.由于有过学长在考场上把yes写成yse,自己也在模拟赛中犯过这个问题,实在心有余悸.
  5. 检查mod数.这玩意出错连对拍都拍不出来.
  6. 想到再补

个人.vimrc配置

set nu
set cindent
set tabstop=4
set shiftwidth=4
syntax on