shicj's blog

Function Content init() 清空BIT add(pos) 将1~pos位置加1 add(pos,val) 将1~pos位置加val query(pos) 查询pos位置 1234567891011121314151617181920struct BIT{ int t[2000006],tot; void init(){ memset(t,0,sizeof(t)); tot=0; } void add(int i,int val=1){ tot++; for(;i<=len;i+=(i&-i)){ t[i]+=val; } } int query(int i){ int s=0; for(;i;i-=(i&-i)){ s+=t[i]; } return s; }}; 一~行~坨BIT 1struct...

Upd：可以使用 AtCoder Lib 打表，可以在几秒内得到结果，详见文章末尾。 打表做法（~可能~不太具有普遍性，但确实可以）~114514114514114514 是一个很好的随机种子~。 首先，做一个非常简单的优化：为了使拼接后的子串种类不重复，可以构造使得其中一种符号远少于另一种，减少打表的次数（我的程序里控制比例为一比十）。 除此之外，其他所有内容都使用了暴力做法，求值函数为 O(n3)O(n^3)O(n3)，判断函数为 O(n2log⁡n)O(n^2\log n)O(n2logn)（使用了 map），最终单次枚举时间复杂度约为 O(n5log⁡n)O(n^5\log n)O(n5logn)，在机房的 Intel(R) Core(TM) i5-6500 CPU @ 3.20GHz 上花了几分钟时间。 这个算法中最重要的是选择正确的随机种子，在多次尝试后，我们发现将 114514114514114514 作为 mt19937...

上一版的算法名称不能识别到目录，不好找，于是有了这一版本 数学算法 求解GCD 123int gcd(int x,int y) { return y?gcd(y,x%y):x;} 快速幂 1234567891011int qpow(int a,int b,int mod) { int tmp=a,ans=1; while(b){ if(b&1){ ans=ans*tmp%mod; } b>>=1; tmp=tmp*tmp%mod; } return ans;} 逆元（质数）数组初始化 12345678910void init(){ fac[0]=1; for(int i=1;i<=100000;i++) { fac[i]=fac[i-1]*i%mod; } ...

十、解析几何 1. 直线 直线的倾斜角和斜率 当 lll 与 xxx 轴相交时，xxx 轴正方向与 lll 向上的方向之间所成的角 α\alphaα 称为直线的倾斜角，倾斜角 α\alphaα 满足 0°≤α≤180°0\degree\le\alpha\le180\degree0°≤α≤180°。（任何直线都有倾斜角） 倾斜角 α\alphaα 的正切值叫做这条直线的斜率，常用 kkk 表示，即 k=tan⁡αk=\tan\alphak=tanα。（不是所有的直线都有斜率） k=tan⁡α=y2−y1x2−x1 (P1(x1,y1),P2(x2,y2),x1≠x2)k=\tan\alpha=\dfrac{y_2-y_1}{x_2-x_1}\ (P_1(x_1,y_1),P_2(x_2,y_2),x_1\neq x_2) k=tanα=x2​−x1​y2​−y1​​ (P1​(x1​,y1​),P2​(x2​,y2​),x1​​=x2​) 若 lll 的斜率为 kkk，他的一个方向向量坐标为 (x,y)(x,y)(x,y)，则...

面对这样小的数据范围，为什么要写搜索？于是我来写一个纯粹的模拟。这题不至于评绿吧？ 大致的思路就是枚举每一个可能的入射方向，暴力模拟光的传播过程，并在这个过程中记录经过的镜面，进行判断。 我认为这题唯一复杂的地方在于对光的反射方向的处理，有一些题解中用了分类讨论，这明显太复杂了，于是可以使用映射来进行记录，方法如下： 为了方便论述，这里先定义以下的方向编号： 12int dx[4]={0,1,0,-1};int dy[4]={1,0,-1,0}; 然后画个图分析一下（画图真的非常重要！）： 注：蓝线是镜子，黑线是入射光线，红线是反射光线，数字表示方向编号。 于是用 mp[m][d] 表示方向为 d 的光线经平面镜 m 反射后的方向，顺便把空格方向不变也定义了： 123mp['/' ][0]=3;mp['/' ][1]=2;mp['/' ][2]=1;mp['/'...

每一轮，Alice 先取数，Bob 后取，当两人所取的和为 kkk 时，加一分，Alice 希望的分最小，Bob 希望最大，两人按最优方式操作，求最终得分。 当两个数的和等于 kkk 时，这一对数就是可得分的，可以发现，Alice 的取数方法与结果无关，而对于 Alice 的数，当这个数可得分时，Bob 会取出对应的一个数使之得分，否则 Bob 则取出一个不可得分的数，没有得分。 于是，答案就是可得分数组合的数量（当然每个数只能用一次）。 于是就有了一个用映射维护的 101010 行写法，注意 tot 不要改为数组，否则可能会访问负数下标。 123456789101112void solve(){ int n,k,x,ans=0; tot.clear(); scanf("%lld%lld",&n,&k); for(int i=1;i<=n;i++){ scanf("%lld",&x); tot[x]++; } for(auto...

0x00 题目翻译 一个长度为 nnn 的序列，求出对于所有 1≤l≤r≤n1\le l\le r\le n1≤l≤r≤n， max⁡(al,al+1,…,ar)−min⁡(al,al+1,…,ar)−(r−l)\max (a_l, a_{l + 1}, \ldots, a_r) - \min (a_l, a_{l + 1}, \ldots, a_r) - (r - l) max(al​,al+1​,…,ar​)−min(al​,al+1​,…,ar​)−(r−l) 的最大值。 每一组数据，先输出这个序列的答案，之后 qqq 行修改操作，每行的 p x 表示把 apa_pap​ 修改为 xxx，修改对之后的所有操作有影响，每一次修改后，输出新序列的答案。 0x01 解题思路 解题的关键就是对这个式子进行变形： max⁡(al,al+1,…,ar)−min⁡(al,al+1,…,ar)−(r−l)\max (a_l, a_{l + 1}, \ldots, a_r) - \min (a_l, a_{l + 1}, \ldots, a_r) - (r -...

八上历史整理 一、屈辱史 鸦片战争（1840-1842） 林则徐虎门销烟 →\rightarrow→ 发动鸦片战争 →\rightarrow→ 签订《南京条约》→\rightarrow→ 和英法美签订其他条约 虎门销烟（836.6.3-25） 民族英雄林则徐，意义：伟大胜利顽强斗志 鸦片战争（1840-1842） 为了打开市场、倾销商品、掠夺原料；关天培、陈化成、三元里 《南京条约》（1842） 五口通商、割香港岛、赔款2100万银元、协定关税 《虎门条约》（1843） 领事裁判权、片面最惠国、口岸租地建房 中美《望厦条约》，中法《黄埔条约》（1844） 意义 改变、破坏、破坏、开始沦为半殖民地半封建社会、近代史的开端 第二次鸦片战争（1856-1860） 炮轰广州 →\rightarrow→ 占领天津，《天津条约》→\rightarrow→ 进逼北京，《北京条约》 原因 打开市场、扩大权益；马神甫事件、亚罗号事件 炮轰广州（1856） 占领天津（1858） 签订《天津条约》《通商章程善后条约》 进逼北京（1860）...

...

...