浅谈being $A$part $F$rom $O$i

也算是一个很可以接受的旅途了

总结

OI

在SS的两年里大抵是学到了一点虚无的东西, 所有的便是远离文化课的寂静与…放松, 也算是挺可以接受的.

$size=1$的单调队列中, 最后终于还是剩下了一点音乐和番剧, 应该是为数不多的值得接受的内容了.

这大概就是高中的OI生涯了, 也算是可以接受.

新的题倒也做了一点, $160+251+18$, 所以用$AND$并列起来还是相当于一事无成吧, 乍一想也挺能接受的.

大概也能达到机房里其他人做题量的$1\%$, 可以接受.

值得愉悦的变化还有$Codeforces$的$Rating$从$\color{Blue}{Conless}$变成了$\color{Aqua}{Conless}$, 下降的少量$Rating$似乎意味着我的分数比起初三的$NOIP2018$并不会下降太多, 可喜可贺.

新的知识倒也确实学了一点, 爆零过的比赛数略多于新学的算法数, 也算是一个可观的数字.

学习

文化课的成绩单论班级上倒是有可观的进步, 从高一第一学期期中考的$Rank 46$进步到了高二第一学期期中考的$Rank 37$, 因此认为我被竞赛影响到文化课的言论也不可谓不愚蠢.

很多认识的聪慧的同学也会问到信息学对于数学、英语的帮助, 考虑到能力通常与排名正相关, 我的亲身经验可能也能在一定程度上让你走上信息学的康庄大道.

CSP-S 2020

考前准备

在考前的最后一个晚上为了放松心情选择玩完游戏就在$27:00 ,Oct.37^{th}$早早入睡, 也于次日$14:31$按时起床.

T0

调试好了电脑

写好了初始源文件

#include <bits/stdc++.h>
#include <con>

#define 最后一次 freopen
#define 比赛 (".in", "r", stdin);
#define 爆零 (".out", "w", stdout);
#define 终于还是要返回值得接受的失败结果吧 return -1;

using namespace std;

int left, right, y0, y1;

int main()
{
    最后一次比赛
    最后一次爆零
    left++; right++; y0++; y1++;
    终于还是要返回值得接受的失败结果吧
}

T1

是一道难度不大的背包类贪心, 每年一道贪心看来要在这里打卡呢.

根据数据$n\le 5000$不难想到$O(n^2)$做法

#include <bits/stdc++.h>

#define MAXN 0005

using namespace std;

int n, m, ans;
int d[MAXN], w[MAXN];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &d[i], &w[i]);
    int mx = 1 << n;
    for (int i = 0; i < mx; i++)
    {
        int res = 0, sum = 0;
        for (int j = 0; j < n; j++)
            if ((mx >> j) & 1)
            {
                res += d[i];
                sum += w[i];
            }
        if (sum <= m)
            ans = max(ans, res);
    }
    printf("%d", ans);
    return 0;
}

T2

是一个稀疏图的单源最短路问题, 考虑到机房大佬说的图论问题数较大时考虑矩阵快速幂, 思考到矩阵快速幂优化Dij

typedef int matrix;

inline matrix pow(matrix a, maxtirx b) { return a + b; }

matrix dis[MAXN][MAXN];

void Dij()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
            {
                int res = pow(dis[i][j], dis[i][k]);
                if (res < dis[j][k])
                    dis[j][k] = dis[k][j] = res;
            }
}

T3

是一个树上问题, 观察到读入数据比较大, 考虑快读:

int main()
{
    ios::sync_with_stdio(true);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
}

这几天学校做了不少树剖的题, 因此已经轻车熟路了, 虽然线段树并不是很记得怎么写区间修改, 我也还是手推了一个很好的写法:

#define sn segTree[node]

void change(int node, int l, int r, int val)
{
    if (!node)
        return;
    if (sn.l > r || sn.r < l)
        return;
    if (sn.l == sn.r)
    	sn.data += val;
    change(sn.lson, l, r, val);
    change(sn.rson, l, r, val);
    pushup();
}

T4

回归【列队】, 我们先考虑在10h内将Splay的模板打上去.

#define root bTree[0].ch[1]
#define bn bTree[node]

class Splay
{

    int tot, cnt;

    struct TreeNode {
        int num, fa;
        int ch[2];
        int sum, recy;
    } bTree[MAXN];

