2019.2.23签到

油滴扩展满分代码:


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
54
55
56
57
58
59
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int box[10];
double r[10],a[10],b[10];
double s,ans,n,le,ri,dw,up,x,y,x_,y_;
bool v[10];
double max(double A,double B)
{
    return A>B?A:B;
}
double min(double A,double B)
{
    return A<B?A:B;
}
void dfs(int k)
{
    if(k>n)
    {
        s=abs(x-x_)*abs(y-y_);
        memset(r,0x3f,sizeof(r));
        for(int i=1;i<=n;i++)
        {
            r[box[i]]=min( min(up-b[box[i]],b[box[i]]-dw) , min(ri-a[box[i]],a[box[i]]-le) );
            for(int j=1;j<i;j++)
            {
                double lena=abs(a[box[i]]-a[box[j]]),lenb=abs(b[box[i]]-b[box[j]]);
                double dis=sqrt(lena*lena+lenb*lenb);
                r[box[i]]=min(r[box[i]], max(dis-r[box[j]],0) );
            }
            s-=3.1415926*r[box[i]]*r[box[i]];
        }
        ans=min(ans,s);
        return;
    }
    for(int i=1;i<=n;i++)
        if(!v[i])
        {
            v[i]=1;
            box[k]=i;
            dfs(k+1);
            v[i]=0;
        }
}
int main()
{
    cin>>n>>x>>y>>x_>>y_;
    ans=0x3f3f3f3f;
    le=min(x,x_);
    ri=max(x,x_);
    dw=min(y,y_);
    up=max(y,y_);
    for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i];
    dfs(1);
    cout<<(int)round(ans);
}

之前错在圆周率取3.14159太少位了,改成3.1415926后pass。

2019.2.14签到

“垃圾陷阱”满分代码:


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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct suit{
    int time,life,high;
}a[100000];
int cmp(suit x,suit y)
{
    return x.time<y.time;
}
int f[1000][1000];
int h,n,ans;
int main()
{
    memset(f,-0x3f,sizeof(f));
    for(int i=0;i<=h;i++)
        f[0][i]=10;
    cin>>h>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].time>>a[i].life>>a[i].high;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=h;j++)
        {
            if(j<a[i].high)
            {
                if(f[i-1][j]>=a[i].time)
                    f[i][j]=f[i-1][j]+a[i].life;
            }
            else
            {
                if(f[i-1][j]>=a[i].time)
                    f[i][j]=f[i-1][j]+a[i].life;
                if(f[i-1][j-a[i].high]>=a[i].time)
                    f[i][j]=max(f[i][j],f[i-1][j-a[i].high]);
            }
            ans=max(ans,f[i][j]);
        }
        if(f[i][h]>=0)
        {
            cout<<a[i].time;
            return 0;
        }
    }
    cout<<ans;
}

一开始,我把生命持续时间作为f[i][j]中的j,因为当前垃圾堆叠的高度更像和最终答案有关系,但这样没必要的循环出现了。题解告诉我把垃圾堆叠的高度作为j,这扩宽了我的思维——做DP题陷入困境时,大胆更换状态。毕竟“小Y包汤圆”状态都那么奇怪了,DP题还有什么状态不能出现呢?

剩下的时间在改错题,可惜,学长没看出来哪里错。

2019.2.13签到

“关路灯”在题解的启迪下通过了,下面是代码:


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
#include<cstdio>
#include<cstring>
#include<iostream>
#define le 0
#define ri 1
int x[100],w[100],f[100][100][2],s[100];
int n,u;
using namespace std;
int main()
{
    memset(f,0x3f,sizeof(f));
    cin>>n>>u;
    f[u][u][le]=f[u][u][ri]=0;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>w[i];
        s[i]=s[i-1]+w[i];
    }
    for(int len=2;len<=n;len++)
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            f[i][j][le]=min(f[i+1][j][le]+(x[i+1]-x[i])*(s[i]+s[n]-s[j]),
            f[i+1][j][ri]+(x[j]-x[i])*(s[i]+s[n]-s[j]));
            f[i][j][ri]=min(f[i][j-1][le]+(x[j]-x[i])*(s[i-1]+s[n]-s[j-1]),
            f[i][j-1][ri]+(x[j]-x[j-1])*(s[i-1]+s[n]-s[j-1]));
        }
    cout<<min(f[1][n][le],f[1][n][ri]);
}

