jr_mz-CSDN博客

原创非常规几何？

复数与几何射影几何交比与调和点列先挖个坑

2018-08-12 22:35:12 251

原创数论数学的皇冠

一整数整数的离散性：对于整数a,b，如果a<b，那么a<=b-1（以下[x]表示不大于x的最大整数）。1. 正整数a,b,c,d满足a/b+c/d<1，a+c<n，证明a/b+c/d<1-1/n^3。2. 给定正整数n,m(m<n)，证明存在非负整数p,q(q<p<n)，满足对于任意正整数x(x<n)，有[qx/p]=[mx/n]...

2018-08-07 11:13:30 1072

原创 math...

可怜的假高中生ztr不再有资格成为一名信竞选手，但他总还可以是一个可怜的数学爱好者。这一页的题目将展现一些常规技巧。一讨论暴力即雅1. 平面上有四个圆，半径分别为1,2,3,R，这四个圆两两相切，且六个切点两两不同。求R的可能取值。2. 平面直角坐标系上有A(0,0),B(0,2),C（未确定）,D(2,2)，存在一点P使得S△ABP=S△BCP=S△CDP=S△ADP，求...

2018-08-06 20:38:08 401 2

原创 CTSC2017游记

2017年来我两次参加NOI系列赛事，一次是非集训队Rank2，另一次也是非集训队Rank2。你问我为什么不是Rank1，大概是因为我心中已经有了Rank1的人。Day0高铁虽快但是路也很远，下午才到北京听说明天一早就考试了，但是扑克还是要打的可是讲讲道理，为什么歧视弱校，就偏偏分给弱校一堆大床房强塞双人呢Day1虽然不知道发生了什么，但是好像就是感冒了而且机房空气

2017-05-14 23:24:00 1218

原创 ZJOI2017Day2 游记

wori竟然真的奶成A队了谢考前一天不阿之恩看了下去年的滚粗记嘛那这里我就来一句NOI2017, count me in!啊好累啊别的不想写直接讲考试了看了下题T1好像很有趣的样子然而对着大样例搞了搞好像并不是很有用没带笔然后懒得找老师借于是用着只有很小的常数步撤销的winxp画图来模拟真不是好主意当然没有相同盘的时候答案很简单这我还是知道的看T2。。。wori。。

2017-04-28 17:41:16 1508 2

原创 ZJOI2017Day1 游记

3.20出发，车程很长，而且还只停了个没KFC只卖烧饼的傻逼服务区，气不气。差不多下午才到，吃个KFC充充午饭啊。晚上浪浪浪，组队在温州城里随机乱逛，大餐吃吃人生聊聊。3.21上午猪猪侠的搜索课，我怎么被请上去了啊，那就假装自己是演员了啊。中午吃的食堂有点迷啊。下午613的stl和吴爷的杂题，那上去演一演是妥妥没跑的啊。晚上继续浪，大餐吃吃，扑克打打。我就出个A

2017-03-24 13:42:02 1026

原创多项式求逆

设已知A(x)B(x)=1(mod x^n)，考虑A(x)C(x)=1(mod x^2n)显然B(x)-C(x)=0(mod x^n)平方得B(x)^2-2B(x)C(x)+C(x)^2=0(mod x^2n)同乘A(x)得A(x)B(x)^2-2B(x)+C(x)=0(mod x^2n)即有C(x)=2B(x)-A(x)B(x)^2，fft即可设A(x)常数项为t，则A(x)

2017-02-19 21:08:45 1412

原创 UOJ86 mx的组合数

大概看到题的时候就会做了。好厉害的题。组合数模质数p等于某值的方案数，很容易想到利用卢卡斯定理。然后要使p进制下每一位对出的结果的乘积在模p意义下为某值，数位dp一波就好。暴力转移是每位p^2的，但是转移的形式是c[i*j]+=a[i]*b[j]，可以考虑找原根R，这就变成了c[logRi+logRj]+=a[logRi]*b[logRj]，这里NTT就好了，模数还刚好是998244353

2017-02-16 21:18:37 665

原创 thuwc2017滚粗记

