DAY12

今天又是风和日丽的一天,好的,我来讲讲今天的题目:
T1:好吧,这题是题小模拟,只要稳一点就可以AC;
T2:匹配只需升序排一遍再枚举一遍即可;
T3:直白的搜索题,深搜宽搜都可以;
T4:一道简单dp,只需暴力枚举一下点再用前缀和即可轻松AC;
好的,i will 好好学习天天向上,wait for tomorrow

Day11

【虚】
题意:从数轴的原点开始,有1/4的概率往左或往右走,有1/2的概率被-1s(站在原地不动)。询问t时到p点的概率。
把一个点拆成两个点,则题目可化成有1/2的概率往左或往右走,询问2t时到2p点的概率。可用排列组合求解。
【传送】
题意:一张n*m的图,从(1,1)开始,可以往左或往下走,在一些点有传送门,可以传送到另一个点,询问最大收益。
tarjin缩点+spfa即可。(为什么说的那么简单?因为我还没写出来)。
【串】
题意:n次操作,有p的概率出现1,否则为0。每个长度为x的1可以获得x^3的分数,求答案的期望。
假设在i之前已经出现了x个1,那么如果新加入的是1,对答案的贡献是(x + 1)^3 - x^3, 化简得3x^2 + 3x + 1。
所以,现在只需要维护x^2、x的期望即可。
x的期望:x1[i] = (x1[i - 1] + 1) * x
x^2的期望:x2[i] = (x2[i - 1] + 2 * x1[i - 1] + 1) * x
答案期望:sum += (3 * x2[i - 1] + 3 * x1[i - 1] + 1) * x

Day8

【小奇挖矿】
题意:规定好路线,对于每一个路过的星球,可以选择得到金钱但能力值下降,或者花费金钱但能力值上升,求最大收益。
对于每次选择,受到影响的只有后面的点,那么,可以想到从后往前贪心。能力值w可以把它拆分为w个1能力值,得出转移方程:
ans = max(ans, ans * k + (double)Be[i])或ans = max(ans, ans * c - (double)Be[i])。最后的答案只要ans*w。
【逆天阵】
题意:求多个字符串的最长公共子串。
对一串字符串暴力枚举后缀,求next数组,与每一串字符串KMP求匹配长度。
由于时间复杂度接近题目要求,需要加点小优化,暴力枚举的串选择长度最短的串,若后缀的长度小于答案的长度则退出。

7.24

今天回泉州啊集训的最后1天,在长乐集训我收获了很多,以前不太懂动态规划现在比以前更懂了。你老师选中了国杨同学在那里继续深造我要向国杨好好学习,虽然他很孤独但是他的收获一定比我们大。

好现在我们来说题解。

第一题用贪心,

第二题用动规,

第三题就深奥啦,用一个归并排序,将许多无序间变成有序间。这个排序倪老师没有教过,当旁边的同学在说要用归并排序我真是二丈和尚摸不着头脑。

第四题不理解,看来要大补一下

 

 

 

 

 

这方面知识了。

2017.7.24

  • 第一题:数列分段
  • 贪心,for到比m大的ans++,清零,最后输出ans即可。绝大部分人都ac了。
  • 第二题:活蹦乱跳的香穗子
  • 正解spfa,从每个点开始spfa。容易知道只有某格x的价值严格小于另一格y的价值,x才能更新y,则我们可以先把每个点保存下来,按照价值从小到大排序,再一个个入队,那么一个点如果被更新过,则这个点不需要再次入队(更新出的值不会更优),否则将其dis设为0,入队
  • 第三题:序列
  • 我直接暴力二重for,40。正解分治,求序列中的逆序对数目,是用分治来解决的典型例题。发现题目有2重约束,i<j且a[i]>a[j],那么我们使用分治,用左区间更新右区间,即保证了i<j,再归并,例如归并时保证数组为升序,i为左区间的指针,j为右区间的指针,则当a[i]>a[j]时,因为a[i+1],a[i+2]......,a[mid-1],a[mid]都比a[i]来的大,对于a[j]就产生了mid-i+1这么多对逆序对(a[j]与a[i]到a[mid]的所有数都满足逆序对定义)。
  • 第四题:海岛求救
  • 这题是求极大子矩阵,n和m比较小,我们可以3方过,记录a[i][j]表示从i,j这个点可以向左拓展多少步。则更新a数组时,先枚举列,再枚举行,看一下i,j和i,j-1的符号就可以nm的得到a数组的值。可以枚举一个i,j的点,然后一直向下拓展到(k,j)这个点,则宽为(k-i+1),宽为拓展过程中a数组的最小值,即min(a[i][j],a[i+1][j].....,a[k][j]),这个东西在枚举k的时候顺便记录一下即可。我打的一堆东西,有点像队列,过了样例和一堆我创造的数据,结果零分,还不如四重for。

