1 清秋身上攻

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 8w+

CodeForces - 939F Cutlet

Description\text{Description}Description注意第 iii 分钟翻转是将现在朝下的一面煎这一分钟再翻。Solution\text{Solution}Solution朴素 DP\text{DP}DP:令 f[i][j]f[i][j]f[i][j] 为煎了 iii 分钟,现在朝上的一面一共煎了 jjj 分钟的最小翻转次数。则有(即翻与不翻):f[i][j]=min⁡(f[i−1][j],f[i−1][i−j]+1)f[i][j]=\min(f[i-1][j],f[

2020-08-13 16:06:54

CodeForces - 319C Kalila and Dimna in the Logging Industry

Solution我们令 f[i]f[i]f[i] 为砍第 iii 棵的最小代价。有转移:f[i]=f[j]+a[i]×b[j](1≤j≤i−1)f[i]=f[j]+a[i]\times b[j](1\le j \le i-1)f[i]=f[j]+a[i]×b[j](1≤j≤i−1)我们考虑为什么这是对的。(因为实际上我们可以选择先砍后面的再砍前面的)首先我们证明不存在先砍 kkk,再砍 jjj 的情况(其中 k≠n,j<kk\ne n,j<kk​=n,j<k)。因为 b[n]=

2020-08-12 11:30:48

CodeForces - 744C Hongcow Buys a Deck of Cards

Solution朴素思路 f[i][j]f[i][j]f[i][j] 表示取卡状态为 iii,用了 jjj 颗红宝石,最少用蓝宝石的数量。瞄一眼数据 1e71e71e7,完全不可做。。。可以反着思考,f[i][j]f[i][j]f[i][j] 表示取卡状态为 iii,省了 jjj 颗红宝石,最多省蓝宝石的数量。为什么可以反着来?首先注意到能省的红/蓝宝石数其实是很少的,红宝石最多省 ∑i=0n−1i=120\sum_{i=0}^{n-1}i=120∑i=0n−1​i=120。其次如果不省,需要的红/蓝

2020-08-11 09:00:51

CodeForces - 1203F2 Complete the Projects (hard version)

Solution这题分成两个部分来做。b[i]≥0b[i]\geq0b[i]≥0。贪心。将 a[i]a[i]a[i] 从小到大排序,然后依次做工作,如果不行就算了。b[i]<0b[i] < 0b[i]<0。发现不能直接贪 (废话直接贪就不是 DP 了)。假设 iii 选完后能选 jjj,那么就有 a[i]+b[i]≥a[j]a[i]+b[i]\ge a[j]a[i]+b[i]≥a[j]。你可能会疑惑为什么这里是 a[i]a[i]a[i] 而不是 rrr 这种东西,其实如果

2020-08-10 15:26:45

CodeForces - 342D Xenia and Dominoes

博主的 BiBi 时间感觉自己压行在向一种无法控制的方向发展。Solution先考虑不管 ‘O’ 该如何进行 DP\mathtt{DP}DP。竖着放的 Domino\mathtt{Domino}Domino 是比较好搞的,关键是解决横着的。令 f[i][j]f[i][j]f[i][j] 为到第 iii 列,之前的 Domino\mathtt{Domino}Domino 已经全部合法,本列需要 i+1i+1i+1 列来空位置的状态为 jjj(如 j=(101)2j=(101)_2j=(101)2​,

2020-08-09 16:02:32

CodeForces - 922E Birds

Solution首先是常规写法:f[i][j]f[i][j]f[i][j] 表示走到第 iii 棵树,如今魔法值为 jjj 能召唤最多的小鸟数。但这面临两个问题:魔法值太大。还有一个魔法上限的限制无法操作,因为上限还和召唤鸟的个数有关。看到 ∑c[i]≤104\sum c[i]\le 10^4∑c[i]≤104,自然想到将其作为 DP\mathtt{DP}DP 的一个状态,其实更正确的思路是发现魔法值和上限都与小鸟数有关。考虑 f[i][j]f[i][j]f[i][j] 表示走到第 iii 棵

2020-08-08 20:04:22

CodeForces - 1316E Team Building

Solution博主先开始想的是 f[i][j]f[i][j]f[i][j] 表示选到第 iii 个人,位置选择情况为 jjj 的最大力量(iii 如果选了位置也包含在里面)。然后把人按 aaa 值从大到小排个序,然后选到某个人进行比赛,如果那个人在当前能选的前 kkk 大之列,就抛弃他在前 kkk 大的地位,在后面找个能选的 k+1k+1k+1 大塞进去。但是这是错的,因为有可能这次最优选择到后面不会推出最优解。正解的预处理和我的一样~~(其实就是误打误撞)~~。只是枚举 iii 时是按照 aaa 值

2020-08-07 17:56:04

CodeForces - 377C Captains Mode

博主的 BiBi 时间博主在外面浪了多天已经退化成原始人的智商了。Description感觉某谷题面漏掉了一些细节,英语辣鸡的博主看了好久。。。两个队伍都使用最优策略。pick\mathtt{pick}pick 与 ban\mathtt{ban}ban 的顺序严格按照题目输入的顺序。这不是废话?Solution感觉很多出题人都喜欢设置一些不会用到的限制/条件。。。对于这道题,misspick\mathtt{misspick}misspick 和 missban\mathtt{missba

2020-08-06 17:18:36

CodeForces - 903F Clear The Matrix

博主的 BiBi 时间能想象博主勤勤恳恳修完锅,交上去直接 MLE\mathtt{MLE}MLE 的快乐?(为什么不直接用滚动数组是真的憨)然后勤勤恳恳改成从 000 开始。Solution我们把矩阵翻过来,改成 nnn 行 444 列。对于左上角在 iii 行的操作,最多只能影响到 i+3i+3i+3 行。所以就令 f[i][a][b][c][d]f[i][a][b][c][d]f[i][a][b][c][d] 为前 i−1i-1i−1 行为 ‘.’,iii 到 i+3i+3i+3 行状态分别为

2020-08-02 10:31:30

CodeForces - 111C Petya and Spiders

博主的 BiBi 时间博主现在在高铁上辽,不过这次的座位玄学变成了卧铺 QwQ\mathtt{QwQ}QwQ。(幸好对面的漂酿小姐姐提醒有充电头,不然只有和黑屏的电脑相对无言,,,岂不美哉?)Solution具体肯定是状压某行,一眼望去发现 n,m≤40n,m \leq 40n,m≤40 觉得搞不动,但是仔细想想发现 n,mn,mn,m 交换对解题没有影响,又有 n∗m≤40n * m\leq 40n∗m≤40,可以得出 min⁡(n,m)≤6\min(n,m)\leq 6min(n,m)≤6,这就可

2020-08-01 16:28:48

CodeForces - 734E Anton and Tree

博主的 BiBi 时间博主还有 1h+11min\mathtt{1h+11min}1h+11min 就ヾノ≧∀≦)o 放假啦!好鸡冻!!!然鹅博主这个小蒟蒻在假期还有作业,但是和平时比较假期作业显得极其划算。hihihihihihihi~Solution感觉这题非常巧。我们将同色的连通块缩成一个点,然后就有一个非常神奇的性质:ansansans 就是 ⌊新树的直径+12⌋\lfloor \frac{新树的直径+1}{2} \rfloor⌊2新树的直径+1​⌋。你可能觉得答案应该是 min⁡(黑点

2020-07-31 20:41:03

CodeForces - 490F Treeland Tour

Solution解法一其实就是暴力求 LIS。只是记录一下 O(nlogn)O(nlogn)O(nlogn) 求 LIS 的算法。解法二博主太蒻,虽咕但下次一定。Code解法一#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 6005;int n, w[N],

2020-07-30 12:02:36

一些结论

数学结论 1若 nnn 为奇数,则在 [1,n][1,n][1,n] 中有奇数个 111 的数字个数为 (n+1)/2(n+1)/2(n+1)/2;若 nnn 为偶数,则 [1,n−1][1,n-1][1,n−1] 中有偶数个 111 的数字个数为 n/2n/2n/2。数据范围结论 1对于约数个数上界的估计...

2020-07-30 08:26:47

一些坑

Point 1CodeForces - 543D Road Improvement正确写法:for(int i = suf[u].size() - 2; i >= 0; -- i)错误写法:for(int i = suf[u].size() - 2; ~i; -- i)原因是 ~iii 只能判断 −1-1−1 的情况。Point 2转自 Arextre。关于 setsetset 的去重情况。假设我们定义了一个 sets,对于结构体 node 我们重载其 < 运算。那么

2020-07-30 08:23:15

CodeForces - 486D Valid Sets

Solution枚举根为 max⁡\maxmax,这样既好判断 max⁡−min⁡<=d\max-\min<=dmax−min<=d 而且能保证同一种联通子图不被计算多次(另外要特判与根的权值相等的情况,只能放一个来 DP\mathtt{DP}DP)。然后考虑选不选子树大力 DP\mathtt{DP}DP 就行了。Code#include <cstdio>const int mod = 1e9 + 7, N = 2010;int n, d, w[N], head

2020-07-29 20:35:06

【转】树的直径

树的直径 By TEoS

2020-07-29 20:20:52

【转】计算几何总结

总结 by clover_hxy

2020-07-29 19:13:39

CodeForces - 1101F Trucks and Cities

Solution直接枚举 mmm 显然是不现实的。不过我们发现,卡车的油箱大小和卡车依靠油箱走的最长的一段路是一次函数关系。而卡车依靠油箱走的最长的一段路是由卡车能将它的路程分为几段决定的。所以可以转化为 iii 到 jjj 分 kkk 段路,使得最长的一段路最短。朴素算法枚举 i,j,ki,j,ki,j,k 和最后一段路的开始 ttt,是 O(n4)O(n^4)O(n4):f[i][j]=min⁡t=1jmax⁡(f[i][t],dis(t,j))f[i][j]=\min_{t=1}^j \m

2020-07-29 17:15:46

CodeForces - 838E Convex Countour

Solution因为是凸多边形,当连接两点时,相当于将序列划分为两段,段与段之间不能有连线。我们要求一顺到底,所以每次的连线,相当于将区间缩小,你会发现只能连区间的两个端点。这个 DP\mathtt{DP}DP 比较好想,我们令 f[i][j][0]f[i][j][0]f[i][j][0] 为 [i,j][i,j][i,j] 区间由 iii 开始的最长不自交路径,f[i][j][1]f[i][j][1]f[i][j][1] 为 [i,j][i,j][i,j] 区间由 jjj ​开始的最长不自交路径:

2020-07-29 09:06:44

CodeForces - 1312E Array Shrinking

Solution先放一下自己的错误代码:#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int N = 505;int n, a[N], dp[N][N];int read() { int x = 0, f = 1; char s; while((s = getchar()) > '9' || s < '0') if(s =

2020-07-28 09:19:41

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。