「SDOI2016」游戏题解

思路

显然需要树链剖分。

对于每一个 \(a \times dis + b\) 的操作，向懒惰标记里添加。如果碰上已经有懒惰信息，那么我们只需要把这样的操作理解为加上直线，把直线下边缘下传到左右子节点即可。（计算长度进行左右决策下传）对于每一个节点，懒惰加法为等差数列求和，计算 \(b \times subtreeSize + a \times \frac{subtreeSize*(subtreeSize-1)}{2}\)。

「APIO2012」派遣题解

思路

可并堆思路：自顶向上做大根堆，然后弹出堆顶直到整个堆的和小于 m。（性质：父亲节点不会选择子树不包含的忍者）。

线段树合并思路：没看懂，不写了。

代码

// P1552.cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
const int MAX_N = 100100;
struct node
{
    int lson, rson;
    ll dist;
} nodes[MAX_N];
ll n, m, li[MAX_N], ci[MAX_N], master, ans = -2e9;
ll sum[MAX_N], siz[MAX_N], pt[MAX_N];
vector<int> G[MAX_N];
int merge(int x, int y)
{
    if (!x || !y)
        return x + y;
    if (ci[x] < ci[y])
        swap(x, y);
    nodes[x].rson = merge(nodes[x].rson, y);
    if (nodes[nodes[x].lson].dist < nodes[nodes[x].rson].dist)
        swap(nodes[x].lson, nodes[x].rson);
    nodes[x].dist = nodes[nodes[x].rson].dist + 1;
    return x;   
}
void dfs(int u)
{
    sum[u] = ci[u], siz[u] = 1, pt[u] = u;
    int siz_ = G[u].size();
    for (int i = 0; i < siz_; i++)
    {
        int to = G[u][i];
        dfs(to);
        sum[u] += sum[to], siz[u] += siz[to];
        pt[u] = merge(pt[u], pt[to]);
    }
    while (sum[u] > m && siz[u])
    {
        sum[u] -= ci[pt[u]];
        pt[u] = merge(nodes[pt[u]].rson, nodes[pt[u]].lson);
        siz[u]--;
    }
    ans = max(ans, li[u] * siz[u]);
}
int main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        ll fa;
        scanf("%lld%lld%lld", &fa, &ci[i], &li[i]);
        if (fa == 0)
            master = i;
        else
            G[fa].push_back(i);
    }
    dfs(master);
    printf("%lld", ans);
    return 0;
}

我之前把数据结构搞复杂了，看了题解发现好简洁。还是要做减法啊。

复活

嘿嘿不用退役了。

P3773:「CTSC2017」吉夫特题解

神仙思路

有一个“显然”的定理：如果满足\(n\&k==k\)，那么\(C^k_n\)为奇数。具体感性证明：litble 的证明。所以，直接上代码。

代码

// P3773.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX_N = 233393, mod = 1000000007;
int n, arr[MAX_N], bucket[MAX_N], f[MAX_N], ans;
int getMod(int num) { return num >= mod ? num - mod : num; }
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]), bucket[arr[i]] = i;
    for (int i = n; i >= 1; i--)
    {
        f[i] = 1;
        for (int j = (arr[i] & (arr[i] - 1)); j; j = arr[i] & (j - 1))
            if (bucket[j] > i)
                f[i] = getMod(f[i] + f[bucket[j]]);
        ans = getMod(ans + f[i]);
    }
    ans = (ans - n + mod) % mod;
    printf("%d", ans);
    return 0;
}

鄙人之代码规范

大体的几条规则

大括号换行（至少在 C 系语言里是这样的，JavaScript 随意，但是我没有见过谁竞赛用 JavaScript）
尽量用题目里的变量名。
临时变量（比如说遍历变量）可以用一个字母或者是两位字母缩写来命名。
全局变量、生成周期长的字段尽量小驼峰命名。
函数、函数变量命名使用小驼峰。
赋值的构造函数、初始化的函数一行搞定（比如说初始一条边或者是并查集初始化）
少用 #define，多用 const。
循环里或者是条件语句中用逗号压行（不要过长）。
使用现代编辑器进行自动格式化（墙裂安利 VSCode，告别 F**K 调试法）。

示例代码：

// snippet.cpp
#include <iostream>
#include <cstdio>
using namespace std;
const int MAX_N = 100;
int n, seqa[MAX_N], seqb[MAX_N], ans;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &seqa[i]), scanf("%d", &seqb[i]);
    for (int i = 1; i <= n; i++)
        ans += seqa[i] - seqb[i];
    printf("%d", ans);
    return 0;
}

变量名表

变量意义	变量名
答案	ans
栈	st
队列	q
最大值	MAX_???
最小值	MIN_???
数组	arr[]
多个数组或数列	seq?[]
源数据/起点	src
目标数据/终点	dst
距离	dist

现在，我已进入半退役状态

背景 – 晃动人心的改革

官方文件：中华人民共和国教育部

在2019的头几天，这个文件就直接惊动了所有竞赛生和竞赛生的家长们。对于竞赛生而言，这个文件里面的几条是直接关系到升学这一大事的：

···二是严格制定录取标准，高校在现有基础上进一步降低给予自主招生考生的优惠分值。三是严格控制招生规模，高校在上一年录取人数基础上适度压缩招生名额。

半退役

我本人听到这个消息之后非常的崩溃。本来省内竞赛竞争加强，然后又出现了这样的文件，对于我这个蒟蒻而言，无疑就是在告诉我，除非进国家集训队，其他的奖拿到手之后都存在非常大的不稳定因素。而且，我短暂的竞赛经历不足以支撑我到达国集水平。如果一本约完全取消、最优惠分数线又高到了我高三无法弥补的地步的话，那么我只能面临退役。

而现在没有任何证据显示一本线取消或者是最优分数线会很高。然而，我这一届就非常之尴尬，万一到了我们最后一年的时候力度加大，我就很容易被卡死。这样来看，观望也非常的亏。

但是，我不想退役。即使高考会比竞赛容易很多（确实容易很多），但是我不想让我的竞赛生涯就停留在5个月的时间，也不想停留在省三这个垃圾奖项上。我想追求更高的目标，想认识更多的神仙，想学习更多的算法，当然也想考上更好的大学，在更好的计算机专业里学习。

我全家现在都在劝我退役，我妈甚至拿“你高考肯定更好”这样的屁话来劝退，我感到压力非常的大。我想追求我自己想要的，尽管全盘皆输。

在官方和家庭的压力之下，我只好进入半退役状态。