2019.10.26 发泄篇

我kiao!!

又来纪中受虐了,心情很是沉重。

今天比赛结束,觉得题目还是较为易懂的,下午该题应该可以很快改出来。

然而,下午讲正解时,说第一题的时间复杂度为O(n^2*logn),但是偶认为,此题若是沿着我早上的思路,应该可以优化成O(n^2)左右,所以打算死磕,然后发现这样打会产生很多细节,但是仍不死心,于是一个下午和一个晚上就没了。也没有调出来,当场自闭,差点爆粗。

SO,通过这件事我们可以得出:我们要相信题解一定是最优的,千万不能又非分之想,否则后果严重!!!

%¥#&……@#@¥%……*……¥(自行脑补脏话)

总结反思 砥砺前行


2019CSP认证第一轮成绩出来,写给学生的话。

下午阅卷结束,成绩几家欢乐几家愁!同学们也许会失望,很迷茫,不满意结果!

这里希望同学要学会反思,善于总结,找到不知之处,为下一次比赛(学习)找到前进的方向。

这里有很多初二(高一)的学生考的不是很好,这是你们第一参加泉州大市的竞赛活动,你在年段也许名列前茅,可是放在鲤城区、泉州市(未来要放在福建省),放到泉州108所初、高中校的大环境中,你肯定是不够优秀的,这也是我们努力的方向。希望能认识到这一点。

在过去一年的竞赛辅导过程中,老师一直强调两点:

1、真实、真诚:训练要真实,改题要真实,有困难要主动提出来,而不是贪图简单、方便选择baidu或copy,要善于问why?每一个知识点的前因后果都要理解,才能立于不败之地;

2、训练中要严格要求自己,历练自己,培养自己的自控能力:训练中,有存在打游戏的现象,对学习目标迷茫,不能严格自己,要在学习中找到乐趣,才能推动你一直进步。提高自学也很重要。

3、还有这次比赛,你准备充分吗?你花了10%,50%,80%,还是200%的时间来准备?也许失败并不是坏事。

失败乃成功之母,希望大家不要迷失在比赛成绩中,重要的是竞赛训练的过程,从过程中学到什么?也许是独自搭公交车、坐高铁、洗衣服。也许若干年后,大家会在一起调侃在机房打题的日日夜夜。

竞赛学习过程中,你有认识几个知心朋友或竞赛伙伴吗?他们是如何学习的?学习不可怕,可怕的是“学霸”过暑假的时间表,既然如此,你还有什么理由不努力呢?

最后,既然选择了远方,就要风雨无阻,不忘初心,砥砺前行!

国庆day6

今天没爆0!!!(因为我刷了一题样例),而且排名一下升到22名
但还是跟往常一样~~我又失误了!

第一题:0分
嗯~~我再看完测试数据后,发现了个东西--0,虽然我打的代码把0也考虑了,但很不巧的,我把去重的数初始值设成0。。。嗯。。。再我把记录的数初始值改成-1后成功AC(我很好奇怎么测试数据都有0)。。。这道题的难点在去重和排序and时间复杂度,不能边循环边排序(除非你想爆时间)
第二题:
嗯。。这道题不会打纯属看不懂题目,后来听学长讲用二分打,打了一会儿也成功AC了。。。(看来语文学好很重要)这道题意义在于考二分(虽然题目看不懂)
第三题:
时间都花在复习初赛和1,2题上,没改。。。听学长说用什么算法(图论)
第四题:
看了一下,随便打了一下,拿了10分。。。没改(不会)

Last Day

老师们都被常州的老师传染了,竟然出了二分题。

第一题  淘淘摘苹果

淘淘四不四有猫病啊,摘个苹果还辣么麻烦。

这道题主要让我崩溃的地方是我布吉岛怎么把同样高度的树进行标记,让它不要在同一次中出现同样高度的树,其他的都还好了。

 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
