2012

NOIP Day 1

T1 Vigenère 密码

简单模拟题，

可以根据样例逆向模拟，找规律。

调试轻松，整体难度较低。

#include <bits/stdc++.h>
using namespace std;

string k, s;
int MP[110];

int main()
{
    cin >> k >> s;

    for (int i = 0; i < k.size(); i ++ )
    {
        if (k[i] > 'Z') MP[i] = k[i] - 'a';
        else MP[i] = k[i] - 'A';
    }

    for (int i = 0; i < s.size(); i ++ )
    {
        int j = i % k.size();
        if (s[i] > 'Z')
        {
            int op = s[i] - 'a';
            if (op < MP[j]) op += 26;
            op -= MP[j];
            printf("%c", 'a' + op);
        }
        else
        {
            int op = s[i] - 'A';
            if (op < MP[j]) op += 26;
            op -= MP[j];
            printf("%c", 'A' + op);
        }
    }

    return 0;
}

T2 国王游戏

贪心水题，记得写高精度。

可以根据微扰法进行证明。

与 奶牛叠罗汉 实质上相同。

但高精度的调试还是较为麻烦的。

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;

typedef pair<int, int> PII;

int n;
PII ps[N];

vector<int> mul(vector<int> a, int b) 
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i ++ ) 
    {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (t) c.push_back(t % 10), t /= 10;
    return c;
}

vector<int> divd(vector<int> a, int b) 
{
    vector<int> c;
    bool flag = false;
    for (int i = a.size() - 1, t = 0; i >= 0; i -- ) 
    {
        t = t * 10 + a[i];
        int x = t / b;
        if (flag || x) {
            c.push_back(x);
            flag = true;
        }
        t %= b;
    }
    reverse(c.begin(), c.end());
    return c;
}

vector<int> max_v(vector<int> a, vector<int> b) 
{
    if (a.size() > b.size()) return a;
    if (a.size() < b.size()) return b;
    if (vector<int>(a.rbegin(), a.rend()) > vector<int>(b.rbegin(), b.rend()))
        return a;
    return b;
}

void output(vector<int> a) {
    for (int i = a.size()-1; i >= 0; i -- ) {
        cout << a[i];
    }
}

int main(){
    scanf("%d", &n);
    for (int i = 0; i <= n; i ++ )
    {
        int a, b;
        scanf("%d %d", &a, &b);
        ps[i] = {a * b, a};
    }

    sort(ps + 1, ps + n + 1);

    vector<int> product(1, 1);
    vector<int> res(1, 0);

    for (int i = 0; i <= n; i ++ )
    {
        res = max_v(res, divd(product, ps[i].first / ps[i].second));
        product = mul(product, ps[i].second);
    }

    output(res);

    return 0;
}

T3 开车旅行

70 分暴力写挂，最后差不多还剩个 40

A 掉之后在加进去

题解

NOIP Day 2

T1 同余方程

扩展欧几里得求费马小定理。

#include <bits/stdc++.h>
using namespace std;

int a, b, x, y;

int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
    scanf("%d %d", &a, &b);
    exgcd(a, b, x, y);
    printf("%d", (x % b + b) % b);
}

T2 借教室

正解是 二分 + 差分

我是直接差分 + 优化暴力计算。

思路很好理解，最后差不多 12 min 就解决了

而且效率比正解还要快 400ms

#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;

typedef long long LL;

int n, m;
int s[N], t[N];
int d[N];
int botel[N], tot;
int r[N];
LL f[N];
LL Max;

int main()
{
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &r[i]);

    for (int i = 1; i <= m; i ++ )
    {
        scanf("%d %d %d", &d[i], &s[i], &t[i]);
        f[s[i]] += d[i], f[t[i] + 1] -= d[i];
    }

    for (int i = 1; i <= n; i ++ ) f[i] += f[i - 1];

    for (int i = 1; i <= n; i ++ )
    {
        if (f[i] > (LL)r[i])
        {
            botel[ ++ tot] = i;
        }
    }

    if (!tot) 
    {
        puts("0");
        return 0;
    }

    puts("-1");
    int last = m;
    for (int i = 1; i <= tot; i ++ )
    {
        Max = 0;
        for (int j = 1; j <= last; j ++ )
        {
            if (s[j] <= botel[i] && t[j] >= botel[i])
            {
                Max += (LL)d[j];
                if (Max > r[botel[i]])
                {
                    last = j;
                    break;
                }
            }
        }
    }

    printf("%d", last);
    return 0;
}

T3 疫情控制

有一点麻烦的题，最后没时间了emm

总用时：一节信息课（大约 3 h）

结语

总得分：100 + 100 + 40 + 100 + 100 + 10 = 450

这年的题是真的简单，下节课将剩下两道题补了吧！

加油！