8月3日 Codeforces Round #501
题目链接:http://codeforces.com/contest/1015

A – Points in Segments & B – Obtaining the String

比较水,不说了。。。

C – Songs Compression

思路:
很显然是一个贪心,按照能够压缩的大小排个序,能够选的就尽量选。然后就好了。

代码:

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

int n, m;
LL tot;

struct A {int x, y;} a[1000005];

bool CMP(A x, A y) {return x.x-x.y>y.x-y.y;}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d%d", &a[i].x, &a[i].y);
    sort(a+1, a+n+1, CMP);
    for(int i=1; i<=n; i++) tot+=a[i].x;
    if(tot<=m) {printf("0\n"); return 0;}
    for(int i=1; i<=n; i++)
    {
        tot-=(a[i].x-a[i].y);
        if(tot<=m) {printf("%d\n", i); return 0;}
        if(i==n) printf("-1\n");
    }
}

D – Walking Between Houses

思路:
蛮有趣的题,类似于构造吧。

我们设当前可以走$k$步,要走$s$距离,我们就以$(s+k-1)/k$为基准值,每一步走的距离都尽量靠近这个值(其实我也不清楚为什么是对的,只是觉得数据不好卡这个算法)。然后注意要特判两种为NO的情况。

代码:

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

LL n, k, s;
int ans[1000000], cnt;

void dfs(int pos, LL k, LL s)
{
    if(k==0 && s==0) return;
    LL dis=(s+k-1)/k;
    if(pos-dis>=1) pos=pos-dis;
    else if(pos+dis<=n) pos=pos+dis;
    else
    {
        LL t1=n-pos, t2=pos-1;
        if(t1>t2) pos=n, dis=t1;
        else pos=1, dis=t2;
    }
    ans[++cnt]=pos;
    dfs(pos, k-1, s-dis);
}

int main()
{
    scanf("%lld%lld%lld", &n, &k, &s);
    if(s>k*(n-1) || k>s) {printf("NO\n"); return 0;}
    printf("YES\n");
    dfs(1, k, s);
    for(int i=1; i<=cnt; i++) printf("%d ", ans[i]);
}

E1 – Stars Drawing (Easy Edition)

思路:
这个数据范围比较小,就是毒瘤模拟。。。我们枚举每个星星的中心,然后选尽可能大的,这个贪心比较显然。所以这个总复杂度为$O(N^3)$的。

代码:

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

int n, m, cnt, maxlen, x[MAXN*MAXN], y[MAXN*MAXN], z[MAXN*MAXN];
bool vis[MAXN][MAXN];
char mmp[MAXN][MAXN];

void check()
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(mmp[i][j]=='*' && !vis[i][j]) {printf("-1\n"); exit(0);}
}

void find(int px, int py, int len)
{
    bool flag=1;
    if(px-len<1 || py-len<1 || px+len>n || py+len>m) return;
    for(int i=py; i<=py+len; i++) if(mmp[px][i]!='*') {flag=0; break;}
    for(int i=py; i>=py-len; i--) if(mmp[px][i]!='*') {flag=0; break;}
    for(int i=px; i<=px+len; i++) if(mmp[i][py]!='*') {flag=0; break;}
    for(int i=px; i>=px-len; i--) if(mmp[i][py]!='*') {flag=0; break;}
    if(flag) maxlen=len;
    find(px, py, len+1);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%s", mmp[i]+1);
    for(int px=1; px<=n; px++)
        for(int py=1; py<=m; py++)
        {
            maxlen=0;
            find(px, py, 1);
            if(maxlen)
            {
                x[++cnt]=px; y[cnt]=py; z[cnt]=maxlen;
                for(int i=py; i<=py+maxlen; i++) vis[px][i]=1;
                for(int i=py; i>=py-maxlen; i--) vis[px][i]=1;
                for(int i=px; i<=px+maxlen; i++) vis[i][py]=1;
                for(int i=px; i>=px-maxlen; i--) vis[i][py]=1;
            }
        }
    check();
    printf("%d\n", cnt);
    for(int i=1; i<=cnt; i++) printf("%d %d %d\n", x[i], y[i], z[i]);
}

E2 – Stars Drawing (Hard Edition)

思路:
这里可以用一个常规的优化,就是用$O(N^2)$的预处理,$O(N^2)$计算,答案来代替$O(N^3)$的普通算法。

不过预处理和计算都比较的巧妙。可以利用类似DP的方法算出每个位置上下左右有多少个连续的‘*’,那么星星最大的大小就是它们的最小值,于是预处理就是$O(N^2)$。

计算每个位置有没有星星覆盖可以利用前缀和的思想,对于位置在$x,y$且大小为$l$的星星,我们可以在$(x-l, y)$处打上$+1$的标记,在$(x+l+1, y)$打上$-1$的标记。类似的,也可以在$(x, y-l)$打上$+1$,$(x, y+l+1)$打上$-1$的标记。最后再扫一遍就可以确定星星的覆盖情况。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#define MAXN 1005
#define LL long long
using namespace std;

int n, m, up[MAXN][MAXN], down[MAXN][MAXN], left[MAXN][MAXN], right[MAXN][MAXN];
int cnt, tag1[MAXN][MAXN], tag2[MAXN][MAXN], x[MAXN*MAXN], y[MAXN*MAXN], z[MAXN*MAXN];
char mp[MAXN][MAXN];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%s", mp[i]+1);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            if(mp[i][j]=='*') up[i][j]=up[i-1][j]+1;
            if(mp[i][j]=='*') left[i][j]=left[i][j-1]+1;
        }
    for(int i=n; i>=1; i--)
        for(int j=m; j>=1; j--)
        {
            if(mp[i][j]=='*') down[i][j]=down[i+1][j]+1;
            if(mp[i][j]=='*') right[i][j]=right[i][j+1]+1;
        }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            int l=min(min(up[i][j], down[i][j]), min(left[i][j], right[i][j]))-1;
            if(l<=0) continue;
            tag1[i-l][j]++; tag1[i+l+1][j]--;
            tag2[i][j-l]++; tag2[i][j+l+1]--;
            x[++cnt]=i; y[cnt]=j; z[cnt]=l;
        }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            tag1[i][j]+=tag1[i-1][j];
            tag2[i][j]+=tag2[i][j-1];
            if(mp[i][j]=='*' && tag1[i][j]==0 && tag2[i][j]==0)
            {
                printf("-1\n");
                return 0;
            }
        }
    printf("%d\n", cnt);
    for(int i=1; i<=cnt; i++) printf("%d %d %d\n", x[i], y[i], z[i]);
}

发表评论

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