第一次打cf的比赛是教育轮，实在被教育了一顿，就过了一题，好好复盘一下。
A. ABC string
签到题，但我打了半小时就离谱。
关键就是，打头的字母一定对应“(”，结束的字母一定对应“)”
B. Berland Crossword
题面大概意思是在一个边长n正方形内，里面有n*n个正方形方格，在四个边界按要求的数量进行涂色，如果可以成功涂色出来就输出yes，反之输出no。
写的时候没有注意到四个角是解决问题的关键，就是说，如果造成涂色失败，都是因为在角的涂色影响了其他的边。那么就是说，只要我们处理完那些必定要涂角的边，再去看看每个边的中间部分要涂的格子数量有没有小于0，如果没有就是可以成功涂色。
官方给的解题思路是遍历16种四角涂色方案，在每一种方案下，根据要涂的角确定每一条边的中间部分要涂多少，若合法就是yes。
C. 1D Sokoban
这道题里面，一条线上有很多箱子，线上有若干特殊点，只能向前推，不能拉，也不能搬起箱子越过其他箱子，但可以推着若干堆叠的箱子前进。
一个关键是：正负两边是完全一样的一个问题，可用一种算法解决。还有一个关键：从初始阶段，将第一个箱子推到前面的第一个特殊点，不会让结果更坏。而且，从当前特殊点再推到下一个特殊点过程中产生的答案，均可以在推到某个特殊点时取得。
因此，可以得到一个朴素的算法，将第一个箱子推到每一个特殊点，然后计算重合的数量，取最大值即可。为了优化，可以先计算出sui 代表第i个箱子到最后一个箱子与特殊点重合的数量。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | #include <iostream>#include <algorithm>#include <vector>using namespace std;int t;int n, m;int calc(vector<int>& a, vector<int>& b){ int n = a.size(); int m = b.size(); vector<int> su(n + 1); int r = m - 1; for(int i = n - 1; i >= 0; i--){ su[i] = su[i + 1]; while(r >= 0 && a[i] < b[r]) r--; if(r >= 0 && a[i] == b[r]){ su[i]++; } } r = 0; int pile = 0; //一起被推动的箱子数量 int res = 0; for(int l = 0; l < m; l++){ while(pile < n && a[pile] < b[l] + pile) pile++; //来到一个特殊点，计算一起推动箱子数 while(r < m && b[r] - b[l] < pile) r++; //计算堆叠的箱子数覆盖了多少个特殊点 res = max(res, r - l + su[pile]); } return res;}int main(){ cin >> t; while(t--){ cin >> n >> m; vector<int> a(n), b(m); for(int i = 0; i < n; i++) cin >> a[i]; for(int i = 0; i < m; i++) cin >> b[i]; vector<int> al, bl, ar, br; for(int i = 0; i < n; i++){ if(a[i] > 0) ar.push_back(a[i]); else al.push_back(-a[i]); } for(int i = 0; i < m; i++){ if(b[i] > 0) br.push_back(b[i]); else bl.push_back(-b[i]); } reverse(al.begin(), al.end()); reverse(bl.begin(), bl.end()); cout << calc(al, bl) + calc(ar, br) << endl; } return 0;} |
