没注意到答案要求从小到大输出和读取数据的循环里把行和列搞反卡了一小下。比较简单。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void solve() {
int m, n, k, l, d;
cin >> m >> n >> k >> l >> d;
vector<int> rows(m);
vector<int> cols(n);
for (int i = 0; i < d; i++) {
int xi, yi, pi, qi;
cin >> xi >> yi >> pi >> qi;
if (xi == pi) {
cols[min(yi, qi)]++;
} else if (yi == qi) {
rows[min(xi, pi)]++;
}
}
priority_queue< pair<int, int> > pq_rows;
priority_queue< pair<int, int> > pq_cols;
for (int i = 1; i < m; i++) {
pq_rows.push({rows[i], i});
}
for (int i = 1; i < n; i++) {
pq_cols.push({cols[i], i});
}
priority_queue< int, vector<int>, greater<int> > pq_row_out;
priority_queue< int, vector<int>, greater<int> > pq_col_out;
pair<int, int> top;
for (int i = 0; i < k; i++) {
top = pq_rows.top();
pq_row_out.push(top.second);
pq_rows.pop();
}
for (int i = 0; i < l; i++) {
top = pq_cols.top();
pq_col_out.push(top.second);
pq_cols.pop();
}
int first;
first = pq_row_out.top();
cout << first;
pq_row_out.pop();
while (!pq_row_out.empty()) {
first = pq_row_out.top();
cout << " " << first;
pq_row_out.pop();
}
cout << endl;
first = pq_col_out.top();
cout << first;
pq_col_out.pop();
while (!pq_col_out.empty()) {
first = pq_col_out.top();
cout << " " << first;
pq_col_out.pop();
}
cout << endl;
}
int main() {
ios::sync_with_stdio(false);
solve();
return 0;
}
比较容易能想到广搜，然后发现重叠子问题，选用动态规划。
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
int dp[31][31]; // i times, j number of student, value number of methods
memset(dp, 0, 31 * 31 * sizeof (int));
dp[0][1] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (dp[i - 1][j] > 0) {
dp[i][(j + n - 2) % n + 1] += dp[i - 1][j];
dp[i][j % n + 1] += dp[i - 1][j];
}
}
}
cout << dp[m][1] << endl;
}
int main() {
ios::sync_with_stdio(false);
solve();
return 0;
}
m0rsun
May 28, 2024, 2:13am
23
OP 通宵了吗
OP 应该没通宵，python 也行吧，但是对 python 不太熟
画 3D ascii art，比较有意思，只要注意到遮挡关系之后按顺序画上去就行了
#include <iostream>
#include <vector>
using namespace std;
inline void draw_box_at(const int i, const int j, vector< vector<char> > &dest);
void solve() {
int m, n;
cin >> m >> n;
// canvas size
int k = 0;
int l = 4 * n + 1 + 2 * m;
vector< vector<int> > input(m, vector<int>(n));
for (int i = 0; i < m; i++) {
int highest_int_row = 0;
for (int j = 0; j < n; j++) {
cin >> input[i][j];
highest_int_row = max(highest_int_row, input[i][j]);
}
k = max(k, 3 * highest_int_row + 1 + 2 * (m - i));
}
// cout << k << " " << l << endl;
// draw from top to bottom, from right to left, and from front to back
vector< vector<char> > output(k, vector<char>(l, '.'));
for (int i = m - 1; i >= 0; i--) {
// cout << "i " << i << endl;
for (int j = n - 1; j >= 0; j--) {
// cout << "j " << j << endl;
for (int z = input[i][j]; z > 0; z--) {
// cout << "z " << z << endl;
draw_box_at((m - i - 1) * 2 + (z - 1) * 3, j * 4 + (m - i - 1) * 2, output);
}
}
}
for (int i = k - 1; i >= 0; i--) {
for (char c : output[i]) cout << c;
cout << endl;
}
}
void draw_box_at(const int x, const int y, vector< vector<char> > &dest) {
// row 0
if (dest[x][y] == '.') dest[x][y] = '+';
for (int i = 1; i <= 3; i++) {
if (dest[x][y + i] == '.') dest[x][y + i] = '-';
}
if (dest[x][y + 4] == '.') dest[x][y + 4] = '+';
// row 1
if (dest[x + 1][y] == '.') dest[x + 1][y] = '|';
for (int i = 1; i <= 3; i++) {
if (dest[x + 1][y + i] == '.') dest[x + 1][y + i] = ' ';
}
if (dest[x + 1][y + 4] == '.') dest[x + 1][y + 4] = '|';
if (dest[x + 1][y + 5] == '.') dest[x + 1][y + 5] = '/';
// row 2
if (dest[x + 2][y] == '.') dest[x + 2][y] = '|';
for (int i = 1; i <= 3; i++) {
if (dest[x + 2][y + i] == '.') dest[x + 2][y + i] = ' ';
}
if (dest[x + 2][y + 4] == '.') dest[x + 2][y + 4] = '|';
if (dest[x + 2][y + 5] == '.') dest[x + 2][y + 5] = ' ';
if (dest[x + 2][y + 6] == '.') dest[x + 2][y + 6] = '+';
// row 3
if (dest[x + 3][y] == '.') dest[x + 3][y] = '+';
for (int i = 1; i <= 3; i++) {
if (dest[x + 3][y + i] == '.') dest[x + 3][y + i] = '-';
}
if (dest[x + 3][y + 4] == '.') dest[x + 3][y + 4] = '+';
if (dest[x + 3][y + 5] == '.') dest[x + 3][y + 5] = ' ';
if (dest[x + 3][y + 6] == '.') dest[x + 3][y + 6] = '|';
// row 4
if (dest[x + 4][y + 1] == '.') dest[x + 4][y + 1] = '/';
for (int i = 2; i <= 4; i++) {
if (dest[x + 4][y + i] == '.') dest[x + 4][y + i] = ' ';
}
if (dest[x + 4][y + 5] == '.') dest[x + 4][y + 5] = '/';
if (dest[x + 4][y + 6] == '.') dest[x + 4][y + 6] = '|';
// row 5
if (dest[x + 5][y + 2] == '.') dest[x + 5][y + 2] = '+';
for (int i = 3; i <= 5; i++) {
if (dest[x + 5][y + i] == '.') dest[x + 5][y + i] = '-';
}
if (dest[x + 5][y + 6] == '.') dest[x + 5][y + 6] = '+';
}
int main() {
ios::sync_with_stdio(false);
solve();
return 0;
}
......+---+---+...+---+
..+---+ / /|../ /|
./ /|-+---+ |.+---+ |
+---+ |/ /| +-| | +
| | +---+ |/+---+ |/|
| |/ /| +/ /|-+ |
+---+---+ |/+---+ |/| +
| | | +-| | + |/.
| | |/ | |/| +..
+---+---+---+---+ |/...
| | | | | +....
| | | | |/.....
+---+---+---+---+......
比较早期的题目，现在可能不会出这种了，越来越偏向数学
排列组合题，让找下一个排列。只要找到下一个序号就行了。
测试文件的换行是 CRLF，代码里只用了一个 cin.get() 来丢掉换行导致第一次提交全爆。
#include <iostream>
#include <vector>
using namespace std;
void solve() {
int s, t, w;
cin >> s >> t >> w;
// discard '\r' if on windows!
// cin.get();
// discard '\n'
cin.get();
vector<int> input(w);
for (int i = 0; i < w; i++) {
input[i] = cin.get() - 'a' + 1;
}
// index 0, 1, 2, 3, 4
// bdfij -> 2, 4, 6, 9, 10
// max 6, 7, 8, 9, 10
for (int i = 0; i < 5; i++) {
// find last number less than max
int j = w - 1;
while (input[j] == t - w + 1 + j) j--;
if (j < 0) return;
input[j]++; // increment
// rearrange all numbers after it
for (j++; j < w; j++) {
input[j] = input[j - 1] + 1;
}
// output result
for (int num : input) {
cout << char(num - 1 + 'a');
}
cout << endl;
}
}
int main() {
ios::sync_with_stdio(false);
solve();
return 0;
}
虽然没过，但好在没有 WA，说明 coding 能力提升了
1 Like
#include <iostream>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const string yes = "Yes";
const string no = "No";
void solve() {
ll m, s, t;
cin >> m >> s >> t;
auto one = new map<ll, ll>;
auto other = new map<ll, ll>;
one->insert({ m, 0 });
for (int time = 1; time <= t; time++) {
for (auto &pair : *one) {
// run on foot
if (other->find(pair.first) == other->end() || (*other)[pair.first] < pair.second + 17) {
(*other)[pair.first] = pair.second + 17;
if ((*other)[pair.first] >= s) {
cout << yes << endl;
cout << time << endl;
delete one;
delete other;
return;
}
}
// use magic
if (pair.first >= 10 && (other->find(pair.first - 10) == other->end() || (*other)[pair.first - 10] < pair.second + 60)) {
(*other)[pair.first - 10] = pair.second + 60;
if ((*other)[pair.first - 10] >= s) {
cout << yes << endl;
cout << time << endl;
delete one;
delete other;
return;
}
}
// recover magic
if (other->find(pair.first + 4) == other->end() || (*other)[pair.first + 4] < pair.second) {
(*other)[pair.first + 4] = pair.second;
}
}
delete one;
one = other;
other = new map<ll, ll>;
}
ll max_dist = 0;
for (auto &pair : *one) {
max_dist = max(max_dist, pair.second);
}
cout << no << endl;
cout << max_dist << endl;
}
int main() {
ios::sync_with_stdio(false);
solve();
return 0;
}
由于拿 map 存的 dp 信息，复杂度应该是 \sim TM log{M} ，其中 1 \le T \le 3 \times 10^5, 0 \le M \le 10^3 。如果能把复杂度降低到 \sim TM 就好了。
但是需要考虑用什么存储来实现高效查询。
虽然 TLE 了，但 256 mb 空间就用了 2 mb，得想办法 trade-off 一下
1 Like
大受震撼
如果能证明出最多恢复一次的话，那确实就不用规划什么了，先用完所有的魔法，剩下的全用跑的
1 Like
初始魔力值、需要几次休息能获得一次魔法、相对速度、使用后变化为什么情况：
初始魔力值
需要几次休息可多获得一次魔法
相当于什么速度 (m/s)
使用后变成什么情况
X0
3
15
(X+1)2
X1
3
15
(X+1)3
X2
2
20
(X+1)0
X3
2
20
(X+1)1
X4
2
20
(X+1)2
X5
2
20
(X+1)3
X6
1
30
(X+1)0
X7
1
30
(X+1)1
X8
1
30
(X+1)2
X9
1
30
(X+1)3
由于步行速度是 17 m/s ，只要等效速度大于 17 这次魔法的积攒和使用就是有效的。
对于初始魔力为 X0, X1 的情况，如果选择恢复 n 次魔力（不是休息 n 次），等效速度为：
v = \begin{cases}
{60n \over {n \over 2} \times (4 + 3)} = 17.14 m/s, n = 2k\\
{60n \over {{n-1} \over 2} \times (4 + 3) + 4} \lt 17.14 m/s, n = 2k + 1
\end{cases}
对于初始魔力为 X2, X3 的情况，如果选择恢复 n 次魔力（不是休息 n 次），等效速度为：
v = \begin{cases}
{60n \over {n \over 2} \times (3 + 4)} = 17.14 m/s, n = 2k\\
{60n \over {{n-1} \over 2} \times (3 + 4) + 3} \lt 17.14 m/s, n = 2k + 1
\end{cases}
X4-X9 都会在一次蓄力 + 释放后转化到 X0-X3。
草，是不是证明失败了
没有找到这个人发的题解或证明，所以认为他在放屁
本题的贪心性质：能闪现的时候闪现一定比跑更快，如果闪了之后的总里程比跑的要快了，下一秒就在闪的基础上接着闪或跑，否则就在各自的基础上继续。
OP 一开始没用贪心的原因是觉得，闪了之后会消耗魔力，这样就影响了后续的选择。但是！其实每次消耗 10 点魔力的话，参考上面的表格，是不会影响下一次需要回复的魔力量的，所以是可以贪心。但是如果每次消耗的不是 10 的倍数的话就确实会产生影响了
#include <iostream>
using namespace std;
typedef long long ll;
const string yes = "Yes";
const string no = "No";
void solve() {
ll m, s, t;
cin >> m >> s >> t;
ll dist_run = 0, dist_magic = 0;
for (int now = 1; now <= t; now++) {
if (m >= 10) {
dist_magic += 60;
m -= 10;
} else {
m += 4;
}
dist_run = max(dist_magic, dist_run + 17);
if (dist_run >= s || dist_magic >= s) {
cout << yes << endl;
cout << now << endl;
return;
}
}
cout << no << endl;
cout << max(dist_run, dist_magic) << endl;
}
int main() {
ios::sync_with_stdio(false);
solve();
return 0;
}
算法导论上对 Huffman 编码的贪心性质的证明有点难懂，看了好久
大概看明白了。
greedy choice property 证的是如果每次选择最小的两个节点 merge 的话，最终的 cost 最小
optimal substructure property 证的是如果 merge 前不是 optimal 的，那么 merge 后的也一定不是 optimal
但是证明过程和用的语言有点绕，让我证肯定证不出来
1 Like
其实看证明是因为这道题的贪心一直没证出来，瞪了一天了。
现在是觉得只要每次 Alice 都选择当前表格中最大值的 cell 所在行就行，如果次大的 cell 在本行，那 Alice 就能赢。
但还没看出来是怎么判输
