2020-2021 ICPC Southeastern European Regional Programming Contest (SEERC 2020)¶

排名	当场过题数	至今过题数	总题数
82/?	7	8	13

A¶

upsolved by TYB

题意¶

给出序列$p$，你需要给整数序列$a$赋值，使得$\sum_{i=1}^na_i\times p_i$最大，并满足：

$1.a_0=a_{n+1}=0$

$2.\forall i\in[0,n],|a_i-a_{i+1}|\le1$

求这个最大值。

$n\le2.5\times10^5,-10^6\le p_i\le10^6$

题解¶

考虑换一种计算贡献的方式，设$s$为$p$的前缀和：

$\forall i\in[0,n-1]$且$a_i<a_{i+1},ans-=s_i$；

$\forall i\in[0,n-1]$且$a_i>a_{i+1},ans+=s_{i+1}$。

看一下题目中的图片，就会觉得比较显然。

然后这就转换成一个经典问题：每天物品有一个价格，一天中只可以买入/卖出一次，求最后的最大收益。

妙啊。

B¶

solved by YZW

题意¶

题解¶

C¶

**upsolved by **

题意¶

题解¶

D¶

solved by YZW

题意¶

略。

题解¶

人类智慧题。

E¶

solved by TYB

题意¶

签到。

题解¶

略。

F¶

solved by JLK

题意¶

有一个长度为$n$的排列，一次操作可以选定一个区间，把区间内所有数变成区间最小值。求做若干次操作后可能产生的序列数。

$1 \le n \le 3000$

题解¶

最后的序列中，如果一个数$A_i$变成了$A_j$，那么一定有$\min\limits_{k=i}^j A_k=A_j $。

$dp_{i,j}$表示前$i$个数确定了，第$i$个数变成了$A_j$，的方案数。

转移到$dp_{i+1,k}$，分类讨论。首先一定要满足上面的要求。

1、$j \le i$

如果$k \le i$，那么一定有$A_k \ge A_j$，否则$A_k$覆盖到$i+1$的时候会破坏$i$。

如果$k \gt i$，那么无论$j$是多少都可以。

2、$j \gt i$

如果$k \lt j$，那么$(i,j)$和$(i+1,k)$一定会产生重叠，不可能。

如果$k \ge j$，那么需要满足$A_k \le A_j$（实际上直接用上面的min条件判断即可）。

用前缀和转移即可做到$O(n^2)$。

G¶

**upsolved by **

题意¶

题解¶

H¶

**upsolved by **

题意¶

题解¶

I¶

solved by JLK

题意¶

给定$n$，求有多少$1,2,\dots ,n$的排列$p$，使得$p_i \mod p_{(i+1)\%n} \le 2$对每个$i$都成立。

$1 \le n \le 10^6$

题解¶

考虑从$n$转移到$n+1$，插入$n+1$，要让插入后前面和后面的模的结果都不超过$2$，那么前面肯定只能是$1$或者$2$，右后面必须是$n-1,n,n+1$其中一个的因子。

首先有一个普通的DP：$dp_{i,j,k}$表示$n=i$时，$1$和$2$后面分别是$j$和$k$的方案数。

转移的时候，要么插入到$1$后面，要么插入到$2$后面，还要枚举后面的数（因子）。

每个数总共只会枚举三次因子，所以总复杂度为$O(n^3\log n)$。

不难发现$j,k$其中有一个肯定等于$i$，而且我们并不关心是$1$还是$2$。所以只用记两个数，$dp_{i,j}$表示$n=i$，$1$和$2$后面不是$n$的数是$j$的方案数。

转移的时候也很简单，如果插入到$i$前面，那么就相当于是$dp_{i,*}$原封不动变成$dp_{i+1,*}$。而另一种情况下，$k$就会变成$i$，只需要枚举因子，转移到$dp_{i+1,i}$即可。

$O(n\log n)$

J¶

**upsolved by **

题意¶

题解¶

K¶

**upsolved by **

题意¶

题解¶

L¶

solved by TYB

题意¶

$n$个二元组$(a_i,b_i)$，求最大的$k$，使得将$n$个数分成$3$类（可以为空），满足第一类数和第二类数都有恰好$k$个，且第一类数的$\sum a>=$第二类数的$\sum b$。

$n\le10^5$

题解¶

考虑如果没有第三类数，可以直接默认一开始都是第一类数，然后计算出每个数改为第二类数的贡献，取前$k$个即可。

那么想办法把三类数转换成两类数。可以发现，将$b_i$从大到小排序，最优方案存在一个分界点，使得左边只有第一类数和第三类数，右边只有第一类数和第二类数，对左右两边分别套用两类数的方法即可。

还需要二分答案，复杂度$\mathcal{O}(n\log^2n)$。

M¶

solved by YZW

题意¶

题解¶

记录¶

JLK过B(0:13)，TYB E WA一次后AC(0:19)，YZW M RE一次后AC(0:47)。

TYB和YZW对I打表，JLK想别的题，后来讨论了一下会I了。

JLK写I，TLE一次后AC(1:42)。TYB写L，WA一次后AC(2:29)。

YZW大力分类讨论写D，JLK和TYB看AFH。

YZW过D(3:34)。但是其他题没有进展。讨论后会了F，JLK开始写。

TYB猜了一下H，顶下JLK开始写，然后WA了，发现假了。

JLK继续写，WA一次后AC(4:27)。

最后想出了H正解，但是没时间写了。

总结¶

JLK：1e6以内数的因子就不要用vector存了

Dirt¶

E(-1)

F(-1)

I(-1)

L(-1)

M(-1)