洛谷站内题库题解

· · 算法·理论

前言

有些题不会（一点也不会），就不写了，欢迎补充。
引用部分将会注明来源和链接。

正文

\texttt{B2001} 入门测试题目

——这道题这么简单你讲个毛线啊？！

简单吗？好吧，这确实很简单。

Code

#include <iostream>
#define int long long

using namespace std;

int a, b;

signed main() {
    cin >> a >> b;
    cout << a + b;
    return 0;
}

\texttt{B2002 Hello,World!}

Code

#include <cstdio>

int main() {    
    printf ("Hello,World!");    
    return 0; 
}

\texttt{B2007 A + B} 问题

见 \texttt{P1001}。

\texttt{P1000} 超级玛丽游戏

参考 @lin_toto の 题解 \color{E8E8E8}\texttt{link}

C 语言中 printf 的多行输出。

Code

#include <stdio.h>

int main() {
    printf(
    "                ********\n"
    "               ************\n"
    "               ####....#.\n"
    "             #..###.....##....\n"
    "             ###.......######              ###            ###\n"
    "                ...........               #...#          #...#\n"
    "               ##*#######                 #.#.#          #.#.#\n"
    "            ####*******######             #.#.#          #.#.#\n"
    "           ...#***.****.*###....          #...#          #...#\n"
    "           ....**********##.....           ###            ###\n"
    "           ....****    *****....\n"
    "             ####        ####\n"
    "           ######        ######\n"
    "##############################################################\n"
    "#...#......#.##...#......#.##...#......#.##------------------#\n"
    "###########################################------------------#\n"
    "#..#....#....##..#....#....##..#....#....#####################\n"
    "##########################################    #----------#\n"
    "#.....#......##.....#......##.....#......#    #----------#\n"
    "##########################################    #----------#\n"
    "#.#..#....#..##.#..#....#..##.#..#....#..#    #----------#\n"
    "##########################################    ############\n"
    );
    return 0;
}

复杂度就算了，这题所有AC代码都不会 T （吧） 。。。

\texttt{P1001 A + B Problem}

Code
C

#include <stdio.h>

int main() {
    int a, b;
    scanf ("%d%d", &a, &b);
    printf ("%d%d", a, b);
    return false;
}

C++

#include <iostream>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << a + b;
    return 0;
}

Pascal

var a, b: longint;
begin
    readln(a, b);
    writeln(a + b);
end.

Java

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String args[]) throws Exception {
        Scanner cin=new Scanner(System.in);
        int a = cin.nextInt(), b = cin.nextInt();
        System.out.println(a + b);
    }
}

Python3

s = input().split()
print(int(s[0]) + int(s[1]))

C# Mono

using System;

public class APlusB {
    private static void Main() {
        string[] input = Console.ReadLine().Split(' ');
        Console.WriteLine(int.Parse(input[0]) + int.Parse(input[1]));
    }
}

我只能说，只要不输出提示文本，就不会 Wrong Answer。

\texttt{P1002} 过河卒

这是一道很好的 DP 题。
由于答案有“亿点点”大，需要 long long。
bool c[25][25] 中，c_{x,y} 表示点 (x,y) 是否是 C 点的马的控制点。那么我们该如何维护呢？
先全部初始化为 true，

for (i = 0; i <= n; i++)
    for (j = 0; j <= m; j++)
        c[i][j] = true;

遍历马的八种移动，设第 i 种移动有 c_{x+dx_i,y+dy_i}=\text{false}。（人话：把马的控制点的 c_{i,j} 设为 false）

for (i = 0; i <= 8; i++) {
    int a = x + dx[i], b = y + dy[i];
    if (0 <= a && a <= n && 0 <= b && b <= m)
        c[a][b] = false;
}

套入式：

\\\newline \begin{aligned} \qquad&\text{if }i\neq0\:&f_{i,j}=f_{i,j}+f_{i-1,j}\\ &\text{if }j\neq0&f_{i,j}=f_{i,j}+f_{i,j-1}\\ &\text{if not }c_{i,j}&f_{i,j}=0\qquad\qquad\; \end{aligned} 
for (i = 0; i <= n; i++)
    for (j = 0; j <= m; j++) {
        if (i != 0) f[i][j] += f[i - 1][j];
        if (j != 0) f[i][j] += f[i][j - 1];
        if (!c[i][j]) f[i][j] = 0;
    }

Code

#include <iostream>

using namespace std;

