8.21

0 最小比例

求边权和点权值的最小比例,由于数据过小,暴力枚举即可。

2 空间航行

“如何从起点到终点时间最少呢。因为有一些星球可以当做另一个跳板可以跳去其他星球,当然,这个跳板是有优势的。从这个星球可以无视时间直接过一条这个星球的直径,那么,就大致可观为求最短路径,把起点和终点加入各个星球行列中,不管是弗洛伊德还是superfather还是迪杰斯塔拉还是什么,算出来就可以啦!”

1和3还没改完,没有后续。

8.20

0 旅游

考试的时候想到选择不同的起点会有不同的结果所以果断不会,打了一个小贪心预估10分,结果90分。

1 做梦

做梦呢,不会。

2 数数

欧几里得?谁啊。

另:考试时由于没网且网页莫名刷新导致后两题题目丢失导致连暴力都打不了。

【2019.8.20】纪中集训Day20

后天就能回家了先让我开心一会

T1:travel

今天唯一改得出的题了

大意:有一堆景点,给出坐标(x,y),观赏时间b,美观度a

从一个景点到另一个景点,耗时为两点间曼哈顿距离

要求游览的一串景点美观度严格递增,求最长观赏时间

  • 将每个点用结构体存储,按照美观度sort一波
  • 我们可以很容易得到一个不太优秀的dp式:f[i]=max(f[i],f[j]+abs(x[i]-x[j])+abs(y[i]-y[j]))(i<j)
  • 显然超时,所以我们考虑做个优化:省去j的循环?暂时不考虑abs,则f[i]=(f[j]-x[j]-y[j])+(x[i]+y[i]),所以我们需要的值只有前半部分与j有关的
  • 由于不知道i、j坐标的大小情况,所以我们需要分别保存f[j]+x[j]+y[j]、f[j]+x[j]-y[j]、f[j]-x[j]+y[j]、f[j]-x[j]-y[j]的最大值。如果x[i]>x[j],则x[i]-x[j]>x[j]-x[i],包含x[j]-x[i]的值一定会被包含x[i]-x[j]代替,这样就不需要特别判断i,j的坐标大小
  • O(n*m)完美a掉

1
2
3
4
5
6
7
8
9
10
11
for(i=bi;i<=t;i++)
{
    if(q[i].a!=q[i-1].a)
    {
        x[0]=y[0];x[1]=y[1];x[2]=y[2];x[3]=y[3];
        y[0]=y[1]=y[2]=y[3]=0;
    }
    f[i]=max(max(x[0]-q[i].x-q[i].y,x[1]-q[i].x+q[i].y),max(x[2]+q[i].x-q[i].y,x[3]+q[i].x+q[i].y))+q[i].b;
    mmp(i);//独家函数名大家千万不要模仿
    ans=Max(ans,f[i]);
}

1
2
3
4
5
6
7
void mmp(int i)
{
    y[0]=max(y[0],f[i]+q[i].x+q[i].y);
    y[1]=max(y[1],f[i]+q[i].x-q[i].y);
    y[2]=max(y[2],f[i]-q[i].x+q[i].y);
    y[3]=max(y[3],f[i]-q[i].x-q[i].y);
}

T2:dream

只会n^2的算法哭哭

T3:count

神踏马的类欧几里得

https://blog.csdn.net/cold_chair/article/details/78847930 某大佬题解

https://blog.csdn.net/WorldWide_D/article/details/54730588 类欧几里得证明

20190820_常州DAY10&小总结

题目我记得不太清楚,随便写点。

T2鸡腿の名单
题意:一个字符串可以无限次反转偶数位的前缀,在这个过程中,所有得到字符串是等价的。问去掉所有等价的字符串,还有多少字符串。
考场思路:先打暴搜,然后发现连N=20的情况都跑不出来,那就开始骗分!把每个字符串的字符从小到大排序,排完的有一样就删掉。(当然这是不对的)
伪题解:对于长度为奇数的字符串,先在末尾加上一个小写字母以外的字符。然后两个为一组,需用字符串hash。

T3鸡腿の骑士
题意:在一个h*w的矩阵中,一个骑士可以向(±a,±b)(±b,±a)八个方向移动。求它可以移动到的格子个数。
考场思路:宽搜。过了N<=100的数据。
不完整题解:预处理,如果a和b的最大公约数x比1大,那就h=h/x+1;w=w/x+1;a/=x;b/=x.
然后a和b有两种情况:一奇一偶;两个奇数。
分别处理即可。(其实我不怎么懂怎么处理,这才是最关键的)
接下来的处理建立在能向同一个方向走两步的基础上。(如果不能,它的w或h必定在20以内,那就搜索)
对于两个奇数的情况,它走不到偶数的格子。
对于一奇一偶,这个还不会。

小总结:

继续阅读20190820_常州DAY10&小总结

常州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]);