Codeforces Testing Round 14

A:The Way to Home

link:http://codeforces.com/contest/910/problem/A

题面：有每次最大跳跃距离d，只有一部分的点可以落脚，求最少几步达到终点D

Solution :预处理+贪心

用f[i]表示离点i最近的可落脚点，贪心即可(dp同理)

#include <bits/stdc++.h>

using namespace std;

int n,d,pre[];

string s;

int main()

{

    cin >> n >> d >> s;

    n--;

    pre[]=;

    for(int i=;i<s.size();i++)

        if(s[i]=='') pre[i]=i;

        else pre[i]=pre[i-];

    int cur=,res=;

    bool f=true;

    while(cur<n)

    {

        if(pre[min(cur+d,n)]==cur)

        {

            f=false;

            break;

        }

        cur=pre[min(cur+d,n)];

        res++;

    }

    if(!f) cout << -;

    else cout << res;

    return ;

}

Problem A

B. Door Frames

http://codeforces.com/contest/910/problem/B

题面：有4个长度为a和2个长度为b的木板，求最少用多少个长度为n的木板可以裁出所要求的所有木板

Solution A:分析法

这也是我用的方法，因为只有2个长度为b的木板，因此只有两种情况，一个n做2个b，或2个n做2个b，其余空间全部由a填满。

Tip:c++中自带的上下取整函数：floor()和ceil()

#include <bits/stdc++.h>

using namespace std;

typedef pair<float,float> P;

int n,a,b;

int main()

{

    cin >> n >> a >> b;

    if(n>=(a+a+b)*) cout << ;

    else if(n>=(a+a+b)) cout << ;

    else

    {

        P n1,n2,n3;

        int res=1e9;

        n1.first=floor(n/a);n1.second=;

        if(n>=*b)

        {

            n3.first=floor((n-*b)/a);

            n3.second=;

            res=min(res,+(int)ceil((-n3.first)/n1.first));

        }

        if(n>=b)

        {

            n2.first=floor((n-b)/a);

            n2.second=;

            res=min(res,+(int)ceil((-*n2.first)/n1.first));

        }

        cout << res;

    }

    return ;

}

Solution A

Solution B:

因为真正会影响最终结果的是裁剪的顺序，因此对6个数全排列即可

在考虑最优解问题时，可以从枚举出每种可能的顺序下手

Tip:next_permutation()如一开始不排序，最终枚举的是该序列之后的排列

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

int main()

{

    int n,a,b,res=1e9;

    cin >> n >> a >> b;

    vector<int> v;

    for(int i=;i<;i++) v.pb(a);

    v.pb(b);v.pb(b);

    sort(v.begin(),v.end());

    do

    {

        int l=n,cur=;

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

            if(l-v[i]>=) l-=v[i];

            else cur++,l=n-v[i];

        res=min(res,cur);

    }

    while(next_permutation(v.begin(),v.end()));

    cout << res;

    return ;

}

Solution B

Solution C:递归

这也是我一开始未想到的，其实本应该是非常直观的思路

用dfs(x,y)返回还剩x个a，y个b最少要用几个n来组成，直接暴力

Tip:当有两层循环且内层循环当i=0时j要从1开始时，可以将起始条件设为j=(i==0)

#include <bits/stdc++.h>

using namespace std;

int n,a,b;

int dfs(int x,int y)

{

    int ret=;

    if(!x && !y) return ;

    for(int i=;i<=x && i*a<=n;i++)

        for(int j=(i==);j<=y && j*b+i*a<=n;j++)

        {

            ret=min(ret,dfs(x-i,y-j));

        }

    ret++;

    return ret;

}

int main()

{

    cin >> n >> a >> b;

    cout << dfs(,);

    return ;

}

Solution C

Solution D:状压DP

Zscoder大神的写法，虽然没有必要，但代码技巧是值得学习的

先用only数组储存所有一个n能组成的情况，接下来进行状压DP

Tip: 1、当判断在二进制下i是否包含j时，使用(i&j)==j

2、当表示在二进制下只在i中但不在j中的1时，使用i^j（前提：i包含j，否则表示的是两者不共同所有的1）

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

int dp[(<<)];

int n,a,b;

int main()

{

    cin >> n >> a >> b;

    vector<int> v;

    for(int i=;i<;i++) v.pb(a);

    for(int i=;i<;i++) v.pb(b);

    for(int i=;i<(<<)+;i++) dp[i]=1e9;

    dp[] = ;

    vector<int> only;

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

    {

        int sum=;

        for(int j=;j<v.size();j++)

            if(i&(<<j)) sum+=v[j];

        if(sum<=n)

        {

            dp[i]=;only.pb(i);

        }

    }

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

        for(int z=;z<only.size();z++)

        {

            int j=only[z];

            if((i&j)==j)

                dp[i]=min(dp[i],dp[j]+dp[(i^j)]);

        }

    cout<<dp[(<<)-];

}

Solution D

C:Minimum Sum

link:http://codeforces.com/contest/910/problem/C

Solution:

先计算出每个字母要计算的总次数，同时记录其是否有可能为首位，接下来贪心

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<ll,bool> P;

int n;

P a[];

int main()

{

    cin >> n;

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

    {

        string s;cin >> s;

        ll time=;

        for(int j=s.size()-;j>=;j--)

        {

            if(!j) a[s[]-'a'].second=true;

            a[s[j]-'a'].first+=time;

            time*=;

        }

    }

    sort(a,a+,greater<P>());

    ll res=,cur=;

    bool used=false;

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

    {

        if(!a[i].second && !used) used=true;

        else

        {

            res+=a[i].first*cur;

            cur++;

        }

    }

    cout << res;

    return ;

}

Problem C

巴特西