7月9日 Codeforces Round #494
题目链接:http://codeforces.com/contest/1003

A – Polycarp’s Pockets & B – Binary String Constructing

比较水,不说了。

C – Intense Heat

思路:
比较好的一题。这题用到了一点分数规划的思想。

首先二分答案,设二分的值为$mid$,然后将原序列全部减去$mid$,如果长度大于k的最大子序和大于等于0,则符合要求。有长度限制的最大子序和也是一个比较重要的模型,利用DP的思想进行维护。

代码:

#include <bits/stdc++.h>
#define eps 1e-8
using namespace std;

int n, k;
double a[5005], b[5005];

bool check(double mid)
{
    for(int i=1; i<=n; i++) b[i]=a[i]-mid, b[i]+=b[i-1];
    double minn=1e9, maxn=-1e9;
    for(int i=k; i<=n; i++)
    {
        minn=min(minn, b[i-k]);
        maxn=max(maxn, b[i]-minn);
    }
    if(maxn>=0) return 1;
    else return 0;
}

int main()
{
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++) scanf("%lf", &a[i]);
    double l=0, r=5000, mid;
    while(fabs(l-r)>eps)
    {
        mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%.8lf\n", mid);
}

D – Coins and Queries

思路:
这道题比较水。。。

因为硬币面值都是2的整数幂,所以存面值的log2就可以了。然后对于每一个询问,利用类似于二进制分解的操作,看能不能由硬币凑出来。

代码:

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

int n, q, num[50], temp;

int main()
{
    scanf("%d%d", &n, &q);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &temp);
        num[(int)log2(temp)]++;
    }
    for(int i=1; i<=q; i++)
    {
        scanf("%d", &temp);
        int ans=0;
        for(int j=(int)log2(temp); j>=0; j--)
        {
            int t=temp/(1<<j);
            temp-=min(t, num[j])*(1<<j);
            ans+=min(t, num[j]);
            if(temp==0) break;
        }
        if(temp==0) printf("%d\n", ans);
        else printf("-1\n");
    }
}

E – Tree Constructing

思路:
构造题。。码力是真的不够,菜死了QWQ。。。

首先满足直径的条件,先构造一个长度为d的链。然后再满足其它条件,对于链上的每一个点进行拓展,在这个点上尽可能多的放子节点。如果还有节点放不下,就是无解啦。。
代码:

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

int n, d, k, tot;

vector< pair<int, int> > edge;

void dfs(int x, int deg, int dep)
{
    if(dep==0) return;
    for(int i=0; i<deg; i++)
    {
        if(tot>=n) return;
        int y=++tot;
        edge.push_back({x, y});
        dfs(y, k-1, dep-1);
    }
}

int main()
{
    scanf("%d%d%d", &n, &d, &k);
    if(k==1 && n>2) {printf("NO\n"); return 0;}
    for(int i=1; i<=d; i++) edge.push_back({i, i+1});
    tot=d+1;
    for(int i=2; i<=d; i++) dfs(i, k-2, min(i-1, d-i+1));
    if(n==tot)
    {
        printf("YES\n");
        for(int i=0; i<edge.size(); i++) printf("%d %d\n", edge[i].first, edge[i].second);
    }
    else printf("NO\n");
}

F – Abbreviation

思路:
超级好的一题。。结合了字符串和DP。

设第i个和第j个字符串后有$f[i][j]$个连续字符串相等。然后f数组可以预处理出来。然后比较暴力的枚举起始字符串i和长度j。将这段进行压缩,然后对于每个i和j枚举出有多少个串能够这样压缩,用这个更新答案。

总结一下,其实也不能说是DP。只是利用了一下预处理优化了一下暴力。

代码:

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

int n, ans, len, f[305][305];
string str[305];

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) cin>>str[i], len+=str[i].size();
    len+=n-1; ans=len;
    for(int i=n; i>=1; i--)
        for(int j=n; j>=1; j--)
            if(str[i]==str[j]) f[i][j]=f[i+1][j+1]+1;

    for(int i=1; i<=n; i++)
    {
        int sum=0;
        for(int j=0; j+i<=n; j++)
        {
            int cnt=1;
            sum+=str[i+j].size();
            for(int pos=i+j+1; pos<=n; pos++)
                if(f[i][pos]>j) cnt++, pos+=j;

            int temp=len-sum*cnt+cnt;
            if(cnt>1 && ans>temp) ans=temp;
        }
    }
    printf("%d\n", ans);
}

发表评论

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