0 2020linweitong

尚未进行身份认证

我要认证

我是中山市石岐中心小学六年级的学生。

等级
TA的排名 13w+

最小步数 题解

最小步数 题解题目在这里。解题方法这道题目是动态规划。具体如下:

2020-07-12 12:42:58

活动安排 题解

活动安排 题解题目在这里。解题方法这道题目直接暴力即可,每一次贪心选取差距最小的。时间复杂度O(n2)O(n^2)O(n2)。

2020-07-12 12:42:01

二项式展开式 题解

二项式展开式 题解题目在这里。解题方法本题的提示写了:(a+b)n(a+b)^n(a+b)n展开式的第i+1i+1i+1项为an−ibia^{n-i}b^ian−ibi,前面的系数为CniC^{i}_{n}Cni​。注:0≤i≤n0\leq{i}\leq{n}0≤i≤n。什么是CniC^{i}_{n}Cni​呢?其实就是第i+1i+1i+1行的杨辉三角。杨辉三角如下:其中ai,j=ai−1,j+ai−1,j−1a_{i,j}=a_{i-1,j}+a_{i-1,j-1}ai,j​=ai−1

2020-07-12 12:41:10

奇数统计 题解

奇数统计 题解题目在这里。解题方法我们发现a⨁a=0a\bigoplus a=0a⨁a=0且a⨁0=aa\bigoplus0=aa⨁0=a,并且发现异或运算可以用交换律。那么其实偶数最终都会变成000,奇数会变成它本身。所以直接全部数异或一遍即可。...

2020-07-12 12:40:09

2020.07.04【NOIP普及组】模拟赛C组42 总结

2020.07.042020.07.042020.07.04【NOIPNOIPNOIP普及组】模拟赛CCC组424242 总结这次考试我成功AKAKAK了。第一题:奇数统计解题方法我们发现a⨁a=0a\bigoplus a=0a⨁a=0且a⨁0=aa\bigoplus0=aa⨁0=a,并且发现异或运算可以用交换律。那么其实偶数最终都会变成000,奇数会变成它本身。所以直接全部数异或一遍即可。第二题:二项式展开式解题方法本题的提示写了:(a+b)n(a+b)^n(a+b)n展开式的第i+1i

2020-07-12 12:38:08

奶牛的声音 题解

奶牛的声音解题方法转化此题,可以发现最难求的地方是判断这个声音由多少个奶牛组成。其实是一个背包问题。设fif_ifi​表示声音iii由多少个奶牛组成。则fi=min⁡j=1Bfi−Vj+1\begin{aligned}f_i=\min_{j=1}^{B}{f_{i-V_j}+1}\end{aligned}fi​=j=1minB​fi−Vj​​+1​。其实是一个完全背包。最后只要按题意模拟即可。...

2020-07-04 15:42:07

懒惰的奶牛[s] 题解

懒惰的奶牛[s][s][s]解题方法这题是菱形的前缀和数组。可以发现将菱形倒转过来后,(i,j)(i,j)(i,j)应该变成(i+j−1,n−i+j)(i+j-1,n-i+j)(i+j−1,n−i+j)。然后就是简单的前缀和了。直接O(n2)O(n^2)O(n2)可以过。类似差分。...

2020-07-04 15:41:28

灌溉农田 题解

灌溉农田解题方法最小生成树模板。用PrimPrimPrim和KruskalKruskalKruskal都可以拿到满分。

2020-07-04 15:40:43

懒惰的奶牛[b] 题解