这是“油滴扩展”70分代码,没找到哪里错,搁置着(我心里很难受)。


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
54
55
56
57
58
59
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int box[10];
float r[10],a[10],b[10];
float s,ans,n,le,ri,dw,up,x,y,x_,y_;
bool v[10];
float max(float A,float B)
{
    return A>B?A:B;
}
float min(float A,float B)
{
    return A<B?A:B;
}
void dfs(int k)
{
    if(k>n)
    {
        s=abs(x-x_)*abs(y-y_);
        memset(r,0x3f,sizeof(r));
        for(int i=1;i<=n;i++)
        {
            r[box[i]]=min( min(up-b[box[i]],b[box[i]]-dw) , min(ri-a[box[i]],a[box[i]]-le) );
            for(int j=1;j<i;j++)
            {
                float lena=abs(a[box[i]]-a[box[j]]),lenb=abs(b[box[i]]-b[box[j]]);
                float dis=sqrt(lena*lena+lenb*lenb);
                r[box[i]]=min(r[box[i]], max(dis-r[box[j]],0) );
            }
            s-=3.14159*r[box[i]]*r[box[i]];
        }
        ans=min(ans,s);
        return;
    }
    for(int i=1;i<=n;i++)
        if(!v[i])
        {
            v[i]=1;
            box[k]=i;
            dfs(k+1);
            v[i]=0;
        }
}
int main()
{
    cin>>n>>x>>y>>x_>>y_;
    ans=0x3f3f3f3f;
    le=min(x,x_);
    ri=max(x,x_);
    dw=min(y,y_);
    up=max(y,y_);
    for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i];
    dfs(1);
    cout<<round(ans);
}

2.13

P1111 修复公路


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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int f[100005],n;
struct node{
    int x,y,t;
}p[100005];
int cmp(node i,node j)
{
    return i.t<j.t;
}
int find(int w)
{
    if(f[w]==w){
        return f[w];
    }
    else{
        return find(f[w]);
    }
}
int hb(int p1,int q1)
{
    int p,q;
    p=find(p1);
    q=find(q1);
    if(f[p]!=q){
        f[p]=q;
        n--;
    }
}
int main()
{
    int k,i,j,m;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        f[i]=i;
    }
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].t);
    }
    sort(p+1,p+m+1,cmp);
    for(i=1;i<=m;i++){
        hb(p[i].x,p[i].y);
        if(n==1){
            printf("%d",p[i].t);
            return 0;
        }
    }
    printf("-1");
    return 0;
}

2019.2.12签到

一个晚上在打“小木棍”这道题,最后得了21分。老师说要把代码贴在这儿,贴一块错误代码,实在没啥意思,但是深夜将至,这题只能搁置,签到在此明示。每天问学长一题,打勾。


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
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int cmp(int a,int b)
{
    return a>b;
}
int v[101],a[101];
int n,s,f,ans;
void dfs(int k,int p,int lentry,int l)
{
    if(ans||lentry>l)
        return;
    if(lentry==l)
    {
        p++;
        lentry=0;
    }
    if(k>n&&lentry==0)
    {
        ans=l;
        return;
    }
    if(k>n&&lentry)
        return;
    for(int j=1;j<=n;j++)
        if(!v[j])
        {
            v[j]=1;
            dfs(k+1,p,lentry+a[j],l);
            v[j]=0;
        }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s+=a[i];
        f=max(f,a[i]);
    }
    sort(a+1,a+1+n,cmp);
    for(int i=f;i<=s;i++)
        if(s%i==0)
            dfs(1,1,0,i);
    cout<<ans;
}

20190129&小总结

blog似乎迟到了,但它并没有缺席。
T1混合牛奶
不想说了。

T2修理牛棚
第一次看题:好像很难的样子。
第二次看题:并不难。
思路是将每一段连续的没有牛的牛棚的个数求出存入数组a,排序后,有牛的牛棚的总数加上a的前(连续的没有牛的牛棚的段数-m+1)个元素即为所求。

T3
不想改。
这题和day4的城堡挺像的,不过这次是直接输入迷宫的地图。
估计又是读入炸了。不炸不要紧,一炸炸三次。
从迷宫的两个出口往迷宫里面BFS,然后注意在搜索过程中在每个点都要取最小步数。然后扫一遍数组找出最大值即为所求。

T4
不想改,这题也挺麻烦的。
我的思路:读入坐标和邻接矩阵(可以用%1d读入)后利用勾股定理可以求出路的长度,再利用并查集求牧区,然后枚举要连边的两个点(这两个点不能在同一个牧区),Floyd求这两个点所在牧区的“直径”。

这几天主要学的是图论算法。
1最短路算法:Floyd Dijkstra Bellman-Ford SPFA
(我到现在还不会打Bellman-Ford。)
2并查集和最小生成树的Kruskal算法。
3欧拉图、欧拉回路、欧拉路径。

因为没有考DP,所以我这几天考试的考得都还行。
这几天考试的主要问题:
1读入;
2题意理解。