首页 > 其他分享 >「解题报告」NOIP 2020

「解题报告」NOIP 2020

时间：2023-09-22 20:22:43浏览次数：36  
标签：结点 le NOIP texttt 样例 back st 解题 2020

总分：90 + 32 + 5 + 35 = 162。

[NOIP2020] 排水系统

题目描述

对于一个城市来说，排水系统是极其重要的一个部分。

有一天，小 C 拿到了某座城市排水系统的设计图。排水系统由 \(n\) 个排水结点（它们从 \(1 \sim n\) 编号）和若干个单向排水管道构成。每一个排水结点有若干个管道用于汇集其他排水结点的污水（简称为该结点的汇集管道），也有若干个管道向其他的排水结点排出污水（简称为该结点的排出管道）。

排水系统的结点中有 \(m\) 个污水接收口，它们的编号分别为 \(1, 2, \ldots , m\)，污水只能从这些接收口流入排水系统，并且这些结点没有汇集管道。排水系统中还有若干个最终排水口，它们将污水运送到污水处理厂，没有排出管道的结点便可视为一个最终排水口。

现在各个污水接收口分别都接收了 \(1\) 吨污水，污水进入每个结点后，会均等地从当前结点的每一个排出管道流向其他排水结点，而最终排水口将把污水排出系统。

现在小 C 想知道，在该城市的排水系统中，每个最终排水口会排出多少污水。该城市的排水系统设计科学，管道不会形成回路，即不会发生污水形成环流的情况。

输入格式

第一个两个用单个空格分隔的整数 \(n, m\)。分别表示排水结点数与接收口数量。
接下来 \(n\) 行，第 \(i\) 行用于描述结点 \(i\) 的所有排出管道。其中每行第一个整数 \(d_i\) 表示其排出管道的数量，接下来 \(d_i\) 个用单个空格分隔的整数 \(a_1, a_2, \ldots , a_{d_i}\) 依次表示管道的目标排水结点。
保证不会出现两条起始结点与目标结点均相同的管道。

输出格式

输出若干行，按照编号从小到大的顺序，给出每个最终排水口排出的污水体积。其中体积使用分数形式进行输出，即每行输出两个用单个空格分隔的整数 \(p\)，\(q\)，表示排出的污水体积为 \(\frac{p}{q}\)。要求 \(p\) 与 \(q\) 互素，\(q = 1\) 时也需要输出 \(q\)。

样例 #1

样例输入 #1

5 1
3 2 3 5
2 4 5
2 5 4
0
0

样例输出 #1

1 3
2 3

样例 #2

样例输入 #2

见附件中的 water/water2.in

样例输出 #2

见附件中的 water/water2.ans

样例 #3

样例输入 #3

见附件中的 water/water3.in

样例输出 #3

见附件中的 water/water3.ans

提示

【样例 #1 解释】

\(1\) 号结点是接收口，\(4, 5\) 号结点没有排出管道，因此是最终排水口。
\(1\) 吨污水流入 \(1\) 号结点后，均等地流向 \(2, 3, 5\) 号结点，三个结点各流入 \(\frac{1}{3}\) 吨污水。
\(2\) 号结点流入的 \(\frac{1}{3}\) 吨污水将均等地流向 \(4, 5\) 号结点，两结点各流入 \(\frac{1}{6}\) 吨污水。
\(3\) 号结点流入的 \(\frac{1}{3}\) 吨污水将均等地流向 \(4, 5\) 号结点，两结点各流入 \(\frac{1}{6}\) 吨污水。
最终，\(4\) 号结点排出 \(\frac{1}{6} + \frac{1}{6} = \frac{1}{3}\) 吨污水，\(5\) 号结点排出 \(\frac{1}{3} + \frac{1}{6} + \frac{1}{6} = \frac{2}{3}\) 吨污水。

【数据范围】

测试点编号 \(n \le\) \(m \le\)
\(1 \sim 3\) \(10\) \(1\)
\(4 \sim 6\) \({10}^3\) \(1\)
\(7 \sim 8\) \({10}^5\) \(1\)
\(9 \sim 10\) \({10}^5\) \(10\)

