Codeforces Round #403 (Div. 2, based on Technocup 2017 Finals)【A,B,C】

~~翻车！翻车！~~

codeforces782A

A题：

水。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int num[100010];

int main()

{

    int n,x;

    memset(num,0,sizeof(num));

    scanf("%d",&n);

    int sum=0,ans=0;

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

    {

        scanf("%d",&x);

        if(!num[x])

        {

            num[x]++;

            sum++;

        }

        else

        {

            sum--;

            num[x]--;

        }

        ans=max(ans,sum);

    }

    printf("%d\n",ans);

    return 0;

}

codeforces782B

B题：

三分，最短时间的位置位于最大位置和最小位置区间内，而时间是咋算的？所有点到位置的max，so两边扩散，肯定是越来越大，凹形曲线，三分求极值。

PS:注意精度1e-6.

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const double eps=1e-6;

const int N=6e4+10;

struct asd{

    double x,v;

}e[N];

int n;

bool cmp(asd a,asd b)

{

    if(a.x<b.x) return true;

    return false;

}

double fun(double x)

{

    double ans=0.0;

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

        if(ans<(fabs(e[i].x-x)/e[i].v))

	        ans=(fabs(e[i].x-x)/e[i].v);

    return ans;

}

int main()

{

    scanf("%d",&n);

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

        scanf("%lf",&e[i].x);

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

        scanf("%lf",&e[i].v);

    sort(e+1,e+n+1,cmp);

    double Left=e[1].x,Right=e[n].x;

    double mid, midmid;

    double mid_value, midmid_value;

    while (Left +eps < Right)

    {

        mid = (Left + Right) / 2;

        midmid = (mid + Right) / 2;

        mid_value = fun(mid);

        midmid_value = fun(midmid);

        ///求最大值改成>= 最小值改成<=

        if (mid_value <= midmid_value) Right = midmid;

        else Left = mid;

    }

    double ans=fun(Left);

    printf("%.9lf\n",ans);

    return 0;

}

codeforces782C

C题：

利用BFS可以轻松处理。

BFS是一层一层的，对于每个结点的儿子结点，都会有一些可以使用的颜色，except（他父亲的颜色，他父亲的父亲的颜色）。

外送两个案例：

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=4e5+10;

struct asd{

    int to;

    int next;

}e[N];

int head[N],tol;

bool vis[N];

int col[N],pre[N],in[N],t;

void BFS(int pos)

{

    queue<int>q;

    memset(vis,0,sizeof(vis));

    pre[0]=pre[pos]=0;

    vis[pos]=true;

    col[pos]=1;

    t=1;

    q.push(pos);

    while(!q.empty())

    {

        int u=q.front();q.pop();

        int tmp=t;

        int num=t;

        for(int i=head[u];~i;i=e[i].next)

        {

            int v=e[i].to;

            if(vis[v]) continue;

            q.push(v);

            pre[v]=u;

            vis[v]=true;

            while(num&&(num==col[u]||num==col[pre[u]]))

                num--;

            if(num)

                col[v]=num--;

            else

                col[v]=++tmp;

        }

        t=tmp;

    }

}

void init()

{

    tol=0;

    memset(head,-1,sizeof(head));

    memset(in,0,sizeof(in));

}

void add(int u,int v)

{

    e[tol].to=v;

    e[tol].next=head[u];

    head[u]=tol++;

}

int main()

{

    int n,u,v;

    scanf("%d",&n);

    init();

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

    {

        scanf("%d%d",&u,&v);

        add(u,v);

        add(v,u);

        in[u]++;

        in[v]++;

    }

    int pos;

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

    {

        if(in[i]==1)

        {

            pos=i;

            break;

        }

    }

    BFS(pos);

    int ans=0;

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

        ans=max(ans,col[i]);

    printf("%d\n",ans);

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

        printf("%d ",col[i]);

    return 0;

}

巴特西

Codeforces Round #403 (Div. 2, based on Technocup 2017 Finals)【A,B,C】

最新文章

热门文章