前言
\(12\) 月的第一场, 没有大样例
这次带了耳塞, 注意考试方法其实并不复杂, 先看题吧
带上耳塞, 终于舒服了
看题
\(\rm{T1}\)
结论题?
\(\rm{T2}\)
\(\rm{HS}\) 似乎讲过???
但是我忘了, 一会看能不能推一下
多半是找规律
\(\rm{T3}\)
性质题?
\(\rm{T4}\)
数据结构维护吧, 只能到时候在分析
时间 : \(1 \rm{h} \ 10 \rm{min} + 1 \rm{h} \ 20 \rm{min} + 1 \rm{h}\)
策略 : 能冲前两题就冲, 不行就用时间去后面拿分
正序开题
\(\rm{T1}\)
应该可以贪心, 掏样例出来手玩一下看看
注意到不管对于什么情况, 一定都是从最大的掏出来 \(k\) 个, 这样子最优
那么我们考虑怎么高效的维护最值或者找到性质直接做
直接用堆做是 \(\mathcal{O}(n ^ 2 \log n)\) 的, 只能通过 \(80 \%\) 的点, 甚至因为性质不确定可能变成 \(\mathcal{O}(n ^ 2 k \log n)\) 只能拿到 \(40 \%\) 也有可能
贪心策略一定不是最优的, 一定要更深入的分析才行, 但是贪心策略的正确性就在于每次更新后重新进行 \(k\) 的取, 这不好处理
时间上来讲, 这题只能打 \(80 \%\) 了
\(\rm{T2}\)
\(\rm{T1}\) 应该就是想复杂了, 应该不难, 所以再次大劣势
容易想到的是, 我们可以预处理出每种逆序对数对应的全排列的数量
怎么还是不好做呢, 一会打表找下规律
直接打出 \(20 \%\)
\(\rm{T3}\)
每个数都可以被四舍五入而来, 我们可以直接打出 \(20 \%\)
感觉像数位 \(\rm{dp}\) , 赛时没时间研究了, 暴力打了跑路
真的可以 数位 \(\rm{dp}\) , 如果早些来一定能做的, 至少能证伪
\(\rm{T4}\)
\(f(T, k)\) 还比较好求, 具体的, 从前往后贪心, 时间复杂度 \(\mathcal{O} (\lvert T \rvert k)\)
直接比较即可, \(20 \% \sim 40 \%\)
代码
剩下 \(1 \rm{h} \ 30 \rm{min}\)
正打
\(\rm{T1}\)
每次对于一个堆, 我们考虑取出前 \(k\) 大的数, 记录堆中最大值 \(max_h\) , 外面最小值 \(max_c\) , 全部减去 \(max_c - max_h + 1\) 之后把小于 \(max_h\) 的扔进去, 重复这个过程直到 $ >0 $ 的数小于 \(k\) 个
时间复杂度玄学, 看运气拿分
#include <bits/stdc++.h>
// #define FILE_IO
#define int long long
const int MAXN = 1e5 + 20;
int T;
int n, k;
int a[MAXN];
std::priority_queue<int> Q;
int NowChoice[MAXN];
int ChoiceNum = 0;
int Ans = 0;
void solve()
{
/*初始化*/
ChoiceNum = 0;
Ans = 0;
while (!Q.empty()) Q.pop();
/*加入堆*/
for (int i = 1; i <= n; i++) {
Q.push(a[i]);
}
while (1)
{
int maxh, minc;
bool endflag = false;
while (!Q.empty() && ChoiceNum < k) {
NowChoice[++ChoiceNum] = Q.top();
if (Q.top() == 0) endflag = true;
Q.pop();
}
if (endflag) {
printf("%lld\n", Ans);
return;
}
maxh = Q.top();
minc = NowChoice[ChoiceNum];
for (int i = 1; i <= ChoiceNum; i++) {
NowChoice[i] -= std::min(minc, minc - maxh + 1);
}
Ans += std::min(minc, minc - maxh + 1);
int NowChoiceNum = ChoiceNum;
for (int i = NowChoiceNum; i >= 1 && (NowChoice[i] < maxh || NowChoice[i] == 0); i--) {
Q.push(NowChoice[i]);
ChoiceNum--;
}
}
}
signed main()
{
#ifdef FILE_IO
freopen("group.in", "r", stdin);
freopen("group.out", "w", stdout);
#endif
scanf("%lld", &T);
while (T--)
{
scanf("%lld %lld", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
solve();
}
return 0;
}
\(\rm{T2}\)
打表玩一下, 顺便最后有时间看一下能不能找到规律
#include <bits/stdc++.h>
// #define FILE_IO
int n, k;
struct node
{
int a[20];
int calc()
{
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (a[j] > a[i]) ans++;
}
}
return ans;
}
friend bool operator < (node a, node b) {
int numa = a.calc(), numb = b.calc();
if (numa == numb) {
for (int i = 1; i <= n; i++) {
if (a.a[i] > b.a[i]) return false;
else if (a.a[i] < b.a[i]) return true;
}
} else {
return numa < numb;
}
}
} JZY[500];
void solve()
{
int cnt = 0;
int a[20];
for (int i = 1; i <= n; i++) {
a[i] = i;
}
do {
cnt++;
for (int i = 1; i <= n; i++)
JZY[cnt].a[i] = a[i];
} while (std::next_permutation(a + 1, a + n + 1));
std::sort(JZY + 1, JZY + cnt + 1);
for (int i = 1; i <= n; i++)
printf("%d ", JZY[k].a[i]);
}
int main()
{
#ifdef FILE_IO
freopen("permutation.in", "r", stdin);
freopen("permutation.out", "w", stdout);
#endif
scanf("%d %d", &n, &k);
if (n >= 20) {
long long LSY = 1;
for (int i = 1; i <= n; i++) LSY *= 1ll * i;
if (LSY == n) {
for (int i = 1; i <= n; i++) printf("%d ", n - i + 1);
} else {
for (int i = 1; i <= n; i++) printf("%d ", i);
}
} else {
solve();
}
return 0;
}
\(\rm{T3}\)
时间不够, 去打 \(\rm{T4}\)
\(\rm{T4}\)
总结
趋势, 每次打不完???
标签：20,赛时,int,max,T4,long,12.2,rm,CW From： https://www.cnblogs.com/YzaCsp/p/18582048