「Ynoi2018」GOSICK

发表于 | 更新于 | 分类于

不知道哪个阴间搬题人，陆续给模拟赛里整了第二分块、第七分块、第十四分块。

第二分块之前写的空间垃圾时间垃圾然后懒得搞了。

第七分块并没有看懂题解。

于是就只能写写这个了。

卡常卡不过别人的主要原因是懒（确信）

阅读全文 »

「CF493E」Vasya and Polynomial

发表于 | 更新于 | 分类于

题意简述

CF493E

给三个正整数 $A, B, C$，求有多少个非负整数系数多项式 $f(x)$，满足 $f(A)=B,f(B)=C$。
无穷个则输出-1。
有限个，则求出次数最高，并且系数从高到低字典序最小的一个。
$A, B, C\le 10^{18},T\le 100$。

阅读全文 »

「CF1442E」Black, White and Grey Tree

发表于 | 更新于 | 分类于

题意简述

给一棵树，树上每个节点都为灰色、白色或黑色。
每次可以选择一个连通块中的一个节点集合，要求集合中不能同时存在黑色和白色的节点，然后删去集合中所有节点。
问最少多少次可以把整棵树删完。

$n\le 200000$。

阅读全文 »

「CodeChef WALKBT」Walks on the binary tree

发表于 | 更新于 | 分类于

题意简述

CodeChef WALKBT

一棵高度为 $n$ 的满二叉树（节点数为 $2^{n+1}-1$），用一个 $[0,2^n)$ 的数 $X$ 表示一条根到叶子的路径（从最高位开始，为0则走左儿子，否则走右儿子）。

初始 $X = 0$，有两种操作共 $q$ 个：

  • 将 $X$ 改为 $(X + 2^C) \bmod 2^n$，然后从根出发走到叶子。
  • 询问当前有多少个节点至少被访问一次。

$n,q\le 10^5$。

阅读全文 »

「CF1423M」Milutin's Plums

发表于 | 更新于 | 分类于

题意简述

交互题。
矩阵 $n\times m$，有性质：
对于任意子矩阵（即任意行的子集和列的子集的交），设子矩阵中第 $i$ 行最小值最先出现的位置是 $L(i)$，则 $L(i)$ 单调不降。

通过不超过 $4(n + m)$ 次单点询问确定该矩阵的最小值。

阅读全文 »

「LOJ2328」「清华集训 2017」避难所

发表于 | 更新于 | 分类于

题意简述

LOJ 2328

设 $F(n,b)$ 表示 $n$ 在 $b$ 进制下各个位上数字的乘积。
如果想求一个最小的 $n$，使得 $p=F(n,b)$，那么一种贪心的方法是从 $b-1$ 开始往下试，如果是 $n$ 的约数就把它放在此时最低的位上。
显然贪心是错的。例如 $b=9,p=216$，那么贪心会给出 $n=(3338)_9$，但正确答案是 $n=(666)_9$。
给定 $b$，你需要给出一个 hack 数据 $p$ 以及它的最优解，或说明不存在。要求 $p\le 10^{18}$。
$t$ 组数据，$t\le 200, 1\le b\le 100000$。

阅读全文 »