WHZ0325's Space

一类换根问题

昨天训练的时候遇到一道树形 DP 题，做法似乎很经典，来记录一下。参考严格鸽的知乎。【CF 633F】The Chocolate Spree求两条不相交链的最大权值和。使用换根 DP，枚举将两条链分开的边，两条链分别在这条边所分成的两棵子树中。可以转化为考虑维护一棵子树中的最长链以及......

Posted by WHZ0325 on 2023-09-06

【Codeforces 1681E】Non-Intersecting Subpermutations

题目描述给定 $n, k$，求由 $[1,k]$ 组成所有长度为 $n$ 的序列的贡献之和，一个序列的贡献为能够在其中找到的最多互不交叉的段数使得每一段长度为 $k$ 且恰好包含 $[1,k]$ 中每个数，输出答案对 $998244353$ 取模的值。 $2\le n,k\le 4000$。 ......

Posted by WHZ0325 on 2023-09-05

ICPC 2022 南京

目前已完成 2/8 题 A. Stop, Yesterday Please No MoreB. Ropeway一个重要的性质是任意长度为 $k$ 的区间中一定有一个点被选。考虑枚举修改位置前后 $k$ 个位置，如果可以计算一定选择该位置时的最小费用，这 $2k$ 个位置取最小值就是答案。 ......

Posted by WHZ0325 on 2023-08-28

【蓝桥杯 2022】最优清零方案

题目描述给定一个长度为 $n$ 的序列 ${a_i}$ 和一个整数 $k$，一次操作可以将连续 $k$ 个整数减一或者将一个整数减一，求将所有整数变为 $0$ 的最少操作次数。 $1\le k\le n\le 10^6$，$0\le a_i\le 10^6$。算法分析啊，这题，我咋不会啊……......

Posted by WHZ0325 on 2023-04-02

【蓝桥杯 2022】推导部分和

题目描述给定一个长度为 $n$ 的未知序列 ${a_i}$，已知 $m$ 个条件 $l_i, r_i,S_i$，表示 $a_{l_i}+a_{l_i + 1}+\dots +a_{r_i}$ 的和为 $S_i$，要实现 $q$ 次询问，每次询问 $a_l+a_{l+1}+\dots +a_r$......

Posted by WHZ0325 on 2023-04-02

【CF 1798F】Gifts from Grandfather Ahmed

题目描述有 $n+1$ 个数 ${a_i}$，分成 $k$ 组，其中第 $i$ 组分得的数之和必须为 $s_i$ 的倍数，保证 $\sum s_i=n+1$，第 $n+1$ 个数丢失，要给出任一满足条件的 $a_{n+1}$ 的值和分组方案。 $1\le n,k\le 200$，$1\le a......

Posted by WHZ0325 on 2023-03-29

【CF 1798E】Multitest Generator

题目描述定义一个序列为 test 仅当序列的第一个元素为这个序列剩下元素的长度。定义一个序列为 multitest 仅当该序列的第一个数为能够将剩下元素组成的序列拆成的 test 的个数。定义一次修改操作可以将序列中任意元素修改为任意一个非负整数。定义函数 $f(A)$ 为将序列修改为 ......

Posted by WHZ0325 on 2023-03-28

【蓝桥杯 2022】青蛙过河

题目描述在 $[1,n-1]$ 之中的每个位置有一个权值 $H_i$，当经过时权值减一，权值为 $0$ 时不能经过，求最小的跳跃距离（每次移动的距离均不超过跳跃距离），使得能够在位置 $0$ 和位置 $n$ 之间往返 $2x$ 次。 $1\le n\le 10^5$，$1\le x\le 10......

Posted by WHZ0325 on 2023-03-25

【蓝桥杯 2022】GCD

题目描述求最小的 $k$，使得 $gcd(a+k,b+k)$ 的值最大。 $1\le a\lt b\le 10^{18}$。算法分析数论忘光了，思博选手不会写数学题。。。首先有 $gcd(a,b)=gcd(b,a-b)$，很好理解：$a=gc$，$b=gd$ 的话 $a-b=g(c-d)$......

Posted by WHZ0325 on 2023-03-25

【CSP 2022】聚集方差

题目描述给你一棵 $n$ 个节点的树，记以节点 $x$ 为根的子树组成集合为 $T(x)$，求 $\sum_{y\in T(x)}\min_{z\in T(x),z\neq y}(a_z-a_y)^2$。 $2\le n\le 3\times 10^5$，$0\le a_i\le 10^9$。......

Posted by WHZ0325 on 2023-03-12

【POJ 1064】Cable master

题目描述给定 $n$ 条长度分别为 $a_i$ 的绳子，求切出 $k$ 条完整绳子的最大长度。 $1\le n\le 10^4$，$1\le k\le 10^4$，$a_i$ 有两位小数。算法分析二分答案，在长度为 $d$ 时能切出 $k$ 条完整的绳子显然在长度小于 $d$ 时也能做到，答......

Posted by WHZ0325 on 2023-03-08

【洛谷 P1175】表达式求值

题目描述给定一个中缀表达式，输出它的后缀表达式及对后缀表达式求值时每一步的结果。算法分析基础题，转后缀的过程中用栈保存运算符，每当当前运算符与栈顶运算符相同（按从左到右顺序计算）或栈顶运算符优先级更高时，要将这些运算符优先计算。注意特判阶乘。代码实现1234567891011121314......

Posted by WHZ0325 on 2022-09-19

【CSP 2019】城市规划

