2017中国大学生程序设计竞赛
E - Evil Forest 题目链接
题目大意：举行绘画比赛，举办n场比赛，告诉你每场比赛的人数，每场比赛至少 要多准备10%的画板，计算至少准备的画板数量。
解析：水题
每场比赛至少要准备多10%的画板，就是每场比赛根据比赛人数的110% 的人数多10% （要分步操作）准备画板就可以了（至少就是只能多不能少，所以要向上取整 ）
关于精度问题
总结：ceil能不用就不用！！！毕竟是double，容易出错
以后做题尽量按照题目意思来吧🤣😂
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int t;
cin >> t;
for(int tt = 1;tt <= t;tt++){
double n , temp;
cin >> n;
int ans = 0;
for(int i = 0;i < n;i++){
cin >> temp;
ans += ceil(temp+temp*0.1);//这里一定要分开写，不然会wa，应该是精度出了问题
}
printf("Case #%d: %d\n",tt,ans);
}
return 0;
}
Dogs and Cages 题目链接
题目大意：编号 0-n-1 的n条狗 进 编号 0-n-1 的n个笼子，问不在自己笼子的狗的期望
解析：题目相当于从n个数字全排列是所有的可能性 总方案数就是n!
第i只狗进对了笼子 就是除了一个数字是对的，剩下的n-1个数字全排列，就是（n-1）！
只有第i只狗不在正确位置上的方案数 n!−(n−1)!
一共有n只狗 n*(n!−(n−1)!）
不在自己笼子的狗的期望就是所有没有进入对的笼子的总数除以总共排列的种数
n*(n!−(n−1)!）/n! 化简后可得 n-1.
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
for(int i = 1;i <= t;i++){
double n;
cin >> n;
printf("Case #%d: %.10f\n",i,n-1);
}
return 0;
}
Rich Game 题目链接
题目大意：羊🐏和熊猫打羽毛球，总所周知，按照羽毛球比赛规则，至少 11 分 并且领先至少 2
分才能获胜一场。现在熊猫输一分，羊给熊猫x元大型打假赛现场熊猫赢一局，熊猫给羊y元，一共打k场。Panda不能够欠Sheep钱。问：在k局内聪明的熊猫最多可以赢多少场。
解析：panda每赢一分给y元，输一分给x元。
①当熊猫赢的时候给羊的钱比他输的时候赢的钱多时，也就是pada输一局可以赢1局以上(>1)的情况，他只要把战局拖得够长，他就可以用羊的钱赢下每一局。（通常某人先得10分他就会赢得比赛，若出现平手（例如10：10），则他应该至少领先对手2分才能赢得这场比赛，个人得分可能会超过1分。）
②当x<=y的情况下，就是当熊猫赢的时候给羊的钱比他输的时候赢的钱少时，也就是熊猫输一局只能赢少于一局（<1)的情况，就要算他输一场（要输就要输的彻底，反正都输了，那就赚最多的钱，输11局，得到11*y的钱）可以支撑他赢几场（赢的时候要用最佳比分赢，用小比分差赢下比赛，9：11，就可以用最小的两点的钱就可以赢一局）
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
for(int i = 1;i <= t;i++){
int x, y ,k, ans = 0;
cin >> x >> y >> k;
if(x > y) ans = k;
else {
int tx = 0,dis = 11*y - 9*x;//dis就是熊猫赢一场需要的钱
for(int j = 0;j < k;j++){
if(tx < dis){ // 就是他当前的钱不够他赢一场，那他就要输一场去赢钱
tx+=11*x;
}else{
tx-=dis;
ans++;
}
}
}
printf("Case #%d: %d\n",i,ans);
}
return 0;
}
Knightmare 题目链接
题目大意：就是给你一个无限大的棋盘，象棋中的马（跳“日”字），飞n步之后可以占领的位置有多少个？（能跳到的地方都可以占领）
一个小技巧：如果数据范围是10^9 ，肯定是O(logn)或者O(1)的算法，就可以先打个表找找规律。
解析：先用dfs打表，跑10步以内的答案，再找规律
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
const int mod = 998244353;
int mp[2005][2005];
int d[8][2]={-1,-2,-2,-1,1,2,2,1,-1,2,2,-1,1,-2,-2,1};
void dfs(int x,int y,int k){//用dfs跑k步能到达的所有点
mp[x][y] = 1;
if(k == 0) return;
for(int i = 0;i < 8;i++){
dfs(x+d[i][0],y+d[i][1],k-1);
}
}
int main(){
vector<int> v;
for(int i = 0;i < 10;i++){
memset(mp,0,sizeof(mp));
dfs(1000,1000,i);//从中心点开始跳
int ans = 0,pre = 0;
for(int ii = 0;ii < 2000;ii++){
for(int j = 0;j < 2000;j++)
if(mp[ii][j]) ans++;
}
printf("%d ",ans);
v.push_back(ans-pre);
pre=ans;
}
cout << endl;
for(int i=0;i<v.size();i++) printf("%d ",v[i]-v[i-1]);
return 0;
}
打出来的答案如下，进行二次差分就可以发现规律了
1 9 41 109 205 325 473 649 853 1085
1 8 32 68 96 120 148 176 204 232 //第一次差分
1 7 24 36 28 24 28 28 28 28//第二次差分
我们可以发现当n>5时，二次差分都是28，所以前面5个特判，后面总结出公式来计算
v[n]-v[n-1] = 28;
不难推出 v[n] = 28*n-20；
v[n]就是a[n]-a[n-1];
所以a[n]-a[n-1]=28*n-20；
a[n-1]-a[n-2]=28*（n-1）-20；
a[n-2]-a[n-3]=28*（n-2）-20；
·······
a[5]-a[4]=28*5-20；
=>a[n]-a[4]=28*((n+5)*(n-4)/2)-20*(n-4)
=>a[n]=14*n*n-6*n+5
long long最大是9.2 × 1018 会发现最后的答案可能会爆ll，所以要用ull
而unsigned long long 是1.8×1019
注意：n也一定要开ll，补题的时候在这又wa了，n在14*n*n的时候，可能会爆ll
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull a[6] = {1,9,41,109,205};
int main(){
int t;
cin >> t;
for(int i = 1;i <= t;i++){
ull ans = 0,n;
cin >> n;
if(n < 5) ans = a[n];
else ans = 14*n*n-6*n+5;
printf("Case #%d: %llu\n",i,ans);
}
return 0;
}