常州Day7心得

今天好惨第一题才20分

通过晚上的不断改进，终于AC了

爽

题1:

首先，我们把每一公里的限速都存入t[]中

再把每一公里的限速与车速比较

用s记录车的超速情况

最后输出s就行了

正确代码如下：


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
<span class="hljs-preprocessor">#<span class="hljs-keyword">include</span>&lt;bits/stdc++.h&gt;</span>

<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;

<span class="hljs-keyword">int</span> main(){

    freopen(<span class="hljs-string">"speeding.in"</span>,<span class="hljs-string">"r"</span>,stdin);

    freopen(<span class="hljs-string">"speeding.out"</span>,<span class="hljs-string">"w"</span>,stdout);

    <span class="hljs-keyword">int</span> n,m;

    <span class="hljs-built_in">cin</span>&gt;&gt;n&gt;&gt;m;

    <span class="hljs-keyword">int</span> l,w,d,v,i1=<span class="hljs-number">0</span>;

    <span class="hljs-keyword">int</span> t[<span class="hljs-number">101</span>],s=<span class="hljs-number">0</span>;

    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;n;i++){

        <span class="hljs-built_in">cin</span>&gt;&gt;l&gt;&gt;w;

        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">0</span>;j&lt;l;j++) t[i1++]=w;

    }

    i1=<span class="hljs-number">0</span>;

    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;m;i++){

        <span class="hljs-built_in">cin</span>&gt;&gt;d&gt;&gt;v;

        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">0</span>;j&lt;d;j++){

            <span class="hljs-keyword">if</span>(v&gt;t[i1]) s=max(s,v-t[i1]);

            i1++;

        }

    }

    <span class="hljs-built_in">cout</span>&lt;&lt;s&lt;&lt;endl;

    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;

}

今天还讲了背包问题

0/1背包：

只考虑动态规划和前 i 件物品，放入大小不超过 j 的背包，所能获得的最大价值

再考虑最后一件物品是否选择

状态转移方程：F[i,j] = max{F[i−1,j],F[i−1,j−Ci]+Wi}

核心代码：

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

for(j=v;j>=1;j--)

f[j]=max(f[j],f[j-c[i]]+w[i]);

常州8.19

T1 超速行驶

一段100米的路，每部分都有不同的限速，按照给的速度走，最多超速多少。

只有100米！！！！！一米一米模拟就能过！！

我的代码大概最多得运算300次。。哈哈哈。。。

也不用担心爆空间！！啦啦啦。。。

T2 选数

有N个数，从中选K个，两两差值的绝对值的最小为S，最大化这个S。。

我想用二分，就先排了序，取头尾、中间，使两两差值最大。。。

但是。。

我小数据都能过（虽然我只测了10以内。。），大的过不了。。。找bug中。。。

T3 生日礼物

一个较（hen）抠的人想在一段彩带中找到最短还包括所有种类珠子的一部分。。。

考试的时候想用DP，用f[i][j]表示从i坐标到j齐全的最短长度，，

方程推到一半卡住了。。。。

结果。。。

标程又是二分？？

是先排了序，再把边界调整。

T4 最长上升子序列

还是二分！！！

我以为用之前的最长不下降子序列改改就好了，但是这题操作好多，暴力都打不出来。。

而且投诉一下，这两天的标程都好难懂，改不出来。。。

嬉戏谷旅游day7

第一题把每一公里的速度和限速都读进来

然后把超限最大的输出去就好了

第二题二分，从小到大排序后，扫一遍验证能否符合即可。

第三题将所有的彩珠按照所在位置排序成一个新的序列，二分珠子的个数进行验证，每次验证可以将新序列从头扫到尾为N。

第四题本以为打个dp然后把两种情况弄进去就好了其实就是先将整个操作建成一棵树然后DFS二分求长上升子序列的长度就好了

超速行驶（speeding）

认真看一下数据，嗯嗯，空间开一维，开到101就行了
N≤100，So时间是 O(n³) 都没问题~

想都不要想，直接暴力！
上代码:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<cmath>

#include<queue>

#include<algorithm>

#include<cstdlib>