对于全部的测试点，保证 \(1 \le n \le {10}^5\)，\(1 \le m \le 10\)，\(0 \le d_i \le 5\)。

数据保证，污水在从一个接收口流向一个最终排水口的过程中，不会经过超过 \(10\) 个中间排水结点（即接收口和最终排水口不算在内）。

拓扑排序，但是只有 \(90\) 分，因为最后一个点要写高精（考场上有时间写高精去拿这十分倒不如去打后面题的暴力 其次我是不会告诉你我已经不会写高精了）。

// The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

const int N = 1e5 + 5;

int n, m;
int in[N], out[N];
vector<int> e[N];
bool watout[N];
queue<int> q;

struct dfrac {
    ll fz, fm;
} water[N];

ll gcd(ll x, ll y) {
    if (!y) {
        return x;
    }
    return gcd(y, x % y);
}

dfrac operator+  (dfrac a, dfrac b) {
    ll fza = a.fz, fma = a.fm, fzb = b.fz, fmb = b.fm;
    ll lcm = fma / gcd(fma, fmb) * fmb;
    ll g1 = lcm / fma, g2 = lcm / fmb;
    fza *= g1, fzb *= g2;
    ll fz = fza + fzb, fm = lcm;
    ll g = gcd(fz, fm);
    fz /= g, fm /= g;
    return dfrac{fz, fm};
}

dfrac operator* (dfrac a, dfrac b) {
    ll fza = a.fz, fma = a.fm, fzb = b.fz, fmb = b.fm;
    ll g1 = gcd(fza, fmb), g2 = gcd(fma, fzb);
    fza /= g1, fmb /= g1;
    fma /= g2, fzb /= g2;
    return dfrac{fza * fzb, fma * fmb};
}

void topsort() {
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        dfrac w = water[u] * dfrac{1, out[u]};
        for (int v : e[u]) {
            water[v] = water[v] + w;
            -- in[v];
            if (!in[v]) {
                q.emplace(v);
            }
        }
    }
}

int main() {
    n = read<int>(), m = read<int>();
    int d, x;
    rep (i, 1, n, 1) {
        d = read<int>();
        out[i] = d;
        rep (j, 1, d, 1) {
            x = read<int>();
            ++ in[x];
            e[i].emplace_back(x);
        }
    }
    rep (i, 1, n, 1) {
        if (!in[i]) {
            water[i] = {1, 1};
            q.emplace(i);
        } else {
            water[i] = {0, 1};
        }
        if (!out[i]) {
            watout[i] = 1;
        }
    }
    topsort();
    ll fz, fm, g;
    rep (i, 1, n, 1) {
        if (watout[i]) {
            fz = water[i].fz, fm = water[i].fm;
            g = gcd(fz, fm);
            cout << fz / g << ' ' << fm / g << '\n';
        }
    }
    return 0;
}

[NOIP2020] 字符串匹配

题目描述

小 C 学习完了字符串匹配的相关内容，现在他正在做一道习题。

对于一个字符串 \(S\)，题目要求他找到 \(S\) 的所有具有下列形式的拆分方案数：

\(S = ABC\)，\(S = ABABC\)，\(S = ABAB \ldots ABC\)，其中 \(A\)，\(B\)，\(C\) 均是非空字符串，且 \(A\) 中出现奇数次的字符数量不超过 \(C\) 中出现奇数次的字符数量。

更具体地，我们可以定义 \(AB\) 表示两个字符串 \(A\)，\(B\) 相连接，例如 \(A = \texttt{aab}\)，\(B = \texttt{ab}\)，则 \(AB = \texttt{aabab}\)。

并递归地定义 \(A^1=A\)，\(A^n = A^{n - 1} A\)（\(n \ge 2\) 且为正整数）。例如 \(A = \texttt{abb}\)，则 \(A^3=\texttt{abbabbabb}\)。

则小 C 的习题是求 \(S = {(AB)}^iC\) 的方案数，其中 \(F(A) \le F(C)\)，\(F(S)\) 表示字符串 \(S\) 中出现奇数次的字符的数量。两种方案不同当且仅当拆分出的 \(A\)、\(B\)、\(C\) 中有至少一个字符串不同。

