昨天训练时有一道并不难的dp题 http://codeforces.com/gym/103202/problem/H
大意是有n种卡，每种卡有d,k,c三个属性，表示有效时间，使用次数和价格，每张卡可以买任意次，也可以不用卡。再给出m天，用$p_i,q_i$表示一个人要在$p_i$天买$q_i$次东西，问最小代价。
阅读全文
MorphLing
9月 30, 2021
B. CannonG. League of Legends题意：给定n个区间，要求将它们分成k组，每组之间有交，最大化每组交长度之和
简化问题，对于如果一个大区间能够完整包含某个小区间，则该大区间只有两种最优决策：
单独归为一组，贡献r-l
与任意一个其包含的小区间归为一组，不对结果产生影响
可以用反证法证明结论，假如大区间和其他区间归为一组，那么将该大区间移出该组，该组的交一定不下降，再放入其包含的小区间组中，小区间所在的组的交也不下降，即大小区间在同一组的决策一定最优
于是可以把所有大区间取出来，单独讨论所有小区间，可以发现，若将剩下的区间按照左端点从小到大排序，其右端点也一定是有序的，接着考虑dp，$f[i][j]$表示考虑前i个区间，分成j组的最优答案，而一组的贡献只与最左和最右两个区间相关，显然有转移$f[k][j+1]=\max\limits_{r[i+1]-l[k]>0} \{f[i][j]+r[i+1]-l[k]\}$
阅读全文
MorphLing
7月 20, 2021
A. Alice and Bob题意：给出两堆石子a、b，两名玩家轮流取石子，取法是在一堆石子里取k个，并在另一堆石子里取$s\times k$个$(s\ge 0)$，给定a、b，问先后手谁必胜
观察得到，对于一堆石子为i个，那么只有最多一个对应的j，使得两堆石子为i、j时为必败态，于是必败态总数不超过n。对于每一个必败态，先枚举k，再枚举s，得到所有能一步达到该状态的必胜态，复杂度为调和级数$O(n\log n)$
阅读全文
MorphLing
7月 18, 2021
F. Nice Positions观察：对于一个序列，任意相邻两个数至少有一个是好的，即不存在两个连续的坏点
简单套个容斥就是
好点>=k的方案 <==> 坏点<=n-k的方案
然后从小到大把每个数插入排列，发现如果插入的数在一个坏点两侧，那么坏点数量不变，否则坏点数量+1
主要是一直在考虑，确定前i个点后再确定第i+1个点，从左往右依次确定的线性推法
但是如果从把最后一个数插入排列的任意位置的角度考虑就会简单很多
阅读全文
MorphLing
6月 10, 2021
斜率优化本质上解决的是，给定一条直线的斜率和平面上的若干个点，要求选择一个点，使得该直线经过该点，且保证此时截距取到最小/最大值。
阅读全文
MorphLing
4月 01, 2021