T1 休假
题目
小 A 需要休假，他制定的规则是每连续工作 \(X\) 天就必须休息，在一次休息前后，加起来不能工作超过 \(Y\) 天，现在老板在第 \(a_1,a_2,\dots,a_n\) 天给了他带薪休假，问他最少还要休息多少天才能按规定度过 \(M\) 天。
\(1 \le x \le 10^6, 0\le X,Y,M\le 10^{18}\)
Solution
其实就是一道模拟+贪心题，作为签到题 T1 比较合适，不过感觉细节稍微多了点，赛时只拿到了 80pts。
会发现在 \(X,Y\) 的限制下，为了休息天数少，肯定要尽量工作时间长，所以一次性工作满 \(X\) 天然后休息再连续工作 \(Y-X\) 天休息这样一定是最优的。需要注意可能在带薪休假前已经工作了一段时间，此时第一次连续工作的时间应该减去这一部分的时间。
代码实现上需要注意天数与时间点之间的转换，所以细节很麻烦。
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int _SIZE = 1e6;
int a[_SIZE + 5];
int n, m, X, Y, ans = 0;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> X >> Y;
for (int i = 1; i <= n; i++) cin >> a[i];
a[++n] = m + 1;
int remained = 0;
for (int i = 1; i <= n; i++) {
int first = min(X, Y - remained); // 第一次连续工作
int dtime = a[i] - a[i - 1] - 1; // 两次带薪休假间的间隔
ans += dtime / (Y + 2) * 2; // 至少休假多少次
if (dtime % (Y + 2) > first) {
ans++;
remained = dtime % (Y + 2) - first - 1;
if (remained > X) remained -= X + 1, ans++; // 注意可能出现 Y>2X 的情况，特判一下
} else {
remained = dtime % (Y + 2);
}
}
cout << ans << '\n';
return 0;
}
p.s. 连续工作 \(10^{18}\) 天，什么神人啊（
T2 开关
题目
有 \(n\) 盏灯，每盏灯开或者关，用 \(0/1\) 来表示。你有三种操作，选择一个区间全开或关，或将某个区间的开关状态反转。现在给定初始状态和结束状态，你需要求出最少多少次操作使得能从初始状态到结束状态。
\(n\le 10^6\)
Solution
赛时硬刚 2 个小时，成功赛时切掉这道题（就切了这一题）。
最开始看到这道题以为是区间 \(\texttt{DP}\)，结果看到 \(10^6\) 的数据范围瞬间懵了，结果再仔细一想发现不需要用区间来讨论，直接从开头到结尾线性 \(\texttt{DP}\) 就可以了，于是就开始了长达 30 分钟的推导。
设 \(f[i][0/1][0/1][0/1]\) 表示前 \(i\) 个灯要从初态变成终态至少需要的操作次数，并且对 \(i\) 是否进行过翻转操作，是否进行过推平成 \(0\) 操作，是否进行过推平成 \(1\) 的操作（下文为了式子的书写方便，也是为了增强可读性，将这个状态后三个数来表示，记作 \((0/1\ 0/1\ 0/1)\)），草稿本上画一下会发现这种设计状态的方式是可以覆盖所有情况的（感谢 FJN 大佬帮我证明了这种状态的正确性，赛时是用对拍验证的正确性）。
但是需要对这个状态设计方式加一些限制：首先是不能对 \(i\) 同时推平成为 \(0\) 和 \(1\)，因为这样肯定不会比直接推平成后一个更优，所以舍去 \((111),(011)\) 这两个状态。此外人为规定如果推平和翻转操作同时出现，一定是先推平再翻转，因为如果先翻转后推平肯定不如直接推平。有了这些限制就可以继续了。
得到这个状态后考虑怎么尝试转移，肯定需要分类讨论。既然每个灯只有 \(0/1\) 两种状态，起始状态和终止状态总共就只有 \(2\times 2=4\) 种，那就直接分类讨论一下。
-
\(a_i = b_i = 1\)
显然为了满足当前 \(a_i\) 不变，肯定不能对 \(i\) 进行翻转操作，所以可行的一种状态是 \((000)\)，此外 \((001)\) 和 \((110)\) 也是可行的。考虑怎么从 \(f[i-1]\) 转移过来（下面在 \(\leftarrow\) 前的表示 \(f[i]\)，后的表示 \(f[i-1]\)），会发现前面的 \(6\) 种状态都可以转移到当前状态。可以推导出下面的三个式子。
\((000) \leftarrow (000),(001),(010),(100),(101),(110)\)
\((001)\leftarrow (100)+1,(000)+1,(010)+1,(001),(101),(110)+1\)
\((110)\leftarrow (000)+2,(001)+2,(010)+1,(100)+1,(101)+1,(110)\)
第一个式子显然是没有任何问题的，相当于是把所有区间操作的右端点都设置在了 \(i-1\) 的位置，就不会对 \(i\) 产生影响。类似的，第二个式子也是这样，从 \((101)\) 转移过来而不需多余操作的原因就是只将翻转操作的右端点设置在了 \(i-1\) 的位置。\((110)\) 转移方式类似。
-
\(a_i=b_i=0\)
可用状态为 \((000),(010),(101)\)。给出转移方式：
\((000)\leftarrow (000),(001),(010),(100),(101),(110)\)
\((010)\leftarrow (100)+1,(000)+1,(010),(001)+1,(101)+1,(110)\)
\((101)\leftarrow (000)+2,(001)+1,(010)+2,(100)+1,(101),(110)+1\)
原因与上面一致，就不做过多解释。
-
\(a_i=1,b_i=0\)
可用状态为 \((100),(010),(101)\)。
\((100)\leftarrow (000),(010)+1,(001)+1,(110),(101),(100)\)
\((010)\leftarrow (100)+1,(000)+1,(010),(001)+1,(101)+1,(110)\)
\((101)\leftarrow (000)+2,(001)+1,(010)+2,(100)+1,(101),(110)+1\)
-
\(a_i=0,b_i=1\)
可用状态为 \((100),(001),(110)\)。
\((100)\leftarrow (000),(010)+1,(001)+1,(110),(101),(100)\)
\((001)\leftarrow (100)+1,(000)+1,(010)+1,(001),(101),(110)+1\)
\((110)\leftarrow (000)+2,(001)+2,(010)+1,(100)+1,(101)+1,(110)\)
经过上述的分类讨论，我们会发现其实相同状态的转移方法是一样的，所以可以进行归纳一下：
-
\(b_i=1\)
可用状态为 \((001),(110)\)。
-
\(b_i=0\)
可用状态为 \((010),(101)\)。
-
\(a_i=b_i\)
可用状态为 \((000)\)。
-
\(a_i\neq b_i\)
可用状态为 \((100)\)。
代码实现的过程中，需要注意当前不可用的状态应该初始化为极大值 \(\inf\) 来防止对后续状态更新产生影响。初始值：\(f[0][0][0][0]=0\)。
其实推完了过后代码实现上基本没有什么问题了。为了代码的可读性，我用了一小点宏定义来使代码更加简洁。
完整代码（赛时）：
#include<bits/stdc++.h>
#define f(a, b, c, d) f[a][b][c][d]
#define g(a, b, c) f[i - 1][a][b][c]
using namespace std;
constexpr int _SIZE = 1e6;
int n, a[_SIZE + 5], b[_SIZE + 5];
char tempstr[_SIZE + 5];
int f[_SIZE + 5][2][2][2];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
cin >> (tempstr + 1);
for (int i = 1; i <= n; i++) a[i] = (tempstr[i] == '1');
cin >> (tempstr + 1);
for (int i = 1; i <= n; i++) b[i] = (tempstr[i] == '1');
memset(f, 0x3f, sizeof f);
f(0, 0, 0, 0) = 0;
for (int i = 1; i <= n; i++) {
if (b[i] == 1) {
f(i, 0, 0, 1) = min({g(1, 0, 0) + 1, g(0, 0, 0) + 1, g(0, 1, 0) + 1, g(0, 0, 1), g(1, 0, 1), g(1, 1, 0) + 1});
f(i, 1, 1, 0) = min({g(0, 0, 0) + 2, g(0, 0, 1) + 2, g(0, 1, 0) + 1, g(1, 0, 0) + 1, g(1, 0, 1) + 1, g(1, 1, 0)});
}
if (b[i] == 0) {
f(i, 0, 1, 0) = min({g(0, 0, 0) + 1, g(0, 1, 0), g(0, 0, 1) + 1, g(1, 0, 0) + 1, g(1, 0, 1) + 1, g(1, 1, 0)});
f(i, 1, 0, 1) = min({g(0, 0, 0) + 2, g(0, 1, 0) + 2, g(0, 0, 1) + 1, g(1, 0, 0) + 1, g(1, 1, 0) + 1, g(1, 0, 1)});
}
if (a[i] == b[i])
f(i, 0, 0, 0) = min({g(1, 0, 0), g(0, 1, 0), g(0, 0, 1), g(1, 0, 1), g(1, 1, 0), g(0, 0, 0)});
if (a[i] != b[i])
f(i, 1, 0, 0) = min({g(0, 0, 0) + 1, g(0, 1, 0) + 1, g(0, 0, 1) + 1, g(1, 0, 0), g(1, 1, 0), g(1, 0, 1)});
}
int ans = min({f(n, 0, 0, 0), f(n, 0, 0, 1), f(n, 0, 1, 0), f(n, 1, 0, 0), f(n, 1, 0, 1), f(n, 1, 1, 0)});
cout << ans << '\n';
return 0;
}
赛后发现每次 \(f[i]\) 的更新都只会和 \(f[i-1]\) 有关，也就是说可以使用滚动数组优化空间和时间常数。需要注意的是，滚动到新的状态的时候需要清空成 \(\inf\)，否则会对后续答案产生影响。
滚动数组优化代码：
#include<bits/stdc++.h>
#define f(a, b, c, d) f[a][b][c][d]
#define g(a, b, c) f[last][a][b][c]
using namespace std;
constexpr int _SIZE = 1e6;
int n, a[_SIZE + 5], b[_SIZE + 5];
char tempstr[_SIZE + 5];
int f[2][2][2][2];
int cur = 0, last = 1;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
cin >> (tempstr + 1);
for (int i = 1; i <= n; i++) a[i] = (tempstr[i] == '1');
cin >> (tempstr + 1);
for (int i = 1; i <= n; i++) b[i] = (tempstr[i] == '1');
memset(f, 0x3f, sizeof f);
f(cur, 0, 0, 0) = 0;
for (int i = 1; i <= n; i++) {
swap(cur, last); // 滚动
memset(f[cur], 0x3f, sizeof f[cur]); // 记得清空
if (b[i] == 1) {
f(cur, 0, 0, 1) = min({g(1, 0, 0) + 1, g(0, 0, 0) + 1, g(0, 1, 0) + 1, g(0, 0, 1), g(1, 0, 1), g(1, 1, 0) + 1});
f(cur, 1, 1, 0) = min({g(0, 0, 0) + 2, g(0, 0, 1) + 2, g(0, 1, 0) + 1, g(1, 0, 0) + 1, g(1, 0, 1) + 1, g(1, 1, 0)});
}
if (b[i] == 0) {
f(cur, 0, 1, 0) = min({g(0, 0, 0) + 1, g(0, 1, 0), g(0, 0, 1) + 1, g(1, 0, 0) + 1, g(1, 0, 1) + 1, g(1, 1, 0)});
f(cur, 1, 0, 1) = min({g(0, 0, 0) + 2, g(0, 1, 0) + 2, g(0, 0, 1) + 1, g(1, 0, 0) + 1, g(1, 1, 0) + 1, g(1, 0, 1)});
}
if (a[i] == b[i])
f(cur, 0, 0, 0) = min({g(1, 0, 0), g(0, 1, 0), g(0, 0, 1), g(1, 0, 1), g(1, 1, 0), g(0, 0, 0)});
if (a[i] != b[i])
f(cur, 1, 0, 0) = min({g(0, 0, 0) + 1, g(0, 1, 0) + 1, g(0, 0, 1) + 1, g(1, 0, 0), g(1, 1, 0), g(1, 0, 1)});
}
int ans = min({f(cur, 0, 0, 0), f(cur, 0, 0, 1), f(cur, 0, 1, 0), f(cur, 1, 0, 0), f(cur, 1, 0, 1), f(cur, 1, 1, 0)});
cout << ans << '\n';
return 0;
}
滚动数组优化过后， XFY 说对数组的下标进行一下状态压缩会不会再减短内存寻址的时间，所以我就再花了一小点时间写了一下，然后发现甚至负优化（逃。
滚动数组+状态压缩代码：
#include<bits/stdc++.h>
#define f(a, b, c, d) f[(a << 3) + (b << 2) + (c << 1) + d]
#define g(a, b, c) f[(last << 3) + (a << 2) + (b << 1) + c]
using namespace std;
constexpr int _SIZE = 1e6;
int n, a[_SIZE + 5], b[_SIZE + 5];
char tempstr[_SIZE + 5];
int f[16];
int cur = 0, last = 1;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
cin >> (tempstr + 1);
for (int i = 1; i <= n; i++) a[i] = (tempstr[i] == '1');
cin >> (tempstr + 1);
for (int i = 1; i <= n; i++) b[i] = (tempstr[i] == '1');
memset(f, 0x3f, sizeof f);
f(cur, 0, 0, 0) = 0;
for (int i = 1; i <= n; i++) {
swap(cur, last);
f(cur, 0, 0, 0) = f(cur, 0, 0, 1) = f(cur, 0, 1, 0) = 0x3f3f3f3f;
f(cur, 1, 0, 0) = f(cur, 1, 0, 1) = f(cur, 1, 1, 0) = 0x3f3f3f3f;
if (b[i] == 1) {
f(cur, 0, 0, 1) = min({g(1, 0, 0) + 1, g(0, 0, 0) + 1, g(0, 1, 0) + 1, g(0, 0, 1), g(1, 0, 1), g(1, 1, 0) + 1});
f(cur, 1, 1, 0) = min({g(0, 0, 0) + 2, g(0, 0, 1) + 2, g(0, 1, 0) + 1, g(1, 0, 0) + 1, g(1, 0, 1) + 1, g(1, 1, 0)});
}
if (b[i] == 0) {
f(cur, 0, 1, 0) = min({g(0, 0, 0) + 1, g(0, 1, 0), g(0, 0, 1) + 1, g(1, 0, 0) + 1, g(1, 0, 1) + 1, g(1, 1, 0)});
f(cur, 1, 0, 1) = min({g(0, 0, 0) + 2, g(0, 1, 0) + 2, g(0, 0, 1) + 1, g(1, 0, 0) + 1, g(1, 1, 0) + 1, g(1, 0, 1)});
}
if (a[i] == b[i])
f(cur, 0, 0, 0) = min({g(1, 0, 0), g(0, 1, 0), g(0, 0, 1), g(1, 0, 1), g(1, 1, 0), g(0, 0, 0)});
if (a[i] != b[i])
f(cur, 1, 0, 0) = min({g(0, 0, 0) + 1, g(0, 1, 0) + 1, g(0, 0, 1) + 1, g(1, 0, 0), g(1, 1, 0), g(1, 0, 1)});
}
int ans = min({f(cur, 0, 0, 0), f(cur, 0, 0, 1), f(cur, 0, 1, 0), f(cur, 1, 0, 0), f(cur, 1, 0, 1), f(cur, 1, 1, 0)});
cout << ans << '\n';
return 0;
}
T3 递增
题目
初始给定一个递增序列 \(a_i\)，然后执行下面步骤若干次：
- 令 \(a'=a\)，并将 \(a\) 排序。
- 对 \(i=1\dots n-1\) 判断，若 \(a_i+1\neq a_{i+1}\)，将 \(\displaystyle\lfloor\frac{a_i+a_{i+1}}{2}\rfloor\) 添加到 \(a'\) 的末尾。
- 若 \(a'=a\) 结束，否则令 \(a=a'\) 并回到第一步。
问最终 \(a\) 序列的最长上升序列长度。
\(n\le 10^5, a_i\le 10^{18}\)
Solution
将样例模拟一下，会发现每次生成的序列都会是一个上升序列，也就是说可以先按照每次生成的顺序先将最终序列进行分组（或者说一组是一个块）。这里用样例来画一下。
\[\overbrace{1,5,9}^{\text{原序列}},\overbrace{3,7}^{\text{第一块}},\overbrace{2,4,6,8}^{\text{第二块}} \]会发现生成的块满足一个性质：设当前块编号为 \(i\)，那么当前块只要不是最后一块就一定满足块长为 \(2^i\)。这里因为样例的原数列是等距的，因此生成出来没有最后一块的散块。
此外还有另一个性质：最终数列的 \(\texttt{LIS}\) 一定是选择了每个块的首项或者是一整个块连接而成的。所以可以用类似链表的方式存储块，而对于原数列的处理就可以直接将每一个数作为单独的一个块处理即可。然后对最后的这个链表用 \(\texttt{BIT}\) 跑一遍 \(\texttt{LIS}\) 就行了。
代码上细节多的要死，而且不算很好理解，对着标程研究了一下午才勉强看明白。
#include<bits/stdc++.h>
using namespace std;
const int _SIZE = 1e5;
typedef long long ll;
int n;
vector<ll> a;
vector<int> nxt;
vector<pair<ll, ll>> b;
vector<ll> f;
ll c[_SIZE + 5];
void ins(int x, ll v) {
for (; x <= n; x += x & -x) c[x] = max(c[x], v);
}
ll ask(int x) {
ll res = 0;
for (; x; x -= x & -x) res = max(res, c[x]);
return res;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
b.push_back({i, 1}); // 原始序列中每一个数单独作一个块
nxt.push_back(-1); // 存储上一个块的编号
}
vector<int> last(n); // 临时存储上一个块的编号
for (int j = 0; j <= 62; j++) {
for (int i = 0; i + 1 < n; i++) {
ll x = min((1ll << j), a[i + 1] - a[i] - (1ll << j)); // 计算块长
if (x > 0) {
b.push_back({i, x}); // 块的首项和块长
nxt.push_back(-1); // 先设置为没有前导块
if (x < (1ll << j)) nxt[b.size() - 1] = last[i]; // 如果满的块就有前导块
last[i] = b.size() - 1; // 记录临时的块
}
}
}
f.resize(b.size()); // BIT 求 LIS
for (int i = 0; i < b.size(); i++) {
f[i] = ask(b[i].first);
if (i > n && nxt[i] == -1) nxt[i] = b[i].first; // 第一块和最后一块
if (nxt[i] >= 0) f[i] = max(f[i], f[nxt[i]] - b[nxt[i]].second + 1); // 从前一块的首项转移过来
f[i] += b[i].second; // 当前块取整块
if (nxt[i] >= 0) f[i] = max(f[i], f[nxt[i]] + 1); // 前一块是整块，当前块只取首项
ins(b[i].first + 1, f[i]); // 加入 BIT
}
cout << ask(n) << '\n';
return 0;
}
T4 不会，以后随缘填坑。