小 C 并不会做这道题，只好向你求助，请你帮帮他。

输入格式

本题有多组数据，输入文件第一行一个正整数 \(T\) 表示数据组数。

每组数据仅一行一个字符串 \(S\)，意义见题目描述。\(S\) 仅由英文小写字母构成。

输出格式

对于每组数据输出一行一个整数表示答案。

样例 #1

样例输入 #1

3
nnrnnr
zzzaab
mmlmmlo

样例输出 #1

8
9
16

样例 #2

样例输入 #2

5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab

样例输出 #2

156
138
138
147
194

样例 #3

样例输入 #3

见附件中的 string/string3.in

样例输出 #3

见附件中的 string/string3.ans

样例 #4

样例输入 #4

见附件中的 string/string4.in

样例输出 #4

见附件中的 string/string4.ans

提示

【样例 #1 解释】

对于第一组数据，所有的方案为

  1. \(A=\texttt{n}\)，\(B=\texttt{nr}\)，\(C=\texttt{nnr}\)。
  2. \(A=\texttt{n}\)，\(B=\texttt{nrn}\)，\(C=\texttt{nr}\)。
  3. \(A=\texttt{n}\)，\(B=\texttt{nrnn}\)，\(C=\texttt{r}\)。
  4. \(A=\texttt{nn}\)，\(B=\texttt{r}\)，\(C=\texttt{nnr}\)。
  5. \(A=\texttt{nn}\)，\(B=\texttt{rn}\)，\(C=\texttt{nr}\)。
  6. \(A=\texttt{nn}\)，\(B=\texttt{rnn}\)，\(C=\texttt{r}\)。
  7. \(A=\texttt{nnr}\)，\(B=\texttt{n}\)，\(C=\texttt{nr}\)。
  8. \(A=\texttt{nnr}\)，\(B=\texttt{nn}\)，\(C=\texttt{r}\)。

【数据范围】

测试点编号 \(\lvert S \rvert \le\) 特殊性质
\(1 \sim 4\) \(10\) 无
\(5 \sim 8\) \(100\) 无
\(9 \sim 12\) \(1000\) 无
\(13 \sim 14\) \(2^{15}\) \(S\) 中只包含一种字符
\(15 \sim 17\) \(2^{16}\) \(S\) 中只包含两种字符
\(18 \sim 21\) \(2^{17}\) 无
\(22 \sim 25\) \(2^{20}\) 无

对于所有测试点，保证 \(1 \le T \le 5\)，\(1 \le |S| \le 2^{20}\)。

用 string 乱搞，最后得到了 \(32\) 分的好成绩，大概是个 \(O_{n^4}\) 的做法。

// The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

int f(string s) {
    int num[26], cnt = 0;
    memset(num, 0, sizeof num);
    for (char c : s) {
        ++ num[c - 'a'];
    }
    rep (i, 0, 25, 1) {
        if (num[i] & 1) {
            ++ cnt;
        }
    }
    return cnt;
}

int T;
string str;

void solve() {
    int ans = 0;
    cin >> str;
    int len = str.size();
    rep (i, 1, len - 2, 1) {
        string C = str.substr(len - i, i);
        string ABi = str.substr(0, len - i);
        rep (j, 2, len - i, 1) {
            if ((len - i) % j != 0) continue ;
            string AB = ABi.substr(0, j), tmp = "";
            int K = (len - i) / j;
            rep (k, 1, K, 1) {
                tmp += AB;
            }
            if (tmp != ABi) continue ;
            rep (k, 1, j - 1, 1) {
                string A = AB.substr(0, k);
                string B = AB.substr(k, j - k);
                if (f(A) <= f(C)) {
                    ++ ans;
                }
            }
        }
    }
    cout << ans << '\n';
}

int main() {
    T = read<int>();
    while (T --) {
        solve();
    }
    return 0;
}

[NOIP2020] 移球游戏

题目描述

小 C 正在玩一个移球游戏，他面前有 \(n + 1\) 根柱子，柱子从 \(1 \sim n + 1\) 编号，其中 \(1\) 号柱子、\(2\) 号柱子、……、\(n\) 号柱子上各有 \(m\) 个球，它们自底向上放置在柱子上，\(n + 1\) 号柱子上初始时没有球。这 \(n \times m\) 个球共有 \(n\) 种颜色，每种颜色的球各 \(m\) 个。