题目描述给定一颗 $n$ 个节点的树，其中给出 $m$ 个节点可选，要求从这 $m$ 个节点中选出 $k$ 个节点使得已选节点两两之间的距离和最小。 $n\le 5\times 10^4$，$m\le 10^4$，$k\le 100$。算法分析树上 0/1 背包动态规划模版题，设 $f[i]......

Posted by WHZ0325 on 2022-08-25

【TJOI 2010】阅读理解

题目描述$N$ 篇短文，$M$ 个询问，每次询问其在哪几篇短文中出现过。 $1\le M\le 10^4$，$1\le N\le 10^3$，每篇短文不超过 $5\times 10^3$ 个字符，每个单词不超过 $20$ 个字符。算法分析用 Trie 树，对 $N$ 篇短文建立字典树的空间复......

Posted by WHZ0325 on 2021-07-13

【网络流24题】火星探险问题

题目描述给定 $p\times q$ 个位置，每个位置可能平坦无障碍、有障碍或有石块，$n$ 个探测车从左上角 $(1,1)$ 出发，每次只能往右或往下走，到达 $(q,p)$，输出使采集岩石最多时每辆车的行走方案。 $n,p,q\le 35$。算法分析难点在于如何表示取走石块，将每个点拆点......

Posted by WHZ0325 on 2019-05-03

【NOI 2010】能量采集

题目描述栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。栋栋的植物种得非常整齐，一共有 $n$ 列，每列有 $m$ 棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一个坐标......

Posted by WHZ0325 on 2019-05-03

【ZJOI 2007】报表统计

题目描述维护一个初始长度为 $n$ 的非负整数序列，支持一下三种操作：在初始第 $i$ 个整数后面插入一个整数，若初始第 $i$ 个整数后面已经插入过其它整数，则将该整数插入到这些整数的最后面。查询整个序列中相邻两个元素之间差值的最小值。查询整个序列中任意两个元素之间差值的最小值。 ......

Posted by WHZ0325 on 2019-05-02

【APIO 2015】巴邻旁之桥

题目描述一条东西走向的穆西河将巴邻旁市一分为二，分割成了区域 $A$ 和区域 $B$。每一块区域沿着河岸都建了恰好 $1000000001$ 栋的建筑，每条岸边的建筑都从 $0$ 编号到 $1000000000$。相邻的每对建筑相隔 $1$ 个单位距离，河的宽度也是 $1$ 个单位长度。区域......

Posted by WHZ0325 on 2019-05-02

【SHOI 2015】超能粒子炮·改

题目描述有 $t$ 组数据，每组数据给定 $n,k$，求 $\sum_{i=0}^kC_n^i\mod 2333$ 的值。 $t\le 100000$，$n,k\le 10^{18}$。算法分析感觉可能是套路题…… 设 $f[n][k]=\sum_{i=0}^kC_n^i\mod 2333$......

Posted by WHZ0325 on 2019-05-01

【国家集训队 2011】礼物

题目描述有 $n$ 件礼物，打算送给 $m$ 个人，其中送给第 $i$ 个人的礼物数量为 $w_i$，求送出礼物的方案数，输出答案模 $p$ 的结果，无解输出 $Impossible$。设 $p=p_1^{c_1}p_2^{c_2}p_3^{c_3}\dots p_t^{c_t}$，$p_i......

Posted by WHZ0325 on 2019-04-29

【CTSC 2017】吉夫特

题目描述给定一个长度为 $n$ 的序列 $A$，求有多少个子序列满足所选下标集合为 ${b_1,b_2,\dots,b_k}$ 时 $a_{b_1}\ge a_{b_2}\ge\dots\ge a_{b_{k-1}}\ge a_{b_k}$ 且 $\prod_{i=2}^kC_{a_{i-1}......

Posted by WHZ0325 on 2019-04-28

【清华集训 2016】组合数问题

题目描述$t$ 组数据，每组数据给定 $n,m$ 和 $k$，求对于所有的 $0\le i\le n$，$0\le j\le \min(i,m)$ 有多少对 $(i,j)$ 满足 $C_i^j$ 是 $k$ 的倍数。 $1\le n,m\le 10^{18}$，$1\le t,k\le 100......

Posted by WHZ0325 on 2019-04-26

【SDOI 2010】古代猪文

题目描述给定两个整数 $n,g$，求 $g^{\sum_{k|n}C_n^k}\mod 999911659$ 的值。$1\le n,g\le 10^9$。算法分析当 $g$ 与模数 $999911659$ 互质时，根据欧拉定理得 $g^{\sum_{k|n}C_n^k}\mod 999911......

Posted by WHZ0325 on 2019-04-18

【WC 2010】重建计划

题目描述给定一棵 $n$ 个节点的树，每条边有其对应的价值 $v_i$，要求一条路径，长度满足在 $[L,U]$ 内且路径上的边权总和与边数之比最大，输出这个最大值，结果保留三位小数。 $n\le 100,000$，$1\le L\le U\le n-1$，$v_i\le 10^6$。 ......

Posted by WHZ0325 on 2019-04-11

【TJOI 2015】弦论

题目描述给定一个字符串，求它的第 $k$ 小子串，$t=0$ 表示不同位置的相同子串算作一个，$t=1$ 表示不同位置的相同子串算作多个，无解输出 $-1$。 $n\le 5\times 10^5$，$t\in {0,1}$，$k\le 10^9$。算法分析利用后缀自动机的性质求解。首先对......

Posted by WHZ0325 on 2019-03-25

竞赛题解