题解joisc 2019

# CF1863D Two-Colored Dominoes 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/CF1863D) [Codeforces](https://codeforces.com/problemset/problem/1863/ ......

之前整理的时候忘记写，现在补上。 # 思路 拉插求自然数幂和。 关于自然数幂和 $\sum\limits_{i = 1}^n i^k$，已知是关于 $n$ 的 $k + 1$ 次多项式，可以用伯努利数 $O(k \log k)$ 求，也可以直接拉插 $O(k)$ 求。 拉插结论：若一个 $n$ 次多 ......

[题目链接](https://www.luogu.com.cn/problem/AT_agc004_d) 躺在床上想到重要性质的题目。。。 首先，由于每个城市只有一个可以直接到达的城市，所以 $n$ 个城市就有 $n$ 条边，容易发现这是一棵基环树，那么我们先从普通树的角度考虑，若要求每个点走 $k ......

## 题意 有一棵有 $n$ 个节点的树，第 $i$ 个节点有点权 $a_i$。 定义 $g(x,y)$ 为 $x$ 到 $y$ 的树上路径所经过的点的点权 $\gcd$。 对于每一个正整数 $k\in[1,2\times 10^5]$ 求出满足以下条件的 $x,y$ 的对数: + $1\le x\ ......

## 题意 给定 $n, k$，对于所有的 $m \in \left[1, k\right]$，求长度为 $n$，值域为 $\left[1,m \right]$ 且最大公约数为 $1$ 的序列种数，对 $10^9 + 7$ 取模。 （$1 \le n,k \le 2 \times 10^6$）。 # ......

[题目传送门](https://www.luogu.com.cn/problem/P7735) 一眼数据结构 考虑树上有什么数据结构支持 $x$ 到 $y$ 节点的修改和查询，那就是：树链剖分。 那么这道树链剖分的题有个 $trick$：**边点转换&染色法，对于每次修改，考虑将修改路径上的点全部染 ......

**不要相信这篇题解的任何一个字，包括标题和这句话。** 省流-恶搞题目：A，B，C，M，Q。 [题目](https://vjudge.net/contest/578685) # [A](https://vjudge.net/contest/578685#problem/A) ## 思路 这道题实在 ......

# P1450 [HAOI2008] 硬币购物 题解 首先考虑只有一种硬币的情况。 如果取的数量没有限制，就是一个完全背包，$f_i$ 表示背包体积为 $i$ 的选择方案数，显然 $f_j = f_{j - v}$。 如果取的数量有限制，用多重背包做一遍会超时，考虑以下思路：所有方案数 - 不合法方 ......

[题目链接](https://www.luogu.com.cn/problem/P2431) 由于每个质量的月饼只有一个，并且质量恰好是2的整数倍，所以考虑将一个质量看成一个二进制位。 那么也就是说，我们要构造一个二进制数 $x$，使得 $x$ 的 $1$ 的个数最多，且满足 $a\le x \le ......

## Description 有一天 Masha 回到家，发现有 $n$ 只老鼠在它公寓的走廊上，她大声呼叫，所以老鼠们都跑进了走廊的洞中。 这个走廊可以用一个数轴来表示，上面有 $n$ 只老鼠和 $m$ 个老鼠洞。第 $i$ 只老鼠有一个坐标 $x_i$ ，第 $j$ 个洞有一个坐标 $y_j$ ......

[原题链接](https://ac.nowcoder.com/acm/contest/64384/C) 先不考虑车子的容量问题，因为结束位置保证是在起始位置之后的，那我们从前往后扫，发现是可以知道每个点时的车内的商品。 但是现在有了容量限制，我们怎么办呢，如果对于一段，k 都是大于每个点的货物量时， ......

## 题意 给定长度为 $n$ 的数组 $a$ 和一个整数 $k$ ，执行下面的代码： ```cpp long long ans = 0; //定义一个初始值为0的长整型变量 for(int i = 1; i typedef long long valueType; typedef std::vec ......

[Maximum Diameter](https://www.luogu.com.cn/problem/AT_abc290_f) ### 题目大意 定义长度为 $n$ 的序列 $a$ 的权值为： - 所有的 $n$ 个点的第 $i$ 个点的度数为 $a_i$ 的树的直径最大值，如果不存在这样的树，其 ......

## D.Matrix Cascade ### 题目描述： 有一个大小为$n \times n$的矩阵，由 0 和 1 组成。行的编号从上到下依次为$1$到$n$，列的编号从左到右依次为$1$到$n$。第$x$行与第$y$列交叉处的单元格记为$(x, y)$。 水月想把矩阵的所有元素都变成 0。她可 ......

## [ZJCTF 2019]NiZhuanSiWei 这是一道有关文件包含漏洞的题目 打开题目之后，给了一段代码，首先进行代码审计 ![image-20230901162446534](https://img2023.cnblogs.com/blog/2957075/202309/2957075- ......

**因为这道题确实让我学到了一些东西，所以来记录一下** STL中有一个尊贵的宝物，叫做unique,unique的使用要建立已经sort好的前提下，所以我们的思路是对 r 和 c 分别 sort，再用unique去重。 关于unique的原理：unique并未创造一个新的数组，而是将重复部分移至后 ......

试试模板注入发现，不行，然后伪协议，不行，再爆破目录也不行。 从`?img=TXpVek5UTTFNbVUzTURabE5qYz0`入手，可能是base64编码。 base64解码： ``` (不知道为什么别的WP上变成这样了，否则解不出来) TXpVek5UTTFNbVUzTURabE5q ``` ......

## 题意 > 有数个大头钉在二维平面上，有四个人从不同的角度观察它们，重叠的点视为一个，是否可能有一个人观察到的大头钉数量远多余其他人？ 让我们把大头钉的位置简化为二维坐标上的点。四个人观察的角度如下： * ```A``` 从左往右观察。即所有 $y$ 坐标相同的点是重叠的。 * ```B``` ......

感觉很不在状态啊，竟然没做出来 E。 ## A.Prime Deletion ### 题目描述： 质数是一个正整数，它正好有两个不同的正除数 $1$和整数本身。例如，$2$、$3$、$13$和$101$是质数；$1$、$4$、$6$和$42$不是质数。 给你一个从$1$到$9$的数字序列，其中**从 ......

# CF1864D Matrix Cascade 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/CF1864D) [Codeforces](codeforces.com/problemset/problem/1864/D) ## Descript ......

## 题意 对于一个排列 $p$，定义 $g$ 为 $p$ 的前缀最大公约数序列，即 $g_i = \gcd\limits_{j = 1}^{i} p_j$。定义 $f(p)$ 为 $g$ 的元素种类数。 给定 $n$，求长度为 $n$ 的且使得 $f(p)$ 取最大值的排列个数，对 $10^9 + ......

## Description 你有一棵有 $n$ 个点的树，树上的每条边权值都为 $1$。现在有 $q$ 次询问，每次询问一个整数 $x$，并将叶子结点全部相连上权值为 $x$ 的边（操作不会保留）。问每次操作后图的直径是多少。图的直径定义为 $\underset{1\leq uans$ 且 $h_ ......

## D.Two-Colored Dominoes ### 题目描述： 有一个$n\times m$棋盘，被分成若干小格。棋盘上还有一些多米诺骨牌。每张骨牌覆盖相邻的两个小格（即共用一条边的两个小格），没有两张骨牌重叠。 皮特认为这块棋盘太无聊了，需要涂上颜色。他要把多米诺骨牌的格子涂成黑色和白色。 ......

VS2019使用QT mvcs2015 32bit编译器的时候出现error C3615: constexpr 函数“qCountLeadingZeroBits”不能生成常量表达式错误。需要对QCore里面的qalgorithms文件进行修改。 ......

# [NOIP2012 提高组] 疫情控制 ## 题意： 给定一棵树，边有边权，有一些结点上有军队（可能不止一支），军队可移动。求最短的时间，使得军队移动后，从根到每个叶子结点的路径上都有军队驻扎。军队可以同时移动。 ## 思路： ~~咳咳咳我当时读错题了以为这题虚高，然后才意识到边境结点只有叶子结 ......

# [NOIP2013 提高组] 华容道 ## 题意： 一个棋盘上，每个格子上都有一个 $1 \times 1$ 的棋子，有些棋子固定，剩下的可以移动。棋子只能移动到空白的格子里。$Q$ 次询问，每次给出空白格子的位置、目标棋子的位置以及终点的位置，问把目标棋子移动到终点的最小步数。无解输出 $-1 ......

文件包含漏洞，和SQL注入等攻击方式一样，文件包含漏洞也是一种注入型漏洞，其本质就是输入一段用户能够控制的脚本或者代码，并让服务端执行。 什么叫包含呢？以PHP为例，我们常常把可重复使用的函数写入到单个文件中，在使用该函数时，直接调用此文件，而无需再次编写函数，这一过程叫做包含。 有时候由于网站功能 ......

看成内向基环森林，操作 $u\to v$ 相当于让 $u$ 连向 $v$ 所连的点，$v$ 变成自环。发现如果一个点 $v$ 变成了自环，那么操作任意一个 $u\to v$ 都没有用。 从简单的情形出发，对于一个内向树（或者说环大小为 $1$ 的内向基环树），每次操作 $x\to fa_x$ 时，相 ......

XXE漏洞原理：发生在应用程序解析XML输入时，没有禁止外部实体的加载，导致可加载恶意外部文件，造成文件读取、命令执行、内网端口扫描、攻击内网网站、发起DOS攻击等危害。XXE漏洞触发的点往往是可以上传XML文件的位置，没有对上传的XML文件进行过滤，导致可上传恶意XML文件。 * DOCTYPE（ ......

## A.Morning Sandwich ### 题目描述： 吃货小 C 喜欢三明治，他有三种材料：面包、芝士、火腿。正确的三明治组合应为一层面包和一层芝士或火腿之一轮流放置，以面包为结尾，例如面包-芝士-面包-火腿-面包就是合法的三明治。 给定每次做三明治的材料：$ b $ 面包，$ c $ 芝 ......