网易2018春招笔试编程题参考代码
练习地址：https://www.nowcoder.com/test/9763997/summary
牛牛的闹钟
分析
对于每一个闹钟，计算x分钟后的时间，和上课时间进行比较，如果不超过上课时间，把闹钟时间和保存的答案进行比较，取最晚。
时间复杂度
O(n)
参考代码
#include <bits/stdc++.h>
using namespace std;
int h[105], m[105];
int main() {
int n, x;
int ans1 = 0, ans2 = 0, temp1, temp2;
int a, b;
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d%d", &h[i], &m[i]);
scanf("%d", &x);
scanf("%d%d", &a, &b);
for(int i = 0; i < n; i++) {
temp2 = m[i] + x;
temp1 = h[i] + temp2 / 60;
temp2 = temp2 % 60;
if(temp1 < a || (temp1 == a && temp2 <= b)) {
if(h[i] > ans1 || (h[i] == ans1 && m[i] > ans2)) {
ans1 = h[i];
ans2 = m[i];
}
}
}
printf("%d %d\n", ans1, ans2);
return 0;
}
迷路的牛牛
分析
统计一共向左和向右转了多少次，计算最后的方向相对于初始方向的差异，模拟即可。
时间复杂度
O(n)
参考代码
#include <bits/stdc++.h>
using namespace std;
char s[1005];
int main() {
int now = 0, n;
scanf("%d", &n);
scanf("%s", s);
for(int i = 0; i < n; i++) {
if(s[i] == 'L')
now--;
else
now++;
}
now = (now % 4 + 4) % 4;
if(now == 0)
printf("N\n");
else if(now == 1)
printf("E\n");
else if(now == 2)
printf("S\n");
else
printf("W\n");
return 0;
}
安置路灯
分析
贪心。
对于一个需要照亮的位置的右边一格放置一个路灯就好了。
时间复杂度
O(n)
参考代码
#include <bits/stdc++.h>
using namespace std;
int n;
char s[1005];
int main() {
int t;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
scanf("%s", s);
int ans = 0;
for(int i = 0; i < n; i++) {
if(s[i] == 'X') continue;
if(s[i] == '.') ans++;
i += 2;
}
printf("%d\n",ans);
}
return 0;
}
被3整除
分析
手算一下会发现规律。
三个数为一组,第一个数不能被3整除,另外两个可以被3整除。
于是把区间端点都移到某组的开端,记录移动过程中满足的数, 之后就可以通过(b - a) / 3 * 2快速计算。
时间复杂度
O(1)
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int l, r;
scanf("%d%d", &l, &r);
int cnt1 = 0, cnt2 = 0, cnt = 0;
if(l % 3 == 2 || l % 3 == 0) cnt++;
if(r % 3 == 2 || r % 3 == 0) cnt++;
while(l % 3 != 1) {
if(l % 3 == 2 || l % 3 == 0) cnt1++;
l--;
}
while(r % 3 != 1) {
if(r % 3 == 2 || r % 3 == 0) cnt2++;
r++;
}
cnt += (r - l) / 3 * 2;
printf("%d\n", cnt - cnt1 - cnt2);
return 0;
}
数对
分析
对于一个b, n范围内的数模b的序列应该是:
0,1,2,...,b-1, 0, 1, 2,..., b-1,...0,1,2,..n%b
前面部分是个循环节,所以可以通过(n / b) * max(0, b - k)计算。
后面部分是max(0, n % b - k + 1),
于是我们枚举合法的b计算就可以了。
k = 0的情况特判处理。
时间复杂度
O(n)
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
if(k == 0) cout << 1LL * n * n << endl;
else {
long long ans = 0;
for(int i = k + 1; i <= n; i++){
ans += (n / i) * (i - k);
if(n % i >= k) ans += n % i - k + 1;
}
cout << ans << endl;
}
return 0;
}
矩形重叠
分析
分别枚举所有的横纵坐标,挨着判断每个矩形是否符合条件，计数维护最大即可。
时间复杂度
O(n^3)
参考代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 50 + 5;
int X1[maxn], Y1[maxn];
int X2[maxn], Y2[maxn];
set<int> xx, yy;
int main() {
int n;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> X1[i];
xx.insert(X1[i]);
}
for(int i = 0; i < n; i++) {
cin >> Y1[i];
yy.insert(Y1[i]);
}
for(int i = 0; i < n; i++) {
cin >> X2[i];
xx.insert(X2[i]);
}
for(int i = 0; i < n; i++) {
cin >> Y2[i];
yy.insert(Y2[i]);
}
int ans = 0;
for(int x : xx) {
for(int y : yy) {
int cnt = 0;
for(int i = 0; i < n; i++) {
if(X1[i] <= x && Y1[i] <= y && X2[i] > x && Y2[i] > y) cnt++;
}
ans = max(ans, cnt);
}
}
cout << ans << endl;
return 0;
}
牛牛的背包问题
分析
容量太大,没办法dp。
看到物品数量是30,直接爆搜也不行。。
于是对半分成两部分枚举之后,二分计算贡献。
当然用个map来做个map版本的背包也是兹磁的吧？
时间复杂度
O(2^(n/2) * log(2^(n/2)))
参考代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL v[35];
vector<LL> val1, val2;
int n, w;
void calc(LL *item, int mx, vector<LL> &val){
for(int i = 0; i < mx; i++){
LL sum = 0;
for(int j = 0; j < 20; j++){
if(i & (1 << j)){
sum += item[j];
if(sum > w) break;
}
}
if(sum <= w) val.push_back(sum);
}
}
int main() {
val1.clear();
val2.clear();
scanf("%d%d", &n, &w);
for(int i = 0; i < n; i++) scanf("%lld", &v[i]);
calc(v, 1 << (n / 2), val1);
calc(&v[n - (n + 1) / 2], 1 << (n - n / 2), val2);
sort(val2.begin(), val2.end());
LL ans = 0;
for(int i = 0; i < val1.size(); i++){
ans += upper_bound(val2.begin(), val2.end(), w - val1[i]) - val2.begin();
}
printf("%lld\n", ans);
return 0;
}
牛牛找工作
分析
实际上对于每个难度的工作，只有报酬最高的那一种是可能成为答案的，剩下的都可以无视。
由于只有N项工作和M个小伙伴，最多只会出现N+M种难度(能力值)，所以可以把难度和能力值映射到不超过N+M个数上(std通过排序+map来完成)。
对这些难度(能力值)分别求出最高的报酬，再按i从小到大的顺序维护难度(能力值)不超过i的最大报酬。最后输出每个小伙伴对应的能力值以下的最高报酬即可。
时间复杂度
O((N+M)*log(N+M))
参考代码
#include <bits/stdc++.h>
using namespace std;
map<int,int> mp;
int cnt = 0;
int ans[200005];
int d[100005], p[100005];
int val[200005];
int a[100005];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%d%d", &d[i], &p[i]);
val[i] = d[i];
}
for(int i = 1; i <= m; i++) {
scanf("%d", &a[i]);
val[i + n] = a[i];
}
sort(val + 1, val + 1 + n + m);
for(int i = 1; i <= n + m; i++) {
if(val[i] != val[i - 1]) {
cnt++;
mp[val[i]] = cnt;
}
}
for(int i = 1; i <= n; i++) ans[mp[d[i]]] = max(ans[mp[d[i]]], p[i]);
for(int i = 2; i <= n + m; i++) ans[i] = max(ans[i], ans[i - 1]);
for(int i = 1; i <= m; i++)
printf("%d\n", ans[mp[a[i]]]);
return 0;
}#春招#