4 quailty

尚未进行身份认证

暂无相关描述

等级
TA的排名 8w+

ZOJ 4111 Square on the Plane (数值分析+分类讨论)

Sourcehttp://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4111The16thZhejiangProvincialCollegiateProgrammingContestSponsoredbyTuSimple-ProblemL组团狙击大失败,还是Claris比较快。填坑中…...

2019-04-29 22:24:13

ACM ICPC 2018 Asia Region - Tehran Site Solution Sketch

比赛主页http://icpc.sharif.edu/2018/这套题目前在CFGym和UVALiveArchive都找不到,只能在官方主页找到题面和数据,没有题解和标程,但是最近有同学问了这套题的题解,我就尝试做了一下,以下做法大部分未经过代码验证,不保证正确性,后续有空会验证,这里也不描述题意了,ProblemA:ICPC根据题意模拟。ProblemB:C...

2019-04-07 21:56:45

计算几何随便做做

这里简单列出退役后做过的计算几何题,仅作为一个题目列表,难度方差可能较大

2018-06-22 20:51:34

quailty's Contest #1 题解

比赛链接:http://www.bnuoj.com/v3/contest_show.php?cid=7561A.道路修建如果使用可持久化并查集,二分答案判定连通性,复杂度是O(mlog^3n),不能在时限内出解。考虑到并查集实际上是一棵树,可以尝试在边上维护一些信息,假设t时刻加了一条边(u,v),若u和v此时未连通,则在root(u)和ro

2016-02-05 23:22:08

2015年北京师范大学新生程序设计竞赛题解

比赛链接http://www.bnuoj.com/v3/contest_show.php?cid=7468总结:本次比赛一共8题,其中AB为签到题,CD为简单题,EF为中档题,G题为防AK题(但是由于spj的问题放了一份错误代码通过),H题为构造题(但是出题人的最初想法有误,并且由于只需输出解的存在性,出现了读错题却AC的情况),各题通过人数与难度大致符合,梯度尚可。

2015-12-26 22:12:53

2015 China Collegiate Programming Contest Nanyang

