- 2024-10-21P3232
椒过#include<bits/stdc++.h>usingnamespacestd;intn,m,tot,lnk[505],ter[500005],nxt[500005],st[500005],ed[500005],deg[505];doublea[505][505],b[505],x[505],f[500005];voidadd(intu,intv){ ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot;}voidGauss(
- 2024-10-09【题目解析】蓝桥杯23国赛C++中高级组 - 斗鱼养殖场
【题目解析】蓝桥杯23国赛C++中高级组-斗鱼养殖场题目链接跳转:点击跳转前置知识:了解过基本的动态规划。熟练掌握二进制的位运算。题解思路这是一道典型的状压动态规划问题。设\(dp_{i,j}\)表示遍历到第\(i\)行的时候,当前行以\(j_{(base2)}\)的形式排列乌龟可以构
- 2024-09-26蓝桥4-R格式-1
知识铺垫(高精度算法):在C/C++中,我们经常会碰到限定数据范围的情况,C++规定:int占32位,即4个字节,即int的范围是[-231,231-1],为10^9数量级longlong占64位,即8个字节,即longlong的范围是[-263,263-1],为10……18数量级如果超过该数量级,则需引入高精度算法。1.高精度加法A+BProblem(
- 2024-09-24【日记】我也想捉螃蟹(505 字)
正文秋分之后,不用开空调也能活下去了。上午把财政局的人拒了回去,因为我们这边授权的人不够。大部分人都下乡扶贫去了。听另一个同事打电话给他们,听到他们扶贫完之后,跑河边捉螃蟹去了……玩得真开心啊。今天把QQ和微信来了一次大清理。消息列表清完之后看起来舒
- 2024-09-1701BFS
P4554小明的游戏大部分bfs题都可以用最短路做,而最短路中dijkstra用堆优化保证权值小的优先操作,而这题权值只有01两种,所以用01bfs,具体用deque操作,增加权值为0时(同色),放到队头,增加的权值为1时(异色),放到队尾,相当于直接\(O(1)\)排序好了。#include<bits/stdc++.h>us
- 2024-09-11CCF201712-4行车路线
题目问题描述小明和小芳出去乡村玩,小明负责开车,小芳来导航。小芳将可能的道路分为大道和小道。大道比较好走,每走1公里小明会增加1的疲劳度。小道不好走,如果连续走小道,小明的疲劳值会快速增加,连续走s公里小明会增加s2的疲劳度。例如:有5个路口,1号路口到2号路口为
- 2024-09-0951nod 1051 最大子矩阵和
51nod1051最大子矩阵和可以用前缀和容斥优化到\(O(n^4)\),但是不够进行如下图操作:将每一列的数值都压缩到一维的数组上,就转换为求最大字段和问题,时间复杂度\(O(n^3)\)。看看代码就知道了。#include<bits/stdc++.h>usingnamespacestd;#definelllonglongintn,m;
- 2024-09-083 Split
赛场上想到了n方枚举n方检验的4方做法,提前想好了实现细节一点点实现,最后一遍过了样例,还是很感动的赛场上超时了,但是交到Codeforces上能以900ms通过正解的确是n^3的,考虑优化枚举,确定1号节点在A后,对于每个1->x->y->1的三元环,要么x在B,y在C,要么x,y都在A,无论如何,x和y都不用被访问第
- 2024-09-04POJ - 3318
他说:O(n^3)是过不了滴一搜……6代码和题解没有实质区别:#include<cstdio>#include<ctime>#include<cstdlib>usingnamespacestd;inta[505][505],b[505][505],c[505][505];intmain(){ srand(time(NULL)); intn; ios::sync_with_stdio(0); cin.tie(0); while(cin
- 2024-09-03POJ - 3318
他说:O(n^3)是过不了滴一搜……6代码和题解没有实质区别:#include<cstdio>#include<ctime>#include<cstdlib>usingnamespacestd;inta[505][505],b[505][505],c[505][505];intmain(){ srand(time(NULL)); intn; ios::sync_with_stdio(0); cin.tie(0); while(cin
- 2024-07-23P1991 无线通讯网
原题链接题解首先,考虑如何分配卫星电话使得\(D\)最小是比较困难的,所以我们考虑怎样的D可以使得卫星电话个数不小于联通块个数由于D越小,联通块个数也就越小,所以具有单调性,考虑二分优化:最后的答案,一定是所有连通块内部,距离最长的树边(即失去该边之后,联通块变得不连通),由此
- 2024-07-10SGU 505
link这里讲两种做法,一个在线,一个离线。在线我们分别考虑前缀和后缀。有一个比较重要的结论,就是把\(s\)按照字典序排序以后,相同前缀的出现位置(其实就是rank)是连续的。\(s\)翻过来,相同后缀的也是连续的。这样我们就可以求出每一个询问前缀和后缀对应的区间是什么,然后就要求
- 2024-06-06自由线段树
#include<bitsstdc++.h>#definelllonglong#definemaxn1000005usingnamespacestd;structnod{ intl,r,v; nod(){} nod(inta,intb,intc){l=a;r=b;v=c;}};intn,q;intnum[505][505];lldp[505][505];vector<nod>now;lldfs(intl,intr
- 2024-05-30CF/505/D 题解
思路这道题的思路其实是根据样例图片来的。首先第一张:这张图片可以得知$n$个点没有环的时候最少需要$n-1$个点。再看第二张:这个图确实很难思考,但稍微思考一下如果我们把含有一个强连通分量的图变成一整个强连通图。这个图的边数不就变成$n$了吗?来推一下
- 2024-04-19L2-023 图着色问题
原题链接题解说用k种颜色,没说用少于k种code#include<bits/stdc++.h>usingnamespacestd;vector<int>G[505];intvis[505]={0};intcolor[505]={0};intv,e,k,n;intsolve(){for(inti=1;i<=v;i++){for(autonext:G[i]){
- 2024-04-18L2-013 红色警报
原题链接题解复杂图论题做多了这种题不会做了直接模拟即可,标记被摧毁的城市,然后遍历所有城市,能一次性搜索到的城市是一个城市群,累积有几个城市群code#include<bits/stdc++.h>usingnamespacestd;vector<int>G[505];intvis[505]={0};intdes[505]={0};voidss(intnow
- 2024-04-18L2-001 紧急救援
原题链接题解确定起点和终点,求救援人数最长,路径最短的路径,只需要集群算法中优先队列中重载比较符修改一下就就行,由于数据量很小,所以输出路径的时候搜索就行(最优解唯一)code#include<bits/stdc++.h>usingnamespacestd;structnode{intto,val;};vector<node>G[505
- 2024-04-17P10282
思路首先想到一个\(n^{4}\)的dp,观察数据范围,发现这应该是一个\(n^{3}\)的算法,考虑如何优化。首先把转移方程写出来\(dp_{i,j}=\sum_{0\leii\lei-1,0\lejj\lej-1,\overline{a_{ii+1}...a{i}}\le\overline{b_{jj+1}...b{j}}}dp_{ii,jj}\),发现都不太好优化。首先枚举\(i\),\(
- 2024-04-13春季月考 #2
做题顺序:\(\texttt{B}\to\texttt{A}\to\texttt{C}\to\texttt{D}\to\texttt{E}\)A.牛奶首先可以发现,除了全部都是\(\texttt{L/R}\)的情况,其他的情况一定可以把数组分割成几段全部都是\(\texttt{L,R}\)的段。像是这样:\(\texttt{RRRLLRLLL}\)如果当前段是\(\texttt
- 2024-03-25五 505. 火柴排队 (归并排序|离散化)
五505.火柴排队(归并排序|离散化)思路:先将两组数组按(2314->2013;3214->2103)规则排序,然后使用c数组建立双方的映射,从c[ai[i]]=bi[i],接着就是使用归并排序求c数组的逆序对即交换次数。importjava.util.*;publicclassMain{privatestaticint
- 2024-03-24广州大学第十八届ACM大学生程序设计竞赛(同步赛)——题解
这套题我答的很失败。没有按照题目的难度去答题,前期浪费了不少时间。题目:A-字符画题解:思维、模拟。这道题我的通过率为62.5,没有过的原因是因为对细节的处理和把控不到位,对一些点忽视,我也记录了搜索的过程,但没有把搜索过的点消掉,而且没有找到最好的顺序去解答这道题,我是按照横的
- 2024-02-26P1653 [USACO04DEC] Cow Ski Area G
原题链接题解非常抽象的缩点大概思路:搜索缩点成有向图,求该点的入度和出度,最后答案一定是\(max(in,out)\)总之很抽象code#definelllonglong#include<bits/stdc++.h>usingnamespacestd;inlinevoidread(ll&x){x=0;llflag=1;charc=getcha
- 2024-02-15P8783 [蓝桥杯 2022 省 B] 统计子矩阵
原题链接题解1.当存在某个矩阵符合题意时,所有小于该矩阵的矩阵都符合题意这是我们就可以想到用双指针code#include<bits/stdc++.h>usingnamespacestd;inta[505][505]={0},sum[505][505]={0};intn,m,k;intcheck(intdown,intright,intup,intleft){returnsu
- 2024-02-01【学习笔记】二分图匹配 匈牙利(NTR)算法
时间复杂度显然,这个算法的时间复杂度是O(一边的点数*边数)因为最坏情况就是每一个点都要把所有的边问一遍能不能匹配显然,常数极小另外可以留意一下数据范围,因为如果是稠密图(\(n=500m=2e5\)这种)就可以考虑邻接矩阵存图,方便判重边S准备以下是跑Ntr算法要用的一些东西如果题
- 2024-02-01【警钟撅烂】6
写二分图匹配匈牙利板子洛谷3386WA#2百思不得其解翻看讨论区并ctrlf发现同样情况的帖子发现原因是函数内循环遍历的是左侧点有如下感受1.wssb2.洛谷的数据怎么这么水以上,警示后人附WA代码#include<bits/stdc++.h>usingnamespacestd;constintN=505;con