我也来到 NOI 了,呢。

郑重声明

本博客内所有与 NOI2019(第 36 届全国青少年信息学奥林匹克竞赛)试题相关之内容,均在对应之机试与复评结束之后发布,详细发布时间与内容可以在 commits 中查看。

Day 499122177

广二宿舍还是没有网.

床边的插座不是一般人能插的..(Orz lbw 插上去了)然而因为有时候要去机房(其实基本上也就刚到那天晚上没事去了..),所以后来还是拔下来了。然后发现不带 220V 转 USB 母头的插头真是个错误的决定..虽然可以用笔记本充电,可如果在寝室门口充电就没法用电脑,所以没法一会儿充电脑用手机、一会儿充手机用电脑。

晚餐有点抽卡的感觉..看名字很难看出拿到手上的到底是什么东西(

吃完晚饭去自习室水了半小时群,然后打短裙 OJ。

切完前两题,好像 rk 5..

然后看 C,问满足一堆条件的个数..一眼容斥..然后真的写了 1h 的容斥 qaq

好不容易过拍了,提交,又 WA 了..

在群里一问,woc,p 不是排列…

5 min 后过了,愉快地垫底了..

过于自闭,看了眼 D,没秒掉,就懒得去想了。

赛后听说 C 可以状压,一想,真的可以状压…..学傻了.webp

Day 557219762

咕掉早饭把火车上剩的吃了。

(开幕式竟然没有 wh 讲话)

灯光打得好!覆盖方位广!给灯光师点个赞!

果然有公开处刑大头照展示,只不过速度比较快,问题不大。

感觉大家喊的口号都听不太清啊..

明 示 爆 零 :

zero0

zero1

dzd 的讲话中,有这么一段话:

无论何种情况,这个竞赛都会继续下去。因为这个竞赛是正当的,是正义的,合法的。

听到这段话,又想起 ひなた 在桥边含泪喊出的那段话了:

但是,我没有后悔,不能后悔,因为,我所做的事情一定没有错!

NOI 可能真的如 dzd 所说,带有一些“净化灵魂”的成分在吧。

最后鸽子蛋破不开,明示摆脱不了爆零的命运

(离场后目击 dzd 被采访)

中餐感觉海星..还是得看看别人买到的是什么再选。(千万不要用排除法来选

中午写了写博客,做了遍笔试,睡了会儿觉。

还是感觉好方..毕竟被鄙视用的错误选项从来没变过(

结果笔试挺水的..题目和题库里完全一样(没有之前在 vfk 博客里看见的“那道题不选 foobar.sh”之类的情况),很多题都不是四个选项而是更少,所以没有任何奇怪的错误选项..

Day 1

看到 T1 就很快想出了 70 分的拆点做法,写完之后几乎一遍过了大样例。

然后去把 T2 和 T3 的 20 + 28 写了,此时 $1.5h​$ 左右。

然后去写 T1 $A=0$ 的部分分,各种写挂写了接近 $2h$..

然后感觉 T2 还是没什么想法,T3 想了几个假贪心,又想了几个假网络流,最后还剩半小时的时候想到了一个考后才叉掉的 $n^3\log$ 的假贪心(讲题时发现稍微改动一下就是正确的 40 分做法..),幸好没写完,不然万一过了样例就 GG 了。

出来之后发现大家都 $148​$ 起步..T1 有正解的,但还有一堆利用数据范围改小的,以及一堆 $70​$ 分算错复杂度的。

T1 我写的数据分治是不可能 $85​$ 以上的,所以特别怕 $70​$ 分做法最后 $90​$ 或者 $95​$。

然后下午一看,我自己倒是没挂分,$85+20+28=133​$,可其它和我写一样东西的都是 $100+20+40​$..

T1 数据范围不知道是不是为了防止爆 int 而改小就算了,复杂度完全错误的 $70​$ 分做法竟然直接 A 了..就很自闭。T3 其他人的 $n^4​$ 常数比我小一截,我也不好说什么..只不过那些“数据有梯度”的出题人凭什么不多给几档部分分啊?

感觉还是赛制问题啊..没有 Subtask 并且现场评测的 OI 赛制出题人也很无奈吧..

把 NOI 嘉年华咕了(玩一些体育运动之类的游戏得奖品什么的),回寝室躺了一会儿,又看了一遍 四色的NOI,感觉自己的心境和 vfk Cu 那年挺像的..只不过就算把 vfk Fe 那年去掉,我也比 vfk 少一年啊..

讲题的话..放一张 T2 讲题的图吧:

d1t2

Day 116195171

今天是社会活动日。

听说真的有人没去..不知道会不会扣分。

坐 D7 的被奶了:

d7700

在博物馆先打了把四人南,然后去随便逛了半个小时。

暗示 route 数据水:

routesea

暗示 Day 2 Au 线 30 Ag 线 20:

auag

假毛请大家自行脑补假毛在风中打转的样子

wuliang

晚上是 zzq 和象的见面会,感觉还是象比较励志,其它三名国家队都是小学开始学的..刷题量好像非常恐怖,而“好好打模拟赛”对我来说几乎不需要解释..我知道平时我是怎样在打模拟赛的,“这个知识点还没学”,“这题没意思”,“题解看不懂”,“这题太简单了,只是考场 sb 了而已,懒得写”,“我先按我的计划补知识点,模拟赛不重要”,最后一题都没有改。这样的话我又在渴求什么呢。

以为自己很努力了,但是不知为何还是系统告诉我:Mission Failed. Play Again.

不知道原因。

张着嘴巴我可以说出一堆:经验少啦,在弱省啦,题做得少啦,数学太弱啦……

但是这是不是真正的原因?怎样解决?

天地无言。

—— vfk《四色的NOI》

可我甚至不能“以为自己很努力了”。

Day 2

今天的纸质题面考前是正面朝上的。

果然有交互,还依然是 I 君。

等等,T2 斗主地?

等等,T1 128MB?简洁数据结构.pdf

开始考试,T1,线段树优化连边?爆空间。88 可能能卡过?感觉很难卡,还得数据分治,写了不到 5min 就放弃了,去写了 72 分。

T2,dp 算洗牌前是 $i​$ 洗牌后是 $j​$ 的概率,第四个点矩阵快速幂,很快就写完了,一遍过样例。这个时候两小时多一点。

考前就想着靠交互翻盘了,还剩接近 3h 肝交互,感觉海星。

这个数据范围好像不太统一啊..既然强制数据分治的话不如会一档写一档好了。

先把 $\mathcal O(n^2)$ 次询问的写了,一开始还写错了,写成了 $n$ 次修改,差点挂掉 $8$ 分。

然后想了一会儿想到了性质 $A$ 一个期望 $\log$ 的做法。写完 + 调完之后 3h 多一点。

然后开始想 T3 各种各样的部分分,乱搞了 2h 一无所获。

出来之后发现大家 T1 都会 K-D Tree,又听说 T2 结论题可以打表..感觉 Ag 基本上没了啊。

我博客用模 998244353 的等比数列,是不是暗示 T2 模 998244353 等差数列,会被禁赛啊。

下午看成绩,$72+30+36=138$,发现 T2 30,原因是 a 数组开小了…只不过不挂分应该也是 Cu,问题不大

讲题的时候松松松把 NOI 弄成了鸭子营。

T2 出题人表示:不止要让训练有素的选手进队,也要让那些能够发现题目性质的选手进队。感觉要是不能打表的话这样的想法也挺有道理的..

出排名,果然 Cu 了。

HB 只有 jxl 和 lwc Ag。只不过两个 E 都上了 Ag 分数线。

zyy 捧杯了,zzy rk2,zzq rk3,_rqy rk4,jumpmelon rk6,myh rk7,zhf rk19。

看到熟悉的名字进集训队的感觉真的很奇妙。

晚上去高校宣讲看热闹。

清华那位老师的气质真的就完全不一样(之前 THUWC 和 THUSC 的时候就体会地非常明显了),有条不紊地讲出硬核的优点(而不是那些花里胡哨的东西)(也没有一种”我是来完成任务“的感觉)(也不会说“那我今天就用这个 PPT 来讲一下”“那我就不用 PPT 了”这样的话),感觉讲了非常多,最后正好卡时讲完了(其它学校都感觉没讲啥就匆匆忙忙结束了)(只不过这也可能是学校实力原因)。(顺带一提,THU 没用 PPT)

北大:我准备了一个 PPT,发邮件的时候挂了,今天我把 PPT 带过来了,我是干讲还是用 PPT,你们觉得怎么样比较好?

主持人:抱歉,请遵守规则口头讲。

北大:我觉得准备这么一个 PPT 不给大家看实在是对不起大家。

(说着就打开了 PPT)

???

天津大学很快就讲完了,然后说“不用打铃了”,很多人鼓掌..感觉 THU 那样打铃的同时有条不紊地结束才比较帅啊(

感觉武大也讲的海星,也是真的在讲而不是完成任务,感觉比较自然。

华东师范大学:男生们可以和很多文科的女生交流。女生们也不要担心,因为你们也可以和很多文科的女生交流。emm…

排在最后的三个学校直接咕了…

只不过我一个 Cu 凭什么评价高校宣讲啊。

“我也是有约的人了!”「两年 OI 换一纸签约」—— 一名拿到人大一等约的我省高二选手。

好像还有面试到晚上十二点,最后拿到“替补二等约”的选手..

看到身边的人退役更是一种说不出的感觉。

Day 232390342

早上咕掉嘉年华,去机房把 D1T1 写了,然后试图学习 k-d tree。

感觉资料还是太少了,也不知道网上那些复杂度是不是对的..

下午闭幕式。大家该 AuAu,该捧的捧该扫射的灯光师继续扫射

结束之后真的落雨大了..下了一个多小时的大雨,选手袜子没了

pb

Cu

我双色 NOI 的第一色,是古铜色的。

Day 4

本来不想写 Day 4 的,但广州南的便利店竟然没有泡面,必须得吐槽一下

G1114 竟然没有插座,更得吐槽了

那么,长沙一中再会。

题解

估计会比较咕

D1T1

“去年 D1T1 最短路,今年也是呢”选手自闭了。

出考场听说斜率优化,以为是斜率优化预处理等待时间的连边然后跑最短路。

看了题解才知道原来这题根本不用最短路,连 DAG 最短路都不用..

把边按结束时间($q_i$)排序,令 $f_i$ 表示走完第 $i$ 条边后还需要的烦躁值的最小值。

$\begin{aligned}f_i&=\min\limits_{p_j\ge q_i,x_j=y_i}\{A(p_j-q_i)^2+B(p_j-q_i)+C+q_j-q_i+f_j\}\\&=\min\limits_{p_j\ge q_i,x_j=y_i}\{Ap_j^2+Bp_j+q_j+f_j-2Ap_jq_i\}+Aq_i^2-Bq_i+C-q_i\end{aligned}​$

然后就可以斜率优化了。(因为转移有 $x_j=y_i$ 的限制,要开 $n$ 个双端队列,但不要开 deque,开大量 deque 是会 MLE 的。写法的话,用 vector 存,普通方法写就好了。)

参考代码

按理来说题解里不应该包含模板,只不过这也不是什么官方题解,我就懒得换成正常写法了。

#ifndef OUUAN
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#endif
#include<bits/stdc++.h>

#define int LoveLive
//#define FAST_IOSTREAM 1

#define For(i,l,r)for(int i=(l),i##end=(r);i<=i##end;++i)
#define FOR(i,r,l)for(int i=(r),i##end=(l);i>=i##end;--i)
#define SON(i,u)for(int i=head[u];i;i=nxt[i])
#define ms(a,x)memset(a,x,sizeof(a))
#define fi first
#define se second
#define pq priority_queue
#define pb emplace_back
#define isinf(x)(x>=INF?-1:x)
#define DEBUG(x)cerr<<(#x)<<":"<<x<<endl
using namespace std;typedef long long LoveLive;typedef pair<int,int>pii;typedef vector<int>vi;
#ifdef int
const int INF=0x3f3f3f3f3f3f3f3fll;
#else
const int INF=0x3f3f3f3f;
#endif
const double eps=1e-9;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());int randint
(int l,int r){return(int)rng()%(r-l+1)+l;}
#ifdef FAST_IOSTREAM
#define br cout<<'\n'
#define sp cout<<' '
long long read(){long long x;cin>>x;return x;}template<typename T>void read(T&x){cin>>x;}template<typename
T>void write(const T&x){cout<<x;}
#else
#define br putchar('\n')
#define sp putchar(' ')
template<typename T>typename enable_if<!is_integral<T>::value,void>::type read(T&x){cin>>x;}long long
read(){char c;long long out=0,f=1;for(c=getchar();!isdigit(c)&&c!='-';c=getchar());if(c=='-'){f=-1;c
=getchar();}for(;isdigit(c);c=getchar())out=(out<<3)+(out<<1)+c-'0';return out*f;}template<typename T
>typename enable_if<is_integral<T>::value,T>::type read(T&x){char c;T f=1;x=0;for(c=getchar();!isdigit
(c)&&c!='-';c=getchar());if(c=='-'){f=-1;c=getchar();}for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+c-'0';
return x*=f;}char read(char&x){for(x=getchar();isspace(x);x=getchar());return x;}double read(double
&x){scanf("%lf",&x);return x;}void read(char*x){scanf("%s",x);}template<typename T>typename enable_if
<!is_integral<T>::value,void>::type write(const T&x){cout<<x;}template<typename T>typename enable_if<
is_integral<T>::value,void>::type write(const T&x){if(x<0){putchar('-');write(-x);return;}if(x>9)write
(x/10);putchar(x%10+'0');}void write(const char&x){putchar(x);}void write(const double&x){printf("%.10lf"
,x);}void write(const char*x){printf("%s",x);}
#endif
template<typename T,typename...Args>void read(T&x,Args&...args){read(x);read(args...);}template<typename
...Args>void read(char*x,Args&...args){read(x);read(args...);}template<typename OutputIt,typename=typename
enable_if<is_same<output_iterator_tag,typename iterator_traits<OutputIt>::iterator_category>::value ||(
is_base_of<forward_iterator_tag,typename iterator_traits<OutputIt>::iterator_category>::value&&!is_const
<OutputIt>::value)>::type>void read(OutputIt __first,OutputIt __last){for(;__first!=__last;++__first)
read(*__first);}template<typename InputIt,typename=typename enable_if<is_base_of<input_iterator_tag,typename
iterator_traits<InputIt>::iterator_category>::value>::type>void wts(InputIt __first,InputIt __last){
for(;__first!=__last;++__first){write(*__first);sp;}}template<typename InputIt,typename=typename enable_if
<is_base_of<input_iterator_tag,typename iterator_traits<InputIt>::iterator_category>::value>::type>void
wtb(InputIt __first,InputIt __last){for(;__first!=__last;++__first){write(*__first);br;}}void wts(const
char*x){write(x);sp;}void wtb(const char*x){write(x);br;}void wte(const char*x){write(x);exit(0);}template
<typename T>void wts(const T&x){write(x);sp;}template<typename T>void wtb(const T&x){write(x);br;}template
<typename T>void wte(const T&x){write(x);exit(0);}template<typename...Args>void wts(const char*x,Args
...args){wts(x);wts(args...);}template<typename...Args>void wtb(const char*x,Args...args){wts(x);wtb(
args...);}template<typename...Args>void wte(const char*x,Args...args){wts(x);wte(args...);}template<typename
T,typename...Args>void wts(const T&x,Args...args){wts(x);wts(args...);}template<typename T,typename...
Args>void wtb(const T&x,Args...args){wts(x);wtb(args...);}template<typename T,typename...Args>void wte
(const T&x,Args...args){wts(x);wte(args...);}template<typename T>inline bool up(T&x,const T&y){return
x<y?x=y,1:0;}template<typename T>inline bool dn(T&x,const T&y){return y<x?x=y,1:0;}

const int N = 100010;
const int M = 200010;

int n, m, a, b, c, id[M];

struct Edge
{
	int u, v, p, q, f;
	bool operator<(const Edge & b) const
	{
		return q > b.q;
	}
} e[M];

struct Point
{
	int x, y;
	Point(int j = 0): x(2 * a * e[j].p), y(a * e[j].p * e[j].p + b * e[j].p + e[j].q + e[j].f) {}
	friend bool cmp(const Point & a1, const Point & a2, const Point & a3)
	{
		if (a1.x == a2.x) return a1.y < a2.y;
		return (a1.y - a3.y) * (a2.x - a3.x) >= (a2.y - a3.y) * (a1.x - a3.x);
	}
	int cal(int k) const { return y - k * x; }
};

struct Deque
{
	vector<Point> q;
	int ql, qr;
	Deque()
	{
		q.resize(1);
		ql = 1;
		qr = 0;
	}
	bool empty() const { return ql > qr; }
	void push_back(const Point & x)
	{
		++qr;
		if (q.size() == qr) q.push_back(x);
		else q[qr] = x;
	}
	void cal(int i)
	{
		while (ql < qr && q[ql + 1].cal(e[i].q) <= q[ql].cal(e[i].q)) ++ql;
		e[i].f = q[ql].cal(e[i].q) + a * e[i].q * e[i].q - b * e[i].q + c - e[i].q;
	}
	void insert(const Point & x)
	{
		while (ql < qr && cmp(x, q[qr], q[qr - 1])) --qr;
		push_back(x);
	}
} q[N];

signed main()
{
#ifdef FAST_IOSTREAM
	cin.sync_with_stdio(false);
	cin.tie(0);
#endif
	
	read(n, m, a, b, c);
	
	For (i, 1, m) read(e[i].u, e[i].v, e[i].p, e[i].q);
	++m;
	e[m].u = 0;
	e[m].v = 1;
	e[m].p = 0;
	e[m].q = 0;
	sort(e + 1, e + m + 1);
	
	For (i, 1, m) id[i] = i;
	sort(id + 1, id + m + 1, [](int x, int y) { return e[x].p > e[y].p; });
	int idp = 1;
	
	For (i, 1, m)
	{
		if (e[i].v == n)
		{
			e[i].f = 0;
			continue;
		}
		while (idp <= m && e[id[idp]].p >= e[i].q)
		{
			if (e[id[idp]].f < INF) q[e[id[idp]].u].insert(Point(id[idp]));
			++idp;
		}
		if (q[e[i].v].empty())
		{
			e[i].f = INF;
			continue;
		}
		q[e[i].v].cal(i);
	}
	
	For (i, 1, m) if (e[i].u == 0) wte(e[i].f);
	
	return 0;
}

D1T3

其实可以模拟费用流,但如果你写一篇模拟费用流的题解,会发现那是一篇费用流建图的题解和一篇贪心题解拼起来。所以下面是一篇纯贪心题解。

我们要从两个序列中各选 $k$ 个下标,考虑每一步(选择一组下标):

  • 如果还允许选两个不一样的下标,那就从剩下还没选的数里选最大的 $a$ 和最大的 $b$。
  • 如果无法选择不一样的下标了,那么有三种选择:
    1. 选择一组 $a_i+b_i$(即 $a$, $b$ 下标相同)
    2. $a_i$ 被选了,$b_i$ 没有被选,那么把 $a_i$ 与 $b_i$ 匹配,再给 $a_i$ 原来匹配的那个 $b_j$ 找到一个剩下的里面最大的 $a_k$,然后把 $b_j$ 和 $a_k$ 匹配。
    3. 把第二条的 $a$ 和 $b$ 互换。

那么,维护剩下的最大的 $a$,剩下的最大的 $b$,剩下的最大的 $a+b$,$a_i$ 已匹配的最大的 $b_i$,$b_i$ 已匹配的最大的 $a_i$,剩余可选择的不一样下标个数,每个数匹配的数,就可以完成这个贪心了。

前三个最大值排序即可,后两个最大值使用堆维护。细节有些多,写的时候注意每一步都确保每个量正确更新了。尤其需要注意的是“剩余可选择的不一样下标个数”的更新。

参考代码
#include <iostream>
#include <cstdio>
#include <cctype>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

int read()
{
    int out = 0;
    char c;
    while (!isdigit(c = getchar()));
    for (; isdigit(c); c = getchar()) out = out * 10 + c - '0';
    return out;
}

typedef pair<int, int> pii;

const int N = 200010;
const int INF = 1e9;

int T, n, k, dif, a[N], b[N], ida[N], idb[N], idab[N], pa, pb, pab, fa[N], fb[N]; // dif 是剩余可选择的不一样下标个数,id 是用来排序的,pa,pb,pab 记录用到了第几个值(即当前最大值是 a[pa] 之类的),fa,fb 分别记录 a_i 和 b_i 匹配的数的下标
priority_queue<pii> sa, sb, emptypq; // sa 是 b 已匹配的 a,sb 是 a 已匹配的 b,emptypq 是用来多测清空的

void link(int u, int v) // 匹配两个数
{
    --dif;
    fa[u] = v;
    fb[v] = u;
    if (u == v) --dif; // 去重,否则会在下面三行代码里加两次
    if (fb[u]) ++dif;
    else sb.push(pii(b[u], u));
    if (fa[v]) ++dif;
    else sa.push(pii(a[v], v));
}

void cut(int u, int v) // 断开匹配
{
    ++dif;
    if (fb[u]) --dif;
    if (fa[v]) --dif;
    if (u == v) ++dif; // 去重
    fa[u] = fb[v] = 0;
}

pii geta() // 获取当前剩余的最大 a
{
    while (fa[ida[pa]]) ++pa;
    return pii(a[ida[pa]], ida[pa]);
}

pii getb() // 获取当前剩余的最大 b
{
    while (fb[idb[pb]]) ++pb;
    return pii(b[idb[pb]], idb[pb]);
}

pii getab() // 获取当前剩余的最大 a + b
{
    while (pab <= n && (fa[idab[pab]] || fb[idab[pab]])) ++pab;
    return pii(pab <= n ? a[idab[pab]] + b[idab[pab]] : -INF, idab[pab]);
}

pii getsa() // 获取 b 已选的最大 a
{
    while (!sa.empty() && fa[sa.top().second]) sa.pop();
    return sa.empty() ? pii(-INF, 0) : sa.top();
}

pii getsb() // 获取 a 已选的最大 b
{
    while (!sb.empty() && fb[sb.top().second]) sb.pop();
    return sb.empty() ? pii(-INF, 0) : sb.top();
}

int main()
{
    T = read();

    while (T--)
    {
        pa = pb = pab = 1;
        sa = sb = emptypq;
        memset(fa, 0, sizeof(fa));
        memset(fb, 0, sizeof(fb));

        n = read();
        k = read();
        dif = k - read();
        for (int i = 1; i <= n; ++i) a[i] = read();
        for (int i = 1; i <= n; ++i) b[i] = read();

        for (int i = 1; i <= n; ++i) ida[i] = idb[i] = idab[i] = i;
        sort(ida + 1, ida + n + 1, [](int x, int y){return a[x] > a[y];});
        sort(idb + 1, idb + n + 1, [](int x, int y){return b[x] > b[y];});
        sort(idab + 1, idab + n + 1, [](int x, int y){return a[x] + b[x] > a[y] + b[y];});

        while (k--)
        {
            if (dif) link(geta().second, getb().second);
            else
            {
                pii nab = getab();
                pii na_a = getsa();
                pii na_b = getb();
                pii nb_a = geta();
                pii nb_b = getsb();
                if (nab.first >= na_a.first + na_b.first && nab.first >= nb_a.first + nb_b.first) link(nab.second, nab.second);
                else if (na_a.first + na_b.first >= nb_a.first + nb_b.first)
                {
                    int t = fb[na_a.second];
                    cut(t, na_a.second);
                    link(t, na_b.second);
                    link(na_a.second, na_a.second);
                }
                else
                {
                    int t = fa[nb_b.second];
                    cut(nb_b.second, t);
                    link(nb_a.second, t);
                    link(nb_b.second, nb_b.second);
                }
            }
        }

        long long ans = 0;
        for (int i = 1; i <= n; ++i) ans += (fa[i] ? a[i] : 0) + (fb[i] ? b[i] : 0);
        printf("%lld\n", ans);
    }

    return 0;
}