题解7.24

题1
贪心,对于某一段不能超出m,记录当前段已经保存的值,加入某个数时如果超出题目范围了就多分一段。
核心代码:
for(i=1;im)//判断是否到达规定数值。
{
sum=0;
temp++;
i--;
}
if(i==n)
temp++;
}
题2
朴素算法:从每个点开始spfa。
正解:容易知道只有某格x的价值严格小于另一格y的价值,x才能更新y,则我们可以先把每个点保存下来,按照价值从小到大排序,再一个个入队,那么一个点如果被更新过,则这个点不需要再次入队(更新出的值不会更优),否则将其dis设为0,入队。(不知什么是朴素算法的我QWQ)
题3(建议不懂分治的先复习一下)
逆序对定义:若存在iaj,则就为一个逆序对
求序列中的逆序对数目,用分治来解决的典型例题。发现题目有2重约束,ia[j],那么我们使用分治,用左区间更新右区间,即保证了ia[j]时,因为a[i+1],a[i+2]......,a[mid-1],a[mid]都比a[i]来的大,对于a[j]就产生了mid-i+1这么多对逆序对(a[j]与a[i]到a[mid]的所有数都满足逆序对定义)。(啥是分治-.-?)
题4
求极大子矩阵
n和m比较小,我们可以3方过,记录a[i][j]表示从i,j这个点可以向左拓展多少步。则更新a数组时,先枚举列,再枚举行,看一下i,j和i,j-1的符号就可以nm的得到a数组的值。
可以枚举一个i,j的点,然后一直向下拓展到(k,j)这个点,则宽为(k-i+1),宽为拓展过程中a数组的最小值,即min(a[i][j],a[i+1][j].....,a[k][j]),这个东西在枚举k的时候顺便记录一下即可。
这次我得了110分,还好没垫底。

7.24

题解

No.1  divide_a

我以为是搜索,于是就错了。。。

正解就是简单的贪心,啊啊啊我为什么想这么复杂。

No.2  jump

向每个点的上下左右,纪录下这个点最多能走的次数,最后找出最多的步数。

No.3   sequence

虽然枚举不是正解,但是毕竟能拿70分。

 

20170724题解

第一题:数列分段Section I

第一遍看题目被骗了,以为是DP,好吧,其实它是贪心。每加入一个数,若加上先前的一段后大于m,则新建一段。

第二题:活崩乱跳的香穗子

枚举每个点作为起点,用搜索计算出最多能走的步数,数据太水,居然过了。。。

第三题:序列

分治算法。

第四题:Skyline的海岛求救


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for(i=1;i<=m;i++)
    for(j=1;j<=n;j++)
        if(map[i][j])
        {
            minn=302;
            for(k=i;k<=m;k++)
            {
                if(!map[k][j])
                    break;
                for(l=j;l<=min(minn+j+1,n+1);l++)
                    if(!map[k][l])
                    {
                        minn=min(minn,l-j);
                        break;
                    }
                if(minn!=302)
                    ans=max(ans,minn*(k-i+1));
            }
        }

 

暑期集训第十天(最后一天)

鹅鹅鹅鹅鹅鹅,听说这次只是第二期,还有第三期,第四期……

那也就只好接受现实了,今天都最后一天了,我就随便谢谢就好了,也就不写题解了,聊聊就好。(而且今天题目貌似有点难)

那就让我xia bi下这十天的总结。

总的来说,这次是我第一次出来集训,我受益匪浅,也更让我意识到了时间的紧迫。不仅仅是竞赛,或许很多方面我都应该开始下功夫了。

7.23心得

差点忘记写博客了。上午考出的分数垫底了,朝露时光,却一波三折,我现在只希望否极泰来,理解能力强一点。许多题目听过,问过,花了整个下午的时间,努力却化为泡影。

题解是虚伪的,为此我来谈谈对“任务分配”的看法――

这题一看就知道用动规,一开始我以为要用三个数组,用一重循环,发现不会产生最优解。看了题解才知道,用下标和数组值分别存储a和b目前用的时间。这个概念非常抽象,看来学奥信得下下下下下下下下下功夫啊。