Day 3: IQ test by kefaa2, antontrygubO_o, and gepardo¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 17/90 | 7 | 8 | 13 |
A¶
solved by YZW
题意¶
题解¶
B¶
solved by JLK&YZW
题意¶
给定长度为\(n\)的序列\(a\)，常数\(k\)和\(w\)。
每次询问把\(a\)里的一个元素永久改动，然后把\(a\)从小到大排序得到\(b\)序列，
求\(\sum\limits_{i=1}^n \lfloor \frac{b_i\times i^k}{w}\rfloor\)。
\(1 \le n,q \le 10^5,1 \le k,w \le 5\)。
题解¶
直接维护\(b\)序列。每次相当于改一个数，然后把这个数移动到对应位置。先想如何用平衡树维护。
考虑\(w=1\)的情况，如何维护\(\sum b_i\times i^k\)。在平衡树上，每次Up操作，左儿子的值不变，对于右儿子里的点，把\(b_i\times i^k\)变成\(b_i \times (i+x)^k\)。这可以二项式展开，每个点维护子树内所有点的\(\sum b_i\times i^P,0 \le P \le k\)即可。
再考虑整除的影响。如果能求出\(\sum ( b_i\times i^k \mod w)\)，那么整除就可以看做是\(\frac {\sum (b_i \times i^k)-\sum ( b_i\times i^k \mod w)}{w}\)。
注意到模\(w\)之后，\(b_i\times i^k\)的值只和\(b_i\mod w,i\mod w\)两个值有关。由于\(w\)很小，有一种暴力维护的方法。就是每个点记录一个\(w\times w\)的矩阵，\((x,y)\)表示子树内\(i \mod w=x,b_i \mod w=y\)的位置的个数。Up的时候左儿子仍然不变，右儿子相当于是每一行循环移动了\(siz[lc]\)次，可以\(O(w^2)\)处理。
最后答案就是把第一个点记录的值处理一下即可。
\(O((n+q)(k^2+w^2)\log n)\)
C¶
**upsolved by **
题意¶
题解¶
D¶
upsolved by TYB
题意¶
给一个数组\(\{a_n\}\)，\(n\)为偶数，\(\forall i\in[1,n], a_i=i\)。每次可以删除相邻的两个数\(x,y\)，花费为\(cost[x][y]\)，给出所有奇数和偶数间的\(cost\)，且保证\(cost\)是\([1,\frac{n^2}{4}]\)的一个排列，求一种删除所有数的方案，使过程中的最大花费最小，输出这个花费。
\(n\le4000\)
题解¶
容易想到\(\mathcal{O}(n^3)\)的区间DP做法，这个做法的瓶颈在于转移，考虑如何优化。考虑用类似dijkstra的处理方法，从一个已有的状态去转移到其它没有被转移过的状态，那么这一定是最优的。假设当前我们的状态是\([l,r]\)，考虑如何用\(f[l][r]\)转移到其它。首先是\(f[l][r]->f[l-1][r+1]\)，当\(f[l][r]>cost[l-1][r+1]\)可以转移，否则可能有更优的解。然后就是\(f[l][r]\)作为左区间或者右区间转移，即\(f[l][r]->f[l][k](k>r)\)或\(f[l][r]->f[k][r](k<l)\)。以前者为例，那么我们要找到的\(k\)满足下列条件：1、\(f[l][k]\)没被转移。2、\(f[r+1][k]\)已被转移。找这个可以用bitset维护每个端点作为左/右端点，还有哪些点有/没有被转移过，每次与一下就好了。至于遍历bitset中的\(1\)，可以用_Find_first函数找到第一个\(1\)，用 _Find_next函数实现找到下一个\(1\)。
\(\mathcal{O}(\frac{n^3}{64})\)。
E¶
solved by YZW
题意¶
题解¶
F¶
solved by YZW
题意¶
题解¶
G¶
solved by JLK&TYB
题意¶
一个\(n\)个点的完全图，每条边是两种颜色之一。对于每个四个点的子图，如果只有一条边和其它边不同色，那么称其为A的。如果三条边相同颜色，另外三条边也是相同颜色，并且没有同色三角形，那么称其为Y的。求Y的数量-A的数量。
\(1 \le n \le 2000\)
题解¶
比较奇妙的题，有点容斥思想。
枚举两个对角点\(a,c\)，用bitset算出满足\(ab,bc\)同色且和\(ac\)不同的\(b\)的数量\(x\)。\(\sum C_x^2\)是这种情况下4条边同色的四元环数量的两倍以及4条边和一条对角线同色的四元环（也就是A）数量之和\(a\)。
枚举两个对角点\(a,c\)，用bitset算出对于两种\(ab\)颜色的情况，分别满足\(ab,bc\)不同色的\(b\)的数量\(x,y\)。\(\sum x\times y\)是这种情况下4条边同色的四元环数量的四倍以及对边2条边和一条对角线同色的四元环数量（也就是Y）的两倍之和\(b\)。前者是因为可以把四元组扭转一下，就变成了外面四条边同色。
答案即为\(\frac b2-a\)。可以画图感受一下。
\(O(\frac {n^3}{64})\)
H¶
solved by YZW
题意¶
题解¶
I¶
**upsolved by **
题意¶
题解¶
J¶
**upsolved by **
题意¶
题解¶
K¶
**upsolved by **
题意¶
题解¶
L¶
**upsolved by **
题意¶
题解¶
M¶
solved by YZW
题意¶
题解¶
记录¶
开局YZW写M(0:04)A(0:13)F(1:03)E(1:30)。
JLK和TYB讨论G，然后过了(2:54)。
YZW写H，WA一次PE一次后AC(3:32)。
还剩BDJ可做，还剩40min左右YZW突然会B了，JLK写，WA一次后AC(4:52)。
总结¶
JLK: 欺负人没有IQ？
TYB：感觉构造题做得不太好，可以练一练。
Dirt¶
B(-1)
H(-2)