7月30号 Codeforces Round #500
题目链接:http://codeforces.com/contest/1013

A – Piles With Stones

过水,不说。

B – And

思路:
首先可以发现答案只能是-1,0,1,2,所以我们一个一个判断。如果已经有重复元素,答案就是0;如果与x后有重复元素,答案就是1;如果两个元素与x后相等,答案就是2;其余的情况答案就是-1。然后就是一些细节注意处理。

代码:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#define INF 0x3f3f3f3f
#define MAXN 1000005
#define LL long long
#define LB long double
using namespace std;

int n, k, a[MAXN], vis1[MAXN], vis2[MAXN];

int main()
{
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]), vis1[a[i]]++;
    for(int i=1; i<=n; i++) if(vis1[a[i]]>=2)
    {
        printf("0\n");
        return 0;
    }
    for(int i=1; i<=n; i++)
        if(a[i]!=(a[i]&k)) vis2[a[i]&k]++;
    for(int i=1; i<=n; i++) if(vis2[a[i]]>=1) 
    {
        printf("1\n");
        return 0;
    }
    for(int i=1; i<=n; i++) if(vis2[a[i]&k]>=2)
    {
        printf("2\n");
        return 0;
    }
    printf("-1\n");
    return 0;
}

C – Photo of The Sky

思路:
蛮神奇的一题。我们可以先将这些坐标排序,并将它们分为两类,横坐标集合与纵坐标集合。可以发现横坐标集合一定是连续的n个,如果你随意交换一对使它不连续,那么纵坐标的极差不变,很坐标的极差增大了,而答案就是两个极差之积。

代码:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#define INF 1e18+5
#define MAXN 100005
#define LL long long
#define LB long double
using namespace std;

int n;
LL ans=INF, a[MAXN*2];

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n*2; i++) scanf("%lld", &a[i]);
    sort(a+1, a+2*n+1);
    for(int i=1; i<=n; i++)
    {
        LL x=a[i+n-1]-a[i], y;
        if(i==1) y=a[2*n]-a[n+1];
        else y=a[2*n]-a[1];
        if(x*y<ans) ans=x*y;
    }
    printf("%lld\n", ans);
}

D – Chemical table

思路:
首先用类似于连二分图的方法连边,把行和列作为节点。那么可以发现,我们要做的就是使整个图变为一个联通块。于是我们可以统计联通块个数,每加一个点就相当于连一条边,所以我们只需要加联通块个数-1个点就好了。

代码:

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

int n, m, q, cnt, ans, head[MAXN], x[MAXN], y[MAXN];
bool vis[MAXN];

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

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void dfs(int x)
{
    vis[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(!vis[to]) dfs(to);
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for(int i=1; i<=q; i++)
    {
        scanf("%d%d", &x[i], &y[i]);
        addedge(x[i], y[i]+n);
        addedge(y[i]+n, x[i]);
    }
    for(int i=1; i<=n+m; i++)
        if(!vis[i]) dfs(i), ans++;
    printf("%d\n", ans-1);
}

E – Hills

思路:
就是一个DP,首先我们设$f[i][j][k]$为第i个位置,建了j座房子所花的代价,$k$表示在位置$i$有没有建房子。然后我可以把位置$i$造房子的代价拆成两个:把左边变的更低的代价$l[i]$,把右边变得更低的代价$r[i]$。

然后就按照DP来,转移方程就看代码吧(懒得写了)。其中有一些细节要注意:如果两座房子中间之隔了一个,那么前一座房子的代价$r[i]$与这一座房子的代价$l[i]$有重合,于是我们特别地把这时的代价记为$val$,于是转移时还要特别考虑这个情况。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 5005
#define INF 0x3f3f3f
using namespace std;

int n, a[MAXN], l[MAXN], r[MAXN], f[MAXN][MAXN][2];

int main()
{
    scanf("%d", &n);
    memset(f, 0x3f, sizeof(f));
    f[0][0][0]=0;
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<=n; i++)
    {
        l[i]=max(0, a[i-1]-a[i]+1);
        r[i]=max(0, a[i+1]-a[i]+1);
    }
    for(int i=1; i<=n; i++)
    {
        f[i][0][0]=f[i-1][0][0];
        for(int j=1; j<=(i+1)/2; j++)
        {
            int val= i<=2 ? INF:f[i-2][j-1][1]+max(0, a[i-2]-a[i])+r[i];
            f[i][j][0]=min(f[i-1][j][0], f[i-1][j][1]);
            f[i][j][1]=min(f[i-1][j-1][0]+l[i]+r[i], val);
        }
    }
    for(int i=1; i<=(n+1)/2; i++) printf("%d ", min(f[n][i][0], f[n][i][1]));
}

发表评论

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