Kalorona

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;
}

鄙人之代码规范

大体的几条规则

  1. 大括号换行（至少在 C 系语言里是这样的，JavaScript 随意，但是我没有见过谁竞赛用 JavaScript）
  2. 尽量用题目里的变量名。
  3. 临时变量（比如说遍历变量）可以用一个字母或者是两位字母缩写来命名。
  4. 全局变量、生成周期长的字段尽量小驼峰命名。
  5. 函数、函数变量命名使用小驼峰。
  6. 赋值的构造函数、初始化的函数一行搞定（比如说初始一条边或者是并查集初始化）
  7. 少用 #define，多用 const。
  8. 循环里或者是条件语句中用逗号压行（不要过长）。
  9. 使用现代编辑器进行自动格式化（墙裂安利 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个月的时间，也不想停留在省三这个垃圾奖项上。我想追求更高的目标，想认识更多的神仙，想学习更多的算法，当然也想考上更好的大学，在更好的计算机专业里学习。

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

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

P1069:细胞分裂题解

思路转化

题目大意是这样的：给出数字\(N\)，\(m_1\)，\(m_2\)，\(S_{i[1\dots N]}\)，求最小的\(t\)，使得某一\(S_i^t \; mod\; m_1^{m_2}\)。

所以之后就非常的显然了，我们只要分析出每一个数的质因数与\(m_1\)的质因数的关系即可。如果有一个数\(c\)的质因数集为\(A\)，那么我们可以遍历\(m_1\)的质因数集，记录答案。如果质因数集不包含\(m_1\)的质因数集直接退出。

代码

// P1069.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const int MX_N = 30020, INF = 0x3f3f3f3f;
ll n, m1, m2, arr[MX_N], pipePrime[MX_N], cellPrime[MX_N], lit, ans = INF;
int main()
{
    scanf("%lld%lld%lld", &n, &m1, &m2);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]);
    if (m1 == 1)
    {
        printf("0");
        return 0;
    }
    for (int i = 2; m1 != 1; i++)
    {
        while (!(m1 % i))
            m1 /= i, pipePrime[i] += m2;
        lit = max(lit, (ll)i);
    }
    for (int i = 1; i <= n; i++)
    {
        ll now = 0;
        for (int j = 2; j <= lit; j++)
            if (pipePrime[j] != 0)
            {
                ll tim = 0;
                while (!(arr[i] % j))
                    arr[i] /= j, tim++;
                if (!tim)
                {
                    now = INF;
                    break;
                }
                now = max(now, (pipePrime[j] - 1) / tim);
            }
        ans = min(ans, now);
    }
    if (ans != INF)
        printf("%lld", ans + 1);
    else
        printf("-1");
    return 0;
}

 

P2501:「HAOI2006」数字序列题解

主要思路

这道题算是非常的毒瘤了。

首先我们来看第一问，根据 XG 巨佬的话，是非常明显的。我们在序列读入时减去元素自己的序号，找 LIS 长度即可。代码：

scanf("%lld", &n);
for (ll i = 1; i <= n; i++)
    scanf("%lld", &arr[i]), arr[i] -= i, dst[i] = INF;
dst[0] = -INF, dp[1] = 1, len = 1, dst[1] = arr[1], arr[0] = -INF, arr[++n] = INF;
for (ll i = 2; i <= n; i++)
{
    ll addr = upper_bound(dst, dst + 1 + len, arr[i]) - dst;
    len = max(len, addr);
    dp[i] = addr;
    dst[addr] = min(dst[addr], arr[i]);
}
printf("%lld\n", n - dp[n]);

第二问我们引出一个小的结论：如果要把区间\([l\dots r]\)之间变得“好看”，那么这个子区间内一定分为两段：高度为\(arr[l]\)的一段和高度\(arr[r]\)的一段。注意，此时\(arr[]\)内的元素已经剪去了元素编号。

所以这第二问就是一道区间 DP，时间复杂度为\(O(n^3)\)。不过好在序列随机，且我们可以使用邻接表预先存好那些可以处理的区间，然后进行 DP。

代码

// P2501.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const ll MX_N = 35020, INF = 0x3f3f3f3f;
ll head[MX_N], arr[MX_N], n, len, dst[MX_N], dp[MX_N], M_curt, f[MX_N], sum1[MX_N], sum2[MX_N];
struct edge
{
    ll to, nxt;
} edges[MX_N << 1];
void addpath(ll src, ll dst)
{
    edges[M_curt].to = dst, edges[M_curt].nxt = head[src];
    head[src] = M_curt++;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &arr[i]), arr[i] -= i, dst[i] = INF;
    dst[0] = -INF, dp[1] = 1, len = 1, dst[1] = arr[1], arr[0] = -INF, arr[++n] = INF;
    for (ll i = 2; i <= n; i++)
    {
        ll addr = upper_bound(dst, dst + 1 + len, arr[i]) - dst;
        len = max(len, addr);
        dp[i] = addr;
        dst[addr] = min(dst[addr], arr[i]);
    }
    printf("%lld\n", n - dp[n]);
    for (ll i = n; i >= 0; i--)
        addpath(dp[i], i), f[i] = INF;
    f[0] = 0;
    for (ll i = 1; i <= n; i++)
        for (ll e = head[dp[i] - 1]; e != -1; e = edges[e].nxt)
        {
            ll v = edges[e].to;
            if (v > i)
                break;
            if (arr[v] > arr[i])
                continue;
            for (ll k = v; k <= i; k++)
                sum1[k] = abs(arr[k] - arr[v]), sum2[k] = abs(arr[k] - arr[i]);
            for (ll k = v + 1; k <= i; k++)
                sum1[k] += sum1[k - 1], sum2[k] += sum2[k - 1];
            for (ll k = v; k <= i - 1; k++)
                f[i] = min(f[i], f[v] + sum1[k] - sum1[v] + sum2[i] - sum2[k]);
        }
    printf("%lld", f[n]);
    return 0;
}

 

