2017中国大学生程序设计竞赛-总决赛-重现赛（感谢哈工大）

昨天的CCPC杭州怎么说好的还是取消了，那么今天就来玩玩这个总决赛

Dogs and Cages

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Special Judge

Problem Description

Jerry likes dogs. He has

Input

The first line of the input gives the number of test cases,

Output

For each test case, output one line containing “Case #x: y”, where

Sample Input

Sample Output

Case #1: 0.0000000000

Case #2: 1.0000000000

Hint

In the first test case, the only dog will enter the only cage. So the answer is 0. In the second test case, if the first dog enters the cage of the same number, both dogs are in the cage of the same number, the number of mismatch is 0. If both dogs are not in the cage with the same number of itself, the number of mismatch is 2. So the expected number is (0+2)/2=1.

A题火速签到啊，随机生成n的全排列，a[i]!=i的数学期望

1只能正确，2可以在1个正确和1个错误的情况下加上1，递归可以发现是n*(n-1)，那么数学期望就是n-1

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T,ca=0;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        printf("Case #%d: %d
",++ca,n-1);
    }
    return 0;
}

Evil Forest

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 241 Accepted Submission(s): 119

Problem Description

The Bear, king of the forest, loves painting very much. His masterpiece – “Back in time” is very famous around all over the forest. Recently he wants to hold a series painting competition to select those animals who are good at painting as well. So the Bear appoints his minister Tiger to help him prepare the painting competitions.
Tiger owns a stationery factory which produces sketchpad, so he wants to let all the competitions use the sketchpads produced by his factory privately. The Bear plans to hold

Input

The first line of the input gives the number of test cases,

Output

For each test case, output one line containing “Case #x: y”, where

Sample Input

13 11 11 11 13 11

Sample Output

Case #1: 82

Hint

For the first test case, two more sketchpads should be prepared for each painting competition.

这个才是真正的签到题，可是自己没有看出来就是求下一个数的110%x的和，这个时候要向上取整

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T,ca=0;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        int s=0;
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            s+=x+x/10+(x%10!=0);
        }
        printf("Case #%d: %d
",++ca,s);
    }
    return 0;
}

Rich Game

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0

Problem Description

One day, God Sheep would like to play badminton but he can’t find an opponent. So he request Mr. Panda to play with him. He said: “Each time I win one point, I’ll pay you

Input

The first line of the input gives the number of test cases,

Output

For each test case, output one line containing “Case #x: y”, where

Sample Input

10 10 1

10 10 2

Sample Output

Case #1: 0 Case #2: 1

Hint

In the first test case, Mr. Panda don’t have enough money to win the only set, so he must lose the only set. In the second test case, Mr. Panda can lose the first set by 0:11 and he can earn 110 dollars. Then winning the second set by 11:0 and spend 110 dollars.

这个题目我感觉还是挺毒的啊，要把全部情况分析出来

赚的比输得多，那就多打几场全赢了，否则要按照11：9去赢，0：11去输，这样可以少输点钱，直接解不等式就可以了，很简单的。我好想本来是考虑错了，然后因为x y弄反了多wa了几次，太傻了

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T,ca=0;
    scanf("%d",&T);
    while(T--)
    {
        int x,y,k,s;
        scanf("%d%d%d",&x,&y,&k);
        if(x>y)
            s=k;
        else
            s=11*k*x/(11*y+2*x);
        printf("Case #%d: %d
",++ca,s);
    }
    return 0;
}

Knightmare

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0

Problem Description

A knight jumps around an infinite chessboard. The chessboard is an unexplored territory. In the spirit of explorers, whoever stands on a square for the first time claims the ownership of this square. The knight initially owns the square he stands, and jumps

Input

The first line of the input gives the number of test cases,

Output

For each test case, output one line containing “Case #x: y”, where

Sample Input

Sample Output

Case #1:1

Case #2: 9

Case #3: 649

一看就是找规律的题，

然后想想矩阵快速幂不对啊，因为没有MOD

所以肯定直接找规律就行了，写代码打表得到了前10项的值，第11项因为栈的问题已经爆炸掉了

1,9,41,109,205,325,473,649,853,1085,1345

然后前后相减没什么规律，继续相减最后几个都是28啊，最后的增量和28有关，前几项试特殊项，找到了那个增量是28*n-20，写一下化简一下，试了试都对

但是我还是没估算好答案，爆了一发ll，要ull

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T,ca=0;
    scanf("%d",&T);
    int a[5]={1,9,41,109,205};
    while(T--)
    {
        unsigned long long n;
        scanf("%llu",&n);
        printf("Case #%d: ",++ca);
        if(n<5)
            printf("%d
",a[n]);
        else
            printf("%llu
",(n*14-6)*n+5);
    }
    return 0;
}

Alice’s Stamps

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0

Problem Description

Alice likes to collect stamps. She is now at the post office buying some new stamps.
There are

Input

The input starts with one line containing one integer

Output

For each test case, output one line containing “Case #x: y”, where

Sample Input

2 5 3 2 3 4 1 1 1 3 100 2 1 1 50 90 100

Sample Output

Case #1: 4 Case #2: 50

Hint

In sample case #1, Alice could buy the first and the third stamp sets, which contain the first four kinds of stamp. Note that she gets two copies of stamp 3, but only the number of different kinds of stamps matters, not the number of stamps of each kind. In sample case #2, Alice could buy the first stamp set, which contains 50 different kinds of stamps.

有一点没搞对，都没来得及交，就是一个简单的dp

以下为后来改的代码

#include<bits/stdc++.h>
using namespace std;
int dp[2005][2005];
int l[2005];
int main()
{
    int T,ca=0;
    scanf("%d",&T);
    while(T--)
    {
        memset(l,0,sizeof l);
        int n,m,k;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0; i<m; i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            for(int i=x; i<=y; i++)
                l[i]=max(l[i],y);
        }
        memset(dp,0,sizeof dp);
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<k; j++)
            {
                if(l[i+1])dp[l[i+1]][j+1]=max(dp[i][j]+l[i+1]-i,dp[l[i+1]][j+1]);
                dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
            }
        }
        int ans=0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=k; j++)
                ans=max(ans,dp[i][j]);
        printf("Case #%d: %d
",++ca,ans);
    }
    return 0;
}

这个端点维护有很大问题，只是先把不覆盖的转移了，解决掉了端点的重合问题

#include<bits/stdc++.h>
using namespace std;
int dp[2005][2005];
int l[2005],f[2005];
int main()
{
    int T,ca=0;
    scanf("%d",&T);
    while(T--)
    {
        memset(l,0,sizeof l);
        int n,m,k;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0; i<m; i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            l[x]=max(l[x],y);
        }
        int ans=0;
        memset(dp,0,sizeof dp);
        memset(f,0,sizeof f);
        for(int i=1; i<=n; i++)
        {
            for(int j=0; j<k; j++)
            {
                if(l[i])
                {
                    dp[i][j]+=(f[i]==0);
                    dp[l[i]][j+1]=dp[i][j]+l[i]-i;
                    f[l[i]]=1;
                }
                dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
            }
            ans=max(ans,dp[i][k]);
        }
        printf("Case #%d: %d
",++ca,ans);
    }
    return 0;
}