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 开了ll也不要忘记写lld
讲讲C题
题意:
有n位同学,分别来自不同的学校,有不同的编程水平,每个学校可以派出n个队,求当每个队人数为k时,每个学校派出的队伍的编程水平总和。
计算方式:
题解
//先总结
我原本写了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();}
}