赵嘉熠的博客

纪念一下

感觉省一有点悬……

题目链接（洛谷）

题目大意

有\([2,n]\)一共\(n-1\)个数，甲乙两个人分别取子集\(S,T\)，要求不存在\(x\in S,y\in T\)，使得\(\gcd(x,y) \neq 1\)。求取子集的方案个数。

对于\(30\%\)的数据，\(2\le n\le 30\)；对于\(100\%\)的数据，\(2\le n\le 500\)

比赛链接（正睿）

比赛链接（正睿）

题目链接（洛谷）

题目大意

给定一棵大小为\(n\)的树，在树上选\(3\)个点，要求两两距离相等，求方案数。

\(n\le 5000\)，内存限制：\(62.5 \operatorname{Mb}\)（大概开\(1.5\times 10^7\)个\(\text{int}\)）

题目链接（UOJ）

题意

一个\(n\)个结点的无向图，有\(m\)条老边已经存在，给定起点、终点、权值，保证权值互不相同且此时图已经联通。还有\(k\)条新边是G老板的，给定起点、终点，权值由G老板指定。

在G老板指定完权值后，在图的最小生成树上，结点\(i\)上有\(p_i\)个人要从结点\(i\)去结点\(1\)（只能走最小生成树上的边）。每个人如果路过新边就要给G老板交权值那么多钱。求G老板最多赚多少。

\(n \le 10^5,m \le 3\times 10^5, k \le 20\)，时间限制：$3 $

题目链接（洛谷）

题目大意

众所周知，从\(n\)个非负整数中任取两个相加共有\(\frac{n\times (n-1)}{2}\)个和。现在给出这\(\frac{n\times (n-1)}{2}\)个和值，要求\(n\)个非负整数。若答案不存在，输出“impossible”。

\(n \le 10\)，给出的数\(\le10^5\)

比赛链接（正睿）

比赛链接（正睿）