初始时一根柱子上的球可能是五颜六色的，而小 C 的任务是将所有同种颜色的球移到同一根柱子上，这是唯一的目标，而每种颜色的球最后放置在哪根柱子则没有限制。

小 C 可以通过若干次操作完成这个目标，一次操作能将一个球从一根柱子移到另一根柱子上。更具体地，将 \(x\) 号柱子上的球移动到 \(y\) 号柱子上的要求为：

  1. \(x\) 号柱子上至少有一个球；
  2. \(y\) 号柱子上至多有 \(m - 1\) 个球；
  3. 只能将 \(x\) 号柱子最上方的球移到 \(y\) 号柱子的最上方。

小 C 的目标并不难完成，因此他决定给自己加加难度：在完成目标的基础上，使用的操作次数不能超过 \(820000\)。换句话说，小 C 需要使用至多 \(820000\) 次操作完成目标。

小 C 被难住了，但他相信难不倒你，请你给出一个操作方案完成小 C 的目标。合法的方案可能有多种，你只需要给出任意一种，题目保证一定存在一个合法方案。

输入格式

第一行两个用空格分隔的整数 \(n, m\)。分别表示球的颜色数、每种颜色球的个数。
接下来 \(n\) 行每行 \(m\) 个用单个空格分隔的整数，第 \(i\) 行的整数按自底向上的顺序依次给出了 \(i\) 号柱子上的球的颜色。

输出格式

本题采用自定义校验器（special judge）评测。
你的输出的第一行应该仅包含单个整数 \(k\)，表示你的方案的操作次数。你应保证 \(0 \le k \le 820000\)。
接下来 \(k\) 行每行你应输出两个用单个空格分隔的正整数 \(x, y\)，表示这次操作将 \(x\) 号柱子最上方的球移动到 \(y\) 号柱子最上方。你应保证 \(1 \le x, y \le n + 1\) 且 \(x \ne y\)。

样例 #1

样例输入 #1

2 3
1 1 2
2 1 2

样例输出 #1

6
1 3
2 3
2 3
3 1
3 2
3 2

样例 #2

样例输入 #2

见附件中的 ball/ball2.in

样例输出 #2

见附件中的 ball/ball2.ans

样例 #3

样例输入 #3

见附件中的 ball/ball3.in

样例输出 #3

见附件中的 ball/ball3.ans

提示

【样例 #1 解释】

柱子中的内容为：按自底向上的顺序依次给出柱子上每个球的颜色。

操作 \(1\) 号柱子 \(2\) 号柱子 \(3\) 号柱子
初始 \(1\ 1\ 2\) \(2\ 1\ 2\)
\(1\ 3\) \(1\ 1\) \(2\ 1\ 2\) \(2\)
\(2\ 3\) \(1\ 1\) \(2\ 1\) \(2\ 2\)
\(2\ 3\) \(1\ 1\) \(2\) \(2\ 2\ 1\)
\(3\ 1\) \(1\ 1\ 1\) \(2\) \(2\ 2\)
\(3\ 2\) \(1\ 1\ 1\) \(2\ 2\) \(2\)
\(3\ 2\) \(1\ 1\ 1\) \(2\ 2\ 2\)

【数据范围】

测试点编号 \(n \le\) \(m \le\)
\(1 \sim 2\) \(2\) \(20\)
\(3 \sim 5\) \(10\) \(20\)
\(6 \sim 8\) \(50\) \(85\)
\(9 \sim 14\) \(50\) \(300\)
\(15 \sim 20\) \(50\) \(400\)

对于所有测试点，保证 \(2 \le n \le 50\)，\(2 \le m \le 400\)。

【校验器】

为了方便选手测试，在附件中的 ball 目录下我们下发了 checker.cpp 文件，选手可以编译该程序，并使用它校验自己的输出文件。但请注意它与最终评测时所使用的校验器并不完全一致。你也不需要关心其代码的具体内容。

编译命令为：g++ checker.cpp −o checker -std=c++11。