第一题:懒惰的奶牛[b][b][b]解题方法这道题目我们直接用前缀和数组(a)(a)(a)就行了。直接枚举右端点,然后求出左端点。l=r−2k−1l=r-2k-1l=r−2k−1我们首先把kkk赋值为2k+12k+12k+1。然后设qqq表示max⁡(max⁡i=1nxi,k)\begin{aligned}\max(\max_{i=1}^{n}{x_i},k)\end{aligned}max(i=1maxn​xi​,k)​。那么答案就是用max⁡i=k+1qai−ai−k−1\begin{al

2020-07-04 15:39:11

2020.06.25【NOIP普及组】模拟赛C组40 总结

2020.06.252020.06.252020.06.25【NOIPNOIPNOIP普及组】模拟赛CCC组404040 总结这次考试我考得不好,只有242424名,160160160分,主要问题就是我没有细心检查,很粗心的做完了。第一题:懒惰的奶牛[b][b][b]解题方法这道题目我们直接用前缀和数组(a)(a)(a)就行了。直接枚举右端点,然后求出左端点。l=r−2k−1l=r-2k-1l=r−2k−1我们首先把kkk赋值为2k+12k+12k+1。然后设qqq表示max⁡(max⁡i=

2020-07-04 15:35:09

最小总代价 题解

最小总代价 题解题目在这里。解题方法这道题目我想得太简单了,以为是最小生成树,其实不是——最小生成树必须是无向图。那么这题就是状压dpdpdp了。设fi,jf_{i,j}fi,j​表示当前传递的状态是iii且现在到了第jjj个人手里的最小价值,此状态必须满足i&2j≠0i\&2^j\not=0i&2j​=0。则fi,j=min⁡k=1nfi−2j,k+ak,j(i&2k≠0,j≠k)\begin{aligned}f_{i,j}=\min_{k=1}^{n

2020-06-24 22:12:27

24点游戏 题解

242424点游戏 题解题目在这里。解题方法直接dfsdfsdfs或暴力枚举。我们得考虑有括号的方法,否则就像我一样没有满分。

2020-06-24 22:11:32

迷宫 题解

迷宫 题解题目在这里。解题方法这道题目的方法很显然是搜索。dfsdfsdfs直接dfsdfsdfs或记忆化dfsdfsdfs就行了,真的没啥好讲。其实我不知道不用记忆化能不能满分。bfsbfsbfs直接按题意bfsbfsbfs。...

2020-06-24 22:10:33

圆圈 题解

圆圈 题解题目在这里。解题方法首先这道题目要求有多少个点在半径为rrr的圆里面。将其转述为,判断一个点(x,y)(x,y)(x,y)是否在半径为rrr的圆里面。怎么判断呢?如下图我们知道点(x,y)(x,y)(x,y)处于绿色线和红色线交错的位置。则红色线的长度是x2+y2\sqrt{x^2+y^2}x2+y2​。因为红色线的长度等于黑色线的长度,所以我们只需要判断黑色线的长度是否小于等于圆的半径即可,如果满足,就代表此点在圆中。也就是判断x2+y2≤r2x^2+y^2\leq{r^

2020-06-24 22:09:09

2020.06.13【NOIP普及组】模拟赛C组38 总结

2020.06.132020.06.132020.06.13【NOIPNOIPNOIP普及组】模拟赛CCC组383838 总结这次考试我考了284284284分,第888名,还可以。第一题:圆圈解题方法首先这道题目要求有多少个点在半径为rrr的圆里面。将其转述为,判断一个点(x,y)(x,y)(x,y)是否在半径为rrr的圆里面。怎么判断呢?如下图我们知道点(x,y)(x,y)(x,y)处于绿色线和红色线交错的位置。则红色线的长度是x2+y2\sqrt{x^2+y^2}x2+y2​。因

2020-06-24 22:03:40

坐船旅行 题解

坐船旅行 题解题目在这里。解题方法这道题的方法是变版floydfloydfloyd或者spfaspfaspfa。floydfloydfloyd每一次我们发现需要是更改的话就直接将以a,ba,ba,b为中间点的长度更新。也就是fi,j=min⁡i=1nmin⁡j=1nfi,a+fa,b+fb,j\begin{aligned}f_{i,j}=\min_{i=1}^{n}{\min_{j=1}^{n}{f_{i,a}+f_{a,b}+f_{b,j}}}\end{aligned}fi,j​=i=1m

2020-06-07 15:07:42

烤饼干 题解

烤饼干 题解题目在这里。解题方法暴力dfsdfsdfs每一次dfsdfsdfs当前行是否需要翻转,如果需要就翻转,然后把全部行都枚举过之后,贪心每一列000和111的个数最大的值并累加进答案,最后与原来的答案取一个最大值就行了。时间复杂度为O(2nm)O(2^nm)O(2nm),可以过。状压dpdpdp暂时不会。...

2020-06-07 15:06:40

寻找星座 题解

寻找星座 题解题目在这里。解题方法这道题的方法是暴力。我们选取一个标准进行尝试就行了,每一次看一看这个标准和是否满足其他的星座,如果符合就输出。

2020-06-07 15:05:10

打牌 题解

打牌 题解题目在这里。解题方法这道题的方法是贪心。我们在第一次出一个最小的牌,然后每一次按规则出牌,当不能出了就出一个最小的。

2020-06-07 15:04:12

2020.06.06【NOIP普及组】模拟赛C组37 总结

2020.06.062020.06.062020.06.06【NOIPNOIPNOIP普及组】模拟赛CCC组373737 总结这次比赛我考了300300300分,第一题没有考虑到一个地方,第三题不知道为什么有一个数据点时间超限。第一题:打牌解题方法这道题的方法是贪心。我们在第一次出一个最小的牌,然后每一次按规则出牌,当不能出了就出一个最小的。得分情况比赛时16.716.716.7分。第二题:寻找星座解题方法这道题的方法是暴力。我们选取一个标准进行尝试就行了,每一次看一看这个标准和是否满

2020-06-06 14:55:50

查看更多

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