<span class="hljs-built_in">cin</span>&gt;&gt;n&gt;&gt;m;
<span class="hljs-keyword">for</span>(i=<span class="hljs-number">1</span>;i&lt;=n;++i){
    <span class="hljs-built_in">cin</span>&gt;&gt;a[i];
    t[a[i]]++;
    <span class="hljs-keyword">if</span>(a[i]&gt;k) k=a[i];
}
<span class="hljs-keyword">for</span>(i=<span class="hljs-number">1</span>;i&lt;=m;++i)
    <span class="hljs-built_in">cin</span>&gt;&gt;b[i];
<span class="hljs-keyword">for</span>(i=<span class="hljs-number">1</span>;i&lt;=m;++i){
    p=<span class="hljs-number">0</span>;
    <span class="hljs-keyword">for</span>(j=<span class="hljs-number">0</span>;j&lt;=k;++j){
        <span class="hljs-keyword">if</span>(p==b[i]) <span class="hljs-keyword">break</span>;
        <span class="hljs-keyword">if</span>(t[j]&gt;<span class="hljs-number">0</span>){
            t[j]--;
            <span class="hljs-built_in">cout</span>&lt;&lt;j&lt;&lt;<span class="hljs-string">" "</span>;
            p++;
        }
    }
    <span class="hljs-built_in">cout</span>&lt;&lt;endl;
}

第二题  替身使者

这道题目应该用二分,具体代码如下:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<span class="hljs-built_in">cin</span>&gt;&gt;n&gt;&gt;k;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)
      <span class="hljs-built_in">cin</span>&gt;&gt;a[i];
    sort(a+<span class="hljs-number">1</span>,a+n+<span class="hljs-number">1</span>);
    <span class="hljs-keyword">while</span>(l&lt;=r)
    {
        m=(l+r)/<span class="hljs-number">2</span>;
        t=<span class="hljs-number">1</span>;
        last=a[<span class="hljs-number">1</span>];
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">2</span>;i&lt;=n;i++)
          <span class="hljs-keyword">if</span>(a[i]-last&gt;=m){
            last=a[i];
            t++;
        }
        <span class="hljs-keyword">if</span>(t&gt;=k) l=m+<span class="hljs-number">1</span>;
        <span class="hljs-keyword">else</span> r=m-<span class="hljs-number">1</span>;
    }
    <span class="hljs-built_in">cout</span>&lt;&lt;l-<span class="hljs-number">1</span>&lt;&lt;endl;

这题就是这样了。

第三题 电流

由于默认起点是在房间1,所以用单源算法SPFA。(不会的先学,谢谢)。
从一个点出发修改能到达的点的值,如果更新成功就入队(已在队列的不重复入队)。这些点拥有了一个较之前更优的值,那么可能可以用来更新这个点出发所能到达的点的最优值。
直到所有的点都被修改完为止。

这道题具体代码还未想出。

第四题 行军

这道题目完全看不懂。

题解太扎心了吧,什么叫水到不能再水了???????明明就完全不会啊!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

国庆10.6

T1 Apple

陶陶有强迫症。。。

陶陶摘的下一个苹果高度一定要比刚刚摘的苹果高,但又要尽可能的低,重现他每次摘苹果的情况。。。

模拟题,但要记得考虑0的情况。。。。我没考虑零。。直接爆零??

我一个一个判断,正解用了桶排,不难。。

T2 Stand

使任意两个替身使者特征值差的绝对值的最小值尽可能大,求这个最大值。。题目要先捋清楚。。。

排序,二分,列举中间差值,缩小范围。。大佬核代如下。。。

while(l<=r) {

m=(l+r)/2;

t=1;

last=w[1];

for(i=1;i<=n;++i) {

if(w[i]-last>m)

{ last=w[i]; ++t; }

}

if(t>=c) l=m+1;

else r=m-1;

}  printf("%d",l);