checker 的使用方式为：checker <inputfile> <outputfile>，参数依次表示输入文件与你的输出文件。

若你输出的数字大小范围不合法，则校验器会给出相应提示。若你的输出数字大小范围正确，但方案错误，则校验器会给出简要的错误信息：

  1. A x，表示进行到第 \(x\) 个操作时不合法。
  2. B x，表示操作执行完毕后第 \(x\) 个柱子上的球不合法。

若你的方案正确，校验器会给出 OK。

不知道为什么总会想起喵了个喵

奔着 \(10\) 分的暴力去的，即 \(n = 2\) 的情况，结果第一次交的时候只有 \(5\) 分，有个处理有点错误，改正后就是 \(10\) 分了。

// The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

const int N = 55;
const int M = 410;
const int K = 820010;

using tii = tuple<int, int>;

int n, m, ans;
vector<int> st[N];
int cnt[N][M];
tii step[K];

void work1() {
    int col = st[2].back(), c;
    while (st[1].back() == col) {
        c = st[1].back();
        st[3].emplace_back(c);
        st[1].pop_back();
        -- cnt[1][c];
        ++ cnt[3][c];
        ++ ans;
        step[ans] = make_tuple(1, 3);
    }
    while (st[2].back() == col) {
        c = st[2].back();
        st[3].emplace_back(c);
        st[2].pop_back();
        -- cnt[2][c];
        ++ cnt[3][c];
        ++ ans;
        step[ans] = make_tuple(2, 3);
    }
}

void getans() {
    int x;
    while (!st[2].empty()) {
        x = st[2].back();
        st[1].emplace_back(x);
        st[2].pop_back();
        ++ ans;
        step[ans] = make_tuple(2, 1);
    }
}

void print() {
    cout << ans << '\n';
    rep (i, 1, ans, 1) {
        cout << get<0>(step[i]) << ' ' << get<1>(step[i]) << '\n';
    }
}

void work2() {
    while (cnt[1][st[3].front()]) {
        if (st[1].back() != st[3].front()) {
            if (st[2].size() < m - 1) {
                st[2].emplace_back(st[1].back());
                -- cnt[1][st[1].back()];
                ++ cnt[2][st[1].back()];
                st[1].pop_back();
                ++ ans;
                step[ans] = make_tuple(1, 2);
            } else {
                st[3].emplace_back(st[1].back());
                -- cnt[1][st[1].back()];
                ++ cnt[3][st[1].back()];
                st[1].pop_back();
                ++ ans;
                step[ans] = make_tuple(1, 3);
            }
        } else {
            if (st[2].size() >= m - 1) {
                st[2].emplace_back(st[1].back());
                ++ cnt[2][st[1].back()];
                -- cnt[1][st[1].back()];
                st[1].pop_back();
                ++ ans;
                step[ans] = make_tuple(1, 2);
                while (st[3].back() != st[3].front()) {
                    ++ ans;
                    step[ans] = make_tuple(3, 1);
                    st[1].emplace_back(st[3].back());
                    ++ cnt[1][st[3].back()];
                    -- cnt[3][st[3].back()];
                    st[3].pop_back();
                }
                ++ ans;
                step[ans] = make_tuple(2, 3);
                st[3].emplace_back(st[2].back());
                ++ cnt[3][st[2].back()];
                -- cnt[2][st[2].back()];
                st[2].pop_back();
            } else {
                st[3].emplace_back(st[1].back());
                ++ cnt[3][st[1].back()];
                -- cnt[1][st[1].back()];
                st[1].pop_back();
            }
        }
    }
}

void work3() {
    int u;
    while (!st[2].empty()) {
        u = st[2].back();
        if (u == st[3].front()) {
            ++ ans;
            step[ans] = make_tuple(2, 3);
            st[2].pop_back();
        } else {
            ++ ans;
            step[ans] = make_tuple(2, 1);
            st[2].pop_back();
        }
    }
}

int main() {
    n = read<int>(), m = read<int>();
    int col;
    rep (i, 1, n, 1) {
        rep (j, 1, m, 1) {
            col = read<int>();
            st[i].emplace_back(col);
            ++ cnt[i][col];
        }
    }
    work1();
    if (cnt[3][st[3].back()] == m) {
        getans();
        print();
        return 0;
    }
    work2();
    work3();
    print();
    return 0;
}