2018 年度总结

Overview

2018 年算是人生中的一个小节点。让这一年如此之特殊的事情就是我通过了中考进入了高中。从红谷实验到江西师大附中，我这一年就是在这两个学校里度过的。说实话，今年整体的心情状态非常的不佳，上半年的原因大致是因为中考前的焦虑和紧张；下半年心情差的原因应该是适应期比较长，所以也没什么好分析的。不过感觉这一年过后沧桑了很多，估计以后发现自己越来越沧桑的时候会越来越多。

Days in HGTES

其实我更想说说我的初中，因为我对我现在的高中的了解不是很透彻，所以我觉得这个内容放在明年会更加合适。在实验学校呆了 9 年，算是资历很深了，再加上我比其他人更注意学校的一些信息，所以我敢说很少学生像我这样了解这所学校。我没有经历过小学到初中切换的那一段时期，所以可能这就是造成我高中适应期过长的一个小原因（？）。我现在回想起上半年，我突然想到我要离开这里的时候是多么的无力。事实证明，从现在的角度来看，那一段时光确实是 Good Old Days。以前和小学同学一起玩 Minecraft:Pocket Edition，没事就去同学家互串联机，也因此学会了一些越狱、ROOT 之类很酷的东西。上了初中以后，经历了七年级一大串的傻逼时刻（不过这些时刻想想挺有意思的）之后，老万确实给了我很大的帮助（即使磨合期也很长）。科技社也终于在七年级下学期正式开始运作，到了八年级上学期的时候就毫无压力的随便乱搞，搞到了十佳社团的那一万块钱（好像现在都不知道用在哪里了）。这期间结实的人和经历的事情可以说是是人生中的一笔巨大财富，我现在觉得那个时候的我还挺酷的，什么东西搞不定就写代码搞定他，也加深了 C# 的能力。现在回想起来真是催泪，确实，以前的那个街区里的人再也回不到年轻的样子了，没机会一起上下学，一起飙自行车，一起讲骚话。非常特别地，我要记起一个前几天让我梦到的人，没有你，可能我真的很难处理好我的初中生活。

就像我之前写的老友记一样，其实那个时候我表达了更多与之相关的情感。也算是第一次体验到失去的就不会再来的感觉（失去了太多我真心喜欢的朋友）。一切都不是老样子了，不过并不是每个人的老样子都这么美好。

导演毕业典礼是我最后一次亲近这个学校了，也是我和刘子楷在学校负责的最后一个小项目。实验啊，有缘再见。

Bet on OI

高中参加OI的话基本就高二一轮的机会，一招不慎，满盘皆输，不过这大抵就是竞赛的魅力吧。——hzwer

我像是把我的人生赌在了竞赛上。

踌躇了一个多月之后，10 月份开始后，我正式地确认了——我现在是一名全职选手。那些初中就开始学的神仙给了我相当大的压力，所以我不得不努力再努力，疯狂地燃烧着我对计算机的热爱（是的，我会把我的毕生心血交给计算机）。

但是 NOIp 2018 凉了，蹭线三等奖令人窒息。Peer Pressure 压的我难以喘息。之后的两周我都是在绝望中度过的。老师的不信任（？）、家长的失望，当然更多是来源于我自己的绝望。虽然可以讲自己是七月底才正式搞 OI 的，但是“今年有 380 分的傻逼分”这种大实话真的令我人生中第一次感觉到腹背受敌的感觉。我心痛，我以为我很努力，然而翻车却狠狠地扇了我一巴掌。停课也让我和班上产生了一点点距离感（班上的同学很好，这是我自己的原因）。

赌徒要继续他的博弈，而能否成功，就看他到底有没有这个能耐了。

Specification

Abilities On Academics

OI

七月末开始接触到 OI 这个神仙东西，然后八月学了一个月的托福（有点后悔）。之后九月份的效率也奇低，到了十月份我才开始真正的搞起来（现在感觉基础仍然非常的薄弱，看来还是要多做题），经历了十一月份的惨败之后反思了很久，也算是目前人生非常黑暗的时候（以后估计多着呢）。十二月份月考之后就去 Yali 集训了，神仙东西看不懂，基础还是打扎实了的。但是仍然不是很信任自己，觉得 GG 还会重新上演。

我热爱 OI。

English

托福 84 滚粗。

Mathematics

学了 OI 之后离散数学好像有了点起色…其他到没学什么，就是跟着高一老师的步伐走了一会。我还是超级喜欢数学的（不知道成绩越来越差之后会不会继续喜欢）。

Computer Science

计科超级有吸引力，在 2018 年我了解了很多底层的东西，渐渐摸清了 AI 的一些真实的细节。总之，太多细节无法总结。

Interpersonal Relationships

跟初中同学一直很好。

今晚的跨年夜真是迷人。我真的很难想到今年的跨年时刻如此的魔幻：雪景中的红谷滩，那群我了解的人，那群了解我的人。烧烤过后的路边雪仗，班长的强势加入，垃圾烂片盖过新年钟声，挥挥手，大家都回到自己原来的地方了。

我不是很了解他们的喜好，所以我在高中同学面前还是有隔阂。尽量去了解吧。

Preview On 2019

文化课

年初和寒假务必保证不要翻车。暑假预习保证高三不至于太翻车。

OI

争取省队名次（反正进不去，参考好了），学神仙东西，写神仙题，膜机房神仙。

Interpersonal Relationships

尽量去了解，温和一点，不要过于敏感。不要太怀旧，少在意别人，制造多一点记忆。

2019，加油。