至于这道题为什么让我想起了区间DP,还得了20分就很迷幻了。。。。

T3 Electric

每个管都有电流限制值,电流只能在电流大小不超过限制值时通过。。。。电流从结点1出发,求出电流最多能够以多大的值到达每个结点。。。

考试时连题目都看不懂,打??算了。。

用单源算法SPFA,队列实现。。。也是魔鬼图论模板题。。。

T4 March

题解说是状态压缩DP。。听都没听过。。题解还说f[i][j]表示车在第i行第j列的位置。

???没啦。。。下次问学长学姐吧。。。。。

20分的一天,…(⊙_⊙;)…

开心的蒟蒻

要走了好开心啊啊啊

第一题

sort和桶排不会超时,怎么想怎么来就是了

第二题

二分二分,从常州跟过来的二分

第三题

除了Floyd就不会用其他的了。。。

因为有限制,所以电流通过后就有可能会削掉,用Floyd比较一番后就好了。。。。吧?

30分的核心呵呵

请用spfa谢谢

没有第四题

国庆Day6

T1陶陶摘苹果

眼瞎忽略了0的情况

靠 样例好狠全都有0

把冒泡改成快排就满分了?!!

cu


T2替身使者

用二分做!!

把在常州学姐辛苦给我and hjj讲的全忘了w

学姐对八七!!

于是 把常州的题套进去就AC了!!

我:??????


T3电流

正解用SPFA做

我用FLoyd

0分、、、


T4行军

正解果然用DP做

hhh果断放弃

(永远推不出状态转移方程自闭了!!)

国庆Day某打卡

陶陶摘苹果

新版傲娇陶陶,只怪脑抽把sort放在了循环,嗯。很好。Σ(っ °Д °;)っ 我的100分啊。。

替身使者

鬼知道是二分做的,我一开始真没看懂题目O__O "… 啊啊啊啊啊啊啊啊。。没有骗分。。。已改。

电流(electric)

 

打完之后过样例时才知道不是弄最后连接的边的最大值,而是最大路径的最小值emmm,我可能对它有什么误解

行军

这题直接找到部分规律,就是它一次隔一条边才能遇到下一个的。so打出20.

今天能全对的自己作死,该骗分的也没有,我。emmmm

 

国庆基地校Day3

今天成绩还算可以

第一梯:就是递归+模拟,难度很低,记住要细心一点,这题处理两个人决策的优先级是重点:比如不能把必杀绝招的处理放在连续攻击后面

第二题:这题用floyd输出的时候要注意统计路上节点,最后的答案需要+2

第三题:这一题用的是最短路径,消除相同字母,我是用直接一路消下来以及两侧分支作比较,然后用最少的消除次数记录这一列,最后把所有列的消除次数比较就行了

第四题:求两串密码的最长上升公共子序列。可以用DP,用 opt1[I,j]表示以 b[j]结尾且是 a[1]-a[i]的子序列的最长公共上升序列的长度,用 opt2[I,j]表示 a[i]=b[j],且以这个数作为结尾的最长上升公共子序列的长度,转移方程如下:


1
2
opt1[I,j]=max{opt1[I-1,j],opt2[I,j]}
opt2[I,j]=max{opt1[I-1,k]+1,1}(k<j,b[k]<b[j],a[i]=b[j])

这种方法的时间复杂度为O(m∧3)

如果想优化可以记录 a[i]=a[l]中的 I,l,在转移时先提前转移 opt2[I,l],这样做就可以减小枚举 k 的范围,因为转移每一个 I,j 都
仅仅从 1 到 m 扫描了一遍。

转移方程如下:
opt1[I,j]=max{opt1[I-1,j],opt2[I,j]}
opt2[I,j]=max{opt2[I,point],opt1[I-1,k]+1,1}
(point=max{l}(a[l]=a[i]),point<k<j,b[k]<b[j],a[i]=b[j])

这题可以反复优化,寻找更好的解题方法