Q779’s Blog

洛谷P1363 幻象迷宫 题解 题目链接：P1363 幻象迷宫 题意： 幻象迷宫可以认为是无限大的，不过它由若干个 \(n \times m\) 的矩阵重复组成。矩阵中有的地方是道路，用 . 表示；有的地方是墙，用 # 表示。cxy 和 q779 所在的位置用 S 表示。也就是对于迷宫中的一个点 \((x,y)\) ，如果 \((x \bmod n, ~y \bmod m)\) 是. 或者 S，那么这个地方是道路；如果 \((x \bmod n,~y \bmod m)\) 是 #，那么这个地方是墙。cxy 和 q779 可以向上下左右四个方向移动，当然不能移动到墙上。 请你告诉 cxy 和 q779，它们能否走出幻象迷宫（如果它们能走到距离起点无限远处，就认为能走出去）。如果不能的话，cxy 就只好启动城堡的毁灭程序了……当然不到万不得已，她不想这么做。。。 输入格式： 输入包含多组数据，以EOF结尾。 每组数据的第一行是两个整数 \(n,m\) 。 接下来是一个 \(n\times m\) 的字符矩阵，表示迷宫里 \((0,0)\) 到 \((n-1,m-1)\) 这个矩阵单...

C++语法-vector 这篇文章来讲下我在 OI 中遇到的 vector 的用法，本文基于 C++14 。 一、vector 底层相关 vector 是封装动态数组的顺序容器，并且是连续存储的，因此除了迭代器，还可以通过指针访问。 vector 的存储是自动管理的，按需扩张收缩，因此内存占用会较多于静态数组。 vector 所用的方式不是在每次插入元素时，而只在额外内存耗尽时重分配，也就是装不下的时候再扩充一定量。 我们可以用 capacity() 函数查询分配的内存总量，还可以用 shrink_to_fit() 返回多出的内存给系统。 vector<int> a(15); // 初始化为15个元素 vector<int> b; // 初始为空 // capacity（意思是“容量”） 查询占用内存，返回的是元素个数 // 值得注意的是，占用内存分配方式取决于标准库的实现方式，不过一定有 占用内存 ≥ 使用内存 cout << (int)a.capacity() << ' ' << (int)b.capacity() <...