开幕讲话一言不合讲到恋爱很滑稽啊？试机题目非常因吹斯听啊？考试题目怎么有点妙啊？第一题怎么提示里给了泰勒展开公式啊？那我们把各种函数强行泰勒展开就可以很容易的维护了啊？那就是一个裸lct了啊？那我要是A了第一题岂不是美滋滋？我怎么lct也码挂了啊？感觉不一定有希望调出来啊？不如码个线段树拿拿55分？第二题感觉是个很高明的计数题啊？后来果然是陈老师的题啊？

2017-02-12 19:21:27 986

原创 WC2017滚粗记

总结一下就是没拿到rank1，太失败了。这次WC在绍兴举办，比去年的绵阳不知道高到哪里去了啊？听听课打打隔膜面面基岂不是美滋滋？考试的时间怎么略微不太对啊？第一题好像很高明啊？第二题官方卡常厉害了啊？第三题提答题并行思想好像也很妙啊？第一题瞎暴力40分啊？第二题卡常姿势并不高超只好45啊？第三题瞎贪心居然也有29分啊？这总共才114分感觉有点滚啊？第一题

2017-02-12 19:10:55 676

原创 NOIp2016滚粗记

总结一下就是没拿到接近600（部分题目卡常），太失败了。Day0被阿了两次，debuff+=inf。然后被阿了之后头有点晕虽然我也不知道为什么会这样。晚饭的时候在校园里逛。顺便看了一下几个好久不见的妹子，然后因为头晕，甚至不知道聊什么话好（雾）。Day1Day1迷之爆炸，过程大概是这样的：T1秒掉。T2预处理了一波发现需要数据结构，map启发式合并可干，然后

2016-11-21 17:27:02 900

原创数据结构复习(Updating)

发现很多数据结构我都是只写过一两次根本不熟练，有些东西的某些应用都不太了解。感觉药丸，反正先挖个坑。UPD 2016.11.23 动态开点线段树及其合并这里居然有个坑。然后我是不是奶了一下，然后我在NOIp中写数据结构就挂了。先来干一发动态开点线段树及其合并，讲一讲基本操作。思路很简单，就是假装有一个下标范围非常大（通常是权值范围1...V）的线段树，原先的结点数量非常

2016-10-17 15:33:42 665

原创 bzoj4589 Hard Nim

http://www.lydsy.com/JudgeOnline/problem.php?id=4589题意：石子堆数为N且每堆石子的数量都是不大于M的质数的Nim游戏，求先手必败的局面数量模10^9+7。N也即，有依次N个不大于M的质数，求异或和为0的方案数。考虑暴力dp，令f[i][j]为前i堆石子异或和为j的方案数，则f[0][0]=1，f[0][j]=0(j>0)，f[i][j

2016-06-07 22:03:48 2408

原创 CTSC2016游记

5.1坐了很久的火车终于到了北京，然后又坐地铁，非常疲惫，然后听说明天就是考试……然而晚上还是出去浪，并决定要买三国杀，但是用谋财地图找了好几个书报亭都没找到……5.2YJQYJQ?YJQYJQ!和WC一样是纸质试题。比赛开始，我先花了一个多小时看懂了第一题的题面，然后敲完了前两题的裸暴力，然后大概剩下三个半小时玩第三题提答。然后因为我是傻逼，又出了一点偏差，本来应该30多

2016-05-06 18:55:28 2632

原创 ZJOI2016Day2游记幻灭

一试我的排名好像大概恰好是15，然而noip分数偏低，所以总排名大概25的样子。这就意味着，二试还得再发挥好些。4.25坐了很久的车到了余姚中学。4.26~4.27感觉讲课非常可听啊，也没有出现像一试中的量子计算理论那样鬼畜的东西啦。4.285 hours of life清晨，雨，我在宾馆的窗户内表面凝出的水汽层上写道。进不进队就决定在这5个小时了，而这个结

2016-04-29 20:13:16 1877 1

原创 bzoj4542 大数

