[总结]2017年3月23日的考试

在 一堆2B题 面前爆零辣。。

心路历程

由于最进做了一大堆数据结构的题,料定要考高级数据结构(flag)

发下卷子看到第一题觉得是一个很版的平衡树,然后想了一会。。发现可以直接用STL开一个set和multset水过(蛤蛤蛤蛤)
然后马上开始写。。写了一半发现我好想不会用STL…样例过不了,居然拿着STL搞了40分钟0.0还没调出来,醉了,十分钟写了个splay+multset好像过了样例就没管了。。(flag*1)

没事没事,我还有2h

第二题貌似是树套树的版,但是我第一秒傻傻的想到了离散化+线段树+splay(既然离散了第一维为何不顺便离散第二维好傻啊啊啊),然后受2B平衡树的心理阴影影响觉得不能这么做。。
然后想了十分钟,觉得好像可以离线之后莫队 O(N*logN*sqrt(N)) 貌似有点高但是能过(flag*2)
然后STL大法好,十几分钟就写完了,自己编了个比较弱的样例试了试过了

第三题。。好像又是树套树(蛤),但是内存好像过不了。于是我去问了一下神犇内存限制,神犇笑着对我说,这题内存原来是 128MB ,可以给你们放松到 256MB ,难道真的是线段树套线段树,但是又不需要修改。。(犯傻*3)用计算器算了一波内存发现好像还是不对。于是又看了一眼数据规模,发现 N<=250
哇！这不是暴力复杂度么,这题原来想复杂啦！
于是果断码了N^3的暴力,开两个intN^3数组刚好内存124MB卡过。
然后过了样例,好像样例有点弱但是这么简单的程序应该不会码错吧(flag*3)

搞好第三题,时间不是很够了,看了一眼第四题发现好像很难得样子(flag*4)肯定是个神奇代码题于是就没去想。
心里很忐忑,主要是因为第二题的复杂度,于是写了个数据生成器,果然！第二题的最大数据要跑30s才能跑完,完了完了爆了爆了,然后突然发现这题可以离散化+线段树套vector(终于反应过来离散化第二维了)哇塞那么好写只有20min了赶快码
然后。。。写挂了。。没抢救成功

但是第一题第三题都搞出来了,第二题这个复杂度还是能骗到分的吧。。(连插三个flag)

开始评测

第一题瞬间wa完
第二题怎么只有一个点???而且好像还是大数据100分!!!果断tle
第三题边wa边tle边re我一脸懵逼
愉快,真·爆零

事后

发现好像SunIsMe和Ender和Jeremyguo都A了第四题。。
(SunIsMe:第四题简单啊! Hineven:%*&^$&^$&…)
第一题忽略了一个细节。。具体是什么我后面再写
第三题读入优化打错+细节错误(蛤)具体见下文
神犇说这四道题都可以用线段树做。。想想好像还真的是！(感觉被欺骗QAQ)
满脑子高级数据结构果然是要出事的。。
JeremyGuo差点AK,%%%

题目以及解题报告

第一题

最近物理学家正在研究一些新的原子，称为X族。他们发现该族中的元素非常相近，但是其质量都不相同。质量越接近的越容易相互转化。现在，物理学家已经发明了一种设备，可以对X族的元素来进行以下三种操作：
1. generate M 产生质量为M的一个元素，如果已经存在，则该操作不产生作用。
2. romove M 销掉质量为M的元素，如果不存在质量为M的元素，则该操作不产生作用。
3. query 查询X族中质量最接近的两种元素的质量差的绝对值。如果此时X族中的元素个数小于2，则输出-1.
现在，请你写一个程序来模拟该设备的操作。
N条指令,N和M是正整数，都不超过100000.

解题报告

