第四周刷题小结

第一天

P1068 [NOIP2009 普及组] 分数线划定 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

这个题感觉不难，主要是用到了结构体cmp的自定义排序，但是还是错了一次，就是没注意到题目给的条件。

#include<iostream>
#include<algorithm>
using namespace std; 
struct node {int a;int b;
}k[5005];
bool cmp(const node q,const node w) {if (q.b == w.b) {return q.a < w.a;}return q.b > w.b;
}
int main() {int n, m;cin >> n >> m;for (int i = 0; i < n; i++) {cin >> k[i].a >> k[i].b;}int w = (m) * 1.5;sort(k, k+n, cmp);int flag = 0;for (int i = w; i < n; i++) {if (k[i].b == k[w - 1].b) {flag++;}else {break;}}cout << k[w - 1].b << ' ' << w + flag << endl;for (int i = 0; i < w+flag; i++) {cout << k[i].a << ' ' << k[i].b << endl;}
}

P1059 [NOIP2006 普及组] 明明的随机数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

一个简单的去重排序，可以直接写出来，用桶排，也可以用c++的去重排序。

#include<iostream>
#include<algorithm>
using namespace std; 
int main() {int n;cin >> n;int a[1000];for (int i = 0; i < n; i++) {cin >> a[i];}sort(a, a + n);  // 排序int m = unique(a, a + n) - a;cout << m << endl;for (int i = 0; i < m; i++) {cout << a[i] << ' ';}
}

第二天

P1376 [USACO05MAR] Yogurt factory 机器工厂 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

这个题用贪心。统计最小代价的变量要用long long。

#include<iostream>
#include<algorithm>
using namespace std; 
int main() {int n, m;long long ans = 0;int minPrice = 0;cin >> n >> m;for (int i = 0; i < n; i++) {int a, b;cin >> a >> b;if (i == 0) {minPrice = a;}else {if (a < minPrice + m) {minPrice = a;}else {minPrice += m;}}ans = minPrice * b + ans;}cout << ans;
}

第三天

P1536 村村通 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

用并查集，每组数据的f数组需要重新赋值，for循环里的下标应从1开始。

#include<iostream>
#include<algorithm>
using namespace std; 
int f[1005];
int getf(int x) {if (x == f[x]) {return x;}else {return f[x] = getf(f[x]);}
}
void merge(int x, int y) {int t1 = getf(x);int t2 = getf(y);f[t1] = t2;}
int main() {int n, m;while (scanf("%d", &n)) {if (n == 0) {break;}cin >> m;for (int i = 1; i <= n; i++) {f[i] = i;}for(int i=0;i<m;i++) {int a, b;cin >> a >> b;merge(a, b);}int ans = 0;for (int i = 1; i <=n; i++) {if (getf(i) == i) {ans++;}}cout << ans - 1 << endl;}
}

第四天

P9810 [CCC 2015 S1] Zero That Out - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

用到vector容器的简单方法

c.clear()         移除容器中所有数据。

c.empty()         判断容器是否为空。

c.erase(pos)        删除pos位置的数据

c.erase(beg,end) 删除[beg,end)区间的数据

c.front()         传回第一个数据。

c.insert(pos,elem)  在pos位置插入一个elem拷贝

c.pop_back()     删除最后一个数据。

c.push_back(elem) 在尾部加入一个数据。

c.resize(num)     重新设置该容器的大小

c.size()         回容器中实际数据的个数。

c.begin()           返回指向容器第一个元素的迭代器

c.end()             返回指向容器最后一个元素的迭代器

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {int n;cin >> n;vector<int> v;for (int i = 0; i < n; i++) {int a;cin >> a;if(a!=0)v.push_back(a);else {v.pop_back();}}int ans = 0;for (int i = 0; i < v.size(); i++) {ans = ans + v[i];}cout << ans << endl;
}

第五天

2.古堡之门：数字之和挑战 - 蓝桥云课 (lanqiao.cn)

思路：

这题要考虑最大值和最小值的限制，还有未longlong也会出错。 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {long long n, m, k;cin >> n >> m >> k;long long ans = 0,mint=0;for (long long i = n; i >= 1; i--) {if (m == 0) {break;}mint = n - i + 1 + mint;ans = ans + i;m--;}if (k <= ans&&mint<=k) {cout << "Yes";}else {cout << "No";}return 0;
}

第六天

P1060 [NOIP2006 普及组] 开心的金明 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

这是一个经典的01背包，我用而被的dp数组好像卡了一个数据点，换成优化后的一维dp数组才可以通过。

#include<iostream>
#include<algorithm>
using namespace std; 
int w[30005];
struct node {int a;int b;
}k[30005];
int main() {int p, n;cin >> p >> n;for (int i = 1; i <= n; i++) {cin >> k[i].a >> k[i].b;}for (int i = 1; i <= n; i++) {for (int j = p; j >=k[i].a; j--) {w[j] = max(w[j], w[j - k[i].a]+ k[i].a * k[i].b);}}cout << w[p];
}