http://www.lydsy.com/JudgeOnline/problem.php?id=4542题意：有一个仅包含'0'～'9'的字符串S[1...N]和一个质数P，M次询问，每次给定正整数L,R，询问有多少个不同位置的允许前导0的子串S[L0...R0]满足L考虑如何快速判断一个子串S[L0...R0]对应的十进制数是否为P的倍数。考虑预处理好每个后缀S[i...N]模P的值

2016-04-19 10:05:54 1139

原创一场BC的台前幕后

#define BC BestCoder一场BC的台前幕后起源大概是这样的：一个月前的BC#75结束后，AK的人非常多，于是CodeVS群里很多人吐槽BC#75的质量，这时YJQ对KPM说：“我们来出一场BC吧！”恰好最近屯了几个原创，并且发现给BC出比赛居然有钱拿，而且还不少，而给CodeVS出比赛就没钱拿，虽然说好有奖品但是奖品一直没有出现，于是我就萌生了给BC出题的想法。然后又觉得一

2016-04-10 01:14:37 1457 3

原创 bzoj3209 花神的数论题

http://www.lydsy.com/JudgeOnline/problem.php?id=3209题意：求sum(1)*sum(2)*...*sum(n)，其中sum(x)表示x的二进制表达中1的数量。答案模10^7+7。n考虑枚举sum(x)的值为t，然后求有多少个不大于n的正整数的二进制表达恰好有t个1，设这个答案为f(t)。这一部分可以用数位dp来实现。例如要求解1...1

2016-04-05 23:43:07 1153

原创 bzoj4404 Binary vs Decimal

http://www.lydsy.com/JudgeOnline/problem.php?id=4404题意：找出第n小的正整数，满足其十进制表达是其二进制表达的后缀。n一个半月没更新博客了，感觉最近好浪啊。对小数据打规律可以发现，如果一个正整数是满足条件的，那么其十进制表达的任何一个（以1开头的）后缀所对应的十进制数也是满足条件的。例如，1100（十进制）是满足条件的，其后缀10

2016-04-05 16:09:39 1146

原创 bzoj2326&CodeVS2314 数学作业

http://www.lydsy.com/JudgeOnline/problem.php?id=2326 http://codevs.cn/problem/2314/题意：求123456789101112……n对m取模的结果。n记f(i)=Concatenate(1...i)，则有f(i+1)=f(i)*10^k+i+1，其中k为i+1的位数。首先，对于连续的一段递推式，10^k的值是

2016-02-16 20:17:02 954

原创 WC2016滚粗记

day1(1.25)坐飞机很不舒服寝室很差day2~day5每天都去第一课堂台上的神犇讲着一些听不懂的东西台下的我打打电脑玩玩手机没电了就睡觉收获甚少有点后悔没去第二课堂不过学生上课总是比较欢乐day6被考试的题目吓傻了第三题开始居然没看到有部分分于是根本不敢打先开始玩第二题不想写SAM,SA,KMP于是机智字符串哈希了一发模数1

2016-02-02 08:14:33 950

原创主席树学习笔记

问题：给定一个n个数的序列，q次询问第x个数到第y个数中的第k最值。我们假定是第k小。为了使讨论更加简便，我们假定序列的每个数都是不大于n的正整数。当然一般题目中元素范围很大，但是可以用离散化预处理来做到这一点。考虑一个比较高端的做法：令g[i][j]为前i个数中，值为j的数的个数。很容易用O(n^2)的代价获得f数组和其前缀和数组f[i][j]，其中f[i][j]表示前i个数中，不大于j

2016-01-05 20:34:25 813

原创 bzoj2819 Nim

http://www.lydsy.com/JudgeOnline/problem.php?id=2819题意：对一棵树单点修改和询问链上各点权作为Nim游戏的初始局面先手是否有必胜策略。n,q众所周知，一个Nim游戏的初始局面是先手必胜的当前仅当各堆石子数的异或结果不为0，因此题目等价于单点修改和询问链异或结果。先考虑没有修改的情况，由于异或运算具有可加减性，很容易想到这个做法：任取一

2015-12-23 14:56:56 759

原创 bzoj3329 Xorequ

