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)