20170717福州集训

 

第一题:二进制

用f[i]表示由00和1组成的i位二进制数个数 mod 15746的余数,f[i]=f[i-1]+f[i-2]。

第二题:修复公路

瓶颈生成树。

无向图的最小生成树一定是瓶颈生成树。瓶颈生成树不一定是最小生成树。

第三题:最小值

用sum[i]表示前i个数的和,则i~j的和为sum[j]-sum[i-1]。将sum数组从小到大排序,则sum数组中相邻两个数差的绝对值中最小的值为所求。

第四题:音量调节

动态规划。用bool数组f[i][j]表示到第i首歌为止,是否可以调节到j音量,代码如下:


1
2
3
4
5
6
7
8
9
or(i=1;i<=n;i++)
    for(j=0;j<=maxlevel;j++)
        if(f[i-1][j])
        {
            if(j-c[i]>=0)
                f[i][j-c[i]]=1;
            if(j+c[i]<=maxlevel)
                f[i][j+c[i]]=1;
        }

 

最后将i从maxleve -> 0循环,若f[n][i]为true,则输出最大音量i。

day 2

第一题题解:
n=1 1
n=2 11 00
n=3 100 001 111
n=4 1100 0000 0011 1001 1111

n=1 1
n=2 2
n=3 3
n=4 5
发现规律f[n] = f[n-1]+f[n-2];

在长度为n-2的所有二进制后面再加两个0;
在长度为n-1的所有二进制后面再加1个1;
如11+00=1100 00+00=0000
100+1=1001 001+1=0011 111+1=1111
而这正是n=5的答案;
这题只要把前四项列出来,就可以发现规律:发现规律f[n] = f[n-1]+f[n-2]; 。
第四题题解:
每个阶段音量可以调高可以调低,所以就是个背包了,与普通背包的不同是一个是选或不选,一个是正或负。
题目截取:输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于0或者高于maxLevel,输出-1。
我看到之后果断cout<<’-1’;
我最后得分为140分。

The scend day of Changle

怀着膜拜的心,我已兢兢业业的度过了第二天的安(bao)定(ling)生活,接下来是我的一些拙见:

题A:一道典型的斐波那契数列,可自推,在此不多说,祥见https://v.qzyz.com/problem/show/2324

题B:刚拿到题时以为是一棵树,实现后发现有n三方的复杂度;果断跳过,后来打了个小并查集,勉强拿到40分

题C:第一眼打了一个模拟,传奇for,拿到20分(我也不知道怎么拿的)后来经提点成功AC;正解为前缀和。

题D:由于数据水的原因吧(外加我相信暴力出奇迹)强行暴搜后成功AC,但正解为动态规划,转移方程推法大致为:f【i】【j】中i表示调节i次;j为可达到的音量,由于只可加或减音量,so f【i】【j】=f【i-1】【j+a【i】】 or f【i】【j】=f【i-1】【j-a【i】】;

今天怕是崩了,才AC两题,故总分260,经提点后400,我一点会好好学习,天天向上

Day 2 (7.17)

解题

题1  二进制

求所有可以只用1和00拼成的长度为N的二进制数的个数除以15746的余数。

比如当N=4的时候,有5个可能的二进制数:0011,0000,1001,1100,1111。

脑子灵光一点就可以直接看出这组数是斐波那契数列了,当然也可以推倒出来:设f[n]为长度是n的字符个数。如果最后是00,那么方案数为f[n-2],如果最后是1,方案数为f[n-1],所以f[n]=f[n-1]+f[n-2],这就是斐波那契数列。

题4  音量调节

给定整数beginLevel,代表吉他刚开始的音量,以及整数maxLevel,代表吉他的最大音量。音量不能小于0也不能大于maxLevel。输入文件中还给定了n个整数c1,c2,…,cn,表示在第i首歌开始之前吉他手想要改变的音量是多少。找到最后一首歌的最大音量是多少。

这题数据给得比较小,所以可以考虑搜索,

动规:设f[i][j]=1表示当前是第i首歌,音量为j是可行的。的方程是f[i][j]=((f[i-1][j+c[i]]&&j+c[i]<=maxL)||(f[i-1][j-c[i]]&&j-c[i]>=0))。看似略显复杂,不过意思就是由i-1的状态,加以条件判断推导出f[i,j]的状态是否存在,决策有两种:升高音量或降低音量,如果j-c[i]<0就不能升高音量,j+c[i]>maxLevel就不能降低音量,最后遍历一遍f[n,i]的状态,求出使f[n,i]=true的最大的i即为答案。

真.Day 2

哈哈正经算的话今天才应该是第二天哈。

