NOIp 2016 解题报告

A – 玩具谜题

sb 题，随便搞。

// P1563.cpp
#include <iostream>

using namespace std;

int main()
{
    int N, M;
    cin >> N >> M;
    int dir[N];
    string occupations[N];
    int cmdKeys[M];
    int cmdPath[M];
    // I/O;
    for (int i = 0; i < N; i++)
        cin >> dir[i] >> occupations[i];
    for (int j = 0; j < M; j++)
        cin >> cmdKeys[j] >> cmdPath[j];
    // Process;
    int currentBias = 0;
    for (int i = 0; i < M; i++)
        if (cmdKeys[i] == 0)
            if (dir[currentBias % N] == 1)
                currentBias += cmdPath[i];
            else
            {
                currentBias -= cmdPath[i];
                if (currentBias < 0)
                    currentBias = N + currentBias;
            }
        else if (dir[currentBias % N] == 1)
        {
            currentBias -= cmdPath[i];
            if (currentBias < 0)
                currentBias = N + currentBias;
        }
        else
            currentBias += cmdPath[i];
    cout << occupations[currentBias % N];
    return 0;
}

Continue reading →

NOIp 2017 解题报告

A – 小凯的疑惑

送命规律题。当然也可以考虑用 exgcd 的性质，以下是感性理解：

考虑设这个数为\(x \equiv ya {\pmod b}\)，展开就是：

\[ x = ya + kb, k \in [1, b – 1] \]

发现\(k \geq 0\)时都满足，那么反过来取\(-1\)就可以又满足最大又满足不满足条件。

// P3951.cpp
#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    unsigned long long a, b, i;
    cin >> a >> b;
    cout << a * b - a - b;
    return 0;
}

Continue reading →

NOIp 2018 解题报告

A – 道路铺设

这道题考场上神智不清，敲了个线段树拿了满分（当然不用这么复杂）。以下是考场代码。

Continue reading →

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

CH1201:最大子序和题解

Solve this Problem with the Priority Queue

单调队列的主要目标其实跟单调栈的主要目标比较相似，都是在一个单调问题中，直接排除一些可以排除的答案进行运算。

在本题中，我们会采用单调队列来解决。首先，我们采用前缀和来进行快速计算。然后，在前缀的前提下，我们会在本题中使用一个策略，那就是：如果有两个位置的前缀和\(sum[i]>sum[j],其中i<j\)，那么处于\(i\)位置的元素对于我们来讲，是毫无用处的。原因是，如果我们要在\(m\)长度内获得和最大的子序列，对于一个这样前缀和又大、又靠前的元素，最优解绝不是由这个元素组成的。

我们来用几个代码块来简述我们的策略。

Continue reading →

NOIp 2018 总结

今天是11月11日。NOIp 2018的二试已经结束了，初步来看，DAY 1的第一题是可以拿到满分的，第二题由于我使用了伪扩展欧几里得暴力算法使得我只能得到部分的分数，第三题纯属双向深度搜索骗分。

而二试便惨淡的多，我花了两个小时写完了第三题（我认为预处理是\(O(n)\)，询问是根据询问的节点深度而定的复杂度），而看到剩下两道关于字典序比大小的神仙题时我便选择了第一题去骗分。得知部分分中有存在只有两个城市连接的几个数据点之后，我便开始写起了暴力骗分代码。而到最后比赛结束，我也没有能调出来，甚至紧张的忘记了抄下样例进行骗分。

我现在在高一年级，而很多初中生甚至是小学生都已经开始角逐NOIp提高组的奖项，我实在是不能与他们比较。对于我这个从7月底开始学OI的超入门者，确实还有很长的路要走。

我打算下周开始补两周的文化课，以便不会落下太多。而在下周成绩出来之后我就要开始联系一些机构和学校，打算直接开始我正式的OI集训，以保证OI的进步速度不下降。

愿景是美好的。时间会给我答案的。