3 ez_yww

尚未进行身份认证

暂无相关描述

等级
TA的排名 2w+

【洛谷U20626】gemo 容斥 FWT 高斯消元

题目大意  给你一个无向图,有mmm个询问,每次给你一个点xxx和一个点集SSS,问你从xxx开始走,每次从一个点随机的走到与这个点相邻的点,问你访问SSS中每个点至少一次的期望步数是多少。  n≤18,m≤100000n≤18,m≤100000n\leq18,m\leq100000题解  有个东西叫min-max容斥:max(S)=∑T⊆S(−1)|T|+1min(T...

2018-03-02 15:36:00

【UOJ347】【WC2018】通道 边分治 虚树 DP

题目大意  给你三棵树,点数都是nnn。求maxi,jd1(i,j)+d2(i,j)+d3(i,j)maxi,jd1(i,j)+d2(i,j)+d3(i,j)\max_{i,j}d_1(i,j)+d_2(i,j)+d_3(i,j)  其中dk(i,j)dk(i,j)d_k(i,j)是在第kkk棵数中i,ji,ji,j两点之间的距离。  n≤100000n≤100000n\leq...

2018-02-13 09:40:41

【UOJ349】【WC2018】即时战略 LCT 动态点分治

这是一道交互题题目大意  有一棵nnn个点的树。最开始111号点是白的,其他点是黑的。  每次你可以执行一个操作:explore(x,y)explore(x,y)explore(x,y)。要求xxx是一个白点。该函数会返回从xxx到yyy的路径上第二个点的坐标并把该点染白。  要求你把所有点都染成白色。  设操作次数为ttt。  对于30%30%30\%的数据:这棵树是...

2018-02-12 16:52:45

【UOJ348】【WC2018】州区划分 状压DP FWT

题目大意  给定⼀个nnn个点的⽆向图,对于⼀种nnn个点的划分{S1,S2,…,Sk}{S1,S2,…,Sk}\{S_1,S_2,\ldots,S_k\},定义它是合法的,当且仅当每个点都在其中的一个集合中且对于任何的i∈[1,k]i∈[1,k]i\in[1,k],点集SiSiS_i⾮空,且导出⼦图不存在欧拉回路。  给定数组wiwiw_i,求对于所有合法的划分{s1,s2,…,sk}{...

2018-02-12 09:24:29

THUWC2018游记

前言  这次THUWC有pretest,非常不错。但还是要对拍。DAY1  上午先去报个到。  下午1:30开始比赛,状态还是很好的。  开场先看题。  发现t1是个联赛贪心题,就花了半个小时写完+拍完了。  然后同时开t2、t3。感觉t2的O(n2)O(n2)O(n^2)挺好写的,但只有101010分,就先放了一下。  感觉t3很可做,就开始写t3。  想...

2018-02-01 22:00:57

【XSY2190】Alice and Bob VI 树形DP 树剖

题目描述  Alice和Bob正在一棵树上玩游戏。这棵树有nn个结点,编号由11到nn。他们一共玩qq盘游戏。  在第ii局游戏中,Alice从结点aia_i出发,Bob从结点bib_i出发。开始时,除了aia_i和bib_i这两个结点外,所有结点都没有染色。结点aia_i被Alice染色,结点bib_i被Bob染色。  接下来,两位玩家轮流移动,两位玩家移动步数之和为kik_i步。A

2018-01-23 17:08:47

【XSY2733】Disembrangle DP

题目描述  有一个3×n3\timesn的网格,一些格子里已经有棋子了,一些格子里还没有。  每次你可以选择往一个没有棋子的格子里放一个棋子,但要满足这个格子上下两个格子都有棋子或左右两个格子都有棋子。  你的任务是把这个网格填满。问你有几种填法。  n≤2000n\leq2000题解  先判无解。  如果四个角没有棋子或在第1/31/3行有两个相邻的空格就无解

2018-01-23 16:53:45

【XSY2732】Decalcomania 可持久化线段树 分治

题目描述  有一个陶瓷瓶周围有nn个可以印花的位置。第ii个与第i+1i+1个位置之间的距离为did_i,在第ii个位置印图案要tit_i秒。  机器刚开始在00号位置,可以以11单位长度每秒的速度移动。  一个位置只能印一个图案。  现在有mm秒,问你最多能印几个图案。  保证时间不足以绕陶瓷瓶一圈。  n≤100000n\leq100000题解  肯定是先

2018-01-23 16:41:48

【XSY2703】置换 数学 置换 DP

题目描述  对于置换pp,定义f(p)f(p)为最小的正整数kk,使得pkp^k为恒等置换。  你需要求对于所有的nn元素置换pp,f2(p)f^2(p)的平均值。  n≤200n\leq200题解  考虑把置换拆成很多个循环。  f(p)f(p)就是所有循环的长度的lcmlcm  可以考虑DP,设fi,jf_{i,j}为放了ii个位置,当前所有循环长度的lcml

2018-01-23 16:19:36

【XSY2701】异或图 线性基 容斥原理

题目描述  定义两个图G1G_1与G2G_2的异或图为一个图GG,其中图GG的每条边在G1G_1与G2G_2中出现次数和为11。  给你mm个图,问你这mm个图组成的集合有多少个子集的异或图为一个连通图。  n≤10,m≤60n\leq10,m\leq60题解  考虑枚举图的子集划分,让被划分到不同子集的点之间没有连边,而在同一个子集里面的点可以连通,可以不连通。

2018-01-23 16:04:54

【BZOJ3997】【TJOI2015】组合数学 Dilworth定理 DP

题目描述  有一个n×mn\timesm的网格图,其中某些格子有财宝,每次从左上角出发,只能向下或右走。问至少走多少次才能将财宝捡完。  此对此问题变形,假设每个格子中有好多财宝,而每一次经过一个格子至多只能捡走一块财宝,至少走多少次才能把财宝全部捡完。  n,m≤1000n,m\leq1000题解  定义偏序关系  把一个格子拆成很多个点,每个点代表一个财宝。

2018-01-19 09:20:46

【XSY2727】Remove Dilworth定理 堆 树状数组 DP

题目描述  一个二维平面上有nn个梯形,满足:   所有梯形的下底边在直线y=0y=0上。   所有梯形的上底边在直线y=1y=1上。   没有两个点的坐标相同。  你一次可以选择任意多个梯形,必须满足这些梯形两两重叠,然后删掉这些梯形。  问你最少几次可以删掉所有梯形。  n≤105n\leq{10}^5题解  先把坐标离散化。  定义AA为所有梯形

2018-01-19 08:56:54

【XSY2032】简单粗暴的题目 组合数

题目描述  给你n,k,a1…ann,k,a_1\ldotsa_n,设ansn=∑i=1n(∑j=ins(j))kans_n=\sum_{i=1}^n{(\sum_{j=i}^ns(j))}^k\\  求ans1…ansnans_1\ldotsans_n  对109+7{10}^9+7取模  n≤50000,k≤100n\leq50000,k\leq100题

2018-01-17 20:04:50

【XSY2731】Div 数论 杜教筛 莫比乌斯反演

题目大意  定义复数a+bia+bi为整数kk的约数,当且仅当aa和bb为整数且存在整数cc和dd满足(a+bi)(c+di)=k(a+bi)(c+di)=k。  定义复数a+bia+bi的实部为aa,虚部为bb。  定义f(n)f(n)为整数nn的所有实部大于00的约数的实部之和。  给定正整数nn,求出∑ni=1f(i)\sum_{i=1}^nf(i)对100453580910

2018-01-16 11:22:26

【XSY2730】Ball 多项式exp 多项式ln 多项式开根 常系数线性递推 DP

题目大意  一行有nn个球,现在将这些球分成kk组,每组可以有一个球或相邻两个球。一个球只能在至多一个组中(可以不在任何组中)。求对于1≤k≤m1\leqk\leqm的所有kk分别有多少种分组方法。  答案对998244353998244353取模。  n≤109,m219n\leq{10}^9,m题解  因为k>nk>n的项都是00,所以我们钦定m≤nm\leq

2018-01-16 10:58:47

【XSY2729】欧拉子图 无向图连通性 数学

题目大意  给你一个nn个点mm条边的无向图(可能有重边),对于这个图的边集的子集(一共有2m2^m个),如果其导出的子图的每个联通块内都存在欧拉回路,我们就把答案加上这个子图的边数的平方,答案对109+7{10}^9+7取模。  n,m≤200000n,m\leq200000题解  先求出这个图的DFS树。  记cc为这个图的联通块个数。  通过观察发现,如果非树边任意

2018-01-16 10:42:22

【CTSC2017】【BZOJ4903】吉夫特 卢卡斯定理 DP

题目描述  给你一个长度为nn的数列aa,求有多少个长度≥2\geq2的不上升子序列ab1,ab2,…,abka_{b_1},a_{b_2},\ldots,a_{b_k}满足∏i=2k(abi−1abi)mod2>0\prod_{i=2}^k\binom{a_{b_{i-1}}}{a_{b_i}}\mod2>0  答案对109+7{10}^9+7取模。  n≤211985,

2018-01-15 11:43:54

【XSY2718】gift 分数规划 网络流

题目描述  有nn个物品,买第ii个物品要花费aia_i元。还有mm对关系:同时买pi,qip_i,q_i两个物品会获得bib_i点收益。  设收益为BB,花费为AA,求⌈BA⌉−1\lceil\frac{B}{A}\rceil-1  n≤400,m≤200000,1≤ai,bi≤100n\leq400,m\leq200000,1\leqa_i,b_i\leq100题解

2018-01-14 21:11:46

【XSY2719】prime 莫比乌斯反演

题目描述  设f(i)f(i)为ii的不同的质因子个数,求∑ni=12f(i)\sum_{i=1}^n2^{f(i)}  n≤1012n\leq{10}^{12}题解  考虑2f(i)2^{f(i)}的意义:有f(i)f(i)总因子,每种可以分给两个人中的一个。那么就有2f(i)=∑d|i[gcd(d,id)=1]2^{f(i)}=\sum_{d|i}[\gcd(d,\frac

2018-01-14 21:01:26

【XSY2720】区间第k小 整体二分 可持久化线段树

题目描述  给你你个序列,每次求区间第kk小的数。  本题中,如果一个数在询问区间中出现了超过ww次,那么就把这个数视为nn。  强制在线。  n≤100000,ain,w≤nn\leq100000,a_i题解  考虑整体二分。  先看看离线要怎么做。  现在我们要计算每个数对每个区间的贡献。  对于每个询问区间和每种数,让这个区间最右边ww个数对这个询问

2018-01-14 20:52:02

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!