2017-2018 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 3/? | 12 | 13 | 13 |
A¶
solved by JLK
题意¶
签到，略
题解¶
B¶
upsolved by TYB
题意¶
\(n\)个人，第\(i\)个人的初始分数为\(p_i\)，这些分数各不相同，现在要将\(m\)分分配给每个人，设第\(i\)个人被分到了\(q_i\)分，要求\(q_i\ge1\)且\(\sum_{i=1}^nq_i=m\)。现在按\(q_i\)升序公布每个人的加分，若\(q_i\)相同则按\(p_i\)升序，若某人的加分已被公布，则其分数为\(p_i+q_i\)，否则为\(p_i\)，要求每次公布加分后，分数最高的人唯一，且与公布前分数最高的人不同，求方案数。
\(n\le12,m\le700\)
题解¶
考虑暴力DP：\(f_{S,i,mx,r}\)表示集合\(S\)里的人已经公布了加分，当前最高分的是第\(i\)个人，其分数为\(mx\)，还剩下\(r\)分可以分配的方案数。转移枚举下一次公布哪个人的加分（加的分数是唯一的，贪心加最少的分数使得其满足条件），显然无法通过。
考虑优化。如果给当前这个人分配了\(t\)分，那么由于\(q_i\)单调不降，后面剩下的每个人都至少需要被分配到\(t\)分，如果提前计算这部分的贡献，即\(r\)减去剩余人数\(\times t\)的值，那么对于每次最高分发生变化这个条件，只需要比较\(p_i\)即可，可以去掉\(mx\)这一维。
C¶
solved by TYB
题意¶
签到。
题解¶
略。
D¶
solved by JLK
题意¶
\(n\)个点的树，每条边有边权。对于一个点，如果从这个点出发的所有路径，路径当中经过的相邻的边的边权没有重复的，那么符合条件。求出所有符合条件的点。
\(1 \le n \le 50000\)
题解¶
考虑相邻，那么枚举一个点的所有边。如果某条边的边权出现至少两次，那么这个子树里出发的点一定不合法。做一下树上差分就可以知道所有合法的点。
\(O(n)\)
E¶
solved by YZW
题意¶
题解¶
F¶
solved by YZW
题意¶
题解¶
G¶
solved by TYB
题意¶
签到。
题解¶
略。
H¶
solved by JLK
题意¶
斜率优化DP裸题，略
题解¶
I¶
solved by JLK
题意¶
初始有一个无限长的序列，有若干次操作，在某个位置插入或者删除。
给定两组操作，问是否等价。
\(1 \le q \le 2000\)
题解¶
大模拟题。
把插入看做挂在原序列的某个位置后面。删除要么是删除原序列的某个位置，要么是把某个插入的数删除了。每次操作枚举一下位置前面的操作，找到这个操作相对原串的真实位置。碰到插入就是相对-1，碰到删除就是相对+1。
需要大力分类讨论和模拟。
有一种情况需要特殊处理，就是删除了一个原串上的点，但是这个点后面挂着一些插入。可以把这些插入挂到原串前面第一个没有被删除的点上。
\(O(q^2)\)
J¶
solved by TYB
题意¶
签到。
题解¶
略。
K¶
solved by JLK
题意¶
给一个长度为\(n\)的数字串，一次操作可以在某个位上+1，会发生进位，长度超过\(k\)时取最后\(n\)位。求最少进行多少次操作，可以变成回文串。
\(1 \le n \le 40\)
题解¶
主要问题在于进位。
\(dp_{i,j,k}\)表示\([1,i]\)和\([n-i+1,i]\)已经回文匹配，第\(i\)位是否有增加的情况为\(j\)，第\(n-i+1\)为是否有进位的情况为\(k\)，的最小操作数。
每次可以枚举\(i+1\)和\(n-i\)各增加了多少（也就是进行了多少操作）。首先要保证它们模10之后相等。如果\(j=0\)但有左边进位，是不合法的。如果\(j>0\)且左边有进位，那么这个进位可以抵消掉前面用掉的一次操作。大力分类讨论一下转移即可。
考虑最后计算答案，如果是偶数可以直接得到，奇数的话还要枚举一下最中间的操作数。
L¶
solved by YZW
题意¶
题解¶
M¶
solved by YZW
题意¶
题解¶
记录¶
JLK过A(0:02)。
YZW过M(0:10)。
TYB过C(0:21)和G(0:33)。
JLK过D(0:44)。
TYB过J(0:55)。
YZW写E，WA一次后AC(1:04)。
然后写M，WA一次后AC(1:31)。
JLK写I，中间比较卡，和B交替进行。
I WA一次后AC(2:50)。
B TLE一次，不会优化。YZW开始写F，TLE一次。
JLK过H(4:13)。YZW过F(4:21)。
TYB继续优化B，JLK会了K。
B没卡过去，JLK开始写K，然后过了(4:58)。
B最后发现假了。
总结¶
JLK：没事不要乱搞题目
TYB：不要只会李超树不会斜率优化；不要觉得暴力能过就放弃思考正解。
Dirt¶
E(-1)
F(-1)
I(-1)
K(-1)
M(-1)