3.29CF

2023-09-25 5 0

3.29CF小结

Educational Codeforces Round 108 (Rated for Div. 2)

AB都是思维题目,我比较快的拿下来了

but我A题又双叒叕忘记看数据范围了,忘记开ll

导致我怀疑是不是我的推断错了,浪费了时间

一 定 要 看 数 据 范 围 , 不 然 就 保 险 一 点 开 l l \color{red} 一定要看数据范围,不然就保险一点开ll ll

开 了 l l 也 不 要 忘 记 写 l l d \color{red} 开了ll也不要忘记写lld lllld

讲讲C题

题意:

有n位同学,分别来自不同的学校,有不同的编程水平,每个学校可以派出n个队,求当每个队人数为k时,每个学校派出的队伍的编程水平总和。

计算方式:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5HWBoGuA-1619840111977)(C:\Users\53055\AppData\Roaming\Typora\typora-user-images\image-20210501111402944.png)]

题解

//先总结

我原本写了multiset,怎么可能不会T嘛,我把考虑的重点糊掉了

(还有multiset就无法在原数组上预处理了,抛弃抛弃

说到底是复杂度不会算,因为真正拉时间的是算答案tmp的时候,

我即使,排序了,每次减去,去遍历也会T

而且multiset的常数我不知道,每次insert之后都保证是有序的,那么每次排序(?)

怎么可能有vector插入完成最后排序一次快嘛

解法
贪心,如果某个学校要让某个人不去的话,那一定是贡献的最小的,那么排序后算一下后缀和

某个学校可能一个队伍都组不起起来,那么用 unordered_set<ll>res存可以组成队伍的学校下标,

要是组不起来,那就erase

(这样就保证不会每次遍历的

我还有一个优化,(虽然时间改变不大187ms到156ms的)就是当要求组队人数大于最大的学校的人数时,那一定输出0

还有下面MLE的部分(为什么报WA?)我赛时发现初始化一直拉到最满(n),是不会WA2的,

赛后将初始化写在前面也是改成n,时间竟然一模一样,哎

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int MAX = 2e5 + 10;
const int INF = 1e9 + 7;
vector<ll> a[MAX];
ll u[MAX];
ll s[MAX];int main() {int T;scanf("%d", &T);while (T--) {int n;scanf("%d", &n);ll maxx = -1;for (int i = 1; i <= n; i++) {scanf("%lld", &u[i]);maxx = max(maxx, u[i]);}//for (int i = 1; i <= maxx; i++) a[i].clear();//可能会MLE,srds显示的是wa/** 假设第一次maxx = 7在第7个有2e5个数据,* 然后第二次maxx = 6,只清空了前6个数据,假设在第6个有2e5个数据,* 。。。* vecotr会炸的*/for (int i = 1; i <= n; i++) {scanf("%lld", &s[i]);}for(int i = 1; i <= n; i++) {a[u[i]].push_back(s[i]);}ll poss = -1;for (int i = 1; i <= n; i++) {poss = max((ll) a[i].size(), poss);}unordered_set<ll>res;for (int i = 1; i <= maxx; i++) {sort(a[i].begin(), a[i].end());for (int j = a[i].size() - 2; j >= 0; j--) {a[i][j] += a[i][j + 1];}res.insert(i);}for (int i = 1; i <= poss; i++) {ll tmp = 0;vector<ll> jian;for (auto j : res) {ll pos = a[j].size() % (i);if (pos < a[j].size())tmp += a[j][pos];if(a[j].size() < i) jian.push_back(j);}for (auto x:jian) res.erase(x);printf("%lld ", tmp);}for (int i = poss + 1; i <= n; i++) {printf("0 ");}printf("\n");for (int i = 1; i <= maxx; i++) a[i].clear();}
}
代码编程
赞赏

相关文章

阿里云服务器添加安全组
前端选择器的简单介绍
变量、数据类型的简单介绍
和java初识
JavaScript对象以及初识面向对象
第三章 JavaScript操作和DOM对象