[NOIP2020] 微信步数

题目描述

小 C 喜欢跑步，并且非常喜欢在微信步数排行榜上刷榜，为此他制定了一个刷微信步数的计划。

他来到了一处空旷的场地，处于该场地中的人可以用 \(k\) 维整数坐标 \((a_1, a_2, \ldots , a_k)\) 来表示其位置。场地有大小限制，第 \(i\) 维的大小为 \(w_i\)，因此处于场地中的人其坐标应满足 \(1 \le a_i \le w_i\)（\(1 \le i \le k\)）。

小 C 打算在接下来的 \(P = w_1 \times w_2 \times \cdots \times w_k\) 天中，每天从场地中一个新的位置出发，开始他的刷步数计划（换句话说，他将会从场地中每个位置都出发一次进行计划）。

他的计划非常简单，每天按照事先规定好的路线行进，每天的路线由 \(n\) 步移动构成，每一步可以用 \(c_i\) 与 \(d_i\) 表示：若他当前位于 \((a_1, a_2, \ldots , a_{c_i}, \ldots, a_k)\)，则这一步他将会走到 \((a_1, a_2, \ldots , a_{c_i} + d_i, \ldots , a_k)\)，其中 \(1 \le c_i \le k\)，\(d_i \in \{-1, 1\}\)。小 C 将会不断重复这个路线，直到他走出了场地的范围才结束一天的计划。（即走完第 \(n\) 步后，若小 C 还在场内，他将回到第 \(1\) 步从头再走一遍）。

小 C 对自己的速度非常有自信，所以他并不在意具体耗费的时间，他只想知道 \(P\) 天之后，他一共刷出了多少步微信步数。请你帮他算一算。

输入格式

第一行两个用单个空格分隔的整数 \(n, k\)。分别表示路线步数与场地维数。
接下来一行 \(k\) 个用单个空格分隔的整数 \(w_i\)，表示场地大小。
接下来 \(n\) 行每行两个用单个空格分隔的整数 \(c_i, d_i\)，依次表示每一步的方向，具体意义见题目描述。

输出格式

仅一行一个整数表示答案。答案可能很大，你只需要输出其对 \({10}^9 + 7\) 取模后的值。
若小 C 的计划会使得他在某一天在场地中永远走不出来，则输出一行一个整数 \(-1\)。

样例 #1

样例输入 #1

3 2
3 3
1 1
2 -1
1 1

样例输出 #1

21

样例 #2

样例输入 #2

5 4
6 8 6 5
3 1
2 1
1 1
2 1
2 -1

样例输出 #2

10265

样例 #3

样例输入 #3

见附件中的 walk/walk3.in

样例输出 #3

见附件中的 walk/walk3.ans

样例 #4

样例输入 #4

见附件中的 walk/walk4.in

样例输出 #4

见附件中的 walk/walk4.ans

提示

【样例 #1 解释】

从 \((1, 1)\) 出发将走 \(2\) 步，从 \((1, 2)\) 出发将走 \(4\) 步，从 \((1, 3)\) 出发将走 \(4\) 步。
从 \((2, 1)\) 出发将走 \(2\) 步，从 \((2, 2)\) 出发将走 \(3\) 步，从 \((2, 3)\) 出发将走 \(3\) 步。
从 \((3, 1)\) 出发将走 \(1\) 步，从 \((3, 2)\) 出发将走 \(1\) 步，从 \((3, 3)\) 出发将走 \(1\) 步。
共计 \(21\) 步。

【数据范围】

测试点编号 \(n \le\) \(k \le\) \(w_i \le\)
\(1 \sim 3\) \(5\) \(5\) \(3\)
\(4 \sim 6\) \(100\) \(3\) \(10\)
\(7 \sim 8\) \({10}^5\) \(1\) \({10}^5\)
\(9 \sim 12\) \({10}^5\) \(2\) \({10}^6\)
\(13 \sim 16\) \(5 \times {10}^5\) \(10\) \({10}^6\)
\(17 \sim 20\) \(5 \times {10}^5\) \(3\) \({10}^9\)