http://www.lydsy.com/JudgeOnline/problem.php?id=3329题意：已知方程x xor 3x=2x，给定N，求该方程有多少个不大于N的正整数解，有多少个不大于2^N的正整数解，第二问的答案对1000000007取模。N方程等价于x xor 2x=3x，又有x+2x=3x，易知x and 2x=0。再注意到2x实际上就是x注意到2^N和0都一

2015-12-18 14:29:03 1026

原创 bzoj1047&CodeVS1715 理想的正方形

http://www.lydsy.com/JudgeOnline/problem.php?id=1047 http://codevs.cn/problem/1715/题意：给定一个a*b的矩阵，找出其中的一个n*n矩阵使得矩阵中数字的极差最小，a,b很显然，如果我们能够求出每一个矩阵中数字的最大值和最小值，那么只要再加一个枚举就够了。这个可以单调队列实现，但是这里由于a*b不是很大，复

2015-12-06 22:40:47 838

原创 NOIp2015提高组解题报告

比赛几个星期前就结束了，玩乐了一会儿，开始学术。此文非题解。只是我自己的现场解题实录。Day_0到宾馆后紧张的要死。晚上写了一堆基础模板：spfa最短路径，prim和kruskal的最小生成树，hungary的二分图匹配，树状数组，kmp字符串匹配，等等。然后突然发现了一个叫做2-SAT的神奇算法。问了下居然是NOIp可能考的。赶紧看了下做法。然后发现自己tarjan强联通分量

2015-12-03 18:34:33 4926

原创 bzoj1040&CodeVS1423 骑士

http://www.lydsy.com/JudgeOnline/problem.php?id=1040http://codevs.cn/problem/1423/前言：这是第一次发bzoj题解，纪念一下。noip在即，大家都要加油哦。题意：有N个点，对于每个点都给出另一个点，表示它们之间有一条无向边。求最大带权独立子集。这整个图不一定联通，但是每一个联通子图都有一个性质：边数

2015-11-06 12:08:34 564

原创 CodeVS2319 最近最远点对

http://codevs.cn/problem/2319/题意：给定笛卡尔平面内的若干个点，求最近两点的距离和最远两点的距离，距离是欧氏距离，点数不大于100,000。对于最近点对考虑分治的做法：用一条直线将所有点分成两部分，对于两部分的点进行分治，然后考虑两部分联合的结果。可以先把所有点按纵坐标排序，这样就容易用平行于x轴的直线划分。设两边分别求出的结果的较小值是d，我们只需考虑直

2015-10-04 13:24:59 1278

原创 CodeVS1513 皇帝的烦恼

http://codevs.cn/problem/1513/题意：n个集合围成一圈，已知第i个集合有Ai个元素，且任意相邻两集合的交集为空集，求所有集合的并集的最小元素数。如果是n个集合围成一排那会非常简单，答案就是每相邻两个Ai之和的最大值，但是这种算法显然不适用于环。观察数据范围我们容易想到这是O(nlogn)的题目，又因为是求最小元素数，可以考虑使用二分。二分答案，然后根据相

2015-09-26 21:05:41 893

原创 CodeVS1428 棋盘制作

http://codevs.cn/problem/1428/题意：给定一个N行M列的01矩阵，要求找出元素数最多的子正方阵和子矩阵，使得其中任意两个相邻元素均不同，N,M任意相邻两个元素均不同就意味着，要么奇数位上全0偶数位上全1，要么奇数位上全1偶数位上全0，这里的奇偶指的是行数和列数之和的奇偶性。这个问题和经典的最大全0子矩阵有着很大的相似性，我们可以考虑转化过去。先来讲一讲最大全

2015-09-25 23:20:54 515

原创 bzoj2751&CodeVS1853 容易题

http://www.lydsy.com/JudgeOnline/problem.php?id=2751 http://codevs.cn/problem/1853/题意：有一个数列共有m项，其中每一项的值都是不大于n的正整数，并且给出k个形如第i项不能为j的约束。求出所有可能的数列的各项之积之和对1,000,000,007取模的结果。例如n=2,m=2,约束第1项不能填1，则数列可以是2

2015-09-22 21:15:09 528

原创 CodeVS1636 向量加法化简

