- 2024-11-09P4381 [IOI2008] Island 基环树
P4381[IOI2008]Island由于每个点只能向外连一条边,\(n\)个点\(n\)条边,中间有环,故不能再向外连边,所以构成基环内向树森林。叶子节点入度为\(0\),故可以判断叶子结点,倒推回环根,存每个子树的最大深度。最终dp处理每个基环树的环,分两种情况:经过环:分两种情况:顺时针和逆时针,
- 2024-10-19LeetCode热题100|买卖股票的最佳时机(贪心)
简述题意省流版:在一个序列里找到max(a[i]-a[k])且i>k。解题思路: 遍历这个序列,i表示当前遍历到了第i个元素,min1表示1到i这个范围内最小的元素,max1表示1到i这个范围内最大的【max(a[i]-a[k])】。max1=max(max1,第i个元素的值-min1)代码如下:classSolution{public:intm
- 2024-07-29问题 E: 深入浅出学算法060-友好城市
题目描述有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸,而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市,但是由于河上雾太大,政府决定避免任意两条航道交叉,以避
- 2024-07-19暑假集训CSP模拟一
赛时rank14T10,T20,T3100,T40T1大模拟出题人_______T1Start大模拟,注意细节。点此查看代码#include<bits/stdc++.h>usingnamespacestd;#ifdefLOCALFILE*InFile=freopen("in.in","r",stdin),*OutFile=freopen("out.out","w&quo
- 2024-07-14F. Minimum Maximum Distance
原题链接题解1.假设有一个以标记点\(c\)为根的子树,且子树内没有其他标记点,易得该子树内所有点的\(f\leqf(c)\),所以我们可以把该子树内的非标记点全部删掉2.完成步骤1之后,图就变成了所有叶子节点均为标记点的树3.题目等价于求该树内,最小的点到边界的最大值,也就是求树的直径
- 2024-07-04信息素养大赛题目 小旗手 AC代码分享
/*AC*程序思路:*1.定义票数数组x,标记数组a,人数n,max1(最大值比较变量),maxi(最大值下标变量)*2.输入人数,票数数组的第一票*3.循环通过数学表达式((x[i-1]*37+33031)%n)+1递推计算票数并存入票数数组x*4.将a数组的x[i]位置+1(桶标记,将这个学号的获票数+1)*5.遍历a
- 2024-07-032024年华为OD机试真题- 分月饼-(C++/Java/python)-OD统一考试(C卷D卷)
2024华为OD机试真题目录-(B卷C卷D卷)-【C++JavaPython】 题目描述中秋节,公司分月饼,m个员工,买了n个月饼,m≤n,每个员工至少分1个月饼,但可以分多个,单人分到最多月饼的个数是Max1,单人分到第二多月饼个数是Max2,Max1-Max2≤3,单人分到第n-1多月饼个
- 2024-05-29【leetcode每日一题】——2903. 找出满足差值条件的下标 I——python
给你一个下标从 0 开始、长度为 n 的整数数组 nums ,以及整数 indexDifference 和整数 valueDifference 。你的任务是从范围 [0,n-1] 内找出 2 个满足下述所有条件的下标 i 和 j :abs(i-j)>=indexDifference 且abs(nums[i]-nums[j])>=valueDi
- 2024-04-08用C语言实现,找出一个整数数组中,第二大的数
用C语言实现,找出一个整数数组中,第二大的数/********************************************************************* filename: * author :
[email protected]* date :2024/04/07* function:找出一个整数数组中,第二大的数* note :None** Copy
- 2024-03-313.25-3.31周报
天梯赛27-10红色警报这道题的题意要注意是删去一个城市后增加了多少个区域,而不是有多少个城市变成了单独的点,赛时理解错了题意,用set做会有点有问题。其实很简单,就是bfs搜一下有多少个联通块,每次删除把被删的点打个标记,每次联通块的个数和上一次的比较一下,只要增加就是改变了连
- 2024-03-13倒计时31天
1.C-李渊的准备_第十四届南京工程学院程序设计及应用竞赛校外同步赛(nowcoder.com)#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=2e5+6;constintinf=0x3f3f3f3f;typedefpair<int,int>pii;boolcmp(piix,piiy){returnx.f
- 2024-02-18P9847 [ICPC2021 Nanjing R] Crystalfly
前景导入当\(t\in[1,2]\)时,本题如何求解?答:树形dp设\(f[i]\)为以\(i\)为根的树,根节点的晶蝶已消散且儿子节点的晶蝶还未被惊动,能获得的最大晶蝶数。则有状态转移方程\(f[i]=(\sumf[u])+max(a[u])\),其中\(u\)为\(i\)的儿子。最终的答案即为\(f[1]+a[1]\)划向更
- 2023-07-27贪心(不同情况下有不同策略)题单报告
书接上回。感觉这个标题起得云里雾里的颇有上次讲的“反悔自动机”的奇妙风范,坏了会回旋镖插我自己身上了(感觉这样的贪心很厉害。什么叫不同情况下有不同策略呢?就是说你要分讨,分讨的每一种情况我们都要保证这是当前的最优解。这听起来是不是还是很扯,其实这是为了方便我自己看的
- 2023-07-102023冲刺国赛模拟 33.1
T1染色直接操作分块,可以做到\(O(n\sqrt{n})\)。(显然树剖求lca约为\(O(1)\))code#include<cstdio>#include<algorithm>#include<vector>#include<cstring>usingnamespacestd;constintmax1=1e5,B=300;intn,m;vector<int>
- 2023-07-072679. 矩阵中的和
给你一个下标从0 开始的二维整数数组 nums 。一开始你的分数为 0 。你需要执行以下操作直到矩阵变为空:矩阵中每一行选取最大的一个数,并删除它。如果一行中有多个最大的数,选择任意一个并删除。在步骤1删除的所有数字中找到最大的一个数字,将它添加到你的分数 中。请你
- 2023-06-182023冲刺国赛模拟 20.1
我是越来越摆了,一下午就改了一道题;而且这么菜,看了半天的题解做法还没看懂。又是被暴踩的一天。T1树染色比较套路的想法是考虑当前以\(u\)为根的子树,考虑第一次选择\(u\)子树内的叶节点,此时我们必须选择\(u\)以上的节点作为链顶,这会对方案数产生贡献。考虑通过第一条链划
- 2023-06-152023冲刺国赛模拟 19.1
T1矩阵正解做法是二维分块,然而直接上树状数组跑的飞快,不过我写的根号重构,加Fastio后可过。code#include<cstdio>#include<algorithm>#include<ctime>#include<iostream>usingnamespacestd;charbuf[1<<21],*p1,*p2;inlinechargc(){if(__builti
- 2023-06-102023冲刺国赛模拟 15.1
T1计数首先考虑计数有标号可重叠的方案数,容易发现此时\(x,y\)两维独立,因此考虑其中\(1\)维,设\(f_{i,j}\)表示此时考虑到第\(i\)对左右边界\((x_{i,1},x_{i,2})\),离散化后的\(x\)坐标形成了\(j\)个点时的方案数,容易发现此时数轴上存在\(j\)个点,以及\(j+1\)个空
- 2023-05-30leetcode 747. Largest Number At Least Twice of Others
Inagivenintegerarraynums,thereisalwaysexactlyonelargestelement.Findwhetherthelargestelementinthearrayisatleasttwiceasmuchaseveryothernumberinthearray.Ifitis,returntheindexofthelargestelement,otherwisereturn-1.Ex
- 2023-05-282023冲刺国赛模拟 6.1
为什么题目名称又是\(A,B,C\)啊!T1嘉然首先对整个序列做一些处理,容易发现连续的颜色相同的一段,我们只能取其中的一个值,贪心的讲,显然需要取这一段的最大值,那么我们将颜色相同的段缩起来,设最终得到的序列长度为\(m\),不难发现我们最多选择\(\lfloor\tfrac{m-1}{2}\rfloor\)
- 2023-05-252023冲刺国赛模拟 4.1
T1宝石需要统计每种方案中所含宝石的种类数之和,考虑对于每种宝石分开统计,设当前考虑了第\(i\)种宝石,容易发现只需要统计包含这种宝石的方案数,因为对每种宝石的方案数求和就是答案。包含的情况不好考虑,考虑求解不包含这种宝石的方案数,设包含这种宝石的节点构成集合\(S\),容易
- 2023-05-232023冲刺国赛模拟 7.0
T1Matrix很容易想到一个\(O(n^4)\)做法,用uint128压位,然后你发现它过了……正解考虑分治,取出矩阵中间的列\(mid\),由于跨越\(mid\)列的询问必然经过\(mid\)列上一点,因此对于\(mid\)左边的点,预处理每个点向右,向下可以到达的所有\(mid\)处的点,对于\(mid\)右边的点,
- 2023-05-222023冲刺国赛模拟 6.0
T1染色我们按照深度分别进行考虑,设当前考虑的深度为\(x\),考虑一种暴力的做法是设\(f_u\)表示将\(u\)节点内所有深度为\(x\)的点全部涂黑的最小代价,显然有转移\(f_u=\min(\sumf_v,a_{x-deep_u})\),正解考虑将深度为\(x\)的点取出来建立虚树,容易发现一个点代表原树一
- 2023-05-14维护集合两元素最大乘积
维护集合两元素最大乘积给出多个集合,不断合并集合,要求求出最大集合中任意两个元素乘积的最大值顾名思义,我们求最大值和次大值相乘一定最大我们考虑到可能为负值,所以我们还需要维护最小值,和次小值怎么维护呢?怎么把操作写的漂亮?规定a序列为更新工具维护b的最大值和次大值
- 2023-05-112023冲刺国赛自测1
T1fun\(\sum_{B}\prod_{i=1}^n\binom{B_i}{A_i}\),设\(B\)序列的长度为\(T\),考虑这个式子的组合意义,首先枚举\(B\)是将长度为\(T\)的序列划分为\(n\)段,\(\binom{B_i}{A_i}\)是在第\(i\)段内选出\(A_i\)个位置,考虑简化这个选择的过程,在原序列中加入\(n-1\)个位