对于所有测试点，保证 \(1 \le n \le 5 \times {10}^5\)，\(1 \le k \le 10\)，\(1 \le w_i \le {10}^9\)，\(d_i \in \{-1, 1\}\)。

好好的一个题让我做成大模拟

\(O_{n^5}\) 的暴力，加上判断 \(-1\) 的情况，最后得到了 \(35\) 分的好成绩。

// The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

const int N = 5e5 + 5;
const int K = 15;
const int mod = 1e9 + 7;

int n, k;
ll ans;
ll w[K];
int c[N], d[N], change[K];

bool check(int i1, int i2, int i3, int i4, int i5) {
    if (i5 == -1e9) {
        if (i4 == -1e9) {
            if (i3 == -1e9) {
                if (i2 == -1e9) {
                    if (i1 < 1 || i1 > w[1]) {
                        return 0;
                    } else {
                        return 1;
                    }
                } else {
                    if ((i1 < 1 || i1 > w[1]) || (i2 < 1 || i2 > w[2])) {
                        return 0;
                    } else {
                        return 1;
                    }
                }
            } else {
                if ((i1 < 1 || i1 > w[1]) || (i2 < 1 || i2 > w[2]) || (i3 < 1 || i3 > w[3])) {
                    return 0;
                } else {
                    return 1;
                }
            }
        } else {
            if ((i1 < 1 || i1 > w[1]) || (i2 < 1 || i2 > w[2]) || (i3 < 1 || i3 > w[3]) || (i4 < 1 || i4 > w[4])) {
                return 0;
            } else {
                return 1;
            }
        }
    } else {
        if ((i1 < 1 || i1 > w[1]) || (i2 < 1 || i2 > w[2]) || (i3 < 1 || i3 > w[3]) || (i4 < 1 || i4 > w[4]) || (i5 < 1 || i5 > w[5])) {
            return 0;
        } else {
            return 1;
        }
    }
}

void dfs(int i1, int i2, int i3, int i4, int i5) {
    int cnt = 0;
    while (check(i1, i2, i3, i4, i5)) {
        rep (i, 1, n, 1) {
            if (c[i] == 1) {
                i1 += d[i];
            }
            if (c[i] == 2) {
                i2 += d[i];
            }
            if (c[i] == 3) {
                i3 += d[i];
            }
            if (c[i] == 4) {
                i4 += d[i];
            }
            if (c[i] == 5) {
                i5 += d[i];
            }
            ++ ans;
            ans %= mod;
            if (!check(i1, i2, i3, i4, i5)) {
                break ;
            }
        }
    }
}

int main() {
    n = read<int>(), k = read<int>();
    rep (i, 1, k, 1) {
        w[i] = read<int>();
    }
    rep (i, 1, n, 1) {
        c[i] = read<int>(), d[i] = read<int>();
        change[c[i]] += d[i];
    }
    int fg = 1;
    rep (i, 1, k, 1) {
        fg = (fg & (!change[i]));
    }
    if (fg) {
        puts("-1");
        return 0;
    }
    rep (i1, 1, w[1], 1) {
        if (k >= 2) {
            rep (i2, 1, w[2], 1) {
                if (k >= 3) {
                    rep (i3, 1, w[3], 1) {
                        if (k >= 4) {
                            rep (i4, 1, w[4], 1) {
                                if (k >= 5) {
                                    rep (i5, 1, w[5], 1) {
                                        dfs(i1, i2, i3, i4, i5);
                                    }
                                } else {
                                    dfs(i1, i2, i3, i4, -1e9);
                                }
                            }
                        } else {
                            dfs(i1, i2, i3, -1e9, -1e9);
                        }
                    }
                } else {
                    dfs(i1, i2, -1e9, -1e9, -1e9);
                }
            }
        } else {
            dfs(i1, -1e9, -1e9, -1e9, -1e9);
        }
    }
    cout << ans << '\n';
    return 0;
}

标签：结点,le,NOIP,texttt,样例,back,st,解题,2020
From： https://www.cnblogs.com/yifan0305/p/17723279.html

