- 博客(99)
- 收藏
- 关注
RSS订阅原创 hackerrank infinitum10 Fun with 1010
题目大意给定N,MN,M,求出 ∑i=1M⎡⎣∑j=1i(Nj)⎤⎦3mod2000003\sum_{i=1}^M \left[\sum_{j=1}^i \binom{N}{j}\right]^3 \bmod{2000003}数据范围1≤N≤M≤10121 \leq N \leq M \leq 10^{12}题解首先，对于i>Ni > N的情况，显然他们的和就等于(M−N)(2N−1)3(M-
2016-12-24 14:58:07
881
原创 Codechef DECEMBER16 BOUNCE
题目大意假设现在有个R∗CR*C的盒子，一开始在(0,0)(0,0)有颗珠子，你朝右上角45度方向把珠子弹出，珠子碰到墙壁会反弹（依据反射定律），珠子到了某个角后就弹出了，游戏结束。珠子每到一个墙，就会相对应的把墙上的字符记录到S(R,C)S(R,C)上，比如珠子先后碰到上下左右，那么S(R,C)="TDLR"S(R,C)="TDLR"，一个盒子的权值就是S(R,C)S(R,C)的长度。 现在给定
2016-12-12 21:42:09
1177
1
原创 比较悲惨的一周
这周打了两场比赛，一场是TC 701，一场是BC Round #89，最终结果都非常不理想，所以在这里总（fa）结（lao sao）一下。TC 701比赛前还是很有信心的，毕竟不做挂基本能涨涨rating就到红名了。一开始看题，第一题第一眼看上去是找个循环节直接做，但是思路不清晰，而且整个人都很紧张，然后就一直在想有没有什么其他规律能不能用其他做法之类的，一直看了20多分钟第一题，然后觉得再做第一题
2016-10-29 22:36:48
1816
2
原创 codeforces 717A
题目大意给定l,r,kl,r,k，求出： ∑i=lr(fi+2k)\sum_{i=l}^r \binom{f_{i+2}}{k} f(n)=n,n≤1f(n) = n,n \leq 1 f(n)=f(n−1)+f(n−2),n>1f(n)=f(n-1)+f(n-2),n>1数据范围k≤500k \leq 500,0≤l≤r≤10180 \leq l \leq r \leq 10^{18}题
2016-09-16 16:51:01
1270
原创 OICamp 2016 Day2 路径数
题目大意给定n,m,q,pn,m,q,p，令 c[i][j]=(qj×c[i−1][j]+c[i][j−1])modpc[i][j] = (q^j \times c[i-1][j] + c[i][j-1]) \bmod{p} 假如i=0i=0或j=0j=0，c[i][j]=1c[i][j]=1。 求出c[n][m]c[n][m]数据范围n,m,q≤109n,m,q \leq 10^9 p≤2
2016-09-06 22:13:06
765
原创 hackerrank infinitum16 E To Infinity and Beyond
题目大意给定A,B,CA,B,C，求出 ∑a=0A∑b=0B(a+ba)∑x=1min(A−a,B−b,C)(A−a−1x−1)(B−b−1x−1)(C−1x−1)\sum_{a=0}^A\sum_{b=0}^B \binom{a+b}{a}\sum_{x=1}^{min(A-a,B-b,C)}\binom{A-a-1}{x-1}\binom{B-b-1}{x-1}\binom{C-1}{
2016-09-05 09:33:16
653
原创 SRM 683 div1 hard
题目大意一开始有个人在(x0,y0)(x_0,y_0)，有tt个时间点，每个时间点这个人会上下左右四个方向随机选一个方向走。给定n,mn,m，最后假如这个人停在了(x,y)(x,y)，他的权值v=xnymv = x^ny^m。问(E[v]×4t)mod109+7(E[v]\times 4^t) \bmod{10^9+7}。n,m≤100,t≤109n,m \leq 100,t \leq 10^9题解
2016-08-25 21:48:46
875
原创 SRM 676 div1 hard
题目大意有nn种植物，每种植物生长需要tit_i的时间，当然了，植物可以同时生长。现在有若干条限制xi,yix_i,y_i，表示植物yiy_i要等xix_i生长完了他才能开始生成长。对于每种植物，可以用cic_i的代价使其生长时间减1，可以重复使用，但最多减为0。问最少要多少时间所有植物才能长完。 n≤50n \leq 50题解这题很难。首先假设有两种超级植物S,TS,T，表示SS要一开始长，TT
2016-08-22 11:12:29
871
2
原创 SRM 697 div1 hard
题目大意有nn个城市，每个城市有个权值wiw_i，任意两个城市i,ji,j之间的道路数有wi∗wjw_i*w_j条。对于每种生成树，设每个点的度数为did_i，其权值定义为∏di\prod d_i。问所有无根生成树的权值和。答案对109+710^9+7取模。 n≤2000n \leq 2000题解因为与度数有关，所以很容易就能套上prufer序列。事实上，答案求的是这个东西： ==∑a1+⋯+a
2016-08-19 08:44:45
1181
原创 NOI2016题解
Day1T1 优秀的拆分T2 网格答案只可能是-1，0，1，2。 1. 先判断答案是否为0，相当于要判空格子是否连通。假如不连通，相当于有空格子被一些障碍点围住了（联想一下围棋。。）。那么我们按八连通把障碍的联通块搜出来，然后对于每个联通块，判断与他们八连通的空格子是否属于一个联通块（四连通），假如不是，则这幅图不连通。 2. 接下来答案为1相当于存在一个割点。首先做一些
2016-08-10 16:04:33
5922
4
原创 NOI2016 day1 总（xia）结（che）
感觉这天考的不算比较好QAQ。。一开始看题，看到第一题数据范围是30000，好难啊不会做，然后看第二题，平面图，割成两半，网络流？？？不会构图啊。。。第三题，什么鬼啊，我连怎么判是不是都不会。。于是再回去看第一题，发现95是n^2暴力，感觉想出来正解再码亏的分不会比5分少，然后这时二，三题都没啥思路，于是就先搞了第一题。感觉码程序的感觉不是很好，9点半左右才搞掉第一题。上了个厕所，发现第二题答案不超
2016-07-24 22:16:46
3127
原创 NOI2016模拟赛（6.20~6.21）（差不多爆零）总结
Day1一开始看题，第一题就是道裸的二维线段树嘛，给了3s，400M一点都不虚。然后就去想想第二题，没有思路，第三题，更没有思路，感觉很奇怪啊。然后看题想题用了1个钟开始码第一题。发现自己忘记了二维线段树要怎么打标记，然后开始推，推着推着觉得常数好像挺大的，不过还是挺相信自己的卡常能力，二维树状数组好麻烦的呀，而且感觉常数没有少多少啊。然后码到9：30，过样例了拍也没有问题。一测极限居然要拍5s。然
2016-06-21 22:46:42
1268
原创 2015 ACM-ICPC Regional长春
A Too Rich题目大意现在有面值为1,5,10,20,50,100,200,500,1000,2000十种硬币，给定每种硬币的数量。你要选出尽量多的硬币，使得其面值恰好为pp，无解输出-1。数据范围p≤109p \leq 10^9，数据组数≤20000\leq 20000题解这题假如没有50，500两种硬币的话，相当于剩下1,5,10,20,100,200,1000,20001,5,10,20
2016-05-23 22:31:30
1406
原创 SDOI2016 平凡的骰子
题目大意给定一个MM个面NN个点的凸多面体，设OO为该凸多面体的重心，以OO为球心做单位球CC。对于每个面，设其点集为SS，对于所有ii，做OO与SiS_i的连线，线必与CC有交点，那么对于一个面，就有一个交点集合也是一个球面TT。一个面的权值是其TT的面积除以4π4 \pi。问每个面的权值是多少。数据范围N,M≤100N,M \leq 100题解这道题考了很多结论，所以我考场上根本不会做。。 首
2016-05-20 20:25:00
1545
原创 APIO2016总结
人生第一次也是最后一次以参赛选手身份参加APIO（谁知道我以后还会不会再来呢？），虽然是“A”队，但没有进前6，所以并没有什么卵用，连个国际牌都坑不过来。Day0第一次广州飞北京没有延误，感觉靠谱，但是到酒店已经5点钟，发现只有唯一一次试机机会刚好5点结束，于是就没得试机了。晚上发现是跟金山中学的高一省队爷陈子陵住，十分好评。但是他晚上好晚才回来，所以睡的不是很好。Day1一早起来发现北京真的是无比
2016-05-09 22:16:39
2693
1
原创 GDOI2016总结
题外话这次我们和石门都挂得很惨啊，听到郭老师说这次15人终于不是这两个学校垄断时居然莫名伤感。不能怪题目，只能怪自己实力不足，高中两年都没有拿到团体总分第一，那张奖状我都有点不爽了，算了算了，反正也是省选退役选手，希望后辈加油，拿回那曾属于我们的奖杯吧。。Day0因为塞车，坐了大概2个半钟才到四会，一路上发现粤北地区跟珠三角差了不只两三年的发展啊。。酒店附近真的什么都没有，有点后悔过来的时候没有买好
2016-05-03 20:29:18
1545
6
原创 GDOI最后一次终极模拟赛总结
最后一次模拟赛结束了，省选前散金一千爆满人品，希望这次GDOI能Rp++吧。。Day1第一天是SDOI Day2三道题加一道CF原题。一开始看题，发现第一题就是一道SAM裸题，然后看第二题，是道奇怪的计数题，没什么思路，然后去看第三题，发现就是一道裸的斜率优化题，第四题忘了题解是什么做法了，然后之前问肥佬也没有告诉我，于是觉得第四题要坑点时间上去。再去看第二题时发现比较SB，然后就开始码，总共读题加
2016-04-27 22:44:53
1295
3
原创 GDOI2016第一次终极模拟总结
感觉发挥的还算平稳，但每天都有分数没有搞到，不能做到分分必拿，还是比较亏的。Day1一开始看题，第一题一看题就开始推公式，发现要维护个凸壳，还要维护前后凸壳，看起来非常地奇怪，再看第二题，看数据范围都知道要矩阵乘法，推了一下状态发现比较简单，然后看第三题，画风比较奇怪，应该要求一个欧几里德最小生成树，然后模拟一下，但不会求，最后一题不怎么懂，只会没有障碍的20分做法。看完题想了一会儿大概过了1个钟，
2016-04-23 22:23:47
1015
1
原创 HNOI2016 矿区
题目大意给定一个NN个点MM条边的平面图GG。有QQ个询问，每次询问平面图上的一个区域AA，（逆时针地给定多边形的点集），你需要求出∑P⊂AS(P)2∑P⊂AS(P)\frac{\sum_{P \subset A} S(P)^2}{\sum_{P \subset A} S(P)}，S(P)S(P)表示PP这个面的面积。数据范围N≤2∗105,M≤3N−6N \leq 2 * 10^5,M \leq
2016-04-20 15:19:59
1747
原创 湖南集训总结
出来二十多天，感受挺深的。。 做了大概六轮，总共13场比赛。有做的好的，也有做的不好的，总体而言发挥的不算太好。雅礼的人的确是挺强的，除了mx和yyt以外其他人的实力都比较均衡，而且都属于比较顶尖的水平。猪猪侠就更强了，基本上每天都是Rank1，相比之下我就比较萎了，没什么比较出色的表现，不过出来就是为了学习以及被虐的，心态放平衡点吧。 做的最崩的就是第三轮了，两天都爆炸了，总分排到了四十几名，
2016-04-15 20:27:09
1372
原创 HNOI模拟4.7 yist
题目大意你需要找到NN个点，每个点离原点的距离分别为R1,R2,⋯,RnR_1,R_2,\cdots,R_n，问NN个点形成的凸包的最大面积是多少？数据范围N≤8N \leq 8题解我们可以先枚举最终凸包上是哪些点，以及这些点的顺序，那么现在的问题相当于要确定一些角度θi\theta_{i}，表示极角序相邻两个点的极角差，满足∑ni=1θi=2∗π,θi≥0\sum_{i=1}^n \theta_{
2016-04-07 20:47:27
1139
原创 HNOI模拟赛总结
这几次模拟真的是炸的非常的严重，而且炸了之后还没有认真反思，导致炸了之后接着炸，感觉整个人都不好了。。Round 1Round1是雅礼出题，发挥的不算太好但还是正常水平。Day1第一天的第一题做过，第二题是一个比较裸的数据结构，第三题是道比较神的字符串题，但是拿30分还是没什么问题的。 第一题很快就打完，但可能是觉得做过，所以读题的时候连数据范围都没有看清楚，2∗1052 * 10^5都能看成是1
2016-04-01 19:24:15
1252
原创 BZOJ4248 JOI15 AAQQZ
题目大意给定一个字串集为[1,C][1,C]的长度为NN的字符串SS，你可以选择一个区间[L,R][L,R]，将[L,R][L,R]中的字符从小到大排序，接着你得到的权值就是当前SS中的最长回文串的长度。问你最多能得到多大权值。数据范围1≤C,N≤30001 \leq C,N \leq 3000题解这道题感觉非常的好玩，不知道为什么要强行说是一个分类讨论题。。。 首先我们将最终得到的最长回文串的回
2016-03-28 22:52:54
1384
原创 HNOI2016模拟 disk
题目大意现在有A,BA,B两个工厂，你有nn天的时间去生产KK张光盘。一开始每张光盘都没有被加工，对于一张光盘，你需要先把他送到AA工厂加工，然后将加工后的光盘送到BB工厂再加工，最终生产出来，注意对于一个工厂每天最多加工一张光盘，但是一天内你可以将一张光盘从AA加工再送到BB处加工。对于AA工厂，其第ii天加工一张光盘的代价为AiA_i，BB工厂为BiB_i。给定N,K,Ai,BiN,K,A_i,
2016-03-28 22:03:05
1182
1
原创 GDOI模拟 装饰
题目大意有一个2∗M2 * M的彩带，彩带的每个格子都可以染上红色，蓝色，绿色中的一种颜色，一个彩带被称为合法的，当且仅当 1. 相邻两个格子的颜色不同 2. 对于每个2*2的小矩阵三种颜色都要出现 3. 整个彩带上有RR个红色格子，BB个蓝色格子，GG个绿色格子。给定M,R,B,GM,R,B,G，求可能的合法彩带数。对109+710^9 + 7取模。数据范围R+B+G=2∗M,0≤M≤100
2016-03-16 21:34:02
992
原创 GDOI模拟 染色配对
题目大意定义一个点的集合SS为团，当且仅当对于任意SS中的两个点，都有边直接连接。定义极大团表示这个集合是团，并且不存在另外一个团包含它。现在给定一副特殊的图，图中的每个点恰好属于两个极大团，给定每个点属于的两个极大团的编号，问这个图的最大匹配是多少，以及其中一种匹配方案。设图中有NN个点，总共有MM个极大团。数据范围N≤2∗105,M≤2∗104N \leq 2 * 10^5,M \leq 2 *
2016-03-09 17:32:59
994
原创 CF 627E
题意给定一个R∗CR * C的矩阵，一开始每个位置都是0。然后有NN个特殊的位置xi,yix_i,y_i，其权值为11。问你可以从这个矩阵中选出多少个子矩阵，满足这个矩阵中有至少KK个11。数据范围1≤R,C,N≤30001 \leq R,C,N \leq 3000 K≤min(N,10)K \leq \min(N,10)题解首先，一个矩阵可以由两个二元组(x,x1),(y,y1)(x,x_1),
2016-03-08 20:46:31
1185
原创 CF 468E
题意给定一个N∗NN * N的矩阵AA。对于AA中的KK个位置(xi,yi)(x_i,y_i)，给定其权值ViV_i。对于其他未被确定的位置，其权值为1。现在希望你求出 ∑σ∏Ni=1Ai,σ(i)\sum_{\sigma} \prod_{i=1}^N A_{i,\sigma(i)}，其中σ\sigma为1∼N1 \sim N的排列。数据范围N≤105,K≤50N \leq 10^5,K \leq
2016-03-07 11:54:31
1475
原创 CF 559E
题目大意在一条(−∞,+∞)(- \infty,+\infty)的数轴上，有NN盏探照灯，坐标分别为aia_i。每盏探照灯都可以往负方向或正方向发射光线，但每盏灯都有一个强度lil_i，也就是说他最多只能照到(ai−li,ai)(a_i - l_i,a_i)或(ai,ai+li)(a_i,a_i + l_i)。问你，在合法的规划每盏灯的方向下，最多能照到多少长度的数轴。一段数轴(l,r)(l,r)的
2016-02-29 20:18:34
10509
原创 GDOI模拟 2.26
做题过程一开始拿到题，第一题好像挺简单的样子。然后第二题不会做，第三题不会做，第四题不会做。。然后觉得二三应该是最不可做的，于是去看第四题。第四题推了一下，算出来了一条式子，感觉线段树可以做。于是开始打第一题，拍了一下，发现没什么问题。于是去打第四题，第四题其实不算难打，但由于是浮点数，所以要考虑各种各样的情况。打完拍完差不多还有一个多钟的时间。然后去打第二题的30分暴力，搞了个随机化想骗点分。接着
2016-02-26 07:15:36
786
原创 CF582D
题目大意给定P,K,NP,K,N,求出有多少对x,yx,y，满足x≤y≤Nx \leq y \leq N，CxymodpK=0C_{y}^{x} \bmod p^K = 0数据范围N≤101000N \leq 10^{1000} 1≤P,K≤1091 \leq P,K \leq 10^9 PP为质数题解首先，Cxy=y!x!∗(y−x)!C_{y}^x = \frac{y!}{x! * (y -
2016-02-24 22:33:11
1249
原创 关于一类位运算多项式相乘的做法
题目大意给定两个下标均为[0..2n−1][0..2^n - 1]的多项式A,BA,B，数组C=A×BC = A \times B，满足 Ci=∑(j op k)=iAj∗BkC_i = \sum_{(j~op~k) = i} A_j * B_k其中opop可以为三种位运算符号or,and,xoror,and,xor。题解这种问题有一个经典的做法，Fast Walsh-Hadamard Trans
2016-02-24 16:41:39
1052
原创 GDKOI2016 总结
高二的第三场比赛，考得还算可以，再接再厉吧。四年了，在同一个地方，从一开始的三等奖，再到二等奖，再到一等奖…Day18：10开考。一开始拿到题目，看了一下第一题，觉得可以直接化成区间和形式，推了一下，发现用10个线段树就好了。然后看第二题，是个计期望的题目，没有灵感。然后去看第三题，这题面看起来很奇怪，再读了一遍题，把式子整理了一下，发现就是个裸的网络流，不过代码量挺大的，接着看第四题，怎么又是道裸
2016-02-23 15:50:07
1146
原创 GDKOI2016 小学生数学题
题目描述给定N,K,PN,K,P，求 (∑Ni=11i)modPK(\sum_{i=1}^{N} \frac{1}{i}) \bmod P^K 若答案不存在则输出-1数据范围N∗PK≤1018N * P^K \leq 10^{18} P≤105P \leq 10^5 PP为质数题解这道题的确是道不错的数学题。设f(n,k)=(∑ni=11i)modPkf(n,k) = (\sum_{i=1}
2016-02-22 21:38:48
1463
5
原创 CF 618G
题目大意一开始有NN个空位。给定一个概率PP。每次你有PP的概率在第NN个空位加入一个11，有1−P1 - P的概率加入一个22。加入之后，你会将这个数字往前推，假如当前数字遇到了另外一个和他值一样的数字，设为vv，那么当前空位的数字变为v+1v + 1，并且继续往前推。直到到达边界或遇到一个不一样的数字。游戏结束当且仅当所有空位都放了数字。一种结束局面的权值定义为所有数字的和。问你最终结束时局面的
2016-02-19 10:27:30
2714
原创 GDKOI前模拟总结
连续做了4天的模拟赛，比赛之前打击一下自信心是很好的事情。Day1一开始看题发现第一题都不会感觉生活没有希望。然后看第二题，好像做过很多遍了。第三题看了题面都觉得不可做，接着第四题，一直在化简式子，没有找到突破点。然后先打了第二题。接着第一题想错了，以为匹配是对的，对拍的时候发现错了。然后一直调后来发现整个算法都是错的。去继续搞第四题，但思维还是没有跳出来，离正解就差一步了。。。还剩1个钟，感觉只有
2016-02-19 08:50:50
901
原创 GDKOI模拟 Manufactoria
化简后题意给定三个用图表示的自动机。自动机上的边分为a,b,nulla,b,null三种，对于当前字符串的位置ii，假如Si=aS_i = a则走aa边，Si=bS_i = b则走bb边，若为空则走nullnull边。设三个自动机为A,B,CA,B,C，从中保留最少的自动机，设为集合TT，使得TT的可识别字符串集合等于A∩B∩CA\cap B \cap C可识别字符串集合。值得注意的是，字符串的长度
2016-02-16 21:02:46
1112
原创 WC2016 expr
题目大意要求操作是在线且完全可持久化的。N≤20000,M≤20000,K≤100N \leq 20000,M \leq 20000,K \leq 100题解先考虑一个简单的问题，K=1K = 1。那么很显然，由于运算满足结合律，那么我们可以直接用一颗简单的可持久化Treap就可以完成所有的操作。接下来考虑k>1k > 1。首先很显然的，假设当前要求出F(S)F(S)，其中SS为一个表达式，我们可以
2016-02-02 19:41:51
871
2
原创 WC2016 NPC
题目大意给定了NN个小球，MM个盒子。每个盒子最多只能装下3个小球。并且对于小球ii，有一个盒子集合SiS_i，表示小球ii只能被装进盒子j∈Sij \in S_i。我们定义一个盒子为好的，当且仅当其最后装的小球个数不超过1个。问在把所有小球都装好之后，最多有多少的好的盒子。M≤100,N≤300M \leq 100,N \leq 300。题解假设最后存在一种方案使得所有盒子都是好的，那么显然就是一
2016-01-31 20:07:33
1246
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人