2 qq_42371755

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 38w+

CF919-E

题目传送门题解根据费马小定理 : a^i 同余 a^(i+(p-1)j) (mod p)又因为 a 同余 a+pi (mod p)设 n = (p-1)j+i则有na^n 同余 b (mod p)则有 na^((p-1j)+i) 同余 b (mod p)则 n*a^i 同余 b (mod p)则 ((p-1)*j+i)*a^i 同余 b (mod p)则有 (i-j)*a^i...

2020-02-12 10:09:56

多项式的各种操作

转载于xez巨佬的文章目录前置知识趋近自然常数对数逆元导函数牛顿迭代与泰勒公式不定积分与定积分各种基本操作多项式乘法多项式求逆元多项式除法/取模多项式牛顿迭代法多项式开根(限制常数版)多项式的自然对数 ln (限制常数版)多项式 exp (限制常数版)多项式 k 次幂结语及完整封装版本写的时候注意各种数组的清空前置知识趋近数学公式中,有类似于 ←\leftarrow← 或者 →\ri...

2019-12-27 19:49:51

树套树练习

树套树讲题T1:二逼平衡树(树套树)题解代码[国家集训队]排队题解代码动态逆序对题解代码k大数查询题解(by zxy)代码T1:二逼平衡树(树套树)传送门题解所谓树套树呢?就是把两棵不同的树套在一起,以达到意想不到的效果。对于这道题,可以线段树套平衡树,也就是每个点维护一个平衡树,下面我来分别讲解一下每种操作。查询k在区间内的排名把区间分解成线段树上的点,查询kkk在每个点上的排名-...

2019-12-06 16:14:06

欧拉函数

欧拉函数定义怎么求欧拉函数O(n*log(n))O(n)O(n\sqrt nn​)O(n)线性求欧拉函数定义欧拉函数为小于n的数中与n互质的数的数目φ(x)φ(x)φ(x)表示x的欧拉函数怎么求欧拉函数O(n*log(n))暴力枚举iii范围:1−n1-n1−n,判断gcd(i,n)gcd(i,n)gcd(i,n)是否等于一O(n)首先了解一下积性函数:形如f(x∗y)=f(x)...

2019-11-22 15:36:23

CSP-2019day1题解报告

day1题解报告题目T1T2从链想起转为正解T3(摘自同级大佬xez)题目T1传送门T2传送门T3传送门T1乍一看,这道题做过,可以用对称性做,如果他的长度过了一半,就输出1,反之输出0,一位一位的输出。#include <bits/stdc++.h>using namespace std;#define int unsigned long longint read...

2019-11-21 21:09:35

CSP2019爆炸退役记

我退役了背景模拟赛不交题在 daydayday-5 被教练拉出批评,说我心态不行,让我好好努力daydayday-1 模拟赛1个半小时写完,但是第一题炸了,心态爆炸,200分daydayday 1 T2,T3保存错地方,daydayday 2当时不想去了,但是还是强行去了但是依旧直接爆炸day 0中午就放学去试机,然后学校有个清华的教授过来开讲座也没有回去,但是班主任并没有捶我。试...

2019-11-19 09:58:24

P5278 算术天才⑨与等差数列

传送门题解:题目中要求查询一段区间内的数能否构成公差为K的等差数列。由于等差数列本身不好维护,那么我们就可以去找区间内的数能构成等差数列的等价条件,再维护这些条件即可。通过看别人的题解,我们可以得到这些条件:1.这些数不相同。(废话)2.最大值减去最小值等于(l-r)k。(直接套公式,还是挺显然的)3.所有相邻两数的差的gcd都为k,即都为k的倍数。(????????)等差数列肯定满...

2019-11-18 16:36:55

P5427 [USACO19OPEN]Left Out

传送门26分做法比较zz,就是我们直接暴力枚举最后哪一个点不一样,然后暴力搜索,我们可以用一些高级搜索什么的反正都那点分,然后我们发现对于n>=5n>=5的我们跑不出来,于是就输出0,然后就26分了,很zz吧满分做法这个做法是我从zxy巨佬那里听来的,这是一个神奇的贪心策略,就是说我们模拟一下操作过程,对于现在的一个图,我们可以用O(n^2)的时间复杂度求出每行每列的R的个数,...

2019-11-18 16:28:44

P5156 [USACO18DEC]Sort It Out

传送门LIS数量统计设f[i]代表以第i个数字为开头的LIS长度,g[i]代表方案数转移时从后往前 f[i]=f[i+1···n]中的最大值 g[i]为最大长度的方案数的和用树状数组维护即可,若需要维护以第i个数字为结尾的最长的LIS长度,正的做即可 (代码和下面题解和在一起了,感觉还算简单)P5156 [USACO18DEC]Sort It Out 题解题目中的排序方式类似于快速排序...

2019-11-18 16:26:32

[USACO18DEC]Balance Beam

