课件

Doll

来源：

IOI2018D2

题意：

略

题解：

构造题

方法很多

构造一行节点，再每个节点下构造一棵完全二叉树

也可以对着数据构造

Highway

来源：

IOI2018D2

题意：

交互题

略

题解：

题解

面向数据答题

先二分找到一条最短路上的边（u，v）

假设S->u->v->T，那么S一定再到u小于到v的距离的集合中，T则反之。

然后以u或v建立bfs树，就可以继续找到S，T中bfs序大的点，

然后就变成子任务2了，二分就完事了。

Meeting

来源：

IOI2018D2

题意：

略

题解：

第一个点暴力，第二个点单调队列优化

剩下不会

丢一个题解

采集贝类

来源：

Korea 2017

题意：

给一个n*n矩阵，每个格子可以收集A_{i,j}个贝类。

定义B_{i,j}为从(i,j)出发，只能向上向左走能收集的贝类最大值。

求\Sigma B_{i,j}。

还有n次修改，每次将某个A_{i,j}加1或减1，并求新的\Sigma B_{i,j}。

n\leq 1500

题解：

考虑每次修改受到影响的点。

用线段树维护。

Train Tracking

来源：

USACO2018

题意：

交互题，题意有点没懂

题解：

看不懂

Airline Route Map

来源：

Japan 2018

题意：

交互通讯题

两个程序，一个得到一个n个点m条边的无向图要用n'给点表示出来。

然后交互库重新编号，要第二个程序还原出来。

n'-n\leq 12

题解：

用10个点的二进制位表示各个点。

然后用11号点向除了12号点全部点连边，可以确定最大度数的点是11号点。

然后12号点向1号点连边，1号向2号，一直形成一个链，就可以确定10个加的点了。

Security Gate

来源：

Japan 2018

题意：

一个括号序列被称为好的当且仅当将某以连续子段取反后是一个合法的序列。

现在有一个带有通配符的括号序列，求有多少个好的括号序列可以匹配上。

n\leq 300

题解：

合法序列有三种

  • 本身合法，此时dp O(n^2)就好
  • 某一侧开始的前缀和是非法的，此时不妨假设从左开始不合法，最优情况下，取反的左端点一定是A，右端点是A+B/2。取反后\leq 2A。（然后就不知道了
  • 两侧都是非法的（反正听不懂，不写了

（听不懂，弃了

Cultivation

来源：

Japan 2017

题意：

有一个R*C的网格，初始有N个格子有草。每年结束可以决定一场风，草沿风传播一格，问最少多少年可以每个格子有草。

题解：

神仙题不会

Sparklers

来源：

Japan 2017

题意：

没懂

题解：

没懂

Arranging Tickets

来源：

Japan 2017

题意：

有n个站，有一套票编号1-n，第i号可以从i到i+1或i+1到i。有k批人，每批c人从a到b，票只能一套一套买，问最少买几套票可以满足全部人。

题解：

可以将区间翻转为[1,l),(r,n]，显然两个不交的区间不会翻转。

令b_i为反转后每个位置被覆盖的次数，假设一种最优方案的交集是[l,r),其中最大值b_t。

可以证明一定存在一组最优方案是b_t=maxb_i或maxb_i-1

令a_i为初始的被覆盖次数，可以证明a_t=maxa_i。如果有多个maxa_i，我们只要取第一个和最后一个就好

Natural Park

来源：

Japan 2017

题意：

有一个n个点的图，每个点不超过7个相邻节点。

你可以通过不超过45000次询问，每次询问A和B能否通过给定点连通，来求出所有边。

n\leq 1400,m\leq 1500

题解：

神仙题听不太懂

看不懂题目名字（

来源：

Russia 2018

题意：

有n个点坐标为(x_i,y_i),两个点之间的代价为2^{min(|x_i-x_j|,|y_i-y_j|)}。

求1到n的最小代价

题解：

优化连边。

以中心画十字，在十字上的连边，对于分成的四块每块向距离最近的一些点连边就好。

因为连边的点都在一条线上，所以用线段树优化连边。

然后对于距离的维护可以使用函数值线段树。

还是看不懂（

来源：

Russia 2017

题意：

有n个点，q次询问。

每次询问是交互库知道另一个在平面上的点P。你可以每次选择一个由n个点中若干给点组成的凸边形，询问P是不是在着里面。你需要找到一个包含P的极小多边形，及凸多边形中不含其他点。

n\leq 2500,q\leq 2000

询问次数每次不超过40次

题解：

考虑Delauney三角剖分

然后神仙算法看不懂了。

看不懂俄文（

来源：

Russia 2017

题意：

两个学期分别开了n,m门课，每门课上完后有一定收益，两个学期相同的课不能同时上。

必须上一段连续的课程，求最大收益。

n\leq 500005

题解：

如果只在一个学期上，显然全部选，如果在两个学期都上课，必然有一个学期的区间要跨过收益的中位数。

不妨假设第一个学期必须跨过，令f[l][r]为第二个学期的区间为l，r的最大值。

那么从小到大枚举l,然后用线段树来维护f[l][r]最大值即可。