- 博客(25)
- 收藏
- 关注
RSS订阅
原创 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
3278
3
原创 小q的博客开通啦
大家好，这里是quailty，一只ACMer，24K纯蒟蒻，大学前没接触过编程。大概是从好几个月前就打算开一个博客了，中间偶尔想起来然而又马上忘掉，不过终于还是下定决心开了这个博客。开这个博客也没有什么目的的样子，总之会定期不更新一些题解，分享一些学习心得体会，说说自己的有趣经历，退役的时候大概还能写个退役文。最后，欢迎大家经常来踩踩啦！#includeusing namespa
2015-06-12 03:08:20
6063
22
原创 ZOJ 4111 Square on the Plane (数值分析+分类讨论)
Source http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4111The 16th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple - Problem L组团狙击 大 失 败，还是 Claris 比较快。填坑中 …...
2019-04-29 22:24:13
1192
原创 ACM ICPC 2018 Asia Region - Tehran Site Solution Sketch
比赛主页 http://icpc.sharif.edu/2018/这套题目前在 CF Gym 和 UVA Live Archive 都找不到，只能在官方主页找到题面和数据，没有题解和标程，但是最近有同学问了这套题的题解，我就尝试做了一下，以下做法大部分未经过代码验证，不保证正确性，后续有空会验证，这里也不描述题意了，Problem A : ICPC根据题意模拟。Problem B : C...
2019-04-07 21:56:45
996
原创 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
5021
3
原创 2015 China Collegiate Programming Contest Nanyang
题目可以在cdoj以及hdoj上找到，先写一份简要题解，A. Secrete Master Plan题意：给定两个2*2的方阵，问能否通过若干次旋转操作把第一个变成第二个。题解：直接模拟即可。C. The Battle of Chibi题意：给定一个长为n(题解：先将所有数离散化一下，记dp[i][j]为末尾是i且长度为j的上升子序列个数，用
2015-10-20 14:13:14
3960
2
原创 平面几何相关 由调和四边形引出的一点点调和性质
先声明这篇文章和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
12724
7
原创 hihoCoder挑战赛14 向日葵 (极角扫描)
题目链接：http://hihocoder.com/contest/challenge14/problem/3题意：给定n对点，从每对点中等概率选出1个点，得到n个点，求凸包面积的期望。分析：凸包的面积可以对每条边的两个顶点用叉积进行计算，相当于将凸包划分为若干个有向三角形，根据期望的线性可加性，可以分别枚举每一条有向边，计算这条边是凸包上的一条边的概率
2015-08-30 23:39:55
1660
3
原创 HDU 3126 Nova (计算几何+最大流)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3126题意：有N个人，每个人已知一个坐标，有一个攻击半径，每次攻击完之后需要休息t时间才能下一次攻击，有m个敌人，然后有K颗树，当一个敌人位于某一个人攻击范围之内，并且他们线段连线上没有树时，才能进行攻击，问最少需要多少时间将所有敌人消灭。分析：先预处理出每个
2015-08-27 20:15:34
1644
原创 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
2560
1
原创 HDU 5299 Circles Game (圆的扫描线+树上SG)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5299题意：平面上有n个两两不交的圆，现在有两个人轮流选取圆，每选到一个圆就要把这个圆及其内部的所有圆都删去，最后不能操作的人输，问谁有必胜策略。分析：由于圆两两不交，如果根据圆的包含关系建个图，可以得到一个森林，问题转化为树上的SG博弈，复杂度O(nlogn)，
2015-08-19 15:24:03
1923
原创 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
1435
原创 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为这个排列的permutation value，求
2015-07-30 01:02:35
4282
6
原创 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. Relational Operator直接模拟。
2015-07-27 05:26:02
2765
2
原创 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. Who Is The Winner?直接排序，复杂度O(nlo
2015-07-20 08:47:12
2947
2
原创 Codeforces 501D Misha and Permutations Summation (康托展开+平衡树优化)
D. Misha and Permutations Summationtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet's define the sum of
2015-07-16 00:31:28
2019
原创 Codeforces 558D Guess Your Way Out! II (区间覆盖+扫描线)
D. Guess Your Way Out! IItime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputAmr bought a new video game "Gues
2015-07-16 00:03:47
1040
原创 Codeforces 558E A Simple Task (计数排序+线段树优化)
E. A Simple Tasktime limit per test5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputThis task is very simple. Given a string S
2015-07-15 11:20:01
1943
原创 BNUOJ 27935 我爱背单词 (加强版) (FFT)
题目链接：BNUOJ 27935 - 我爱背单词 (中文题面)分析：原题数据范围很小，可以直接暴力计算新单词对每一天需要背的单词量的贡献，注意到这个过程实质是一个多项式乘法，第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
1197
原创 BNUOJ 12887 isumi (计算几何+最小割)
题目链接：BNUOJ 12887 - isumi (中文题面)分析：对题目中的图乱画一下发现，如果根据圆和矩形上下边相交的关系以及圆与圆之间相交的关系建图，由于存在一条从矩形左边走到右边且不与任何圆相交的路径等价于S和T不连通，那么只需选取尽可能少的点，使得删去这些点之后S和T不连通，拆点求最小割即可。代码：#include#include#in
2015-06-25 21:21:40
1003
原创 ZOJ 3842 Cirno's Perfect Math Class (Kummer定理)
Cirno's Perfect Math ClassTime Limit: 2 Seconds Memory Limit: 65536 KB "Minnaa ~ Cirno no Sansuu Kyoushitsu Hajimaruyo ~ "Cirno's perfect math class is fashionable over the world. But
2015-06-20 05:49:51
2874
1
原创 Codeforces 546E Soldier and Traveling (最大流)
E. Soldier and Travelingtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputIn the country there are n cities a
2015-06-20 05:35:03
1665
1
原创 Codeforces 551E GukiZ and GukiZiana (分块)
E. GukiZ and GukiZianatime limit per test10 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputProfessor GukiZ was playing with ar
2015-06-14 00:12:59
1742
7
原创 Codeforces 12D Ball (线段树)
D. Balltime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputN ladies attend the ball in the King's palace. Ever
2015-06-12 20:30:58
1981
2
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人