赵嘉熠的博客

语文小说习作一篇

下载游戏

系统要求：Windows XP及以上；暂不支持其它操作系统

最新版本

v1.0_64位（点击此处下载）

v1.0_32位（点击此处下载）

发布日期：2022/3/18

纪念一下

感觉省一有点悬……

题目链接（洛谷）

题目大意

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

对于$30\mathrm{\%}$的数据，$2\le n\le 30$；对于$100\mathrm{\%}$的数据，$2\le n\le 500$

比赛链接（正睿）

比赛链接（正睿）

题目链接（洛谷）

题目大意

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

$n\le 5000$，内存限制：$62.5\mathrm{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$