7月7号 Codeforces Round #495
题目链接:http://codeforces.com/contest/1004

A – Sonya and Hotels

过水,不多说。

B – Sonya and Exhibition

思路:
神仙题!!!我做完E题才想到。。。

千万不要想多了,就是0101010101…直接输出就好了,因为这样就可以保证任意一个序列中0和1的差最多相差1。也就保证了和最大。
代码:

#include <bits/stdc++.h>
#define MAXN 1005
#define LL long long
using namespace std;

int n, m;
struct A {int l, r;} a[MAXN];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++) scanf("%d%d", &a[i].l, &a[i].r);
    for(int i=1; i<=n; i++)
    {
        if(i&1) printf("1");
        else printf("0");
    }
}

C – Sonya and Robots

思路:
就是求每个数之前有多少个不一样的数。记录每一个数上一次出现位置,从后向前扫,设num为之前有多少个不一样的数。如果上一次出现位置为0(也就是之前没有这个数)那么num–。

然后对于每个数最后的位置求一个num的和就好了。
代码:

#include <bits/stdc++.h>
#define MAXN 100005
#define LL long long
using namespace std;

int n, a[MAXN], vis[MAXN], last[MAXN], pos[MAXN], num;
LL ans;

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
        last[i]=pos[a[i]];
        if(pos[a[i]]==0) num++;
        pos[a[i]]=i;
    }
    for(int i=n; i>=1; i--)
    {
        if(!last[i]) num--;
        if(pos[a[i]]!=i) continue;
        ans+=num;
    }
    printf("%lld\n", ans);
}

D – Sonya and Matrix

思路:
比较难的一题。我们可以知道最大的数一定是在最角落,所以我们定义a为左上角的数,b为左下角的数。然后我们可以根据数量推出x的值,通过暴力枚举枚举出n,m的值。

知道了这些后我们就可以推出n, m, x, y, a, b。进而确定矩形,然后check一下这个矩形是否符合要求,如果符合直接输出,结束。
代码:

#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;

int t, temp, n, m, x, y, b, num[MAXN], cnt[MAXN];

void solve(int n, int m, int x, int y)
{
    memset(cnt, 0, sizeof(cnt));
    y=n+m-x-b;
    if(x<0 || x>n || y<0 || y>m) return;
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++)
    {
        int dis=abs(x-i)+abs(y-j);
        cnt[dis]++;
    }
    for(int i=1; i<=b; i++) if(cnt[i]!=num[i]) return;
    printf("%d %d\n%d %d\n", n, m, x, y);
    exit(0);
}


int main()
{
    scanf("%d", &t);
    for(int i=1; i<=t; i++)
    {
        scanf("%d", &temp);
        num[temp]++;
        b=max(b, temp);
    }
    if(num[0]!=1) {printf("-1\n"); return 0;}
    for(x=1; x*4==num[x]; x++) ;
    for(int i=1; i*i<=t; i++)
    {
        if(t%i) continue;
        solve(i, t/i, x, b);
        solve(t/i, i, x, b);
    }
    printf("-1\n");
}

E – Sonya and Ice Cream

思路:
相对于E题比较水吧。。。没有什么思维含量,就是码量大。。

和NOIP那道树网的核差不多,路径一定是在数的直径上,在直径上$O(n)$枚举路径,$O(1)$确定最远距离,用这个最远距离更新答案就好了。
代码:

#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;

int n, k, maxlen, maxdis, root, l, r, cnt, head[MAXN], son1[MAXN], son2[MAXN], dis[MAXN], tag[MAXN], vis1[MAXN], vis2[MAXN];

struct Edge {int next, to, dis;} edge[MAXN*2];

void addedge(int x, int y, int z)
{
    edge[++cnt].next=head[x];
    edge[cnt].to=y;
    edge[cnt].dis=z;
    head[x]=cnt;
}

int findline(int x, int fa)
{
    int len1=0, len2=0;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        int len=findline(to, x)+edge[i].dis;
        if(len>=len2) len2=len, son2[x]=i;
        if(len2>len1) swap(len2, len1), swap(son1[x], son2[x]);
    }
    if(len1+len2>maxlen) maxlen=len1+len2, root=x;
    return len1;
}

void finddis(int x, int fa)
{
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa || tag[to]) continue;
        finddis(to, x);
        dis[x]=max(dis[x], edge[i].dis+dis[to]);
    }
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(!tag[to] || to==fa) continue; 
        finddis(to, x);
    }
    maxdis=max(maxdis, dis[x]);
}

int solve(int l, int r)
{
    int ans=1e9, ldis=0, rdis=maxlen, x=l, y=l;
    for(int i=1; i<k; i++)
    {
        for(int j=head[y]; j; j=edge[j].next)
        {
            int to=edge[j].to;
            if(!tag[to] || vis1[to]) continue;
            rdis-=edge[j].dis;
            vis1[y]=1; y=to; 
        }
    }
    ans=min(ans, max(rdis, ldis));
    while(y!=r)
    {
        for(int j=head[y]; j; j=edge[j].next)
        {
            int to=edge[j].to;
            if(!tag[to] || vis1[to]) continue;
            rdis-=edge[j].dis;
            vis1[y]=1; y=to;
        }
        for(int j=head[x]; j; j=edge[j].next)
        {
            int to=edge[j].to;
            if(!tag[to] || vis2[to]) continue;
            ldis+=edge[j].dis;
            vis2[x]=1; x=to;
        }

        ans=min(ans, max(rdis, ldis));
    }
    return max(ans, maxdis);
}

int main()
{
    scanf("%d%d", &n, &k);
    for(int i=1; i<n; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        addedge(x, y, z);
        addedge(y, x, z);   
    }
    findline(1, 0);
    tag[root]=1; l=r=root;
    for(int i=son1[root]; i; i=son1[edge[i].to]) tag[edge[i].to]=1, l=edge[i].to;
    for(int i=son2[root]; i; i=son1[edge[i].to]) tag[edge[i].to]=1, r=edge[i].to;
    finddis(root, 0);
    printf("%d\n", solve(l, r));
}

发表评论

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