分类：训练日志

国庆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分的一天，…(⊙＿⊙；)…

国庆Day6

T1陶陶摘苹果

眼瞎忽略了0的情况

靠 样例好狠全都有0

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

cu

T2替身使者

用二分做!!

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

学姐对八七!!

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

我:??????

T3电流

正解用SPFA做

我用FLoyd

0分、、、

T4行军

正解果然用DP做

hhh果断放弃

（永远推不出状态转移方程自闭了!!）

开心的蒟蒻

要走了好开心啊啊啊

第一题

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

第二题

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

第三题

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

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

30分的核心呵呵

请用spfa谢谢

没有第四题

国庆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])

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

国庆嗨皮day3

第1题递归+模拟，难度超低只不过要细心一点哈注意处理两个人决策的优先级：比如不

能把必杀绝招的处理放在连续攻击后面

第2题直接 floyd输出的时候统计路上节点即可就是注意一点 .. 答案要+2

第3题将地图中相邻且相同的点距离为 0，不相同为 1，然后建立两个假点，源点 s 和最

上面一排所有点相连，距离为 0；同样的，汇点 t和最下面一排所有点相连，距离也为

0；接下来就是求 s 到 t 的最短路 ans，输出 ans+1 即为答案。

第4题

就是求两个序列的最长上升公共子序列，而对于求最长公

共子序列和最长上升序列这两个动态规划的基础模型，我们已经十分熟悉。因

此本题可以考虑在经典问题的经典解法的基础上进行改动，于是我们想到，可

以先求两个序列的最长公共序列，再对其求最长上升序列，即为答案。

转移方程如下：

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])

国庆10.5

T1 World

一个世界中互杀。。。刷样例30。。。。

正解是递归+模拟只不过要细心一点哈？？？奈何我连题目都没看懂？？

T2 City

计算所有能从景点u到景点v的最短路径上的景点数量的和。。。。

直接 floyd。输出的时候统计路上节点即可。。。。。就是注意答案要+2，加上起点和终点两个点。。。统计如下。。

for(int j=1;j<=n;j++)

for(int j=1;j<=n;j++)

if(f[a][j]+f[j][b]==f[a][b]) sum++;

考试时floyd打出来了，不知道怎么统计。。爆零了。。。

T3 Game

相同字母可以一次性全部消除，清除出一条从上到下的道路，求最少的点击次数。。。

最短路模版题，但我没见过。。。

T4 Password

求两串密码的最长上升公共子序列。。。我用DP，用f[i][j]表示a串前i个字母和b串前j个字母中最长上升公共子序列，40分的核代如下。。

for(i=1;i<=l;i++)

for(j=1;j<=r;j++)

if(f[i][j]&&(a[jl]<a[i]||f[i-1][j-1]==0))

{

f[i][j]=f[i-1][j-1]+1;

jl=i;

}

else f[i][j]=max(f[i-1][j],f[i][j-1]);

printf("%d\n",f[l][r]);

求教。。。。

70分的一天，Ծ‸ Ծ