废话不多说,第一题设f[n]为长度是n的字符个数。如果最后是00,那么方案数为f[n-2],如果最后是1,方案数为f[n-1],所以f[n]=f[n-1]+f[n-2];第二题利用prim或者kruskal求最小生成树,最大的边权即为答案;第三题用前缀和的方法,即用sum[i]表示a[1]+…+a[i]。则a[i]+…+a[j]即为sum[j] – sum[i – 1]要使|sum[j] – sum[i – 1]|最小处理出所有sum[i]后排序, 在sum值相同的情况下,记录下标最小与最大的位置。最后一题转移方程为f[i][j]=((f[i-1][j+c[i]]&&j+c[i]<=maxL)||(f[i-1][j-c[i]]&&j-c[i]>=0)),看似略显复杂,不过意思就是由i-1的状态,加以条件判断推导出f[i,j]的状态是否存在,决策有两种:升高音量或降低音量,如果j-c[i]<0就不能升高音量,j+c[i]>maxLevel就不能降低音量。最后遍历一遍f[n,i]的状态,求出使f[n,i]=true的最大的i即为答案。

2017.7.17

  • 题目一:二进制
  • 找规律,可以发现它是斐波那契数列,用for或递归都可以过。但我没有注意到数十分大,要先取余,结果导致零分。
  • 题目二:修复公路
  • 瓶颈生成树,但我不会,直接骗分输出-1,得十分。
  • 瓶颈生成树的定义:最大的边权值是所有生成树中是最小的。                                               定理:无向图的最小生成树一定是瓶颈生成树。                                                                        注意:瓶颈生成树不一定是最小生成树。                                                                                      利用prim或者kruskal求最小生成树,最大的边权即为答案。
  • 题目三:最小值
  • 我直接暴力,40分。正解前缀和。
  • 题目四:音量调节
  • 我直接深搜(难得我第一个自己打出来的搜索),60分,超时了。正解动态规划,设f[i][j]=1表示当前是第i首歌,音量为j是可行的。转移方程为f[i][j]=((f[i-1][j+c[i]]&&j+c[i]<=maxL)||(f[i-1][j-c[i]]&&j-c[i]>=0))。

2017长乐集训day2

首先是其实是A+组的B组

T1      今天唯一的得分项也是这几天第一次A的题,题目要求区间[0...1000]一些二次函数的最大值中的最小值,注意区间可取的数可为实数(刚开始被这个卡样例),因为二次函数的a总是大于零,即开口向上,可知F[x]在区间内定有最小值,画图可知。于是便可用三分查找的方法不断逼近最小值(要注意精度)。

 

T2        字符串分块,动态规划,不是很清楚

 

T3        非常强势的暴力,同样需要非常强势的预处理。。用线段树什么的

--------------------------------------下面是萌萌的分割线----------------------------------

继续阅读2017长乐集训day2

7.17心得

按板块学习C++,功效比碎片式刷题多得多。就像外国的青少年学习,是整个学期一个一个科目上下来的。

I=============================================I

最小生成树是指在N个顶点中的N条边中,取边后使代价最小,通常有算法:

从一个顶点开始,往外不断寻找较小的代价,直到最后一个顶点。你需要一个数组来判断一个顶点是否被访问过,一个数组来存储最小的代价,在不断更新存储代价的数组的过程中,答案就浮出水面了。

 

Day2

【曲线】
题意:令f(x)为多个二次(一次)函数的最大值,求f(x)的最小值。
画图可以发现两个二次函数取最大值的图像形状类似二次函数,可得f(x)的图像也类似二次函数。那么,可以在所给区间内用三分求出答案。
二分也可完成此题,二分答案ans,暴力判断每个二次函数<=ans的区间是否有交集,若有,则答案可行,反之答案不可行。

【挑战】

题意:将字符串分块,使每个块中的字母都在下一个块中出现过。(即下一块每个字母的出现次数比当前块多)。求最多的分块。
令f[i][j]表示在i位是最后一个块的长度为j的答案。可由f[i - j][k]转移得到。时间复杂度为O(n ^ 3)。可得70分。
改进这个算法,因为要求块最多,应用贪心的思想,每个块的长度越少,块的数量越多。令f[i]表示以i为结尾最后一块的长度最短是多少。可以由f[i - f[i]]转移得到。

【序列】

题意:判断序列的所有子序列是否都有数只出现一次。
暴力枚举每个子序列,判断是否符合条件,可得30分。
改进暴力,对于一个a[i],前一次出现记为pre[i],后一次出现记为nex[i]。那左端点l在pre[i]+1..i,右端点在i..nex[i]-1都是合法的。如果判定一个区间[l,r],a[i]是其中唯一出现过的数字。那这个区间就可以切割成判定2个区间[l,i - 1],[i + 1, r]。那对于一个区间[l,r],i,j同时从左边和右边开始扫,碰到第一个唯一出现的数字就切割。直到l>=r。
这种做法看起来很像暴力,但实际上跑得飞快。时间复杂度证明:T(n) = T(k) + T(n-k)+min(n, n - k)。一种直观的想法就是,每次复杂度都是较小的那个区间。倒过来看相当于较小的合并到较大的。那就是启发式合并。O(nlogn)。

主要代码如下:

继续阅读Day2

长乐____Day2

第一题一道简单模拟 找最大公约数 因一个细节没有初始化丢了50分 orz

第二题一个机器人操作 暴力得40分

第三题一个字符串处理 得90分 由于一个细节没有处理好导致没AC

第四题暴力40分,结果文件名多打了空格 ,自领50个俯卧撑

今天应得分200+,结果180,一大堆细节不应该错误,希望明天不会再这样。orz