题目连接：http://codeforces.com/contest/448

A:给你一些奖杯与奖牌让你推断能不能合法的放在给定的架子上。假设能够就是YES否则就是NO。

<span style="font-size:18px;">#include <algorithm>

#include <iostream>

#include <stdlib.h>

#include <string.h>

#include <iomanip>

#include <stdio.h>

#include <string>

#include <queue>

#include <cmath>

#include <stack>

#include <map>

#include <set>

#define eps 1e-12

///#define M 1000100

///#define LL __int64

#define LL long long

///#define INF 0x7ffffff

#define INF 0x3f3f3f3f

#define PI 3.1415926535898

#define zero(x) ((fabs(x)<eps)?0:x)

using namespace std;

const int maxn = 100010;

int num[maxn];

int main()

{

    int a1, a2, a3;

    int b1, b2, b3;

    int n;

    while(cin >>a1)

    {

        cin >>a2>>a3;

        cin >>b1>>b2>>b3;

        cin >>n;

        int sum1 = 0;

        sum1 += a1;

        sum1 += a2;

        sum1 += a3;

        int sum2 = 0;

        sum2 += b1;

        sum2 += b2;

        sum2 += b3;

        int x = sum1/5;

        if(sum1%5) x++;

        int y = sum2/10;

        if(sum2%10) y++;

        if(x+y<= n) cout<<"YES"<<endl;

        else cout<<"NO"<<endl;

    }

    return 0;

}</span>

B：给你两个字符串，推断假设让s串变成t串须要什么操作。

假设仅仅是删除一些字母就能够得到输出：automaton。假设仅仅是通过调换字母的顺序就输出：array。如既要删除字母又要调换顺序输出：both。假设须要加入新的字母输出：need tree。

#include <algorithm>

#include <iostream>

#include <stdlib.h>

#include <string.h>

#include <iomanip>

#include <stdio.h>

#include <string>

#include <queue>

#include <cmath>

#include <stack>

#include <map>

#include <set>

#define eps 1e-12

///#define M 1000100

///#define LL __int64

#define LL long long

///#define INF 0x7ffffff

#define INF 0x3f3f3f3f

#define PI 3.1415926535898

#define zero(x) ((fabs(x)<eps)?0:x)

using namespace std;

const int maxn = 110;

char s1[maxn];

char s2[maxn];

int vis[maxn];

int num[maxn];

int main()

{

    while(cin >>s1)

    {

        cin >>s2;

        int len1 = strlen(s1);

        int len2 = strlen(s2);

        memset(vis, 0, sizeof(vis));

        memset(num, 0, sizeof(num));

        for(int i = 0; i < len1; i++) vis[s1[i]-'a']++;

        int flag1 = 0;

        for(int i = 0; i < (len1-len2); i++)

        {

            int flag = 0;

            for(int j = 0; j < len2; j++)

            {

                if(s1[i+j] != s2[j])

                {

                    flag = 1;

                    break;

                }

            }

            if(!flag)

            {

                flag1 = 1;

                break;

            }

        }

        int flag2 = 0;

        for(int i = 0; i < len2; i++) num[s2[i]-'a']++;

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

        {

            if(num[i] > vis[i])

            {

                flag2 = 1;

                break;

            }

        }

        if(flag2) cout<<"need tree"<<endl;

        else if(flag1) cout<<"automaton"<<endl;

        else if(len1 == len2 && !flag2) cout<<"array"<<endl;

        else

        {

            int top = 0;

            for(int i = 0; i < len1; i++) if(s1[i] == s2[top]) top++;

            if(top == len2) cout<<"automaton"<<endl;

            else cout<<"both"<<endl;

        }

    }

}

C给你一串数字代表木板的高度，每块木板的宽度都为1。

让你算出最少须要多少次能够把木板染完颜色。染得时候能够每次染长度为1的一横行（能够多个连续的木板）或者能够竖着然这个一块木板。每一个木板能够反复染色。

思路是：dp[i][j]表示染到第i块木板的时候染了j次横的。

须要注意的是要从后向前的dp。

#include <algorithm>

#include <iostream>

#include <stdlib.h>

#include <string.h>

#include <iomanip>

#include <stdio.h>

#include <string>

#include <queue>

#include <cmath>

#include <stack>

#include <map>

#include <set>

#define eps 1e-12

///#define M 1000100

///#define LL __int64

#define LL long long

///#define INF 0x7ffffff

#define INF 0x3f3f3f3f

#define PI 3.1415926535898

#define zero(x) ((fabs(x)<eps)?0:x)

using namespace std;

const int maxn = 5010;

int dp[maxn][maxn];

int num[maxn];

int main()

{

    int n;

    while(cin >>n)

    {

        num[0] = 0;

        for(int i = 1; i <= n; i++) scanf("%d",&num[i]);

        for(int i = 0; i <= n; i++) dp[n][i] = 0;

        for(int i = n; i >= 1; i--)

        {

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

            {

                if(num[i] <= num[j])

                {

                    dp[i-1][j] = dp[i][i];

                    continue;

                }

                dp[i-1][j] = min(dp[i][j]+1, dp[i][i]+num[i]-num[j]);

            }

        }

       cout<<dp[0][0]<<endl;

    }

    return 0;

}

D给你n。m，k。n*m的矩阵中的每一个元素是i，j的成绩。然后让你求一个x满足在这个n*m的矩阵中有k个元素小于x。

思路二分枚举x，范围是1-n*m。

可是这里要高速求出小于x的数的个数。

for(int i = 1; i <= n; i++) ans += min(m, mid/i);这个能够高速的统计出这一行中有多少个元素是小于x的。

#include <algorithm>

#include <iostream>

#include <stdlib.h>

#include <string.h>

#include <iomanip>

#include <stdio.h>

#include <string>

#include <queue>

#include <cmath>

#include <stack>

#include <map>

#include <set>

#define eps 1e-12

///#define M 1000100

///#define LL __int64

#define LL long long

///#define INF 0x7ffffff

#define INF 0x3f3f3f3f

#define PI 3.1415926535898

#define zero(x) ((fabs(x)<eps)?0:x)

using namespace std;

const int maxn = 5010;

int dp[maxn][maxn];

int num[maxn];

int main()

{

    LL n, m, k;

    while(cin >>n>>m>>k)

    {

        LL l = 1;

        LL r = n*m;

        while(l < r)

        {

            LL mid = (l+r)>>1;

            LL ans = 0;

            for(int i = 1; i <= n; i++) ans += min(m, mid/i);

            if(ans >= k) r = mid;

            else if(ans < k) l = mid+1;

        }

        cout<<r<<endl;

    }

}