相关文章

  • BUUCTF Reverse/[NPUCTF2020]你好sao啊
    里面就一个加密函数，分析后发现这是一段变表的base解密，将四个字符替换成三个字符点击查看代码void*__fastcallRxEncode(constchar*a1,inta2){intv3;//[rsp+18h][rbp-38h]intv4;//[rsp+1Ch][rbp-34h]intv5;//[rsp+20h][rbp-30h]intv6;//[rsp+2......
  • 《从0到1的CTF成长之路》1.1.1 常见的搜集 解题过程
    纯新手，写题日记，不是Writeup！随便摸索dockerps发现有端口80直接用浏览器打开127.0.0.1:80解题试试书里教的工具scrabblegitclonehttps://github.com/denny0223/scrabble.git./scrabble127.0.0.1...fatal:notagitrepository(oranyoftheparentdirectori......
  • P7200 [COCI2019-2020#1] Lutrija
    发现相邻的奇数只能恰好差\(2\)（偶质数只有\(2\)）。而大于\(3\)的三个连续奇数至多有两个是质数，因为有一个能被\(3\)整除。对于357这三个数，我们可以构造成3527以归入下面的构造方法。所以相邻的奇数最多只有两个。但我们可以放偶质数\(2\)。显然，放多个\(2\)肯......
  • 已解决 File “F:\File_Anaconda\2020CV\yolov5-master\20200701.py“, line 5 Sy
    已解决File“F:\File_Anaconda\2020CV\yolov5-master\20200701.py”,line5SyntaxError:Non-UTF-8codestartingwith‘\xc0’infileF:\File_Anaconda\2020CV\yolov5-master\20200701.pyonline5,butnoencodingdeclared;seehttp://python.org/dev/peps/pe......
  • Buuctf——[网鼎杯 2020 青龙组]AreUSerialz
    这是一道序列化的题目<?phpinclude("flag.php");highlight_file(__FILE__);classFileHandler{protected$op;protected$filename;protected$content;function__construct(){$op="1";$filename="/......
  • P1075 [NOIP2012 普及组] 质因数分解
    算法一根据唯一分解定理，小于\(n\)的最大的能整除\(n\)的整数一定就是答案，可以暴力枚举。时间复杂度\(O(n)\)，实际得分\(60\)。算法二发现算法一不能通过的原因是较大的那个质数可能的取值范围太大了。而较小的那个质数一定小于等于\(\sqrtn\)，我们枚举它即可。时间复......
  • [NOIP2012 普及组] 摆花
    [NOIP2012普及组]摆花[NOIP2012普及组]摆花题意有\(n\)个数，每种可以选\(0\lex_i\lea_i\)个，问有多少种方法可以使得\(\sum_{i=1}^nx_i=m\)。Solution1.深搜\(dfs\)显然可以先暴力深搜。#include"bits/stdc++.h"usingnamespacestd;constintmaxn=......
  • P1024 [NOIP2001 提高组] 一元三次方程求解
    因为精度要求很低，所以有一个暴力的想法就是枚举区间内相差很小的两个数然后判断。保留两位小数后记得判重。考虑优化。发现根与根差的绝对值大于等于\(1\)这个条件没有利用。有了这个条件我们发现相邻两个整数之间（不包含端点）最多有一个根。于是可以先判掉整数然后在区间内有根......
  • 2020ICPC区域赛南京站
    2020ICPC区域赛南京站KCo-primePermutation解题思路:首先，根据样例2不难发现，\(k\)的下界为\(1\)，因为1和排列中的任何数都会互质。其次，我们考虑下上界大概是多少，也就是\(k=n\)是否一定合法。假设，我们有一个初识排列\(p_i=i\).此时我们有\(1\)个元素和他的下标互质。根据......
  • 揭秘ES2020令人兴奋的语言特性
    大家好！我是星辰编程理财。今天我分享一篇关于ES2020（ES11）的文章，它将介绍ES2020的语言特性和功能，包括可选链操作符、空值合并操作符、Promise.allSettled()、import.meta等等。通过故事形式以及详细的阐述和示例，带领大家一起探索这些特性的用处，作为刚入门的新手，它能让你能够在前端开......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99