jimmywang

题解

/ 注册

全部文章 / 题解（共11篇）

题解 | #[ZJOI2007]仓库建设#

首先山脚的那个一定得建。因为只能往山脚运，所以考虑从后往前dp dp[i]dp[i]dp[i]：在iii建一个仓库，后缀最小的值。所以 dp[i]=c[i]+j=i+1n(dp[j]+∑k=i+1j−1p[k]×(x[j]−x[k]) )dp[i]=c[i]+\min_{j=i+1}^...

C++ 动态规划

2021-10-15

0 482

题解 | #[SDOI2012]任务安排#

和P3628 [APIO2010]特别行动队差不多，都是序列拆成几个连续子段，每段都有一个权值，求权值最大/最小。于是如法炮制。 dp[i]:dp[i]:dp[i]:前iii个的总代价最小值。众所周知，后面的权值会被前面的决策影响。所以每次更新的时候加上如果这样决策后面的数增加的权值。于是...

C++ 动态规划

2021-10-15

0 439

题解 | #[NOIP2018]摆渡车#

观察到ttt很小，于是考虑在时间轴上dpdpdp。设c[i]c[i]c[i]为在iii时刻出发的人数。设dp[i]dp[i]dp[i]是在iii时刻出发，前iii分钟等待时间最少的值。所以 dp[i]=j=1i−mdp[j]+∑k=j+1i(i−k)∗c[k]dp[i]= \min_{j=1}...

C++ 动态规划

2021-10-15

0 543

题解 | #Array Without Local Maximums#

能填的数≤200\leq 200≤200。 hmmmmmm。。。。于是dp[i][j][k]dp[i][j][k]dp[i][j][k]表示填到iii，这一位填jjj，前一位填kkk。然后是O(n∗2002)O(n*200^2)O(n∗2002)的啥都别说了就是不可能过得去算法。然后我们发现这...

C++

2021-10-15

0 438

题解 | #Number of Components#

考虑链上的联通块性质。发现对于f(l,r)f(l,r)f(l,r)中，设一个联通块[x,y][x,y][x,y]（位置），那么它一定满足ax−1∉[l,r],ay+1∉[l,r],ax∈[l,r],ay∈[l,r]a_{x-1}∉[l,r],a_{y+1}∉[l,r],a_x∈[l,r],a_y∈...

C++

2021-10-15

0 427

题解 | #[SDOI2016]征途#

首先方差的式子： S2=1m∑i=1m(x‾−xi)2S^2=\dfrac{1}{m}\sum_{i=1}^{m}(\overline{x}-x_i)^2S2=m1∑i=1m(x−xi)2 =1m∑i=1mx‾2−2x‾xi+xi2=\dfrac{1}{m}\sum_{i=1}^{m}\ove...

C++ 动态规划

2021-10-15

0 376

2020牛客NOIP赛前集训营-普及组（第五场）T3 最少移动

参考https://ac.nowcoder.com/acm/problem/16739 均分纸牌均分纸牌这道题是移动纸牌，就相当于相邻的两堆一堆+1，一堆-1，就是此题了。代码： #include<bits/stdc++.h> using namespace std; #define...

2020-10-28

2 631

2020牛客NOIP赛前集训营-普及组（第三场）A 牛半仙的妹子串

果不其然，又是字符串操作题。首先，我们很容易想到用struct来存每个妹子的信息。那么根据题意，我们就需要定义这样一个结构体： struct node{ string nm;//妹子的名字 ll rk;//妹子的评分 int x;//输入顺序 };题目中问法有些有趣：询问...

2020-10-23

2 585

题解：[SCOI2006]整数划分

让我们想一想，n划分成什么最优？（首先一定要保证划分出来的数接近）来暴搜枚举一下： n=1:1=1 n=2:2=2 n=3:3=3 n=4:4=2*2 n=5:6=2*3 n=6:9=3*3 n=7:12=3*2*2 n=8:18=3*3*2 n=9:27=3*3*3 ...... 都是2或3呢...

2020-10-09

0 536

题解【CQOI2007】三角形TRI

题解三角形这题……真的是省选吗？首先，有一个很重要的性质！！！观察这幅图（题目里的）：每个三角形最多与个三角形相邻！！！理论解释：首先我们知道，如果B不包含A，且A的某一条完整的边是B的某条边的一部分，则我们说A靠在B的边上 ---P4536 [CQOI2007]三角形解...

2020-10-09

1 621