- 2024-10-02题解:SP1703 ACMAKER - ACM (ACronymMaker)
题目大意:一个有一些单词组成的短语,给定一个缩写词,求此缩写由此短语的单词组成的可能方案数。注意,短语中所有重要的单词都要用到,顺序必须和缩写词单词顺序一致。思路动态规划设置:\(dp_{i,j}\):使用前\(i\)个重要单词形成前\(j\)个缩写字符的方法数。\(dp2_{k,m}\):辅助数组
- 2024-10-01每日OJ题_牛客_DP2跳台阶_动态规划_C++_Java
目录牛客_DP2跳台阶_动态规划题目解析C++代码Java代码牛客_DP2跳台阶_动态规划跳台阶_牛客题霸_牛客网题目解析 当前值只和数组的前两个值有关,在往前面的就无关了,所以没必要申请一个数组,直接使用两个变量即可,这样空间复杂度就满足要求了。C++代码
- 2024-09-14虾皮9.14笔试
三道都是简化的板子题第一题给出每个位置的过路费,求从左上角到右下角的最小花费是多少。只允许往下或者往右走。数据范围只有100直接暴力搜索即可。intminPathSum(vector<vector<int>>&grid){intm=grid.size();intn=grid[0].size();intres=
- 2024-09-05POJ-3264
这是rmq半懂不懂(因为已经会线段树了)但是!它的代码真的好短啊啊啊啊啊!#include<bits/stdc++.h>usingnamespacestd;intdp1[500010][20],dp2[500010][20],w[1000010];intmain(){ intn,k,q,l,r; ios::sync_with_stdio(0); cin.tie(0); cin>>n>>q; for(inti=1;i<=n;i+
- 2024-08-10P1091 [NOIP2004 提高组] 合唱队形
这道题主要考察的是线性dp,最基础的dp,这道题的主要思路1.求出最大子序列,2.求出最小子序列,3.找出最少要多少个人要出列。其实我们主要2可以变成逆序查找最大子序列,所以我们只需要把前两个找出来之后我们就可以求出主要3(注意一定要减1,因为中间的那个同学一定会被多算一次所以必
- 2024-07-30P1081 [NOIP2012 提高组] 开车旅行
思路:首先令\(nxt1_i\)表示右侧最近的城市距离(\(id1_i\)为编号),令\(nxt2_i\)表示右侧第二近的城市编号(\(id2_i\)为编号);可以使用set找出离这个城市最近的\(4\)个城市(前面两个,后面两个)。定义:\(f_{i,j}\)表示从\(i\)点出发走\(2^j\)轮最后到达的位置。\(dp1_{i,
- 2024-07-28「BZOJ4899」 记忆的轮廓
题意:从根节点\(1\)走到\(n\),会等概率选择一个儿子走下去,其中\(1-n\)的简单路径上编号依次递增,编号在\([1,n]\)的叫做正确节点,\([n+1,m]\)的叫做错误节点,一共有\(p\)次存档的机会,\(1\)和\(n\)必须存档,存档只能在正确节点上进行,而且同一个节点不能存多次档,每次到达一个
- 2024-07-26可以捕捉高动态范围成像的的AR0521SR2C09SURA0-DP2、AR0522SRSM09SURA0-DP2、AR0821CSSC18SMEA0-DPBR图像传感器
AR0521SR2C09SURA0-DP2、AR0522SRSM09SURA0-DP2、AR0821CSSC18SMEA0-DPBR图像传感器——明佳达1、AR0521SR2C09SURA0-DP2是一款1/2.5英寸CMOS数字图像传感器,带有2592(H)×1944(V)有效像素阵列。它能在线性或高动态范围模式下捕捉图像,且带有卷帘快门读取,其中包含了复杂
- 2024-07-20换根dp三题
真的是公公又式式啊换根dp的宗旨是利用已有的信息来推出其他信息换根dp的题目通常是树,o(n)时间空间,要求每一个点的答案。我们如果指定了以1为根,那么可以算出每个点往下的答案,但是每个点的父亲对本身的贡献还没有算,所以我们可以记录dp1,dp2两个数组,分别记录专用图注意,dp1[u]
- 2024-06-22力扣每日一题 6/21 数组
博客主页:誓则盟约系列专栏:IT竞赛专栏关注博主,后期持续更新系列文章如果有错误感谢请大家批评指出,及时修改感谢大家点赞
- 2024-06-18基础背包问题
01背包有N种物品,第i种物品的体积是v[i],价值是w[i],每件物品最多只能选1件。有一个容量为V的背包,问将哪些物品装入背包,可使这些物品的总体积不超过背包,并且总价值最大,输出最大价值。#include<bits/stdc++.h>usingi64=longlong;voidsolve(){intN,V;std::cin
- 2024-06-08【leetcode 1510 石子游戏】【记忆化搜索】
存在和对于一切的语言importjava.util.Arrays;classSolution{publicbooleanwinnerSquareGame(intn){dp=newBoolean[n+1];dp2=newBoolean[n+1];Arrays.fill(dp,null);Arrays.fill(dp2,null);dp[0]=fa
- 2024-06-04严格次小生成树
如果我早点遇见你,结局是不是会不一样模板题链接很久没有写过这么长的代码了重要部分就是对倍增LCA的改动以下是代码,维护了最大边权和次大边权//Createdbyqyyon2024/6/4.#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#definePIIpai
- 2024-05-25算法学习笔记——动态规划.最长上升/下降子序列 2024.5.24
LanqiaoOJ 773这道题是一道动态规划的题目,主要考察最长上升/下降子序列,难度中等,但是对思维的考察比较重要,特别是如何解决其第二问题目描述某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以
- 2024-04-20基环树算法总结
基环树算法总结一、什么是基环树基环树,顾名思义,有两个要素:环和树。因此,基环树就是一棵树的一个节点,扩成一个环,做题时,多棵基环树组成的基环树森林,常以如下方式出现:每个点只有一个出边。每个点只有一个入边。图中一共有\(n\)个点,\(n\)条边。那么,基环树类型的题目应该怎
- 2024-03-28数位dp
数位dphttps://leetcode.cn/problems/reverse-bits-lcci/description/publicintreverseBits(intnum){intmax=0;intdp1=0;intdp2=0;for(inti=0;i<32;i++){if((num&1)==1){
- 2024-03-24导弹拦截
一、问题描述P1020[NOIP1999提高组]导弹拦截二、问题简析该题要我们求两个问题:1、不上升子序列的最大长度2、不上升子序列的最少个数利用\(Dilworth\)定理,我们得到不上升子序列的最少个数等于上升子序列的最大长度。现在,就是求这两个问题:1、不上升子序列的最大长
- 2024-03-04p7914-solution
P7914Solutionlink先考虑Subtask\(4\)。设\(dp_i\)表示长度为\(i\)的方案数,按题目定义转移:AB,ASB:\(\displaystyledp_n\getsdp_n+\sum_{i=1}^{n-1}\sum_{j=0}^kdp_i\timesdp_{n-i-j}\)(A):\(\displaystyledp_n\getsdp_n+dp_{n-2}\)(SA),(AS):\(\displa
- 2024-01-26寒假训练2024/1/26
2024,1,26今天做石子合并的题比较多贴一个模板 for(intlen=2;len<=n;len++){ for(inti=1,j;(j=i+len-1)<=n;i++){for(intk=i;k<j;k++){if(dp[i][j]>dp[i][k]+dp[k+1][j]+pre[j]-pre[i-1]){
- 2024-01-15AtCoder Beginner Contest 336
B-CTZ难度:⭐题目大意给定一个数n,输出其二进制最后有几个连续的0;解题思路模拟一下就行;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#defineendl'\n'usingnamespacestd;
- 2023-12-11牛客挑战赛71 B树上博弈
Link一道很有意思的min-max博弈用树上dp来解决,那么显然的,当前节点是谁取的会影响答案,\(dp2_{i,j}\)表示取当前阶段,被Alice/Bob取走的结果,并且这个题是取子树上任意的节点,那么还需要保存子树上的信息,故使用\(dp_{i,j}\)记录下子树中的Alice/Bob取走的结果,然后就可以顺着dp解决这
- 2023-12-09Codeforces Round 801 (Div. 2)
基本情况A就开始犯病,导致+2.B、C都过样例了,但是都错。B.CircleGame赛时推出来奇数必输,也知道偶数不是必赢,但是思路不清楚。这里我没意识到一个很关键的性质。奇数堆拿的石堆会变,这也导致了必输,比如三个堆\(1,2,3\)。表粗的为JOE。123123显然JOE拿的石堆是变化的
- 2023-11-27DP2
DP2UVA12141LineChart先离散化一波,记位置从小到大第\(i\)个元素离散化后的大小为\(a_i\)。这题最大的难点就在于如何避免计重。如果现在要更新\(i\)位置的dp值,且\(\existsp<q,a_p=a_q\neqa_i\),则贪心地考虑用\(q\)转移,而不是\(p\),因为\(q\)位置结尾包
- 2023-11-08导弹拦截
[NOIP1999普及组]导弹拦截题目描述某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统
- 2023-10-16P7914 做题笔记
题目链接CSP考前做下历年真题。转移很多,我刚开始设$dp1[i][j]$为$i$到$j$合法的方案数,$dp2[i][j]$为左边一段$*$,右边是合法的方案数,以及$dp3[i][j]$,右边是$*$,左边合法。然后就进坑了,比如$()()()$,会在第二个位置统计一下,(两个合法的字符串拼起来)也会在第四个位置统计