http://codevs.cn/problem/1636/题意：定义一个向量的格式为：非零向量为XY，其中X和Y都是大写字母，即省略了箭头，零向量则是单独的一个0。给定n个向量，计算化简这些向量的和，表示为XY或kXY或0的形式。如AB，BC，AC应该被化简为2AC。考虑基础情况：PQ+QR=PR，实质上是把一个向量的前位和另一个向量的后位拼接，但是前者的后位必须等于后者的前位。

2015-09-21 21:16:20 621

原创 CodeVS1280 无限序列

http://codevs.cn/problem/1280/题意：有一个无限序列：123456789101112……问第Ai位是什么数字。线性的模拟会超时，因为这里的序列很有规律，所以可以考虑用数学方法来计算。序列是由每个正整数依次连接的，但是正整数的位数有所不同，无法统一计算，因此应该先观察Ai位对应的正整数是几位的。可以预先处理好小于某10的幂的所有正整数位数之和t[]，以便根

2015-09-20 12:36:01 581

原创 bzoj1911&CodeVS1318 特别行动队

http://www.lydsy.com/JudgeOnline/problem.php?id=1911 http://codevs.cn/problem/1318/题意：给出n个数，要求把它们分成若干个连续段。对于一个数之和为s的连续段，得分为f(s)=a*s*s+b*s+c，其中a,b,c已经给定且a是负数。求最大的总得分。要求线性复杂度。很容易想到这道题的一个DP算法：设dp[i]为

2015-09-18 23:06:59 538

原创 CodeVS1394 数字串

http://codevs.com/problem/1394/题意：给定一个长度为n的序列，每个元素都是不大于m的正整数。找出最短的连续数段，满足每一个不大于m的正整数都在其中出现。n和m均不大于200,000。最简单的想法是，暴力枚举左右端点形成序列，在序列中分别查找每个不大于m的正整数。时间复杂度O(n^3·m)。可以想到的一个简单优化是，可以枚举左端点，然后不断向右扫描，用一个桶

2015-09-17 22:26:55 438

原创 CodeVS4096 点的最小化距离

http://codevs.cn/problem/4096/题意：平面直角坐标系中有N个整数点(Xi,Yi)，再找出一个可以与其他点重合的整数点(X,Y)，使得该点到N个点的距离之和最短。这里的距离不是欧式距离，而是横坐标之差的绝对值加上纵坐标之差的绝对值。即若A(X1,Y1),B(X2,Y2)，则dist(A,B)=|X1-X2|+|Y1-Y2|。输出距离之和的最小值以及有多少个整数

2015-09-15 20:27:23 483

原创 CodeVS3785 项链

http://codevs.cn/problem/3785/题意：有一个数列E[1]…E[n]，当1现给定E[1]，E[n]以及D[2]…D[n-1]，求出完整的E数列。n由于中间的E[2]…E[n-1]未知，当n>3时没有任何某两个下标差为1或2的已知E值，因此无法直接计算。我们可以用方程的思想来解决，设E[2]=x，这样联系E[1]和D[2]就可以用x表示出E[3]，并且不断利

2015-09-14 22:02:14 368

原创 CodeVS2599 电路的稳定性

http://codevs.cn/problem/2599/题意：一个电路有n个元件，给出连接方式以及各元件的断路概率，求出总电路的断路概率连接方式的描述方法如下：单个元件用大写字母表示；A,B,C,……,Z表示这些电阻串联；(A)(B)(C)……(Z)表示这些电阻并联串联和并联可以相互递归，如(A)(B,C)表示先将B与C串联，再将其与A并联两个概率为a和b的路，串联的结果是a+

2015-09-13 09:40:47 1226

原创写在开始的话

在这里我的身份是一名OIer，目前主要使用的OJ是CodeVS（太弱而暂时用不起BZOJ），在CodeVS交流群（QQ群号181992559）里的群名片是蒟蒻Mz。问我Mz是什么？Mz是我的英文名Moiezen的缩写，而不是meizi！！！不要问我Moiezen是什么。2015-09-13，在大浙江的刚开始读初三的我开始使用csdn博客来写写解题报告或者其他OI相关之事，不知道是早是晚（以

2015-09-13 09:28:45 558

空空如也

空空如也