crazy_cloud's Blog

题目大意

给定一个有 \(n\) 个整数的序列 \({a_n}\)，有一个初始为 \(0\) 的值 \(res\)，重复下面的过程 \(k\) 次：

随机选择一个 \([1,n]\) 之间的下标 \(x\)，\(res\) 加上所有满足 \(i\neq x\) 的 \(a_i\) 的乘积，然后将 \(a_x\) 减去 \(1\)。

求最后 \(res\) 的期望值，对 \(10^9+7\) 取模。

\(1\leq n\leq5\times10^3,1\leq k\leq10^9\)

题目大意

在二维平面上有 \(n\) 个红点和 \(m\) 个蓝点。

你要画一个圆，使得这个圆内部不含任何蓝点，且至少包含一个红点。边界上的点可以算也可以不算。

你要计算圆的半径最大能是多少。

\(1\leq n,m\leq10^3,1\leq x_i,y_i\leq10^4\)

没有两点重合。

题目大意

在二维平面上有 \(2n\) 个球。

在 \((0,i)(1\leq i\leq n)\) 有 \(n\) 个机器人，激活后会拿走纵坐标为 \(i\) 的最左边的球；类似地，在 \((i,0)(1\leq i\leq n)\) 有 \(n\) 个机器人，激活后会拿走横坐标为 \(i\) 的最下面的球。

问一共 \((2n)!\) 种激活顺序中，多少种能拿走所有的球。

\(2\leq n\leq10^5,1\leq x_i,y_i\leq n\)

题目大意

给一幅 \(n\) 个点的无向无权简单图。

判断是否对于任意一种把点涂成 \(\frac n2\) 个黑点和 \(\frac n2\) 个白点的染色方式，都存在黑白点之间的完美匹配。

\(1\leq n\leq 100\) 且为偶数。

题目大意

二维平面上有 \(n\) 个蓝点和 \(m\) 个红点。你要画出一个凸多边形，使其在不包含任何红点的同时包含尽可能多的蓝点。请输出最多包含的蓝点数。

这个凸多边形可以退化成点或线段。

\(1\leq n,m\leq 50\)

坐标都是 \([0,10^3]\) 的整数，保证没有两点重叠和三点共线。

题目大意

给定平面上的 \(n\) 个点，请使用最少的互相平行的直线覆盖所有的点。 保证答案 \(K\) 不超过 \(400\)。

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

简介

本文将介绍一种 \(O(n\sqrt n)\) 解决区间逆序对计数的在线算法。

似乎又是某分块中学那边的奇技淫巧

题目大意

给定 \(d\) 张无向图，每张图都有 \(n\) 个点。一开始，在任何一张图中都没有任何边。

接下来有 \(m\) 次操作，每次操作会给出 \(a,b,k\)，意为在第 \(k\) 张图中的点 \(a\) 和点 \(b\) 之间添加一条无向边。

你需要在每次操作之后输出有序数对 \((a,b)\) 的个数，使得 \(1\leq a,b\leq n\)，且 \(a\) 点和 \(b\) 点在 \(d\) 张图中都连通。

\(1\leq d\leq200,1\leq n\leq5000,1\leq m\leq 10^6\)

题目大意

给出 \(n\) 件 T-shirt 的质量 \(q_i\) 和花费 \(c_i\)，有 \(k\) 个人最开始分别有 \(b_i\) 的金钱。

每个人的选衣服的策略都是一样的：将所有 T-shirt 按照重要程度从大到小排序，重要程度相同的按花费从小到大排，然后每个人从头开始取 T-shirt，如果金钱数大于当前的 T-shirt 的花费，那么就买下这件衣服，问每个人最多能够买的 T-shirt 数量。

\(1\leq n,k\leq 2\times10^5\) \(1\leq q_i,c_i,b_i\leq 10^9\)

题目大意

你有一个 \(n\) 个点 \(m\) 条边的无向连通图，边的总数为偶数。

设图中有 \(k\) 个奇点（度数为奇数的点），你需要把它们配成 \(\frac k2\) 个点对（显然 \(k\) 被 \(2\) 整除）。对于每个点对 \((u,v)\)，你需要用一条长度为偶数（假设每条边长度为 \(1\)）的路径将 \(u\) 和 \(v\) 连接。

每条路径允许经过重复的点，但不允许经过重复的边。这 \(\frac k2\) 条路径之间也不能有重复的边。

无解输出 NIE。

\(2\leq n,m\leq 2.5\times10^5\)