Nebius Welcome Round (Div. 1 + Div. 2) A~E
A. Lame King
题意
从 (0,0) 走到 (a,b) ，每秒的可选项有：
- 在原地等待 1 秒
- 向左走一步
- 向右走一步
- 向上走一步
- 向下走一步
连续的两秒不能选择同一选项，问至少需要几秒才能到达目标。
代码
void solve()
int a, b;
cin >> a >> b;
a = abs(a);
b = abs(b);
if(a > b) swap(a, b);
int ans = a * 2;
b -= a;
if(b == 0) cout << ans << '\n';
else cout << ans + b * 2 - 1 << '\n';
B. Vaccination
题意
已知 t_1,t_2,\cdots,t_n 天各有一个病人有疫苗需求。对于达到时间为 t 的病人，必须在第 t+w 天或之前使其接种疫苗。
每一包疫苗都是 k 人份的，保质期为 d 天。若第 t 天开始使用，则直到第 t+d 天还保持有效，但第 t+d+1 天则无效。
请给出最少需要的疫苗包数。
分析
采用贪心方法。在满足所有病人需求的情况下，尽可能晚地打开疫苗是明智选择。
因此策略为：
- 如果某一病人等待时间已经到达 w 天，且没有得到处理，此时必须打开一包疫苗，且是可选时间中的最晚时间。
即可得出答案。
代码
void solve()
int n, k, d, w;
cin >> n >> k >> d >> w;
int t[n+1];
for(int i=1;i<=n;i++) cin >> t[i];
int last = -1e9; // 上一次打开疫苗的时间
int ans = 0;
int num = 0; // 当前疫苗包的疫苗数量
for(int i=1;i<=n;i++)
if(t[i] <= last + d && num > 0)
// 如果可行, 使用当前疫苗包
num--;
continue;
num = k - 1;
ans ++;
last = t[i] + w;
cout << ans << '\n';
C. Pull Your Luck
题意
询问是否有 [1,p] 中的整数 f 使得 \frac{f(f+1)}{2}+x \equiv 0 \pmod n
3\le n\le 10^5 ，所有测试点中 n 的和不超过 2\times10^5 。
分析
可以采用枚举策略，最多只需要枚举到 2n 即可。这是因为
\frac{f(f+1)}{2}-\frac{(f+2n)(f+2n+1)}{2}\equiv \frac{4nf+2n^2+2n}{2}\equiv 0\pmod n
代码
void solve()
int n, x, p; cin >> n >> x >> p
;
for(int i=1;i<=min(2*n, p);i++)
if(((long long)i * (i+1) / 2 + x) % n == 0)
cout << "Yes\n";
return;
cout << "No\n";
D. Accommodation
题意
现有 n 层每层 m 个窗户的大型建筑。每个窗户要么是明亮的，要么是昏暗的。
其中，每间公寓要么是一居室，房间内有一个窗户，要么是两居室，房间内是同一层的连续两个窗户。每一层中，恰好有 \frac{m}{2} 个一居室和 \frac{m}{4} 个两居室。保证 m 是 4 的倍数。
对于一间公寓，只要其中有一个窗户是明亮的，则称这间公寓是明亮的。对于所有划分公寓的方法，求明亮的公寓的数量的最大值和最小值。
分析
各层之间是没有影响的，所以我们对于一层考虑。
最小值的求解方法比较容易，我们采取贪心方法。由于明亮的窗户数量是固定的，所有操作中，仅有以下操作能使得明亮的公寓数减少（占用更多明亮的窗户）。
- 选择连续的两个明亮的窗户，划分为一个两居室。
所以，可以从前到后枚举，尽可能多地划分这样的两居室。
最大值的求解采取类似的思路，我们需要减少将两个连续的明亮的窗户划分为一间公寓，换言之，在明亮的窗户数量固定的情况下，最大化仅包含 0 或 1 个明亮的窗户的公寓数量。
假设我们对窗户分成连续的若干段，使得每一段中都没有连续的两个连续的明亮的窗户存在，且每一段的长度分别为 l_1,l_2,\cdots,l_k ，则数量是 \min(\frac{m}{4},\sum_{i=1}^k\lfloor\frac{l_i}{2}\rfloor) 。我们尽可能地合并这些段，能最大化这个值。
代码
void solve()
int n, m; cin >> n >> m;
auto getminmax = [&](string s){
// 最小的情况
int u = m / 4;
int minv = 0, maxv = 0;
for(int i=0;i<s.length();)
if(s[i] == '1' && i+1 < s.length() && s[i+1] == '1' && u > 0)
i += 2;
u --;
minv ++;
minv += (s[i] == '1');
i++;
// 最大的情况
u = 0;
int num = 0;
for(int i=0;i<s.length();i++)
if(i+1 == s.length() || (s[i] == '1' && s[i+1] == '1'))
num ++;
u += num / 2;
num = 0;
num ++;
u = min(m/4, u);
maxv = count(s.begin(), s.end(), '1') - (m/4-u);
return (array<int, 2>){minv, maxv};
int X = 0, Y = 0;
for(int i=0;i<n;i++)
string s;
cin >> s;
auto [x, y] = getminmax(s);
X += x;
Y += y;
cout << X << " " << Y << '\n';
E. Routing
题意
有一个 n 点 m 边的无向图，边权均为 1 。
现在，对于每个结点 i ，你可以选择一个与其直接相连的点 v_i ，然后增加一条 i\to v_i 的边权为 0 的边。
问：是否能合理分配 v_i ，使得对于所有点对 (u, v) ，存在一条 u\to v 的路径，使得路径长度不超过 1 ，且除了最后一步以外的权值均为 0 。
分析
观察样例 1 ，可以发现其中一种构造方法是：
- 选取图中的一个环，且其他所有点都与环中的某个结点直接相连。
存在这样的构造方法，是题述问题有解的充分必要条件。充分性很好证明，所以接下来看必要性，即：
- 若所有环可能的环 C 都不满足以上性质，则没有其他合适的构造方法。
设新增加的 n 条（有向）边构成图 G ，则 G 中存在至少一个环。
考虑图 G 中的一个环 C ，设存在环外点 u 在原图中与 C 的任意结点都不直接相连，则环内的点 v 没有办法到达点 u （它们分配的边权 0 的边都在环上，而环与 u 不直接相连），所以，这一方案是不合理的。如果所有的环都不满足这一性质，则任意的方案都不合理，问题无解。
因此，我们只需要遍历图中的所有环，并逐一检查。考虑到 2\le n\le 20 ，复杂度应当与 2^n 有关——枚举环内的点，高效地判断能否构成环。
存在一种判定哈密顿环的动态规划方法。
设 dp_{i,j}=0/1 表示是否能从集合 i （用二进制 01 表示）中选取一个点 u ， u 能通过若干边，经过所有 i 中的点并以 j 作为最后一个点（不要求 j 直接可达 u 从而形成环）。这样，有状态转移方程：
- dp_{i+2^k,k}=dp_{i,j} ，若 dp_{i,j}=1 并且 j 与 k 直接相连。
为了后面输出方便，我们令 dp_{i,j} 在可行的情况下，表示 j 的前驱结点，否则设为 -1 。这样，稍作改动变为：
- dp_{i+2^k,k}=j ，若 dp_{i,j}\neq -1 并且 j 与 k 直接相连。
这样，写出代码如下：
for(int i = 1; i < (1 << n); i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
if(i & (1 << k)) continue;
if(dp[i][j] != -1 && adj[j][k]) { dp[i ^ (1 << k)][k] = j; }
不失一般性地，我们可以认为 i 中最小的结点是环的起始点，方便后续的判断。这样，循环稍有改动。
for(int k = __builtin_ctz(i) + 1; k < n; k++)
因此，只需要枚举集合 i 作为环，然后按照顺序：
- 判断是否其他点能直接与环中结点相连。
- 根据 dp 数组和邻接矩阵，判断是否构成环。
- 根据 dp 数组输出环。
代码实现如下。
void solve()
int n, m;
cin >> n >> m;
vector adj(n, vector< int >(n, 0));
vector dp((1 << n), vector(n, -1));
for(int i = 1; i <= m; i++)
int x, y;
cin >> x >> y;
x--;
y--;
adj[x][y] = adj[y][x] = 1;
for(int i = 0; i < n; i++)
// dp[i][j]: dp 从 i 中的某个点出发, 最终可以到达 j
dp[(1 << i)][i] = 0;
for(int i = 1; i < (1 << n); i++)
for(int j = 0; j < n; j++)
for(int k = __builtin_ctz(i) + 1; k < n; k++)
if(i & (1 << k)) continue;
if(dp[i][j] != -1 && adj[j][k]) { dp[i ^ (1 << k)][k] = j; }
for(int i = 1; i < pow(2, n); i++)
bitset< 20 > b(i);
vector< int > ans(n, 0);
if([&]() {
// 判断环外点能否直接连到环内点
for(int j = 0; j < n; j++)
if(b[j] == 1) continue;
bool flag = false;
for(int k = 0; k < n; k++)
if(b[k] == 1 && adj[j][k] == 1)
ans[j] = k;
flag = true;
break;
if(flag == false) return true;
return false;
continue;
// 可行
for(int j = 0; j < n; j++)
if(dp[i][j] != -1 && adj[j][__builtin_ctz(i)])
cout << "Yes\n";
// 从 i 开始
int start = __builtin_ctz(i), end = j, now = i;
while(start != end)
ans[dp[now][end]] = end;
int pre = dp[now][end];
now ^= (1 << end);
end = pre;
ans[j] = start;
for(auto it : ans) cout << it + 1 << " ";
return;