线段树做法: 离散化都不用,直接插入删除维护懒标记就可以了
考场上的做法: 用平衡树维护点权,用multset维护两两距离,每次插入点时查找前驱后继,在multset中更新一下(删除一次插入两次),其他操作类似,query输出multset最小值即可
果然相比线段树,太复杂了
考试时忽略了插入时需要在multset中删除被分开的两个点的距离,样例(自己)太弱没发现,于是就wa完了。。 还是要自己写测试数据啊。。
代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
const int MAXD = 110000;
namespace splay {
    struct Node {
        int ch[2], fa, val;
    } d[MAXD]; int dtot, root;
    inline void clear() {dtot = 0, root = 0;}
    inline int newNode (int val) {
        memset(d+(++dtot), 0, sizeof d[0]);
        d[dtot].val = val;
        return dtot;
    }
    inline void rotate (int x) {
        int y = d[x].fa;
        bool f = (d[y].ch[1] == x);
        d[y].ch[f] = d[x].ch[!f];
        d[d[y].ch[f]].fa = y;
        d[x].ch[!f] = y;
        d[x].fa = d[y].fa;
        d[y].fa = x;
        if(d[x].fa) d[d[x].fa].ch[d[d[x].fa].ch[1] == y] = x;
    }
    inline void splay (int x, int g = 0) {
        while(d[x].fa != g) {
            int y = d[x].fa, z = d[y].fa;
            if(z && z != g) {
                if((d[z].ch[1] == y) == (d[y].ch[1] == x))
                    rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
        if(g == 0) root = x;
    }
    inline int insert (int val) {
        int u = root, l = 0;
        while(u) {
            if(d[u].val == val) return 0;
            l = u;
            u = d[u].ch[d[u].val < val];
        }
        u = newNode(val);
        if(l) d[l].ch[d[l].val < val] = u;
        else root = u;
        d[u].fa = l;
        splay(u);
        return u;
    }
    inline void erase (int u) {
        while(d[u].ch[0] || d[u].ch[1])
            if(d[u].ch[0]) rotate(d[u].ch[0]);
            else rotate(d[u].ch[1]);
        d[d[u].fa].ch[d[d[u].fa].ch[1] == u] = 0;
        splay(d[u].fa);
    }
    inline int locate (int val) {
        int u = root;
        while(u) {
            if(d[u].val == val) break;
            u = d[u].ch[d[u].val < val];
        }
        return u;
    }
    inline int getNextVal (int pos, bool flg) {
        splay(pos);
        if(!(d[pos].ch[flg])) return 0;
        pos = d[pos].ch[flg];
        while(d[pos].ch[!flg]) pos = d[pos].ch[!flg];
        return d[pos].val;
    }
}
#include <set>
using namespace std;
multiset<int> ans;
int main () {
    //freopen("atomic.in", "r", stdin);
    //freopen("atomic.out", "w", stdout);
    int cas;
    scanf("%d", &cas);
    while(cas --) {
        splay :: clear();
        splay :: insert(-99999999);
        splay :: insert(99999999);
        ans.clear();
        ans.insert(99999999*2);
        int N, cnt = 0;
        scanf("%d", &N);
        for(int i = 1; i<=N; i++) {
            char cmd[30]; int a, pos;
            scanf("%s", cmd);
            if(cmd[0] == 'g') {
                scanf("%d", &a);
                if(!(pos=splay :: insert(a))) continue;
                cnt ++;
                int lef = a-splay :: getNextVal(pos, 0);
                int rig = splay :: getNextVal(pos, 1)-a;
                ans.erase(ans.find(lef+rig));
                ans.insert(lef);
                ans.insert(rig);
            }
            if(cmd[0] == 'r') {
                scanf("%d", &a);
                int pos = splay::locate(a);
                if(!pos) continue ;
                cnt --;
                int lef = a-splay :: getNextVal(pos, 0);
                int rig = splay :: getNextVal(pos, 1)-a;
                ans.erase(ans.find(lef));
                ans.erase(ans.find(rig));
                ans.insert(lef+rig);
                splay::erase(pos);
            }
            if(cmd[0] == 'q') {
                if(cnt < 2) {puts("-1"); continue;}
                printf("%d\n", *(ans.begin()));
            }
            //printf("cnt:%d\n", cnt);
        }
        puts("");
    }
}

第二题

给出球星们的能力值、年份、名字，有很多个查询，每个查询给出一个年份的范围，求出这个范围里能力值从高到低排列的前11名球员，如果能力值相同则按年份从低到高排，如果年份仍然相同，则按名字的字典序排。如果不足11个球员，就用XXX代替输出凑够11行。
输的所有数入在10^9内,N小于等于50000。

解题报告

正解:离散化后线段树,每个节点保存一个vector表示年龄在这个区间的球员,预处理排序每个vector,查询有序合并区间内节点的vector,保留11个最好的就可以了。
爆掉的莫队:离线询问,离散化询问年龄,对询问进行分块排序,然后用一个set维护当前年份内的球星,然后。。。开始暴力。。。
得认真看题啊。。题目有很多的性质都没用上。
代码略。

第三题

给一个边长小于等于250的数字矩阵和数字K,10^6个询问,给`(x,y)`回答以这个点为右上角的边长为K的矩阵内最大值和最小值的差
### 解题报告
N^3预处理出每个点位右上角的边长为K矩阵最大值和最小值,开四个辅助数组就可以了
如果滚动数组可以空间降到N^2(但是N^3也能卡过就没降)
JeremyGuo用的很优秀的倍增算法,时间`O(N^2logN)`,询问`O(1)`，思路差不多只是预处理时倍增一下,由于询问时正方形不是长方形不会被卡(写到这里时他跑过来说用`O(N^2log^2N)`预处理就可以处理长方形辣,好像是的。。无尽膜拜)。
考试时读入优化写错了。。读入长度超过1的数就会爆。。然而样例的数字长度全是1。。@&\*\*%#\*&^%&。。。
发现除了读入优化写错还有个错误,在代码中给出了
循环范围注意想清楚啊。。
暴力N^3代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using std :: max;
using std :: min;
const int MAXN = 252;
int h[MAXN][MAXN];
int mxrow[MAXN][MAXN];
int mxcol[MAXN][MAXN];
int mnrow[MAXN][MAXN];
int mncol[MAXN][MAXN];
int mxmat[MAXN][MAXN][MAXN];
int mnmat[MAXN][MAXN][MAXN];
int main () {
    int N, T, M;
    scanf("%d%d%d", &N, &T, &M);
    for(int i = 1; i<=N; i++)
        for(int j = 1; j<=N; j++)
            scanf("%d", &h[i][j]);
    for(int i = 1; i<=N; i++)
        for(int j = 1; j<=N; j++) {
            mxmat[i][j][0] = mnmat[i][j][0] = h[i][j];
            mxrow[i][j]    = mnrow[i][j]    = h[i][j];
            mxcol[i][j]    = mncol[i][j]    = h[i][j];
        }
    for(int k = 1; k<T; k++) {
        for(int i = 1; i<=N; i++)
            for(int j = 1; j+k<=N; j++) {
                mxrow[i][j] = max(mxrow[i][j], h[i][j+k]);
                mnrow[i][j] = min(mnrow[i][j], h[i][j+k]);
            }
        for(int i = 1; i+k<=N; i++)
            for(int j = 1; j<=N; j++) {
                mncol[i][j] = min(mncol[i][j], h[i+k][j]);
                mxcol[i][j] = max(mxcol[i][j], h[i+k][j]);
            }
        for(int i = 1; i+k<=N; i++)
            for(int j = 1; j+k<=N; j++) {
                mxmat[i][j][k] = max(mxmat[i][j][k-1], mxrow[i+k][j]);
                mxmat[i][j][k] = max(mxmat[i][j][k], mxcol[i][j+k]);
                mnmat[i][j][k] = min(mnmat[i][j][k-1], mnrow[i+k][j]);
                mnmat[i][j][k] = min(mnmat[i][j][k], mncol[i][j+k]);
            }
    }
    for(int i = 1; i<=M; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", mxmat[x][y][T-1] - mnmat[x][y][T-1]);
    }
} 

第四题

Mirko的披萨店在镇上很受欢迎，每个人都把披萨作为午餐。Mirko提供外送服务，他的送货速度非常快，所以送货的时间可以忽略不计。镇上每个人都有自己最喜欢的口味，所以，Mirko给每个人做的披萨需要不同的时间。他只有一个小烤炉，每次只能烤一个披萨。如果他给某个人的披萨早于那个人的午餐时间k个时间单位，那么他可以收到k单位的小费，反之，如果晚于客户的午餐时间k个时间单位，那么他将损失k单位的钱。所以，Mirko需要提前安排好每个披萨制作的次序，以保证他的小费尽量多。每个客户的午餐时间是确定的，他的披萨需要花多少时间做好也是确定的。但是，可能客户会有所改变，一旦改变，那么mirko可能需要调整他的计划。Mirko从时刻0开始制作披萨。 问:Mirko能获得的最多的小费。

解题报告

很简单的题目。。
发现小费=所有用户的用餐时刻-Mirko制作每个披萨的时间(包括炉子被占用的时间)和
贪心地最小化上面等式右边的披萨制作时间和(在后文中,这个值会被叫做R),肯定需要时间最短的披萨排在前面
接下来考虑改变操作
吧改变拆分成删除和插入
那么删除一个披萨会让R减少一下量: 这个披萨的制作时间 + 制作这个披萨之前过去的时间 + 排在这个披萨后面制作的披萨数量 \* 这个披萨的制作时间
插入操作类似,不再赘述
用两个树状数组维护排名和制作单个披萨之前过去的时间就可以搞搞搞辣

代码很好写也很短:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
inline int lowbit (int a) {return a & -a;}
template <int SIZE, class T> struct BinaryArr {
    T c[SIZE];
    void add (int p, T v) {while(p < SIZE) c[p] += v, p += lowbit(p);}
    T query(int p){T ret = 0; while(p) ret += c[p], p -= lowbit(p); return ret;}
    void addRev (int p, T v) {while(p) c[p] += v, p -= lowbit(p);}
    T queryRev(int p){T ret = 0; while(p < SIZE) ret += c[p], p += lowbit(p); return ret;}
};
const int MAXN = 200100;
const int MAXL = 100100;
typedef long long LL;
BinaryArr<MAXL, LL> sumT, rkRev;
int inp[MAXN][2], mp[MAXN];
bool compMap (int a, int b) {return inp[a][1] < inp[b][1];}
int main () {
    int N, C;
    scanf("%d%d", &N, &C);
    for(int i = 1; i<=N; i++)
        scanf("%d%d", &inp[i][0], &inp[i][1]), mp[i] = i;
    std :: sort(mp+1, mp+N+1, compMap);
    LL total = 0, tmp = 0, now = 0;
    for(int i = 1; i<=N; i++) {
        int pos = mp[i];
        total += inp[pos][0];
        tmp += inp[pos][1], now += tmp;
        rkRev.addRev(inp[pos][1], 1);
        sumT.add(inp[pos][1], inp[pos][1]);
    }
    printf("%lld\n", total - now);
    for(int i = 1; i<=C; i++) {
        int id, L, T;
        scanf("%d%d%d", &id, &L, &T);
        now -= (LL)inp[id][1]*(LL)rkRev.queryRev(inp[id][1]+1);
        now -= sumT.query(inp[id][1]);
        sumT.add(inp[id][1], -inp[id][1]);
        sumT.add(T, T);
        rkRev.addRev(inp[id][1], -1);
        rkRev.addRev(T, 1);
        total -= inp[id][0], total += L;
        now += sumT.query(T);
        now += (LL)T*(LL)rkRev.queryRev(T+1);
        inp[id][0] = L, inp[id][1] = T;
        printf("%lld\n", total - now);
    }
}