题目可以在cdoj以及hdoj上找到,先写一份简要题解,A.SecreteMasterPlan题意:给定两个2*2的方阵,问能否通过若干次旋转操作把第一个变成第二个。题解:直接模拟即可。C.TheBattleofChibi题意:给定一个长为n(题解:先将所有数离散化一下,记dp[i][j]为末尾是i且长度为j的上升子序列个数,用

2015-10-20 14:13:14

平面几何相关 由调和四边形引出的一点点调和性质

先声明这篇文章和ACM本身并没有多大关系==考虑上图这样一个基本构形,其中AB,AC是圆O的切线,A,P,Q三点共线,利用相似容易证明PB/QB=PC/QC,称这样的四边形PBQC为“调和四边形”,连接BC交APQ于D,得到下图,那么有AP/DP=(AC*sin∠ACP)/(DC*sin∠DCP),AQ/DQ=(AC*sin∠ACQ)/(DC*sin∠DCQ)

2015-09-26 22:27:57

hihoCoder挑战赛14 向日葵 (极角扫描)

题目链接:http://hihocoder.com/contest/challenge14/problem/3题意:给定n对点,从每对点中等概率选出1个点,得到n个点,求凸包面积的期望。分析:凸包的面积可以对每条边的两个顶点用叉积进行计算,相当于将凸包划分为若干个有向三角形,根据期望的线性可加性,可以分别枚举每一条有向边,计算这条边是凸包上的一条边的概率

2015-08-30 23:39:55

HDU 3126 Nova (计算几何+最大流)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3126题意:有N个人,每个人已知一个坐标,有一个攻击半径,每次攻击完之后需要休息t时间才能下一次攻击,有m个敌人,然后有K颗树,当一个敌人位于某一个人攻击范围之内,并且他们线段连线上没有树时,才能进行攻击,问最少需要多少时间将所有敌人消灭。分析:先预处理出每个

2015-08-27 20:15:34

HDU 5407 CRB and Candies (Kummer定理)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5407题意:给定n,求C(n,0),C(n,1),...,C(n,n)的lcm(最小公倍数)对1e9+7取模的值。分析:C(n,k)中只包含不大于n的素因子,对每个素因子p,需要找出这n个组合数中p的幂最大的,由Kummer定理,这相当于找一个k,使得

2015-08-20 21:58:21

HDU 5299 Circles Game (圆的扫描线+树上SG)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5299题意:平面上有n个两两不交的圆,现在有两个人轮流选取圆,每选到一个圆就要把这个圆及其内部的所有圆都删去,最后不能操作的人输,问谁有必胜策略。分析:由于圆两两不交,如果根据圆的包含关系建个图,可以得到一个森林,问题转化为树上的SG博弈,复杂度O(nlogn),

2015-08-19 15:24:03

HDU 5396 Expression (数学期望+区间DP)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5396题意:给定一个有n个数字,运算符只有"+","-","*"的表达式,每次合并相邻两项,求所有合并方式所得到的结果之和对1e9+7取模的值。分析:如果将这个过程随机化,每次等概率选择相邻两项,记dp[i][j]为随机合并第i个到第j个数字这一段的表达式之后

2015-08-19 15:01:54

HDU 5322 Hope (CDQ分治+NTT)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5322题意:给定n,考虑一个1,2,...,n的排列A[1],A[2],...,A[n],对于每个i,选取最小的j(若存在)使得j>i且A[j]>A[i],则在i到j之间连一条边,记P为图中所有连通块的大小之积,定义P*P为这个排列的permutationvalue,求

2015-07-30 01:02:35

Codeforces Gym 2015 ACM Arabella Collegiate Programming Contest

比赛链接:http://codeforces.com/gym/100676题目链接:http://codeforces.com/gym/100676/attachments/download/3333/acm-arabella-collegiate-programming-contest-en.pdfA.RelationalOperator直接模拟。

2015-07-27 05:26:02

Codeforces Gym 2015 ACM Amman Collegiate Programming Contest

比赛链接:http://codeforces.com/gym/100712题目链接:http://codeforces.com/gym/100712/attachments/download/3454/acm-amman-collegiate-programming-contest-en.pdfA.WhoIsTheWinner?直接排序,复杂度O(nlo

2015-07-20 08:47:12

Codeforces 501D Misha and Permutations Summation (康托展开+平衡树优化)

D.MishaandPermutationsSummationtimelimitpertest2secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputLet'sdefinethesumof

2015-07-16 00:31:28

Codeforces 558D Guess Your Way Out! II (区间覆盖+扫描线)

D.GuessYourWayOut!IItimelimitpertest2secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputAmrboughtanewvideogame"Gues

2015-07-16 00:03:47

Codeforces 558E A Simple Task (计数排序+线段树优化)

E.ASimpleTasktimelimitpertest5secondsmemorylimitpertest512megabytesinputstandardinputoutputstandardoutputThistaskisverysimple.Givenastring S

2015-07-15 11:20:01

BNUOJ 27935 我爱背单词 (加强版) (FFT)

题目链接:BNUOJ27935-我爱背单词 (中文题面)分析:原题数据范围很小,可以直接暴力计算新单词对每一天需要背的单词量的贡献,注意到这个过程实质是一个多项式乘法,第Q天所需要背的单词量为多项式(N[1]*x+N[2]*x^2+...+N[D]*x^D)(1+x^(R[1]-1)+x^(R[2]-1)+...+x^(R[k]-1))展开式中x^Q项的系数,

2015-06-25 22:04:44

BNUOJ 12887 isumi (计算几何+最小割)

题目链接:BNUOJ12887-isumi (中文题面)分析:对题目中的图乱画一下发现,如果根据圆和矩形上下边相交的关系以及圆与圆之间相交的关系建图,由于存在一条从矩形左边走到右边且不与任何圆相交的路径等价于S和T不连通,那么只需选取尽可能少的点,使得删去这些点之后S和T不连通,拆点求最小割即可。代码:#include#include#in

2015-06-25 21:21:40

查看更多

勋章 我的勋章
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。