8月11日 2018百度之星初赛 (A)
题目链接:http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=825

1001 – 度度熊拼三角

思路:
我们将木棒长度排序之后,可以发现我们要选的三根木棒一定是连续的,因为连续了才最优嘛。于是我们扫一遍,碰到符合要求的就记录下答案。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#define MAXN 1005
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n, a[MAXN], ans;

vector<int> vec;

bool check(int x)
{
    if(a[x]>=a[x-1]+a[x-2]) return false;
    return true;
}

int main()
{
    while(scanf("%d", &n)!=EOF)
    {
        ans=-1;
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        sort(a+1, a+n+1);
        for(int i=n; i>=3; i--)
            if(check(i))
            {
                ans=a[i]+a[i-1]+a[i-2];
                break;
            }
        printf("%d\n", ans);
    }
}

1002 – 度度熊学队列

思路:
神TM,我以为区间翻转要splay。。。像我这么菜不会splay,于是比赛是就弃掉这题了。。

看题解说用双向链表模拟,突然醒悟过来,于是码了一发。其中有很多细节要注意,特别是指针什么的。但码完后发现区间翻转并不是O(1)的,复杂度也并没有保证,数据强一点就会卡掉,O(1)的区间翻转我不知道到底怎么写QWQ,哪位大佬教一下啊。。

虽然复杂度没有保证,但还是A了,可能是数据水吧。。

代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#define MAXN 1500005
using namespace std;

void read(int &x)
{
    char ch = getchar(); x = 0;
    for (; ch < '0' || ch > '9'; ch = getchar());
    for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}

int n, Q;

struct Link
{
    int val;
    Link *nxt, *pre;
} *head[MAXN], *tail[MAXN];

int main()
{
    while(scanf("%d%d", &n, &Q)!=EOF)
    {
        for(int i=1; i<=n; i++) tail[i]=head[i]=NULL;
        for(int i=1; i<=Q; i++)
        {
            int op, u, v, w, val;
            read(op);
            if(op==1)
            {
                read(u); read(w); read(val);
                Link *temp=new Link;
                temp->val=val;
                if(w==0)
                {
                    if(!head[u])
                    {
                        temp->pre=temp->nxt=NULL;
                        head[u]=tail[u]=temp;
                    }
                    else
                    {
                        temp->nxt=head[u];
                        temp->pre=NULL;
                        head[u]->pre=temp;
                        head[u]=temp;
                    }
                }
                else
                {
                    if(!tail[u])
                    {
                        temp->pre=temp->nxt=NULL;
                        head[u]=tail[u]=temp;
                    }
                    else
                    {
                        temp->nxt=NULL;
                        temp->pre=tail[u];
                        tail[u]->nxt=temp;
                        tail[u]=temp;
                    }
                }
            }
            if(op==2)
            {
                read(u); read(w);
                if(w==0)
                {
                    if(!head[u]) printf("-1\n");
                    else
                    {
                        printf("%d\n", head[u]->val);
                        if(head[u]!=tail[u])
                        {
                            head[u]=head[u]->nxt;
                            free(head[u]->pre);
                            head[u]->pre=NULL;
                        }
                        else free(head[u]), tail[u]=head[u]=NULL;
                    }
                }
                else
                {
                    if(!tail[u]) printf("-1\n");
                    else
                    {
                        printf("%d\n", tail[u]->val);
                        if(head[u]!=tail[u])
                        {
                            tail[u]=tail[u]->pre;
                            free(tail[u]->nxt);
                            tail[u]->nxt=NULL;
                        }
                        else free(tail[u]), tail[u]=head[u]=NULL;
                    }
                }
            }
            if(op==3)
            {
                read(u); read(v); read(w);
                if(!tail[v]) continue;
                if(w)
                {
                    Link *temp=head[v];
                    while(temp)
                    {
                        swap(temp->pre, temp->nxt);
                        temp=temp->pre;
                    }
                    swap(head[v], tail[v]);
                }
                if(tail[u])
                {
                    head[v]->pre=tail[u];
                    tail[u]->nxt=head[v];
                }
                else head[u]=head[v];
                tail[u]=tail[v];
                head[v]=tail[v]=NULL;
            }
        }
    }
}

1003 – 度度熊剪纸条

思路:
首先头和尾的两段1(如果存在的话)把他们剪出来只需要一刀。中间部分的一段1剪出来需要两刀,但是有一点要注意,就是最后你可以少剪一刀。所以把每一段的代价和贡献都记录一下,最后跑一个背包就好了。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define MAXN 1000005
using namespace std;

int n, k, a[MAXN], f[MAXN];

struct B {int val, cost;} b[MAXN];

int main()
{
    while(scanf("%d%d", &n, &k)!=EOF)
    {
        int head, tail, cnt=0, tot=0;
        memset(f, 0, sizeof(f));
        memset(a, 0, sizeof(a));
        for(int i=1; i<=n; i++) scanf("%1d", &a[i]);
        for(head=1; a[head]; head++) ;
        if(head!=1) b[++tot].val=head-1, b[tot].cost=1;
        for(tail=n; a[tail]; tail--) ;
        if(tail!=n && tail!=0) b[++tot].val=n-tail, b[tot].cost=1;
        for(int i=head; i<=tail; i++)
        {
            if(a[i]==0 && cnt)
            {
                b[++tot].val=cnt;
                b[tot].cost=2;
                cnt=0;
            }
            if(a[i]==1) cnt++;
        }
        if(k==0) {printf("%d\n", head-1); continue;}
        for(int i=1; i<=tot; i++)
            for(int j=k+1; j>=b[i].cost; j--) f[j]=max(f[j], f[j-b[i].cost]+b[i].val);
        printf("%d\n", f[k+1]);
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注