0103abc 的网站

考虑一个非常食的写法。 首先观察性质，若存在 $i\in[1,n)\cap\mathbb{N+}$，$si$ 为 且 $s_{i+1}$ 为 则 $[1,i]$ 区间中任何一个数都不能移动到 $[i+1,n]$ 区间，反之同理。 因此考虑维护若干个连续段...

~~呃呃呃，大水题~~ 首先有一个简单的贪心策略：先加边权大的边，然后再加边权小的边。容易证明她是正确的。 然后问题变为对于每一个 $k\in[1,n]\cap\mathbb{N+}$ 计算有多少个整数对 $(i,j)$ 满足 $1\le i<j\le n$ 且 $\gcd(i,j)=k$ 了。考虑...

很厉害的题。首先套路的发现 $f(x)=2^x$ 这个函数增长速度十分的快，在 $x\approx 20$ 的时候代价就超过了直接遍历整张图。因此考虑建 $20$ 层的分层图，若此时能跑到最短路，则可以证明答案一定最优。 还有一种可能就是说 $20$...

首先问题具有单调性，因此考虑二分答案。设当前二分到的答案为 $p$，则对于每一个商品考虑贪心： 前 $p$ 天内没有活动，那么最后一天以 $2$ 的价格购买。 前 $p$ 天内有活动，那么在最后一个活动日以 $1$ 的价格购买，剩下部分以 $2$ 的价格购买。 时间复杂度为 $O(n\log...

首先问题具有单调性，因此考虑二分答案。设当前二分到的答案为 $p$，则对于每一个商品考虑贪心： 前 $p$ 天内没有活动，那么最后一天以 $2$ 的价格购买。 前 $p$ 天内有活动，那么在最后一个活动日以 $1$ 的价格购买，剩下部分以 $2$ 的价格购买。 时间复杂度为 $O(n\log...

~~史中食~~ 考虑巨大分类讨论（后面需要满足前面的不满足）： $m=1$：输出任意一条边。 $m\equiv 1\pmod 2$ ：正反循环输出一条边。 $\exists x,y,a{x,y}=a{y,x}$：一直输出这一条边。 $n=2$：无解。...

黑色的双倍经验！P7670 前置定义：$k0$ 表示 $0$ 的数量，$k1$ 表示 $1$ 的数量，$k_?$ 表示 $?$ 的数量。 前置知识：数据点分治，快速沃尔什变换（FWT）。 首先考虑一个非常 trival 的暴力，对于每一个 字符，将其暴力替换为 和 然后判断答案。因此获得了一个...

黑色的双倍经验！ATjoi2018hoe 前置定义：$k0$ 表示 $0$ 的数量，$k1$ 表示 $1$ 的数量，$k_?$ 表示 $?$ 的数量。 前置知识：数据点分治，快速沃尔什变换（FWT）。 首先考虑一个非常 trival 的暴力，对于每一个 字符，将其暴力替换为 和 ...

题意：给定一张无向图 $G$，现在给定四个点 $S$，$T$，$u$，$v$，你需要任意选取 $S\to T$ 的一条最短路，并使得将其上所有边边权均赋为 $0$ 后 $u\to v$ 最短路长度最短。 题解： 首先考虑下面的引理： $\textbf{Lemma}$ 图中 $S\to...

题意：给定一张无向图 $G$，现在给定四个点 $S$，$T$，$u$，$v$，你需要任意选取 $S\to T$ 的一条最短路，并使得将其上所有边边权均赋为 $0$ 后 $u\to v$ 最短路长度最短。 题解： 首先考虑下面的引理： $\textbf{Lemma}$ 图中 $S\to...