# 2017CCPC-final hdu 6243,6245,6253 - hold on！！！ - CSDN博客

hdu 6243 组合数学（公式推导）

# Dogs and Cages

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

Problem Description
Jerry likes dogs. He has N dogs numbered 0,1,...,N?1. He also has N cages numbered 0,1,...,N?1. Everyday he takes all his dogs out and walks them outside. When he is back home, as dogs can’t recognize the numbers, each dog just randomly selects a cage and enters it. Each cage can hold only one dog.
One day, Jerry noticed that some dogs were in the cage with the same number of themselves while others were not. Jerry would like to know what’s the expected number of dogs that are NOT in the cage with the same number of themselves.
?

Input
The first line of the input gives the number of test cases, T. T test cases follow.
Each test case contains only one number N, indicating the number of dogs and cages.
1T105
1N105
?

Output
For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the expected number of dogs that are NOT in the cage with the same number of itself.
y will be considered correct if it is within an absolute or relative error of 10?6 of the correct answer.
?

Sample Input
2
1
2
?

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.

#include
#include
#include
using namespace std;

int main()
{
int cases=1,n,T;
//freopen("in.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
printf("Case #%d: %0.8lf\n",cases++,(n-1)*1.0);
}
return 0;
}

hdu 6245 简单博弈

# Rich Game

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

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 X dollars. For each time I lose one point, you should give me Y dollars back.”
God Sheep is going to play K sets of badminton games. For each set, anyone who wins at least 11 points and leads by at least 2 points will win this set. In other words, normally anyone who wins 11 points first will win the set. In case of deuce (E.g. 10 points to 10 points), it’s necessary to lead by 2 points to win the set.
Mr. Panda is really good at badminton so he could make each point win or lose at his will. But he has no money at the beginning. He need to earn money by losing points and using the money to win points.
Mr. Panda cannot owe God Sheep money as god never borrowed money. What’s the maximal number of sets can Mr. Panda win if he plays cleverly?
?

Input
The first line of the input gives the number of test cases, T. T test cases follow.
Each test case contains 3 numbers in one line, X, Y , K, the number of dollars earned by losing a point, the number of dollars paid by winning a point, the number of sets God Sheep is going to play.
1T105.
1X,Y,K1000.
?

Output
For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the maximal number of sets Mr. Panda could win.
?

Sample Input
2
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.


#include
#include
#include
#include
using namespace std;
const int maxn = 100+5;

int n,m;

int main()
{
//freopen("in.txt","r",stdin);
int T;
int kase = 0;
scanf("%d",&T);
while(T--)
{
printf("Case #%d: ",++kase);
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
if(x>y)  printf("%d\n",k);
else
{
int money = 0;
int ans = 0;
while(k--)
{
money += 9*x;
if(money < 11*y)  money += 2*x;
else
{
money = money - 11*y;
ans++;
}
}
printf("%d\n",ans);
}
}
return 0;
}

hdu 6253 打表找规率

# Knightmare

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

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 N times before he gets bored.
Recall that a knight can jump in 8 directions. Each direction consists of two squares forward and then one squaure sidways.

After N jumps, how many squares can possibly be claimed as territory of the knight? As N can be really large, this becomes a nightmare to the knight who is not very good at math. Can you help to answer this question?
?

Input
The first line of the input gives the number of test cases, T. T test cases follow.
Each test case contains only one number N, indicating how many times the knight jumps.
1T105
0N109
?

Output
For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the number of squares that can possibly be claimed by the knight.
?

Sample Input
3
0
1
7
?

Sample Output
Case #1: 1
Case #2: 9
Case #3: 649

bfs打表：这里我们打的表示每一步占领了多个地方，前缀和就是答案

#include
#include
#include
#include
#include
using namespace std;
const int maxn = 100+5;

int n,m;
int dx[] = {1,1,2,2,-1,-1,-2,-2};
int dy[] = {2,-2,1,-1,2,-2,1,-1};

int vis[1000][1000];
int ans[100];

struct node
{
int x,y;
int step;
};

int main()
{
//freopen("in.txt","r",stdin);
memset(vis,0,sizeof(vis));
queue q;
node p;
p.x = 500, p.y = 500, p.step = 0;
ans[0] = 1;
vis[500][500] = 1;
q.push(p);
while(!q.empty())
{
p = q.front(); q.pop();
if(p.step == 20)  continue;
for(int k =0;k<8;k++)
{
int xx = p.x + dx[k];
int yy = p.y + dy[k];
if(vis[xx][yy])  continue;
vis[xx][yy] = 1;
node tmp;
tmp.x = xx;
tmp.y = yy;
tmp.step = p.step+1;
ans[tmp.step]++;
q.push(tmp);
}
}

for(int i=0;i<=20;i++)
cout<<>

#include
int a[10]={1,9,41,109,205,325,473};
int main()
{
int cases=1;
long long n,T;
//freopen("in.txt","r",stdin);
scanf("%lld",&T);
while(T--)
{
scanf("%lld",&n);
printf("Case #%d: ",cases++);
if(n<=6) { printf("%d\n",a[n]);continue;}
unsigned long long ans = (n-6)*176+(n-6)*(n-7)/2*28;
printf("%llu\n",ans+473);
}
return 0;
}


(注：此网站文章大都来自公开的博客，如有原作者发现有侵权问题，请在此留言，我们会立刻删除相关文章。)