传送门 https://codeforces.com/contest/1271
A. Suits
签到.
Code
B. Blocks
因为最终只有可能全为黑或全为白, 那么分两种情况进行翻转即可.
一开始只考虑了一种情况然后 FST 了... 话说, 如果我一开始考虑的是另一种情况进行翻转, 样例都过了, 那样的话就应该反应过来需要考虑两种情况了吧 = = 过题还是要看运气 hhh
- Code
- C. Shawarma Tent
题意:
给出一个点 \((s_x,s_y)\), 再给出 \(n\) 个点 \((x_i,y_i)\).
现在找到一个点 \((x_0,y_0)\), 使得 \(cnt\) 最大. 每当有一个点 \((x_i,y_i)\) 到点 \((s_x,s_y)\) 的最短曼哈顿距离经过 \((x_0,y_0)\) 时,\(cnt\)++.
最后输出 \(cnt\) 和 \((x_0,y_0)\).
思路:
显然, 所有最短曼哈顿路径必然存在于一个矩形之内.
那么我们直接将所有以 \((s_x,s_y),(x_i,y_i)\) 为顶点的矩形画出来即可发现最优位置只可能存在于 \((s_x,s_y)\) 的四个方向上.
所以直接统计在哪个方向上最优即可.
Code
D. Portals
题意:
现在有 \(n\) 个堡垒, 要从 \(1\) 到 \(n\) 逐个攻破.
起初带有 \(k\) 个士兵, 每占领一个堡垒需要 \(a_i\) 的士兵, 可以在每座堡垒中招募 \(b_i\) 的士兵.
在占领堡垒的过程中不会发生伤亡. 每座堡垒有一个价值 \(c_i\), 若派遣一个士兵去防守, 那么可以获得 \(c_i\) 的价值.
防守的方式有两种:
占领一座堡垒之后可以就留下一名士兵;
图中存在某些单向通道 \(u\rightarrow v,u>v\), 当你在 \(u\) 时可以派遣一名士兵前往 \(v\)(每名士兵只能穿越通道最多一次).
现在问能否占领所有的堡垒, 若能, 最大能获得多少的价值.
思路:
这题初看是个模拟题, 仔细想其实不是个模拟题,... 带有一些 \(dp\) 的性质在里面.
首先有个观察:
如果我要防守 \(i\) 堡垒, 那么我肯定是在最后时刻派遣士兵过来最优.
正确性显然, 如果我们在较早时刻派遣士兵进行防守, 那么我们也可以将那个士兵留在后面再派遣.
那么图中现在只剩下最多 \(n\) 条边.
然后就考虑 \(dp:\) 令 \(dp[i][j]\) 表示当前在第 \(i\) 号堡垒, 带有 \(j\) 个士兵能获得的最大价值.
因为招募这个条件有点特殊, 我们不能就在 \(i\) 这个位置由 \(j\rightarrow j+b_i\) 转移, 所以可以考虑再加一维状态表示招募与否, 或者直接向 \(i+1\) 进行转移.
可以发现后者并不影响结果. 因为即便得到当前的答案, 后面也会继承当前的结果.
那么一种情况就是招募士兵:\(dp[i][j]\rightarrow dp[i+1][j+b_i]\);
另一种情况就是派遣士兵回防:\(dp[i+1][j]\rightarrow dp[i+1][j-1]\).
需要注意两个的顺序不能颠倒.
最终时间复杂度为 \(O(5000\cdot n+n)\).
- Code
- E. Common Number
题意:
定义函数 \(f(x):\)
\[ f(x)=\left\{ \begin{aligned} \frac{x}{2}, \ \ \ &if\ x\ is\ even\x-1 \ \ \ &otherwise \end{aligned} \right. \]
同时定义 \(path(x)\) 为 \(f(x),f(f(x)),\cdots\) 的所有值.
现在要找最大的一个 \(y\), 满足 \(1\)~\(n\) 中, 不少于 \(k\) 个数, 有 \(y\in path(x_i)\).
思路:
观察得到若最终答案 \(y\) 为奇数时, 合法的 \(x\) 为:\(y,\ \ 2\cdot y,2\cdot y+1,\ \ 2^2\cdot y,2^2\cdot y+1,2^2\cdot y+2,2^2\cdot y+3,\ \cdots\).
同样能找到答案为偶数时的序列.
那奇数情况举例, 若答案为奇数时, 那么最终个数为 \(1+2+4+\cdots\), 同时对应的数以 \(y\cdot 2^0,y\cdot 2^1,\cdots\) 为起点.
那么只需要找到最大的 \(r,2^r\leq n\), 再计算出总长度即可得到答案为某个奇数时满足条件的 \(x\) 个数.
显然问题具有单调性, 所以二分答案即可.
因为偶数的情况和奇数的情况有点小区别, 所以分奇偶两种情况二分, 最后取最大值即可.
- Code
来源: http://www.bubuko.com/infodetail-3334167.html