Day24h

分类

2019 Multi-University Training(2) 2019牛客暑期多校训练营(1) CF(37) Record My Feelings(5) 动态规划(23) 图论(4) 字符串(3) 数学(20) 数据结构(8) 未归档(5) 模板(23)

/ 注册

全部文章（共131篇）

取整

取整共包括三个函数，都在<math.h>头文件下向下取整 floor() 向上取整 ceil() 四舍五入 round() 这些函数很显然只对小数有用，而当要运算两个整型数之间的除法时，要乘一个 1.0，以此来进行浮点数运算。

2020-01-15

0 472

背包问题

背包问题当范围很小的背包问题是很容易解决的，而当范围很大\((例如：1\le n\le 100,1\le w_i\le10^7,1\le v_i\le 100,1\le W\le 10^9)\)时，就应该换一种 dp 的表示方式，这样才能够降低其复杂度。 \(dp[i+1][j...

dp

2020-01-14

0 390

完全背包问题

完全背包问题 \(\begin{cases}dp[0][j]=0\\dp[i+1][j]=max(dp[i][j-k*w[i]]+k*v[i]) \end{cases}\) 代码： int n,W; cin >> n >> W; for(int i=0;...

dp

2020-01-14

0 561

最长公共子序列

最长公共子序列注：子序列是可以不连续的。递推公式： \(dp[i+1][j+1]=\begin{cases}dp[i][j]+1&(s_{i+1}=t_{j+1})\\max(dp[i][j+1],dp[i+1][j])&(其他)\end{cases}\...

字符串 dp

2020-01-14

0 398

Petya and Exam

C. Petya and Exam 重要的事情说三遍！认真读题！认真读题！认真读题！思维要开阔一点，不要被局限住了。因为 t 很大，所以我们不能遍历 t，但是 n 只有1e5，所以我们可以遍历每道题的截止时间。然后在其多余的时间内尽可能多的做后面还没有做过的简单题，做完了...

思维贪心

2020-01-14

0 458

K for the Price of One

B. K for the Price of One (Hard Version) 赛时失手推错了规律... 这个题不是单调递增的但是它有一个规律：当买同样多的东西时，优先买便宜的所以我们可以求出买 i 个东西时最便宜的价格 sort(a+1,a+n+1); for...

思维 dp

2020-01-14

0 394

Mafia

C. Mafia 参考：Editorial for Codeforces Round #202 假设最终答案为\(x\)，则\((x-a[i])\)表示的是第\(i\)个人可以充当监护者的局数，而\(\sum^n_{i=1}{(x-a_i)}\)表示得则是在进行\(x\)局游戏保...

思维二分

2020-01-13

0 432

三分

三分亲测wa了无数遍得到的板子.... 模板： int l=0,r=n,ans=inf; while(l<=r-1) { int mid=(l+r)>>1; int midmid=(r+mid)>>1; int ans1=jud...

三分

2020-01-13

0 373

Molly's Chemicals

C. Molly's Chemicals 这道题的思路跟C. Summarize to the Power of Two十分的相似。都是要求关于某个数的倍数。优化方式都是用一个 map 来储存存在的数字，然后用某个数的幂次方减去当前遍历数字，看 map 是否存在有这个值。因为转化为幂次...

前缀和

2020-01-12

0 409

DNA Alignment

C. DNA Alignment 来推导一下这个题：假设在给定的 s 串中，A，T，C，G分别有 a，b，c，d 个，而要匹配的串中有 A，B，C，D 个，所以其 ρ 值为\(Aa+Bb+Cc+Dd\)，而 \(A+B+C+D=a+b+c+d=n\)，我们可以自己掌控 A B C D 的多...

思维快速幂

2020-01-12

0 415