传送门分步证明,首先抛出结论:每个点的策略要么是不动,要么是随机移动直到左右两个点中的一个落下。结论1:从点x开始在a和b之间移动在b落下的概率为 (x-a)/(b-a)设概率为f[x]=k,则f[a]=0,f[b]=1。因为x有1/2几率往左走或往右走,所以f[x]=(f[x-1]+f[x+1])/2即f(x)满足等差数列的性质,则图像为由(a,0),(b,1)组成的直线,做两条垂线...

2019-11-18 16:14:07

[USACO08FEB]酒店Hotel

传送门这题可以使用线段树做,每个节点维护三个信息:前缀、后缀和中间的最大值。但是,线段树的题怎么能用线段树做呢,所以我写了一个fhq treap的代码(成功把蓝题变成紫题)平衡树可以维护数列信息。具体做法是将平衡树的节点以下标为关键字组织,即节点在平衡树内的rank即为其在数列里的位置。这样,每个子树都代表一个区间。为了输出位置,每个节点还要格外记录横跨其的段的左端点相对于其代表的区间的左端...

2019-11-18 16:11:07

[USACO18DEC]Teamwork

传送门有一个长度为n的序列 a 每次可以将附近连续几个比自己小的数变为自己 , 求最大技能水平和。不难想到是动态规划!令 dp[i] 为前 i 头奶牛可以达到的技能水平之和的最大值 , 可列出转移方程:dp[i]=max(dp[j]+(i-j)*max(a[j]))其中(max(0,i-k)≤j<i)上代码:#include <cstdio>#include &l...

2019-11-18 16:07:28

[十二省联考2019]春节十二响

传送门骗分方法如果你实在一点思路也没有,暴力都不会打,那么请考虑一下骗分。方法一输出所有 M 的和。期望得分:0分。实际还有5分方法二注意到有 15 分为一条链,分两种情况考虑:1号点有一个儿子——详见方法一。1号点有两个儿子——把对这两个儿子下的两条链弄成两个堆,每次取出两个堆的堆顶,取 max 加入答案,当一个堆取尽后,把另一个堆里的所有元素加入答案,最后加入 M期望得分...

2019-11-18 16:01:03

[十二省联考2019]异或粽子

传送门题解看到区间的xor,有一个常见的套路是求一次前缀xor和,这样一个区间的xor就可以表示为两个前缀的xor了。于是问题转化为:给定n+1个数(注意最开头的长度为0的前缀也要算),求两两xor的前k大。一道经典的问题是求两两xor的最大值是多少,相信大家应该都会这个trie树上贪心的做法:从左往右扫过去,每次看一下这个数与之前的数的xor的最大值是多少,只需要在trie树上贪心地尽可...

2019-11-18 15:54:41

P3919 【模板】可持久化数组(可持久化线段树/平衡树)

传送门概述算法模型:可持久化线段树(主席树)空间复杂度:O((n+m)logn)时间复杂度:O((n+m)logn)其中预处理:O(nlogn)单次修改:O(logn)单次查询:O(logn)1.思想根据题目要求,我们要做的就是保存m个版本的状态,并实现查找与修改操作。简单想法:真的开数组保存每个版本。当然会MLE(空间复杂度O(n*m))!!!idea:我们注意到,对于修改...

2019-11-18 15:46:23

Splay

v标题好长!真是声势浩大,徒有其表。splay树的基本思路出于某些原因(cache原理),在访问了某个节点之后,接下来有90%的概率很频繁地再次访问该节点,如果能把这个大概率会被多次访问的结点放到离树根尽可能近的地方,那么就可以节省不少的时间。(大概如此)所以要想办法把最近访问的结点扔到距离根节点尽可能近的位置。著名计算机学家tarjan就想到了办法。基本的定义不写这个后文进行不下...

2019-11-18 15:39:11

20190815 T3

20180815 T3题目三角形(triangle.c/cpp/pas)【题目描述】平面上有n行m列,一共n*m个方格,从上到下依次标记为第1,2,…,n行,从左到右依次标记为第1,2,…,m列,方便起见,我们称第i行第j列的方格为(i,j)。小Q在方格中填满了数字,每个格子中都恰好有一个整数a_{i,j}。小Q不喜欢手算,因此每当他不想计算时,他就会让你帮忙计算。小Q一共会给出q个询问,...

2019-08-15 20:50:21

20190815 t2

20190815 t2t2题目洛谷 P5428赛况铺垫正解代码(题解给的,作者还在研究中)t2题目洛谷 P5428跨栏(jump.cpp/c/pas)【问题描述】在过去,校长曾经构思了许多新式学生运动项目的点子,其中就包括学生障碍赛,是学生们在赛道上跑越障碍栏架的竞速项目。他之前对推广这项运动做出的努力结果喜忧参半,所以他希望在他的操场上建造一个更大的学生障碍赛的场地,试着让这项运动更...

2019-08-15 19:32:35
勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。