#include<bits/stdc++.h>

using namespace std;

int f[101],h[101];

int main()

{

    freopen("speeding.in","r",stdin);

    freopen("speeding.out","w",stdout);

    

    int n,m;

    int l,w,d,v;

    int k=0,p=1,t=0;

    cin>>n>>m;

    

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

    {

        cin>>l>>w;

        k+=l;

        for(int j=p;j<=k;j++)

            f[j]=w;

        p=k+1;

    }

    

    k=0;

    p=1;

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

    {

        cin>>d>>v;

        k+=d;

        for(int j=p;j<=k;j++)

            h[j]=v;

        p=k+1;

    }

    

    for(int i=1;i<=100;i++)

    {

        if(h[i]>f[i]) t=max(t,h[i]-f[i]);

    }

    

    cout<<t;

    



    return 0;

}

开两个数组，一个储存公路上的限速，一个储存司机的速度；之后比较，如果超过限速，就记录。

over~
再见！

常州研学

第一题超速行驶

这题我考试ing 想着一段一段比较，一个数一个数比较，发现超速就储存下来。再打擂台，明明过了好多样例，但还是爆零了.

正解：这题数据比较小，可以一米一米做。(这明明跟我的差不多，为什么我错了）

第二题选数

这题我是先排序，然后用贪心的办法，明明样例也对了，为什么我又爆零。

第三题生日礼物

这题，我暴力搜索，把每种珠子齐全的情况都找齐了，再比较。结果时间超限了！！！

第四题最长上升子序列

这题我用模拟，直接根据题目做了。就是分别考虑两种情况，然后第一个数为零时，再考虑之前的是零还是一，判断队列是否要清空。明明我刷了好多数据了都对了，why还错啊！！！！！！

这题的正确解法是二分。

常州嬉戏谷欢乐游DAY 7

今天的第一题有点水但我中间少考虑了才90······

第一题基本就是一段一段的地读进来，存进限速的数组里。然后照样搬着读进来车的速度，最后慢慢比较，当有超速的时候比较超过多少，最后输出最大超出了多少。

还有一种是一段一段比较，把多的一段删掉当成下一段进行处理，但会比较麻烦，而且要多考虑几种情况。所以慢慢模拟基本做得出来，而且数据也比较小~~~~

第二题二分查找，首先将读入进来的数排序，当一个数能被选的时候进行二分，不断调整上边界和下边界，最后输出下边界的值就行了。

第三题还不太懂，考场上准备贪心，打出来了发现只过了样例，于是开始暴力。正解：将所有的彩珠按照所在位置排序成一个新的序列，二分珠子的个数（直接二分长度可能会超时）进行验证，每次验证可以将新序列从头扫到尾为N，二分复杂度<=20，O（20*N）并不会超时。

第四题我依旧暴力DP，当0的时候很好算，数字加进去DP，等于1时数组清空到后面的数值，继续重复，但还是打不出来，而且每一次都DP效率好像很低。题解是二分法求最长上升子序列的长度，然后递归恢复，将这一过程建成一棵树，于是我又爆了

懒癌

所以：

题目：

题目描述

有N段道路，第i段长度为L[i]米，速度限制为W[i]，道路总长100米。新司机小W依次行驶过这N段道路，整个行驶过程中，他分为M段开：依次以V[j]的速度开了D[j]米，现在请问整个行驶过程中有没有发生过超速？如果有，超速最严重的时候超速了多少？

输入

第一行包含两个整数N和M；
接下来N行，每行两个整数L[i] 和 W[i]。
接下来M行，每行两个整数D[j]和V[j]。

输出

输出一个整数，表示超速最严重的时候超速了多少，如果从未超速，输出0。

样例输入

样例输出

代码：


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

int a[105],b[105],c[105],d[105],n,m,i,j,k=0,l=0,ma=0;

int main()

{

    freopen("speeding.in","r",stdin);

    freopen("speeding.out","w",stdout);

    cin>>n>>m;

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

        cin>>a[i]>>b[i];

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

        cin>>c[i]>>d[i];

    i=1;

    j=1;

    while(i!=n+1&&j!=m+1)

    {

        if(a[i]>c[j])

        {

            ma=d[j]-b[i];

            a[i]=a[i]-c[j];

            j++;

        }

        else

        if(a[i]==c[j])

        {

            ma=d[j]-b[i];

            j++;

            i++;

        }

        else

        if(c[j]>a[i])

        {

            ma=d[j]-b[i];

            c[j]=c[j]-a[i];

            i++;

        }

        if(ma>k)        

            k=ma;

    }

    if(k<=0)

        cout<<0;

    else

        cout<<k;

    

    

    return 0;

}

水啦~~~~~~~~~~~~~

第一题

非常简单的模拟

第二题

二分，从大到小排一遍，然后扫一遍；

第三题

暴力可以得一些分，抄个题解：

将所有的彩珠按照所在位置排序成一个新的序列，二分珠子的个数（直接二分长度可能会超时）进行验证，每次验证可以将新序列从头扫到尾为N，二分复杂度<=20，O（20*N）并不会超时。

第四题

模拟+dp应该吧，感觉会超时

超速行驶

http://59.61.214.20:3001/oj/#main/show/2702

将一段100m的路分成n段，每段有自己的限速；（交通规定）

将一段100m的路分成m段，每段用一定的速度；（司机）

本题可以直接模拟道路，循环判断超速；

#include<bits/stdc++.h>
using namespace std;
int l[101],w[101],d[101],v[101],x,y,u=1,uu=1;
int main()
{
freopen("speeding.in","r",stdin)；
freopen("speeding.out","w",stdout)；
int n,m,ans=0;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>l[i]>>w[i];
for(int j=1;j<=m;j++)cin>>d[j]>>v[j];
for(int i=1;i<=100;i++) { if(i>x&&i<=l[u]+x&&i>y&&i<=d[uu]+y) { ans=max(ans,v[uu]-w[u]); } if(i+1>x+l[u])
{
x+=l[u];
u++;
}
if(i+1>y+d[uu])
{
y+=d[uu];
uu++;
}
if(u==n+1&&uu==m+1)break;
}
cout<<ans;
return 0;
}

超速行驶

题目描述

呃。。。这题没AC只有60分。

我是直接暴力，因为只有100米，所以我就将每一米的速度枚举出来，再相减，求出最大的，输出答案。

AC代码：


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>

using namespace std;

int n,m;

int w[105],v[105],d[105],l[105];

int s[105],x[105],ans[105];

int t=1;

int main()

{

    //freopen("speeding.in","r",stdin);

    //freopen("speeding.out","w",stdout);

    cin>>n>>m;

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

   {

       cin>>l[i]>>w[i];

   }

    for(int i=1;i<=m;i++)

   {

       cin>>d[i]>>v[i];

   }

   for (int i=1,p=0; i<=n; i++)

       for (int j=1; j<=l[i]; j++)

    s[++p]=w[i]; 

   for (int i=1,p=0; i<=m;i++)

       for (int j=1; j<=d[i]; j++)

    x[++p]=v[i];

   for(int i=1;i<=100;i++)

   {

       ans[i]=x[i]-s[i];

       //cout<<ans[i]<<" ";

   }

   sort(ans,ans+101);

   if(ans[100]<=0)

   {

       cout<<"0";

   }

   else

   cout<<ans[100];

    return 0;

}

分类：训练日志

常州Day7心得

常州8.19

嬉戏谷旅游day7

超速行驶（speeding）

常州研学

常州嬉戏谷欢乐游DAY 7

超速行驶

懒癌

超速行驶 _{(File IO): input:speeding.in output:speeding.out}

题目描述

输入

输出

样例输入

样例输出

水啦~~~~~~~~~~~~~

嬉戏谷旅游Day 7

第一题

第二题

第三题

第四题

超速行驶

超速行驶

题目描述

懒癌

超速行驶 (File IO): input:speeding.in output:speeding.out

题目描述

输入

输出

样例输入

样例输出

水啦~~~~~~~~~~~~~

第一题

第二题

第三题

第四题

题目描述

超速行驶 _{(File IO): input:speeding.in output:speeding.out}