打卡五月模拟题编程题(C++附前两题渣渣代码)
入场太慢,想起来的时候已经19:30了.
编程题写了前两道,发现第三题似乎是bfs裸题???
不要吐槽代码规范.
虽然第一题感觉用树状数组,第二题用dp也可以搞,但是我就是这么暴力.
1. 第一道就是一个容斥原理 (100%)
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int mt[1005][1005]{0};
int dp[1005][1005]{0};
int main() {
int n, m, x, y;
memset(mt, 0, sizeof(mt));
memset(dp, 0, sizeof(dp));
cin >> n;
while(n--) {
cin >> x >> y;
mt[x][y] = 1;
}
for(int i = 1; i <= 1000; ++i) {
for(int j = 1; j <= 1000; ++j) {
dp[i][j] += dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + mt[i][j];
}
}
// for(int i = 1; i < 4; ++i) {
// for(int j = 1; j < 4; ++j) {
// cout << mt[i][j] << " ";
// }
// cout << endl;
// }
// for(int i = 1; i < 4; ++i) {
// for(int j = 1; j < 4; ++j) {
// cout << dp[i][j] << " ";
// }
// cout << endl;
// }
cin >> m;
int x1, y1, x2, y2;
while(m--) {
cin >> x1 >> y1 >> x2 >> y2;
cout << dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1] << endl;
}
return 0;
}
/*
4
1 1
2 2
3 3
1 3
4
1 1 2 2
1 1 3 3
2 2 3 3
1 2 2 3
*/
2. 第二道题用贪心(100%)
按照单价递减排序,相同单价,优先选择数量多的.
然后顺序买就可以了,需要考虑可能剩下n个人,但是>n张票更便宜的情况.
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int main() {
int n, m, k;
int x, y;
vector<pii> vec;
cin >> n >> m >> k;
++ n;
vec.push_back(make_pair(1, k));
while(m--) {
cin >> x >> y;
vec.push_back(make_pair(y, x));
}
sort(vec.begin(), vec.end(), [](pii& a, pii& b){
double diff = a.second * 1.0 / a.first - b.second * 1.0 / b.first;
if(fabs(diff) < 1e-4) return a.first > b.first;
return diff < 0;
});
int ans = 0;
int min_cnt = 1 << 30;
for(auto v : vec) {
while(n >= v.first) {
n -= v.first;
ans += v.second;
}
if(n < v.first) {
min_cnt = min(min_cnt, ans + v.second);
}
}
cout << min(min_cnt, ans) << endl;
}
/*
2 2 5
6 2
13 3
*/ 3. 应该就是bfs最短路径,然后取最短的那个路口对应的路径吧?不知道题目有没看错. 
查看2道真题和解析