- 博客(64)
- 问答 (1)
- 收藏
- 关注
RSS订阅原创 Codeforces Round #790 (Div. 4) (AC代码)
G题题目看错了，一直在调，结果是输入n-1个数不是n个数，难受的一批。导致H题一个简单的树状数组也没写出来，比赛完就调出来了。Rank 3000/29000A题#include<iostream>#include<algorithm>#include<cmath>#include<cstring>#include<vector>#include<queue>#include<stack>#include&l
2022-05-11 16:05:04
343
原创 ACwing802-离散化-python-(数组数组+离散化)
比较难理解的一道题。我们首先对所有要进行添加操作的坐标进行离散化，用树状数组保存。当我们查询的时候，找到左右侧的端点，再利用树状数组求和即可。AC代码global a,lthglobal treedef low_bound(l,r,val): while l<=r: mid=l+r>>1 if val<=a[mid]: r=mid-1 else: l=mid+1 r
2022-03-31 19:58:30
515
原创 洛谷1177-归并排序--C++（归并排序）
归并排序的步骤就是先划分，再把两部分进行两两合并，合并的时候就用到了归并排序。归并排序是一个稳定的排序，算法的时间效率是O(nlgn)，空间效率是O(n)，是一个比较好的排序。AC代码#include<iostream>using namespace std;const int N=100010;int a[N];int n;void merge(int l,int r,int mid){ int tmp[N]={0}; int lpos=l,rpos=mid+1,pos=l;
2022-03-29 20:21:36
1204
原创 ACwing196-质数距离-C++（线性筛）
AC代码#include<iostream>#include<cstring>using namespace std;typedef long long LL;const int N=1000010;int n,m;int a[N];int prime[N],cnt,vis[N];void EulerFilter(){ for(int i=2;i<=N;i++){ if(!vis[i]){ prime[cnt++
2022-03-27 14:46:31
845
原创 ACwing95-开关-python-(递推与递归)
对于第一行来说，一共有1<<5种操作状态，枚举这些操作状态，得到第一行的状态，最后通过递推看最后一行能否达到都是开的状态即可。AC代码#我们枚举得是第一行得开关操作的种类import copyglobal msg,tmpdx=[0,0,0,-1,1]dy=[0,-1,1,0,0]def turn(x,y): for i in range(5): a,b=x+dx[i],y+dy[i] if 0<=a<5 and 0<=b&
2022-03-25 21:43:38
1423
原创 洛谷1835-素数密度-C++-（欧拉筛）
对于这种快要移溢出但是又没有溢出的数据范围，一律开long long，索引越界了，调试了一个小时。有一个测试点r=2147483647，加1就越界了，循环停不下来了：(难受AC代码#include<iostream>#include<cmath>using namespace std;typedef long long LL;const int N=1e6+10;int l,r;int a[N],prime[N],visit[N],cnt;void Euler(
2022-03-23 18:01:50
896
原创 洛谷1069-细胞分裂-C++-（质因数分解）
AC代码本质上是分解质因数和一层覆盖关系，调试了几个小时，问题出在数组越界，难受死我了，不过最后还是AC了。#include<iostream>using namespace std;#define inf 0x3f3f3f3fconst int N=10010;int n,m1,m2;int s[N];//底数的质因数分解int base[200][2],cnt;//培养皿的质因数分解int tbase[100010][2],tcnt;void mysplit(int
2022-03-23 01:01:03
595
原创 洛谷3601-签到题-C++-（欧拉函数）
欧拉函数模板：对于某一个数n，我们要求小于n并且与 n互质的数的个数，我们就可以用欧拉函数来求解。phi(n)=n×(1-1/p1)×(1-1/p2)×…×（1-1/pk），其中p是小于n的质因数，这里我们可以联想整数的质因数分解定理，枚举1~sqrt（n）的所有质数，更改其欧拉函数值，同时缩小n,如果最后的值大于1，则再改变一次即可。#include<iostream>using namespace std;#define mod 666623333#define N 100
2022-03-22 22:24:43
1292
原创 洛谷3388-割点-C++ && python-(tarjan割点算法)
AC代码C++#include<iostream>#include<vector>using namespace std;#define N 20010int n,m;int dfn[N],low[N],vis[N],tim=1;int flag[N],u,v;vector<int> point[N];int min(int x,int y){ return x>y?y:x;}void tarjan(int cur,int far){
2022-03-21 16:27:04
1796
原创 力扣285场单周赛-python
2000/7500此次比赛成绩十分惨烈，卡在第三题过不去。用的0-1背包+回溯，一直超时，后来看题解就是一个简单的枚举，我服了。第四题看都没看。T1class Solution: def countHillValley(self, nums: List[int]) -> int: lth=len(nums) index=1 def get_left(t,val): while t>=1 and nums[t]=
2022-03-20 14:36:49
1076
原创 力扣74场双周赛-python
第一次AK，心情十分预约！T1class Solution: def divideArray(self, nums: List[int]) -> bool: dic={} for i in range(len(nums)): if nums[i] in dic: dic[nums[i]]+=1 else: dic[nums[i]]=1
2022-03-20 00:00:07
727
原创 ACwing43场周赛-python
T1def judge(a,b,c): if a+b>c and a+c>b and b+c>a: return True return Falsen=int(input())ans=[]for i in range(1,n+1): for j in range(i,n+1): for k in range(j,n+1): if i^j^k==0 and judge(i,j,k): .
2022-03-19 20:22:16
80
原创 洛谷1443-马的遍历-python-(BFS)
AC代码if __name__=="__main__": n,m,x,y=map(int,input().split()) MAP=[[-1 for i in range(m+1)] for j in range(n+1)] visit=[[0 for i in range(m+1)]for j in range(n+1)] MAP[x][y]=0 visit[x][y]=1 dx=[-1,-2,-2,-1,1,2,2,1] dy=[2,1,-1
2022-03-19 08:28:26
481
原创 洛谷1092-最大公约数与最小公倍数-python-(gcd)
此题注意一定要对枚举的数进行预处理，确保这个数是x的倍数，是y的因子，这样枚举就不会超时。AC代码def gcd(x,y): return x if y==0 else gcd(y,x%y)x,y=map(int,input().split())ans=[]for i in range(x,y+1): if i%x==0 and y%i==0: ans.append(i)lth=len(ans)cnt=0for i in range(lth): fo
2022-03-17 18:33:27
638
原创 ACwing-每日一题打卡第三题-python-(bfs)
分类比较复杂，整体来讲比较简单dic={'Ox': 1, 'Tiger': 2, 'Rabbit': 3, 'Dragon': 4, 'Snake': 5, 'Horse': 6, 'Goat': 7, 'Monkey': 8, 'Rooster': 9, 'Dog': 10, 'Pig': 11, 'Rat': 12}n=int(input())side=[[] for i in range(n)]#记录一共出现了几个名字namedic=set()#记录每个牛的生肖animal={"Be
2022-03-16 19:32:52
458
原创 洛谷3865-ST表模板-C++-（ST表+倍增）
AC代码关于这个代码，调了大半天，最后错在运算符优先级上，真的服了自己。对于j+1<<(i-1)这一段语句，我原本想的是 j加上2^(i-1)， 但是运算的结果却是(j+1)^(i-1),导致代码一直出错。😦 难受的一个晚上希望在以后的代码过程中能够避免此类错误。#include<iostream>#include<algorithm>#include<math.h>using namespace std;#define N 100010#
2022-03-16 00:02:13
877
原创 洛谷3379-LCA-C++-（LCA+倍增）
由于python超时了四五个点，所以用C++写了一下AC代码#include<iostream>#include<vector>using namespace std;#define N 500010int n,m,s;int vis[N],far[N][20],dep[N];vector<int> point[N];void dfs(int root,int deep){ dep[root]=deep; vis[root]=1; for(int
2022-03-15 13:04:06
1435
原创 洛谷3366-最小生成树-python-(kruskal+并查集)
TLE3个点的代码,没办法，python循环太慢了。#克鲁斯卡尔global n,mglobal sideglobal parentdef find(x): while parent[x]!=-1: x=parent[x] return xdef kruskal(): ans=0 #找到n-1条边就退出循环 count=0 for i in range(m): u,v,w=side[i][0],side[i][1],
2022-03-15 10:52:43
818
原创 洛谷3366-最小生成树-python-（prim算法）
70分代码，python超时了# primglobal n,m,side,pointglobal lowcost,clostdef prim(sta): lowcost[sta],lth=0,len(point[sta]) for i in range(lth): u,v,w=side[point[sta][i]][0],side[point[sta][i]][1],side[point[sta][i]][2] if v!=sta:
2022-03-14 21:46:45
480
原创 洛谷1257-最近的两个点-python-(优化算法)
AC代码import mathglobal msgdef solution(left,right): dis=float("inf") #递归终点 if left==right: return dis elif left+1==right: return distance(msg[left],msg[right]) mid=(right+left)//2 d1=solution(left,mid) d2=
2022-03-14 19:33:36
680
原创 力扣284场单周赛-python
这次周赛的成绩是有史以来最好的一次，其实这不是最让我高兴的。周赛做出了三道题，前两道还行，第三道没有思路，直接看第四道，第四道是最短路有关的问题，一看就是迪杰斯特拉最短路问题，利用反向建图求出终点到所有点的最短路，即多源单点最短路，然后两个起点的单源最短路。当我看到数据范围时，如果使用朴素的dijkstra最短路，这是一定会超时的，所以一定要用二叉堆来优化，而二叉堆的优化问题以及二叉堆的实现，我在昨天的博客中就已经介绍了，并且完成了，所以正好用上了，这是让我十分意外的。周赛代码#1class S
2022-03-13 12:21:45
444
原创 洛谷4779-最短路优化-python-(手搓二叉堆+dijkstra)
"""堆优化+dijkstra"""class node: def __init__(self,val,idx): self.val=val self.idx=idxclass heap: arr=[] def __init__(self,s=None): if s!=None: self.arr.append(s) def change(self,x,y): s
2022-03-12 10:40:18
596
1
原创 洛谷2085-最小函数值-python-(二叉堆)
最近在学习dijkstra最短路算法，朴素算法的时间复杂度是O(N^2),也就是说当数据量达到1e5的时候，1S可能就不够了，因此我们需要对算法进行优化，如果能让时间复杂度变为O(NlogN)的话，一般来说能过所有的dijkstra最短路相关的问题，那么我们如何进行优化呢？我们知道dijkstra算法外面一层循环，里面两个循环，范围都是1~n，外面循环一次就确定一个最短路径的长度，这是不能够去优化的，因此我们想到优化内部的循环。内部算法的目的是找到一个还未被访问，并且单源路径最短的一个点，并且对这个点所能
2022-03-11 21:58:49
985
原创 洛谷1434-滑雪-python-(记忆化搜索+dfs)
什么是记忆化搜索呢？搜索的低效在于没有能够很好地处理重叠子问题；动态规划虽然比较好地处理了重叠子问题，但是在有些拓扑关系比较复杂的题目面前，又显得无奈。记忆化搜索正是在这样的情况下产生的，它采用搜索的形式和动态规划中递推的思想将这两种方法有机地综合在一起，扬长避短，简单实用，在信息学中有着重要的作用。记忆化搜索,我们在dfs过程中对于一已经搜索过的点，就不必再去搜索，直接返回，大大提高了搜索的效率相比于常规的dfs算法,不用一条路搜到底，我们只需要在之前搜索过的点停止搜索即可。python代码我们在
2022-03-10 20:13:27
605
原创 洛谷5788-单调栈模板-C++-（单调栈）
AC代码#include<iostream>#include<stack>using namespace std;int n;int a[3000010],res[3000010];struct node{ int value; int index;};int main(){ stack<node> mystack; node tmp; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("
2022-03-07 22:23:46
455
原创 洛谷3397-地毯-C++-（二维差分+二维前缀和）
#include<iostream>using namespace std;int n,m;int x1,y1,x2,y2;int mp[1010][1010],presum[1010][1010];int main(){ cin>>n>>m; while(m>0){ cin>>x1>>y1>>x2>>y2; mp[x1][y1]+=1; mp[x2+1][y1]-=1; mp[x1][y
2022-03-06 21:43:24
498
原创 洛谷3368-树状数组-C++-（差分+树状数组模板）
一般来说，树状数组在做单点修改，区间查询操作的效率是比较高的，所以当我们遇到一个数组，要对其进行多次的某个位置上的值的修改时，或者查询一段区间的值的和的查询时，我们优先考虑树状数组。但是，当我们要进行单点查询和区间修改时，可以引入差分，这时，区间修改就是两次单点修改，单点查询就是一次区间查询差分的学习链接#include<iostream>using namespace std;typedef long long ll;ll a[500010];int s,x,y,k;int n,
2022-03-05 12:06:43
433
原创 洛谷3371-最短路-python-(dijkstra+floyd)
著名的最短路算法包括dijkstra,floyd,SPFA,本次代码主要是前两种，SPFA算法版之后更新"""dijkstra"""global side,pointglobal visit,dis,pdef dijkstra(n,s): visit[s]=True p[s]=s dis[s]=0 for i in range(len(point[s])): sd=point[s][i] v=side[sd][1]
2022-03-03 22:00:08
377
原创 第十届蓝桥杯-省赛-Java-A组-python代码
Adef judge(num): num=str(num) if "2" in num or "0" in num or "1" in num or "9" in num: return True return Falseans=0for i in range(1,2020): if judge(i): ans+=i**2print(ans)#2658417853Bf1=1f2=1f3=1for i in range(
2022-03-02 21:54:31
98
原创 洛谷3807-卢卡斯定理-python-(lucas+费马小定理+快速幂)
*AC代码global n,m,pdef fast_pow(a,b): ans=1 while b: if b&1: ans=(ans*a)%p a=(a**2)%p b>>=1 return ansdef getCombination(a,b): if b>a: return 0 if b>a-b: b=a-b u=1
2022-03-02 21:37:22
532
原创 洛谷1908-逆序对-python-(树状数组+离散化)
#树状数组模板global treeglobal n,rank#返回末尾的第一个1的位置#也就是的到下一个要查询的点的位置def lowbit(x): return x&(-x)def query(x): ans=0 while x: ans+=tree[x] x-=lowbit(x) return ansdef add(index,k): while index<=n: tree[ind
2022-02-28 17:39:39
377
原创 洛谷2004-领地选择-python-(二维数组的前缀和)
推荐学习视频n,m,c=map(int,input().split())gra=[0 for i in range(n)]for i in range(n): gra[i]=list(map(int,input().split())) #矩阵数组dp=[[0 for i in range(m)]for j in range(n)]dp[0][0]=gra[0][0]for i in range(1,m): dp[0][i]=dp[0][i-1]+gra[0][i]fo
2022-02-28 13:36:54
390
原创 洛谷1807-最长路-python-(拓扑排序+dp)
AC代码n,m=map(int,input().split())if m==0: print(-1)else: side=[0]*m point=[[] for i in range(n+1)] rud=[0]*(n+1) dp=[-float("inf")]*(n+1) for i in range(m): side[i]=list(map(int,input().split())) point[side[i][0]]
2022-02-27 23:16:42
280
原创 洛谷3916-图的遍历-python-(tarjan强连通分量算法+缩点+图的重建+dfs算法)
题目要求我们求出从每一个点出发所能到达的点的最大值思路1：对每一个点采用dfs搜索，求出最大点的编号。这样从理论上来说是可行的，但是时间复杂度是O（n^2），肯定是会超时。思路2：对原图进行缩点，每一个强联通分量都看成一个点，连接这几个点，然后进行dfs，求出每一个点能够到达的最大值作为这一个强连通分量的最大值，最后就是输出答案了。这里采用思路2来进行解题：①如何求出一张图的强连通分量tarjan算法def tarjan(v): global time,num vis[v]=1
2022-02-27 16:34:46
634
原创 洛谷3884-二叉树问题-python-(dfs+bfs+lca+倍增)
对于一个二叉树来讲，我们通常的问题一般有一下几种：①求解二叉树的深度②求解二叉树的宽度③求解两个结点最近的公共祖先下面就利用一些算法来实现以上的要求该代码存储树结点的数据结构主要是利用嵌套列表，即每一个结点都用一个列表存储，列表内一共有四个元素，分别是该结点的左孩子结点，该结点的右孩子结点，该结点的父亲结点，该结点的深度。对于题目中的数据的存储方式的代码n=int(input())tree=[[0 for j in range(4)] for i in range(n+1)]#用列表来存储
2022-02-24 19:43:03
555
原创 洛谷1536-村村通-C-（并查集）
并查集AC代码#include<stdio.h>int parent[1010];int n,rel,x,y;int find(int x){ int t_val=x; while(parent[t_val]!=-1) t_val=parent[t_val]; return t_val;}void union_xy(int x,int y){ int root_x=find(x); int root_y=find(y); if(root_x!=root_y){
2022-02-23 00:27:52
176
原创 洛谷3372-线段树1-python-(线段树)
看注释global n,m,nums,MAX_LENS,treeMAX_LENS=10000#树存储结构tree=[0]*MAX_LENS#懒惰标记存储结构lazy_tag=[0]*MAX_LENS#建树def build_tree(node,sta,end): if sta==end: tree[node]=nums[sta] return mid=(sta+end)//2 left_node=2*node+1 righ
2022-02-21 16:48:07
632
原创 洛谷1102-A-B对-C++-（二分查找细节）
对于一个有序的数组，我们要查找一个元素，假设值为value，我们需要求出这个有序的数组中有几个value值，这个时候我们怎么做？首先找到第一个值为value的值，再找出第一个值不为value的值，两者下标相减即可找第一个值为valueint find_1(int l,int r,int value){ while(l<=r){ int mid=l+(r-l)/2; if(value<=a[mid]){ r=mid-1; } else{ l=mid+1; }
2022-02-12 14:04:28
618
原创 洛谷1498-谢尔宾斯基三角形-python-(递归)
这题乍一看很简单，就是在三角形内绘制三角形。找到三角形的三个点连接即可。但是运行的过程不可能是通过画图来完成的啊，用编程语言实现起来还是比较麻烦的。输入一个n，我们通过看题可以得知，输出图形的高度为2n,宽度为2(n+1)。所以我们初始就要定义一个与此维度相当的数组利用列表推导式即可n=int(input())msg=[[" " for i in range(2**(n+1))] for j in range(2**n)]接下来我们就要对这个题目进行分析了：我们要输出，输出是一行一行的，所以我
2022-02-11 16:51:43
819
空空如也
更新eclipse之后出现如下问题，真不知道怎么办。
2021-11-16
TA创建的收藏夹 TA关注的收藏夹
TA关注的人