洛谷P2886 [USACO07NOV]Cow Relays G 题解 题目链接：P2886 [USACO07NOV]Cow Relays G 题意： 给定一张 \(T\) 条边的无向连通图，求从 \(S\) 到 \(E\) 经过 \(N\) 条边的最短路长度。 输入格式： 第一行四个正整数 \(N,T,S,E\) ，意义如题面所示。 接下来 \(T\) 行每行三个正整数 \(w,u,v\) ，分别表示路径的长度，起点和终点。 输出格式： 一行一个整数表示图中从 \(S\) 到 \(E\) 经过 \(N\) 条边的最短路长度。 数据范围： 对于所有的数据，保证 \(1\le N\le 10^6\)，\(2\le T\le 100\)。 所有的边保证 \(1\le u,v\le 1000\)，\(1\le w\le 1000\)，无重边。 这道题考察了无向图邻接矩阵的性质。 如果矩阵 \(A\) 表示走了 \(x\) 步的最短路，矩阵 \(B\) 表示走了 \(y\) 步的最短路， \[ C_{i,j} \downarrow A_{i,k} + B_{k,j} \] 矩阵 \(...

洛谷P5789 [TJOI2017]可乐 题解 题目链接：P5789 [TJOI2017]可乐（数据加强版） （双倍经验：P3758） 题意： 加里敦星球的人们特别喜欢喝可乐。因而，他们的敌对星球研发出了一个可乐机器人，并且放在了加里敦星球的 \(1\) 号城市上。这个可乐机器人有三种行为： 停在原地，去下一个相邻的城市，自爆。它每一秒都会随机触发一种行为。现在给加里敦星球城市图，在第 \(0\) 秒时可乐机器人在 \(1\) 号城市，问经过了 \(t\) 秒，可乐机器人的行为方案数是多少？ 输入格式： 第一行输入两个正整数 \(N,M\) ，\(N\) 表示城市个数，\(M\) 表示道路个数。 接下来 \(M\) 行输入 \(u,v\) ，表示 \(u,v\) 之间有一条双向道路。 最后输入时间 \(t\) 。 输出格式： 输出可乐机器人的行为方案数，答案可能很大，请输出对 \(2017\) 取模后的结果。 数据范围： \(n,m\leq 100,~t\leq 10^9\) 。 朴素的无向图邻接矩阵快速幂，自爆的话，加个虚点“天堂”就好啦~ 注意每个点要连自环，并且向虚点的...

洛谷P3216 [HNOI2011]数学作业 题解 题目链接：P3216 [HNOI2011]数学作业 题意： 小 C 数学成绩优异，于是老师给小 C 留了一道非常难的数学作业题： 给定正整数 \(n,m\)，要求计算 \(\text{Concatenate}(n) \bmod \ m\) 的值，其中 \(\text{Concatenate}(n)\) 是将 \(1 \sim n\) 所有正整数 顺序连接起来得到的数。 例如，\(n = 13\) , \(\text{Concatenate}(n) = 12345678910111213\)。 小 C 想了大半天终于意识到这是一道不可能手算出来的题目，于是他只好向你求助，希望你能编写一个程序帮他解决这个问题。 输入格式： 一行两个正整数 \(n,m\)。 输出格式： 输出一行一个整数表示答案。 数据范围： \(1\le n \le 10^{18},~1\le m \le 10^9\)。 设 \(f_{i}\) 表示前 \(i\) 个数拼起来的答案，则 \[ \large f_{i} = f_{i-1} \times 10^{\...

洛谷P5678 [GZOI2017]河神 题解 题目链接：P5678 [GZOI2017]河神 题意： cxy 从河神给的选择中，获得了一道当年挂掉的代数题的灵感。 但现在他希望你来帮忙解答，因为他自己忙着去搜妹纸资源去了。 给出数列 \(\{a_n\}\) 和 \(\{b_n\}\) 以及 \(\{A_n\}\) 的递推关系，试求出数列 \(\{A_n\}\) 第 \(N\) 项。 递推关系为： \[ A_n=\begin{cases}a_n & 0 \le n < K \\[8pt] \bigoplus (A_{n-K+t} \otimes b_t) & n \ge K \end{cases} \] 其中，\(\otimes\) 表示与操作，\(\oplus\) 表示或操作。 输入格式： 第一行两个正整数 \(N\) 和 \(K\) 。 第二行 \(K\) 个空格隔开的非负整数，表示 \(\{a_n\}\)。 第三行 \(K\) 个空格隔开的非负整数，表示 \(\{b_n\}\)。 输出格式： 一行，一个整数，表示\(\{A_n\}\)。 数据范围...

洛谷P1707 刷题比赛 题解 题目链接：P1707 刷题比赛 题意： 洛谷OJ当然算是好地方，nodgd 同学打算和朋友分享一下。于是他就拉上了他的朋友 Ciocio 和 Nicole 两位同学一起刷题。喜欢比赛的他们当然不放过这样一次刷题比赛的机会！ 在第 \(1\) 天 nodgd,Coicoi,Nicole 都只做了 \(1\) 道题。 在第 \(2\) 天 nodgd,Coicoi,Nicole 都只做了 \(3\) 道题。 他们都有着严格的刷题规则，并且会在每一天都很遵守规则的刷一定量的题。 nodgd 同学第 \(k+2\) 天刷题数量 \[ a_{k+2}=pa_{k+1}+qa_k+b_{k+1}+c_{k+1}+rk^2+tk+1 \] Ciocio 同学第 \(k+2\) 天刷题数量 \[ b_{k+2}=ub_{k+1}+vb_k+a_{k+1}+c_{k+1}+w^k \] Nicole 同学第 \(k+2\) 天刷题数量 \[ c_{k+2} = xc_{k+1}+yc_k + a_{k+1} + b_{k+1} + z^k+k+2 \] （以上...

洛谷P4838 P哥破解密码 题解 题目链接：P4838 P哥破解密码 题意： 定义一个串合法，当且仅当串只由 \(\tt{A}\) 和 \(\tt{B}\) 构成，且没有连续的 \(3\) 个 \(\tt{A}\) 。 P哥知道，密码就是长度为 \(N\) 的合法字符串数量对\(19260817\)取模的结果。 但是P哥不会算，所以他只能把 \(N\) 告诉你，让你来算 至于为什么要对这个数取模，好像是因为纪念某个人，但到底是谁，P哥也不记得了 然而他忘记字符串长度 \(N\) 应该是多少了，于是他准备试 \(M\) 组数据。 输入格式： 第一行给出一个整数 \(M\) 表示询问次数 接下来M行每行给出一个正整数 \(N\) ，表示该组询问中字符串的长度 输出格式： 对于每一次询问输出一行一个整数表示答案 数据范围： \(N\leq 10^9,~M\leq 10\) 设 \(f_{i,j}\) 表示长度为 \(i\) 的字符串，有长为 \(j(j = 0,1,2)\) 的后缀全为 \(\tt{A}\) ，则 \[ f_{i,0} = f_{i - 1,0} + f_{i -...

洛谷P2151 [SDOI2009] HH去散步 题解 题目链接：P2151 [SDOI2009] HH去散步 题意： HH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间 内，走过一定的距离。 但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。 又因为HH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多 少种散步的方法。 现在给你学校的地图（假设每条路的长度都是一样的都是 \(1\) ），问长度为 \(t\) ，从给定地点 \(A\) 走到给定地点 \(B\) 共有多少条符合条件的路径 输入格式： 第一行：五个整数 \(n,m,t,A,B\)。其中 \(n\) 表示学校里的路口的个数， \(m\) 表示学校里的路的条数，\(t\) 表示HH想要散步的距离，\(A\) 表示散步的出发点，而 \(B\) 则表示散步的终点。 接下来 \(m\) 行，每行一组 \(A_i,B_i\) ，表示从路口 \(A_i\) 到路口 \(B_i\) 有一条路。数据保证 \(A_i \ne B_i\) ，但不保证任意两个路口之间至多...

2023年01月31日 随笔 大年初五的晚上拍的烟花，挺好看的。

洛谷P7395 弹珠游戏 题解 题目链接：P7395 弹珠游戏（2021 CoE-I C） 题意： \(\operatorname{Alice}\) 对弹珠游戏已经有些厌烦了，她经常在电脑上玩这个游戏。她之所以感到厌烦是因为在这个游戏上她已经是专家级别，她总是能够和电脑打成平手。\(\operatorname{Bob}\) 为 \(\operatorname{Alice}\) 创造了一款新的电脑游戏。以下是这款两人电脑游戏的规则： （1）游戏在如下图所示的菱形棋盘上进行； （2）两名玩家轮流放置弹珠，可以在横向、纵向、\(45\) 度斜线、\(135\) 度斜线方向未放置弹珠的位置连续放置 \(1\) 至 \(3\) 颗弹珠，玩家在可以放置弹珠的情况下，必须至少放置 \(1\) 颗弹珠。以下是合法的单次放置操作的示例（黑色圆点表示放置了弹珠，白色圆点表示未放置弹珠，进行该次操作前棋盘为空）： 以下是非法的单次放置操作的示例（黑色圆点表示放置了弹珠，白色圆点表示未放置弹珠，进行该次操作前棋盘为空）： 非法原因的解释：（\(a\)）三颗弹珠不在同一条斜线（或者垂直线）上；（\...

lsof 查看端口占用 lsof 是一个 shell 指令，用于列出当前系统打开的文件。 lsof 查看端口占用的语法格式如下： lsof -i:[端口号] 在 Linux 上需要 root 权限，而 MacOS 上不需要。 例：查看电脑 4000 端口的占用情况： % lsof -i:4000 COMMAND PID USER FD TYPE DEVICE SIZE/OFF NODE NAME node 64950 qry 42u IPv6 0x71ca5fa9e8b96e4d 0t0 TCP *:terabase (LISTEN) 可以发现 4000 端口已经被 nodejs 服务占用（其实是我博客的本地调试端口） 输出信息的意义如下： 其他 lsof 的命令如下： lsof -i:8080 # 查看 8080 端口的占用 lsof abc.txt # 显示开启文件 abc.txt 的进程 lsof -c abc # 显示 abc 进程现在打开的文件 lsof...