爱悠闲 > 分类 >

BZOJ 第51页

BZOJ 2671 Calc 数论
题目大意:给定 N ,求 ∑ni=1∑nj=1[i+j|ij]1 跪Nodgd= = 不妨设 d=gcd(i,j),i=ad,j=bd,gcd(a,b)=1 ,那么有 (a+b)d|abd2 即 a+b|abd ∵gcd(a,b)=1 ∴gcd(a+b,a)=1,gcd(a+b,b)=1 ∴a+b|d 不妨设 d=(a+b)t ,那么我们求的就是三元组 (a,b,t) 的个数,其中满足 a<b,g
BZOJ 2721 Violet 5 樱花 数论
题目大意:给定 n ,求有多少正整数数对 (x,y) 满足 1x+1y=1n! 由于 x,y>0 ,故显然有 y>n! 不妨设 y=n!+t(t>0) ,那么有 1x+1n!+t=1n! 化简后得到 n!(n!+t)+x(n!)=x(n!+t) x=(n!)2t+n! 故答案为 d((n!)2) #include <cstdio> #include <cstring> #include <iost
BZOJ 2083 Poi2010 Intelligence test 链表
题目大意:给定序列A,多次询问某个序列B是不是A的子序列 设某个序列B当前需要匹配的元素是x,那么就将所有x相同的B序列存成一个链表放在head[x]上 然后对于A的每个元素x,去head[x]上撸一遍链表,更新这些B序列的当前元素即可 时间复杂度是线性的 不过为毛跑的这么慢= = #include <vector> #include <cstdio> #include <cstring> #in
BZOJ 1336 Balkan2002 Alien最小圆覆盖 随机增量法
题目大意:求最小圆覆盖 随机增量法裸题 注意多输出几位小数不然过不去= = #include <cmath> #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <algorithm> #define M 100100 #define EPS 1e-7 using namespac
BZOJ 1337 最小圆覆盖 随机增量法
题目大意:求最小圆覆盖 我又写了一遍233 尼玛上一遍居然忘记random_shuffle了= = #include <cmath> #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <algorithm> #define M 100100 #define EPS 1e-7 us
BZOJ 2280 Poi2011 Plot 二分答案+随机增量法
题目大意:给定n个点,要求分成m段,使每段最小覆盖圆半径的最大值最小 二分答案,然后验证的时候把点一个个塞进最小覆盖圆中,若半径超了就分成一块…… 等等你在跟我说不随机化的随机增量法? 好吧 那么对于一个点pos,我们要计算最大的bound满足[pos,bound]区间内的最小覆盖圆半径不超过二分的值 直接上二分是不可取的,因为我们要求m次,如果每次都验证一遍[1,n/2]直接就炸了 我们可以这么
JLOI2015试题大意及部分题解
================Day1=============== T1:求 (b+d√2)n 的整数部分对p取模后的值 其中 bmod2=1,dmod4=1,b2≤d<(b+1)2,n≤1018 思路: 构造数列 an=b∗an−1+d−b24∗an−2 其中 a0=2,a1=b 然后我们求出这个数列的通项公式,得到 an=(b+d√2)n+(b−d√2)n 因此得到 (b+d√2)n=an
BZOJ 4002~4007 JLOI2015 代码
题解http://www.aiuxian.com/article/p-2430286.html 4002 有意义的字符串: #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define P 7528443412579576937ull using name
BZOJ 3996 TJOI2015 线性代数 网络流
题目大意:给定一个 n∗n 的矩阵 B 和一个 1∗n 的行向量 C ,求一个 1∗n 的01矩阵 A ,使 (A×B−C)×AT 最大 (A×B−C)×AT=A×B×AT−C×AT 我们可以考虑有 n 个物品,每个物品选不选对应 A 中每个位置是 1 还是 0 那么行向量 C 可以看做每个物品的代价 而矩阵 B 可以看做同时选择某两个物品时的收益 那么这个模型就被我们直接分析出来了,网络流走起~
BZOJ 3997 TJOI2015 组合数学 Dilworth定理
题目大意:给定一个网格图,每次从左上角出发,只能往右或往下走,最后到达右下角,每个格子有最低经过次数,问最少走几次 Dilworth定理:DAG的最小链覆盖=最大点独立集 最小链覆盖指选出最少的链(可以重复)使得每个点都在至少一条链中 最大点独立集指最大的集合使集合中任意两点不可达 此题中最大点独立集显然是一个集合满足集合中任意两点都是左下-右上的关系 DP一遍就能出解 复杂度 O(Tmn) #i