    void update(int node)
    {
        bn.sum = bTree[bn.ch[0]].sum + bTree[bn.ch[1]].sum + bn.recy;
    }
    int identify(int node)
    {
        return bTree[bn.fa].ch[0] != node;
    }
    void connect(int node, int fa, int son)
    {
        bn.fa = fa;
        bTree[fa].ch[son] = node;
    }
    void rotate(int node)
    {
        int fa = bn.fa,
            gfa = bTree[fa].fa,
            son = identify(node),
            gson = identify(fa),
            nson = bn.ch[son ^ 1];
        connect(nson, fa, son);
        connect(fa, node, son ^ 1);
        connect(node, gfa, gson);
        update(fa);
        update(node);
    }
    void splay(int node, int to)
    {
        to = bTree[to].fa;
        while (bn.fa != to)
        {
            int nxt = bn.fa;
            if (bTree[nxt].fa == to)
                rotate(node);
            else {
                if (identify(nxt) == identify(node))
                {
                    rotate(nxt);
                    rotate(node);
                }
                else {
                    rotate(node);
                    rotate(node);
                }
            }
        }
    }
    int create(int num, int fa)
    {
        tot++;
        bTree[tot].num = num;
        bTree[tot].fa = fa;
        bTree[tot].sum = bTree[tot].recy = 1;
        return tot;
    }
    void destroy(int node)
    {
        bn.num = bn.ch[0] = bn.ch[1] = bn.sum = bn.fa = bn.recy = 0;
        if (node == tot)
            tot--;
    }

public:
    int getroot() { return root; }
    int find(int num)
    {
        int node = root;
        while (true)
        {
            if (bn.num == num)
            {
                splay(node, root);
                return node;
            }
            int nxt = (num >= bn.num);
            if (!bn.ch[nxt])
                return 0;
            node = bn.ch[nxt];
        }
    }
    int build(int num)
    {
        cnt++;
        if (root == 0)
        {
            create(num, 0);
            root = tot;
        }
        else {
            int node = root;
            while (true)
            {
                bn.sum++;
                if (num == bn.num)
                {
                    bn.recy++;
                    splay(node, root);
                    return node;
                }
                int nex = (num >= bn.num);
                if (!bn.ch[nex])
                {
                    create(num, node);
                    bn.ch[nex] = tot;
                    splay(tot, root);
                    return tot;
                }
                node = bn.ch[nex];
            }
        }
        return 0;
    }
    void push(int num)
    {
        int node = build(num);
        splay(node, root);
    }
    void pop(int num)
    {
        int pos = find(num);
        if (!pos)
            return;
        cnt--;
        if (bTree[pos].recy > 1)
        {
            bTree[pos].recy--;
            bTree[pos].sum--;
            return;
        }
        if (!bTree[pos].ch[0])
        {
            root = bTree[pos].ch[1];
            bTree[root].fa = 0;
        }
        else {
            int node = bTree[pos].ch[0];
            while (bn.ch[1])
                node = bn.ch[1];
            splay(node, bTree[pos].ch[0]);
            int rson = bTree[pos].ch[1];
            connect(rson, node, 1);
            connect(node, 0, 1);
            update(node);
        }
        destroy(pos);
    }
    int get_rank(int num)
    {
        int node = find(num);
        return bTree[bn.ch[0]].sum + 1;
    }
    int get_num(int k)
    {
        if (k > cnt)
            return -INF;
        int node = root;
        while (true)
        {
            int len = bn.sum - bTree[bn.ch[1]].sum;
            if (k > bTree[bn.ch[0]].sum && k <= len)
                break;
            if (k < len)
                node = bn.ch[0];
            else {
                k -= len;
                node = bn.ch[1];
            }
        }
        splay(node, root);
        return bn.num;
    }
    int upper(int num)
    {
        int node = root;
        int result = INF;
        while (node)
        {
            if (bn.num > num && bn.num < result)
                result = bn.num;
            if (num < bn.num)
                node = bn.ch[0];
            else node = bn.ch[1];
        }
        return result;
    }
    int lower(int num)
    {
        int node = root;
        int result = -INF;
        while (node)
        {
            if (bn.num < num && bn.num > result)
                result = bn.num;
            if (num > bn.num)
                node = bn.ch[1];
            else node = bn.ch[0];
        }
        return result;
    }
} btree;

可以看出这确实是一个短小精炼的数据结构, 我在考场上的时侯出了后面16个成员函数都很好地默了出来.

最终评测的结束也宣告了我5年OI生涯的终止, 最后可喜可贺的是, 对于定义一个考生能力的函数$F(i)=\frac{rank_i}{point_i}$来讲, 若不考虑无穷, 由于原函数值越小能力越强, 确实没有人的函数求值结果小于我.

未来

为了大学能获得ACM市赛爆零的机会, 需要积极投入文化课学习, 稳定在年级前列, 有望达到本科录取线.

听从机房大佬的谆谆教诲要好好学好yìng语

希望文化课的成绩与另一位机房大佬相比, 不要低超过900名

就这样吧, 下周再来填坑.

估计要被禁赛3年了8~