- 博客(19)
- 收藏
- 关注
RSS订阅原创 2021-08-11 树状数组的离线询问
以牛客题目为例对于每一次询问要求[L,R]范围内有多少个数字与其他数互质对于这种多次询问的一般需要把每次询问的贡献都加入到端点上，然后离线进行询问，对于每一个[L，R]的区间，区间外的其他数字不会对答案产生影响对于m次询问，需要一次遍历将所有答案都加入在端点上，在使用类似找点对的方式进行查询，对于本题，要找到对于每一个数的对应的可行区间 (l,r)，首先需要每一个数字进行质因子分解，处理出来第i个数的最大互质区间为(l,r)，对于每次查询的[L,R]按照L进行排序， 若有互质区间左端超过查询区间的左端
2021-08-12 23:19:15
120
原创 牛客 23616 小A的数学题 -----------莫比乌斯反演
不会公式编辑，手写吧枚举d，和d的倍数带入计算即可#include<bits/stdc++.h>using namespace std;const int maxn=1e6+17;const int mod=1e9+7;#define ll long longint ok[maxn];int mu[maxn];int prime[maxn];void seive(ll n){ int cnt=0; mu[1]=1; for(int i=2;i&l.
2021-03-09 19:40:42
123
原创 LDU新生排位赛第一场 ——J 学呀学呀学矩形
题意：求 ab的所有因子的和%mod思路把 a 质因子分解，每个质因子的幂次乘 b然后根据唯一分解定理的推论可以发现每一部分都是一个等比数列对其求和可得(P1(a1+1)-1)/（p1-1）…(pn(an+1)-1)/(p n-1)快速幂求分子，逆元求分母相乘即可过程中注意取模ll p[MAXN], c[MAXN], cnt;ll qpow(ll n, ll m){ ll ans = 1; while(m) { if(m & 1) ans = ans*n% mod
2021-03-07 11:31:53
139
1
原创 牛客problem/201985 立方数--------------------分解+优化
首先可以想到第一种思路 直接枚举A,因为N<=1018,所以A只需要枚举到106总体复杂度为O（N1/6)，但是由于T太大，会TLE,.然后我们去质因子分解N,如果直接分解复杂度为O(n1/2)很显然不可取。考虑到前面出现了A3所以分解出来的素数只有出现3次以上才会对答案又贡献，很显然N不可能存在超过3个105以上的质因子。所以本题的优化思路就是先把小于105的质因子全部筛掉，如果出现超过三次就计算贡献，最后N会剩下一部分，假设筛完之后N剩下X,那么X的所有质因子都大于105,那么X最多还剩下3
2021-03-04 21:46:27
193
1
原创 牛客-牛牛的幂运算-------------------数论+调精度
题意很简单 求有多少组ab=cd首先考虑 a=b=1时对于每一个c和d都满足，所以一共是n*n中当
2021-03-03 20:18:57
257
1
原创 Codeforces Round 102(EDU) D Program ---RMQ - ST表
D. ProgramYou are given a program that consists of n instructions. Initially a single variable x is assigned to 0. Afterwards, the instructions are of two types:increase x by 1;decrease x by 1.You are given m queries of the following format: query l r.
2021-01-16 12:21:17
206
原创 11-08-UPC训练赛 Know your Aliens
Know your AliensOur world has been invaded by shapeshifting aliens that kidnap people and steal their identities.You are an inspector from a task force dedicated to detect and capture them. As such, you were given special tools to detect aliens and differ
2020-11-09 19:42:35
206
原创 Unknown Treasure
On the way to the next secret treasure hiding place, the mathematician discovered a cave unknown to the map. The mathematician entered the cave because it is there. Somewhere deep in the cave, she found a treasure chest with a combination lock and some nu.
2020-09-11 11:23:31
183
1
原创 7-31-UPC-C Swap
如果你需要移动一样东西，显然接触或者使用磁场电场之类的可以解决。但是有没有办法进行超越距离的随心所欲的移动？对于物体或者文字进行超距离移动一直是人类的梦想，有一天这个难题终于被我们的大牛解决了！他现在需要的就是整理数列。数列就是所谓的写在纸上或者在电脑品目上的数列…整理数列需要一个叫做swap的操作，swap操作就是指大牛通过超距离的控制把数列中的某一位直接插入某两位的中间或者数列的开始或者终止的操作。这个操作的关键在于超距离控制，显然这种事情不能干太多次，不但降RP，而且很耗体力。你的任务就是从初始.
2020-07-31 17:24:30
202
原创 最小异或生成树 ————codeforce 888 G
题意：给出n个点的，求最小异或生成树：连接 x,y，则这条边的权值为a[x] ^a[y]思路：根据贪心的思路如果一个点要与另一个点相连，他与 和它同一个lca的点相连是最优的，因为此时上面的部分都异或掉了所以只需要将每个点的权值转换成二进制,从高位往低位依次插入01字典树.建立字典树之后一个节点下的最小异或生成树 = 左子树 + 右子树 + 左右合并的最小值。dfs遍历该字典树的每个结点,如果某个结点有两个子节点,这两个子节点的子树分别会构成两个连通块,要在这两个连通块之间各选一个点连边并使它们.
2020-07-31 17:12:47
255
原创 7-6 UPC--BUREK
BUREK贝克金宝有N个三角形。他的儿子乔伊有一个很大的刀，准备切割这些三角形。每一次切割，乔伊能够用与x轴平行的直线（y=c）或与y轴平行的直线（x=c）对这些三角形进行切割。你的任务是计算每一次切割，有多少个三角形会被切割。注意：被切割过的三角形仍看作一个三角形；三角形被切割当且仅当三角形在直线以左的部分的面积和在直线以右的部分的面积，都应大于0。输入 第一行是一个正整数N（2<=N<=100000），三角形的个数。第2到N+1行每行包含6个整数x1,y1,x2,y2,x
2020-07-06 13:57:25
264
原创 HDU1812——————Count the Tetris（思路）
设G是p个对象的一个置换群，用k种颜色染这p个对象，若一种染色方案在群G的作用下变为另一种方案，则这两个方案当做是同一种方案，这样不同染色方案数为HDU 1812例题一共有8个置换，其中4个翻转（上下，左右，右上，左上），4个旋转，计算出这个置换的循环节数，然后对k做幂运算相加先看翻转1上下翻转需要分奇数偶数讨论，n是奇数的话–中间一行不动，其循环节为n个（自己到自己），其他n-1行的所有元素发生两两互换，每两个数可以构成一个循环节共计（（n-1）/2 ） * n个;n是偶数的话，所有的
2020-06-11 11:34:18
326
1
原创 UPC——喜爱
这里是引用小s最近对数字情有独钟。他又发现了一种神奇的数字。对于数x，如果它二进制表示中只有一位是0，则x就会被小s所喜爱。比如5，二进制为101，则它被小s所喜爱。现在，小s想知道，对于一个区间[L,R]，有多少数是他所喜爱的。对于100%的数据:L,R≤1018，T≤10000题意：求[l,r]范围内二进制只有一位是1的数的个数；可以看出从2i 到2i+1一共有i个满足题意的数；...
2020-03-24 15:05:03
300
1
原创 蒟蒻刷题日志
Bi-shoe and Phi-shoe给出n个数字的序列a[]，对于每个数字ai找到一个欧拉函数值大于等于ai的数bi，求找到的所有数bi的最小值之和sum我们可以知道一个φ（p),如果p是一个素数的话，那么φ（p)=p-1;而对于所有小于p的值a，φ（a)<φ（p);这里我们知道φ（bi)>=ai;求bi的最小值，就只需要求出大于ai的第一个素数，将所有结果加和就可以了；...
2020-03-13 14:03:44
202
原创 Codeforces Round #627 (Div. 3)——ABCD题
本蒟蒻的第一篇cf解题报告题意：1X1的方块，每一列有不同数量的方块，可以用任意数量的长度为2X1的方块，能否将每一列都变成数量相同；可以发现进行填充之后每一列都要和最高的那一列同高 可以先找到最大值，如果每一列都要达到最大值数量的方块，就要求每一类和最大值的差值都是2的倍数，如果有一列不是，就不可以达到目标#include<bits/stdc++.h>using name...
2020-03-13 12:56:17
158
1
原创 UPC——奖牌整理——隐藏的水题
上完一天的课，小 Z 不但没有一丝疲惫感，反而觉得浑身是劲，好象又回到了童年， 他蹦蹦跳跳地回到家，吃过晚饭很快就做完了作业，抬头一看觉得房间太乱了，这不进入 初三后由于课业繁重一直没时间整理房间，现在有空了是时候该好好整理一下了。小 Z 首 先想要整理的是他那些心爱的奖牌，这些奖牌记录了小 Z 成长的足迹，其中有龙城少儿围 棋比赛的银牌，有华罗庚杯少年数学邀请赛的铜牌，份量最重的当数全国信息学...
2019-12-16 16:12:28
810
2
原创 UPC——美丽的大树——模拟题
题目描述兴中道是中山最美丽的道路，路中间的绿化带上种了两列漂亮的大树，这些大树分成了50行，每行两棵大树，一共100棵大树，这些大树被编上了号，编号方式如下：1 3 5 7 ………… 45 47 492 4 6 8 ………… 46 48 50再过几天奥运火炬就要在中山传递了，美丽的兴中道当然是最重要的必经之路，但是某天晚上却发生了一件令人震惊的大事–可恶的破坏分子为了破坏奥运，让中山人民...
2019-12-10 21:25:41
801
原创 UPC-栓奶牛————二分法
UPC——栓奶牛有n头奶牛（2≤n≤100），有k个木桩（n≤k≤100），每个木桩有一个位置，一个木桩上只能拴一头奶牛。由于奶牛好斗，所以在拴奶牛的时候要求距离最近的奶牛的距离尽可能大。输入1行：n,k,p1三个整数（0≤p1≤100），其中p1为第1个木桩的位置，其他木桩pi (i≥2)的位置由下面公式给出：pi=pi-1+((pi-1×2357+137) mod 10)+1...
2019-11-28 14:35:24
1232
3
原创 UPC-魔术数————暴力解法
UPC-魔术数注意数据范围10^10；直接遍历会超时，我们采取另一种方式。条件一要求该数一定是一个平方数，就拿1-1e5的数平方后在判断，直接将次数减了一半，输入数据后需要找到两数平方根之间所有的数进行平方在遍历即可 if(floor(sqrt(a)) == sqrt(a)) { i=x; } else { i=x+1; } for(;i<=y...
2019-11-27 19:36:34
309
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人