const int dx[9] = {0, -1, -2, -2, -1, 1, 2, 2, 1};
const int dy[9] = {0, -2, -1, 1, 2, -2, -1, 1, 2};
long long n, m, x, y, f[25][25], i, j;
bool c[25][25];
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
int main() {
    n = read(); m = read();
    x = read(); y = read();
    for (i = 0; i <= n; i++)
        for (j = 0; j <= m; j++)
            c[i][j] = true;
    for (i = 0; i <= 8; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (0 <= a && a <= n && 0 <= b && b <= m)
            c[a][b] = false;
    }
    f[0][0] = 1;
    for (i = 0; i <= n; i++)
        for (j = 0; j <= m; j++) {
            if (i != 0) f[i][j] += f[i - 1][j];
            if (j != 0) f[i][j] += f[i][j - 1];
            if (!c[i][j]) f[i][j] = 0;
        }
    cout << f[n][m];
    return 0;
}

\texttt{P1003} 铺地毯

说实话，我一开始没读懂题......

注意遵循一个物理原则：后铺的地毯会盖在上面。

思路：直接模拟，每铺一块地毯就将地毯覆盖的范围改成地毯的编号。

但是显然不是最优，时间复杂度是 O(n\sum^{g_1k_1}_{g_nk_n}) 的。

所以考虑到只维护访问位置，接下来枚举每块地毯，如果被第 i 块地毯覆盖，就替换成这块地毯的编号。

这样时间复杂度显然是 O(n) 的。

Code

#include <iostream>

using namespace std;

int n, ans = -1, x, y, i;

struct N {
    int a, b, g, k;
}c[ 100005 ];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> c[i].a >> c[i].b >> c[i].g >> c[i].k;
    cin >> x >> y;
    for (i = 1; i <= n; i++)
        if (x >= c[i].a && x <= c[i].a + c[i].g && y >= c[i].b && y <= c[i].b + c[i].k)
            ans = i;
    cout << ans;
    return 0;
}

\texttt{P1009 [NOIP 1998} 普及组\texttt] 阶乘之和

高精度？

套模板！！！！！！！！！！！！

struct Bigint {
    int len, a[100];
    Bigint(int x = 0) {
        memset(a, 0, sizeof(a));
        for (len = 0; x; len++)
            a[len] = x % 10, x /= 10;
    }
    int &operator[](int i) { return a[i]; }
    void flatten(int L) {
        len = L;
        for (int i = 0; i < len; i++)
            a[i + 1] += a[i] / 10, a[i] %= 10;
        for (; len >= 1 && !a[len - 1]; )
            len--;
    }
    void print() {
        for (int i = max(len - 1, 0); i >= 0; i--)
            printf ("%d", a[i]);
    }
};

接下来高精度必做——重导运算符！

Bigint operator*(Bigint &a, int b) {
    Bigint c;
    int len = a.len;
    for (int i = 0; i < len; i++)
        c[i] = c[i] + a[i] * b;
    c.flatten(len + 11);
    return c;
}
Bigint operator+(Bigint &a, Bigint &b) {
    Bigint c;
    int len = max(a.len, b.len);
    for (int i = 0; i < len; i++)
        c[i] += a[i] + b[i];
    c.flatten(len + 1);
    return c;
}

Code（1000 字符）

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

struct Bigint {
    int len, a[100];
    Bigint(int x = 0) {
        memset(a, 0, sizeof(a));
        for (len = 0; x; len++)
            a[len] = x % 10, x /= 10;
    }
    int &operator[](int i) { return a[i]; }
    void flatten(int L) {
        len = L;
        for (int i = 0; i < len; i++)
            a[i + 1] += a[i] / 10, a[i] %= 10;
        for (; len >= 1 && !a[len - 1];)
            len--;
    }
    void print() {
        for (int i = max(len - 1, 0); i >= 0; i--)
            printf ("%d", a[i]);
    }
};

Bigint operator*(Bigint &a, int b) {
    Bigint c;
    int len = a.len;
    for (int i = 0; i < len; i++)
        c[i] = c[i] + a[i] * b;
    c.flatten(len + 11);
    return c;
}
Bigint operator+(Bigint &a, Bigint &b) {
    Bigint c;
    int len = max(a.len, b.len);
    for (int i = 0; i < len; i++)
        c[i] += a[i] + b[i];
    c.flatten(len + 1);
    return c;
}

int main() {
    Bigint ans(0), fac(1);
    int m;
    cin >> m;
    for (int i = 1; i <= m; i++) {
        fac = fac * i;
        ans = ans + fac;
    }
    ans.print();
    return 0;
}

后记

字数：8千

行数：3百