洛谷站内题库题解

前言

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

正文

$\texttt{B2001}$ 入门测试题目

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

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

Code

CPP

#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

CPP

#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

CPP

#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++

CPP

#include <iostream>

using namespace std;

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

Pascal

PASCAL

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

Java

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

PYTHON

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，

CPP

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）

CPP

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}

CPP

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

CPP

#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

CPP

#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]$ 阶乘之和

高精度？

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

CPP

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

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

CPP

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 字符）

CPP

#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百

$\texttt{Update 2025.05.24}$ ：添加了 $\texttt{P1003}$ 的详解。
$\texttt{Update 2025.06.03}$ ：添加了 $\texttt{P1009}$ 的详解。
$\texttt{Update 2025.06.08}$ ：添加了 $\texttt{B2001,B2002,B2007}$ 。

\hspace{9.2cm}

孤帆

\hspace{2pt}

写于北京

洛谷站内题库题解

文章操作

前言

正文

$\texttt{B2001}$ 入门测试题目

$\texttt{B2002 Hello,World!}$

$\texttt{B2007 A + B}$ 问题

$\texttt{P1000}$ 超级玛丽游戏

$\texttt{P1001 A + B Problem}$

$\texttt{P1002}$ 过河卒

$\texttt{P1003}$ 铺地毯

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

后记

相关推荐

评论

洛谷站内题库题解