逐渐日更。然后弃更。
似乎这套题会比2018集合那套会简单一点。
A 题面
为了找到自己满意的工作,牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下,牛牛选择报酬最高的工作。在牛牛选定了自己的工作后,牛牛的小伙伴们来找牛牛帮忙选工作,牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了,于是他只好把这个任务交给了你。
题解 不知道其他人怎么做的,总感觉我做的有点麻烦。
首先定义$a[i]$代表能力值为$i$所能达到的最大报酬。有了数据就可以对这个数组进行赋值,然后再扫一遍数组使得$a[i]=\max\limits_{j=0}^{i-1}a[j]$。这样就可以知道每一个能力之所能达到的最大报酬了。
但很显然这样复杂度会很大,会达到$O(\max(\text{工作难度,小伙伴的能力值}))$。
但是很容易就会发现,这个数组中只会用到其中很少的下标值,所以进行一下离散化处理就ok了。
时间复杂度$O(n\log(n))$
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 #include <bits/stdc++.h> using namespace std ;typedef long long ll;void Main () ;int main () { ios::sync_with_stdio(false ), cin .tie(0 ), cout .tie(); Main(); return 0 ; } void Main () { int n, m; cin >> n >> m; vector <int > lsh; vector<pair<int, int>> v(n); for (int i = 0 ; i < n; i++) { int d, p; cin >> d >> p; lsh.push_back(d); v[i] = {d, p}; } vector <int > query (m) ; for (int i = 0 ; i < m; i++) { int q; cin >> q; lsh.push_back(q); query[i] = q; } sort(lsh.begin(), lsh.end()); lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end()); vector <int > mx (lsh.size(), 0 ) ; for (int i = 0 ; i < n; i++) { int id = lower_bound(lsh.begin(), lsh.end(), v[i].first) - lsh.begin(); mx[id] = max(mx[id], v[i].second); } int cm = 0 ; for (int i = 0 ; i < int (mx.size()); i++) { cm = max(cm, mx[i]); mx[i] = cm; } for (int i = 0 ; i < m; i++) { int id = lower_bound(lsh.begin(), lsh.end(), query[i]) - lsh.begin(); cout << mx[id] << '\n' ; } }
B 题面
小Q得到一个神奇的数列: 1, 12, 123,…12345678910,1234567891011…。 并且小Q对于能否被3整除这个性质很感兴趣。 小Q现在希望你能帮他计算一下从数列的第l个到第r个(包含端点)有多少个数可以被3整除。
题解 首先要知道一个性质:一个正整数如果他是3的倍数,那么他的各位数之和也是3的倍数。
我们只需要关心这个序列各位数之和是不是3的倍数即可。
假设$f(x)$是$x$的各位数之和对$3$取模的值,$g(x)$是这个序列的第x项各位数之和对$3$取模的值。
那么就有
$$ g(n)=(\sum\limits_{i=1}^{n}f(i))\bmod 3=f(\sum\limits_{i=1}^{n}i)=f(\frac{n\cdot(n+1)}{2}) $$
那么我们只需要关心$\frac{n\cdot(n+1)}{2}$是不是$3$的倍数即可。
很明显,当$n\equiv 1\pmod{3}$时这个数不是$3$的倍数,其余两种情况是。
那么问题就变成了 $l\le i\le r$ 内有多少个数不满足$i\equiv 1\pmod{3}$。
然后用前缀和的思想求区间$[1,r]$之间的数的情况减去区间$[1,l-1]$之间的结果即可。
不过非常神奇的是这题的数据好像有点诡异。
时间复杂度$O(1)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <bits/stdc++.h> using namespace std ;typedef long long ll;void Main () ;int main () { ios::sync_with_stdio(false ), cin .tie(0 ), cout .tie(); Main(); return 0 ; } int solve (int x) { return x - (x / 3 + (x % 3 >= 1 ? 1 : 0 )); } void Main () { int l, r; while (cin >> l >> r) { cout << solve(r) - solve(l - 1 ) << '\n' ; } }
C 题面
小Q正在给一条长度为n的道路设计路灯安置方案。 为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用’.’表示, 不需要照亮的障碍物格子用’X’表示。 小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。 小Q希望能安置尽量少的路灯照亮所有’.’区域, 希望你能帮他计算一下最少需要多少盏路灯。
题解 贪心的思想,从左到右如果当前的地没有照亮且需要照亮,那么把一盏灯放在这个位置的右边一格是省灯的。
时间复杂度$O(n)$
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 #include <bits/stdc++.h> using namespace std ;typedef long long ll;void Main () ;int main () { ios::sync_with_stdio(false ), cin .tie(0 ), cout .tie(); Main(); return 0 ; } void Main () { int T; cin >> T; while (T--) { int n; cin >> n; string s; cin >> s; vector <bool > ok (n + 2 , false ) ; int ans = 0 ; for (int i = 0 ; i < n; i++) { if (!ok[i] && s[i] == '.' ) { ans++; ok[i] = ok[i + 1 ] = ok[i + 2 ] = true ; } } cout << ans << '\n' ; } }
D 题面
牛牛去犇犇老师家补课,出门的时候面向北方,但是现在他迷路了。虽然他手里有一张地图,但是他需要知道自己面向哪个方向,请你帮帮他。
题解 模拟一下就可了。
设置北方向为$0$,往左转方向减一对$4$取模,往右转方向加一对$4$取模。
那么最终方向是$0$即北,最终方向是$1$即东,以此类推。
时间复杂度$O(n)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <bits/stdc++.h> using namespace std ;typedef long long ll;#define debug(...) do { } while(false) void Main () ;int main () { ios::sync_with_stdio(false ), cin .tie(0 ), cout .tie(); Main(); return 0 ; } const string str = "NESW" ; void Main () { int n; cin >> n; string s; cin >> s; int cur = 0 ; for (int i = 0 ; i < n; i++) { if (s[i] == 'L' ) cur = (cur + 3 ) % 4 ; else cur = (cur + 1 ) % 4 ; } cout << str[cur] << '\n' ; }
E 题面
牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。 但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。 牛牛希望你能帮他计算一共有多少个可能的数对。
题解 枚举$y$,然后$x$能取值的个数就可以$O(1)$求出。
看下能分出多少个连续的大小为$y$的块,每一个块的符合条件的$x$的个数是确定的,然后再讨论最后一个大小没有$y$这么大的块的个数即可。
我这里分开讨论$k=0$的情况,因为大概正常算会对结果有影响。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <bits/stdc++.h> using namespace std ;typedef long long ll;void Main () ;int main () { ios::sync_with_stdio(false ), cin .tie(0 ), cout .tie(); Main(); return 0 ; } void Main () { ll n, k; cin >> n >> k; if (k == 0 ) { cout << n * n << '\n' ; return ; } ll ans = 0 ; for (ll y = k + 1 ; y <= n; y++) { ll cur = n / y * k; ll q = min(n % y, k - 1 ); ans += n - cur - q; } cout << ans << '\n' ; }
F 题面
平面内有n个矩形, 第i个矩形的左下角坐标为(x1[i], y1[i]), 右上角坐标为(x2[i], y2[i])。 如果两个或者多个矩形有公共区域则认为它们是相互重叠的(不考虑边界和角落)。 请你计算出平面内重叠矩形数量最多的地方,有多少个矩形相互重叠。
题解 他这个题的点非常的奇葩(或许是我太奇葩)。我以为的点是一个1x1大小的块,结果WA了一下就发现不太对hh。
我的解决办法是将所有点坐标拉伸2倍,然后左下角的两个坐标值都加一,右上角的两个坐标值都减一。这样就是我平常想象的样子了。
然后显然,对结果有用的点只有两两矩形相交的矩形的四个角点。这样枚举所有这样的点大概会有$O(n^2)$个。
然后再枚举这些点,看一下这些点能在多少个矩形之中,取一个最大值即可。
时间复杂度$O(n^3)$
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 #include <bits/stdc++.h> using namespace std ;typedef long long ll;void Main () ;int main () { ios::sync_with_stdio(false ), cin .tie(0 ), cout .tie(); Main(); return 0 ; } struct jx { int x1, y1, x2, y2; }; void Main () { int n; cin >> n; vector <jx> v (n) ; vector <pair <int , int >> ps; for (int i = 0 ; i < n; i++) { cin >> v[i].x1; v[i].x1 <<= 1 ; v[i].x1++; } for (int i = 0 ; i < n; i++) { cin >> v[i].y1; v[i].y1 <<= 1 ; v[i].y1++; } for (int i = 0 ; i < n; i++) { cin >> v[i].x2; v[i].x2 <<= 1 ; v[i].x2--; } for (int i = 0 ; i < n; i++) { cin >> v[i].y2; v[i].y2 <<= 1 ; v[i].y2--; } for (int i = 0 ; i < n; i++) { for (int j = 0 ; j < n; j++) { const int X1 = max(v[i].x1, v[j].x1), Y1 = max(v[i].y1, v[j].y1); const int X2 = min(v[i].x2, v[j].x2), Y2 = min(v[i].y2, v[j].y2); if (X1 > X2 || Y1 > Y2) continue ; ps.push_back({X1, Y1}); ps.push_back({X1, Y2}); ps.push_back({X2, Y1}); ps.push_back({X2, Y2}); } } int ans = 0 ; for (int i = 0 ; i < int (ps.size()); i++) { int cnt = 0 ; const int x = ps[i].first, y = ps[i].second; for (int j = 0 ; j < n; j++) { if (v[j].x1 <= x && x <= v[j].x2 && v[j].y1 <= y && y <= v[j].y2) { cnt++; } } ans = max(ans, cnt); } cout << ans << '\n' ; }
G 题面
牛牛总是睡过头,所以他定了很多闹钟,只有在闹钟响的时候他才会醒过来并且决定起不起床。从他起床算起他需要X分钟到达教室,上课时间为当天的A时B分,请问他最晚可以什么时间起床
题解 这题的描述有点不太清楚啊。。我一直在想如果上课时间是在第二天怎么办。
然后顺着出题人应该想考的东西写了一个考虑内容非常不周全的代码,居然通过了。。。感觉没什么意思啊。
时间复杂度$O(n)$
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 #include <bits/stdc++.h> using namespace std ;typedef long long ll;void Main () ;int main () { ios::sync_with_stdio(false ), cin .tie(0 ), cout .tie(); Main(); return 0 ; } void Main () { int n; cin >> n; vector<pair<int, int>> v(n); for (int i = 0 ; i < n; i++) { cin >> v[i].first >> v[i].second; } sort(v.begin(), v.end()); int x; cin >> x; int a, b; cin >> a >> b; int ans = -1 ; for (int i = 0 ; i < n; i++) { int ta = v[i].first, tb = v[i].second; tb += x; ta += tb / 60 ; tb %= 60 ; if (a > ta || (a == ta && b >= tb)) { ans = i; } } cout << v[ans].first << " " << v[ans].second << '\n' ; }
H 题面
牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w。 牛牛家里一共有n袋零食, 第i袋零食体积为v[i]。 牛牛想知道在总体积不超过背包容量的情况下,他一共有多少种零食放法(总体积为0也算一种放法)。
题解 很显然的折半枚举。
枚举一半的零食的所有情况,对所有这些情况进行排序,方便后面的二分查找。
然后枚举另一半零食的所有情况,假设当前的枚举的总体积是$q$,那么需要找到前面一半零食的体积在$w-q$以下的总类数。
特判$n=1$能降低错误率。
时间复杂度$O(n\cdot 2^{\frac{n}{2}})$
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 #include <bits/stdc++.h> using namespace std ;typedef long long ll;void Main () ;int main () { ios::sync_with_stdio(false ), cin .tie(0 ), cout .tie(); Main(); return 0 ; } void Main () { int n, w; cin >> n >> w; vector <int > v (n) ; for (int i = 0 ; i < n; i++) { cin >> v[i]; } if (n == 1 ) { if (v[0 ] < w) cout << "2\n" ; else cout << "1\n" ; return ; } vector <int > vs; const int A = n >> 1 , B = n - (n >> 1 ); for (int i = 0 ; i < (1 << A); i++) { ll m = 0 ; for (int j = 0 ; j < A; j++) { if ((i >> j) & 1 ) { m += v[j]; } } if (m <= w) { vs.push_back(m); } } sort(vs.begin(), vs.end()); int ans = 0 ; for (int i = 0 ; i < (1 << B); i++) { ll cur = 0 ; for (int j = 0 ; j < B; j++) { if ((i >> j) & 1 ) { cur += v[j + A]; } } if (cur <= w) { ans += upper_bound(vs.begin(), vs.end(), int (w - cur)) - vs.begin(); } } cout << ans << '\n' ; }
最近 不知道做这些简单题到底有没有太大的意义。
为了做好面试的准备,背了一点操作系统和计网的知识,但一到面试就忘得差不多了233。可能是总感觉背这些内容意义不大,自己也做过一些不涉及利益的小项目,基本都没用过这些知识,也不知道未来的工作和这些到底有什么相关的。只会做题到底能不能拿到令人满意的offer呢?(腾讯wxg已挂)
疑惑。
回到开头