BZOJ3333 排队计划
D1T2 排队计划Description:对于一个序列 $h$,有 $m$ 次操作,每次操作 $j$ ,将 $p_j\le i\le n$中,小于等于第 $h_j$ 的元素取出并重排后插入。求每次操作后的逆序对的数量。
Solution:一开始以为是个三维偏序
首先考虑暴力解法。对于每次询问重新求逆序对即可,预计时间复杂度为 $O(mnlogn)$ ,而且常数巨大。
然后考虑优化。可以观察到这次询问的答案可以从上一次的答案更新。易得对于每个取出的数 $h_i$ ,减少的逆序对的数量就是 $h_i$ 后比它小的数的个数。因为每次操作后序列都趋向有序,所以逆序对的数量会减少,单点暴力修改的时间复杂度是有保证的。
Code:1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798 ...
10.25 CSP-J模拟
总结难度不算特别大,但是我是傻逼
T1 一眼贪心
T2 无脑暴力
T3 毫无头绪
T4 写不出来
(没有押好韵)
T1 地鼠游戏题意: 有 $n$ 个物品 $a_i$,在 $t_i$ 秒之内选中 $a_i$ 个物品会获得 $v_i$ 的权值,求最大权值。
一眼贪心,跟那道 智力大冲浪 完全是一回事。把每个物品以 $v_i$ 为关键字排一遍顺序,然后枚举每一个 $a_i$ 找到一个时间点放进去,然后累加就完了。
然后我就写错了,特此贴出来警示自己。还没开 freopen(寄
123456789101112131415161718192021222324252627282930#include<bits/stdc++.h>using namespace std;struct ele{ int t,v; double p;}a[100005];bool cmp(ele a,ele b){ if(a.t==b.t) return a.v>b.v; return a.t<b.t;}int n,Time[5005],ans=0,cnt ...
10.22 CSP-J模拟
“这是一场难度约为 $CSP-J$ 的模拟赛”正确的,一针见血的。这么说我都不晓得当年怎么拿的2=(悲
T1 考场上想到了前缀和这么个鬼东西,也在考虑是不是该旋转矩阵,然后发现自己完全转不来,只能随手敲个 $O(n^2k)$ 的暴力前缀和,然后 $n \leq 400$ 的数据硬是越界了8个点。高低也算个黄题吧。
T2 只记得以前做过一道类似的,但是看到超级大的 $k$ 是在想不吃什么不超时的揭解法了,随手敲了个优先队列交上去准备骗点分。黄题水准罢。
T3 一眼线段树模板题,然后我用字符串操作写了30行的代码直接跑路,要不是那个数据太坑说不准还能骗点分。可能有个绿题。
T4 是真的没头绪,大概猜出来是个 $dp$ 但是完全不知道方程怎么推,然后完全没动(悲。绿到蓝吧。
T1 sum题意: 给定一个 $n * m$ 的矩阵,可以随意选一个点向上下左右走 $k$ 步,求取得的和的最大值。
solution:把矩阵旋转45度后利用前缀和求解。这个旋转的方法确实有点骚。
code1234567891011121314151617181920212223242526272829303132333 ...


