crazy_cloud's Blog

题目大意

给定一颗 \(n\) 个点的无根树，求最少加多少条边使形成的图形任意删除一条边后都联通，边是无向的。

输出最少加边数和任意一种加边方案。注意不能加已出现的边。

\(3\leq n\leq 5\times10^5\)

题目大意

给你一个大小为 \(m\) 的集合 \(S\)。

对于一个所有数和为 \(n\) 的正整数序列 \(\{a_k\}\)，如果 \(\exists 1\leq i\leq k,\sum_{j=1}^ia_i\in S\) 则该序列是非法的。

一个合法的序列的贡献是 \(\prod_{i=1}^ka_i^2\)。给定 \(n,m\) 和 \(S\)，请问所有合法的序列的贡献之和为多少，答案对 \(10^9+7\) 取模。

\(1\leq n\leq 10^9,0\leq m\leq 10^5\)

\(\forall x\in S,1\leq x< n\)

简介

Fast Walsh-Hadamard Transform (FWT) 是用来解决一类二(\(K\))进制运算卷积问题的快速算法，可以理解为每一维大小为 \(2\)(\(K\)) 的高维快速傅里叶变换。这类问题的一般形式是，给定 \(A\) 和 \(B\)，求出 \(C\) 满足： \[ C_i=\sum_{j\otimes k=i}A_jB_k \] 其中 \(\otimes\) 是一种二(\(K\))进制运算。

本文将从回顾 FFT 开始，深入理解 FFT 的原理，然后再引出二进制的 FWT。讨论 FWT 时，我们先会介绍 \(\mathrm{or}\) 和 \(\mathrm{and}\) 运算卷积两种较为简单的情况，然后进一步介绍 \(\mathrm{xor}\) 的复杂情况。最后我们会将 \(\mathrm{xor}\) 运算卷积推广至 \(K\) 进制的情况。

前言

弱鸡选手第一次认真打 CC 马拉松，然而多项式菜不会异或卷积，题答水平又低，于是只能做 \(8\) 道题……

让我们跳过傻逼题

题目大意

给定一个 \(1\times n\) 的格子图。每一个格子都有着一种颜色（红蓝绿白之一）。每个格子上都有一定数量的硬币，不同的格子的硬币数一定是不同的。

你需要从格子图任选一个格子作为开始位置，每次你可以从一个格子跳到图中另外一个没有访问过的格子上。

跳格子有一个规则：从红色或者蓝色格子只能跳到绿色或白色格子上，从绿色或白色格子只能跳到红色或蓝色格子上。

你要一直跳到没有能够继续跳的格子为止。将你经过的所有格子的硬币数记录成一个序列，我们希望最大化这个序列的最长上升子序列长度。

\(1\leq n\leq4\times10^5\)

题目大意

给定一个 \(X\) 部和 \(Y\) 部都有 \(n\) 个点的带边权二分图，\(X\) 部的每一个点都会和 \(Y\) 部的两个不同的点有连边。

对于这个二分图的一个完美匹配，定义它的权重是所有匹配边的边权乘积。

你需要计算这个二分图所有完美匹配的权重之和，答案对 \(998244353\) 取模。

题目保证一定存在完美匹配。

\(1\leq n\leq 3\times10^5\)

题目大意

给定一个长度为 \(n\) 的序列\({a_n}\)，对于任意 \(x\neq y\)，如果 \(a_x=a_y\)，则在 \(x\) 和 \(y\) 之间画一条弧。

称两条弧 \((x,y)\) 与 \((l,r)\) 相交当且仅当 \(x<l<y<r\) 或者 \(l<x<r<y\)。求有多少条异色弧相交。

\(1\leq n\leq 10^5,1\leq a_i\leq 10^5\)

题目大意

给定三个在平面直角坐标系的第一象限上矩形 \([x_1,y_1][x_2,y_2],[x_3,y_3][x_4,y_4],[x_5,y_5][x_6,y_6]\)。

你要从第一个矩形内选出一个整点作为起始点，第二个中选出一个中转点，第三个中选出一个结束点，然后从起始点开始不断向上或右走，经过中转点最后到结束点。求不同的路径的总数量。

两条路径不同当且仅当它们的起始/中转/结束点存在不同或者路线不一样。

\(1\leq x_1\lt x_2\lt x_3\lt x_4\lt x_5\lt x_6\leq10^6,1\leq y_1\lt y_2\lt y_3\lt y_4\lt y_5\lt y_6\leq10^6\)

题目大意

给定一颗 \(n\) 个节点的无根树，除此之外还给定一些非树边 \((x,y)\)。 这些非树边比较特殊，它们满足将树看成 \(1\) 为根的有根树的时候，\(\mathrm{lca}(x,y)=1\)。 树边和非树边的数量之和是 \(m\)。 要求求出恰好删除两条树边的一个最小的割。

\(3\leq n\leq 2\times10^4,n-1\leq m\leq 10^5\)

折腾了一个下午总算用 Hexo + GitHub Page 搭了一个博客

一直都觉得在各种博客平台上写 blog 和拘束，更何况最近 csdn 出了一个怪丑的皮肤。现在总算有了一个自由度比较高的站。