CCPC-Wannafly Camp Day7 总结
7-8 7H. 游戏
有1到n这些数字各一个。你用这些数字进行若干轮游戏。 对于每一轮，如果剩下的数字个数超过1个，那么就等概率随机选择两个剩下的数字删去。如果这两个数字互质，得一分。 重复以上操作直到没数字可以删除为止。请问最后期望得多少分？
输入格式
一行一个整数n (1≤n≤5000)。
输出格式
输出一个最简约数
b
a
表示答案。
输入样例
2
4
输出样例
1/1
5/3
思路
一开始因为0/0直接输出了0，WA了好久……
#include<iostream>
#include<vector>
#define ll long long
using namespace std;
ll gcd(ll a, ll b)
{
if(a%b==0)
return b;
else
return gcd(b, a%b);
}
int main()
{
ll n, x=0, fenmu, fenzi;
cin>>n;
if(n==1)
{
cout<<"0/1"<<endl;
return 0;
}
for(ll i=1; i<=n; i++)
{
for(ll j=i+1; j<=n; j++)
{
if(gcd(i, j)==1)
{
x++;
}
}
}
fenzi=x*(n/2)*2;
fenmu=n*(n-1);
ll mod=gcd(fenmu, fenzi);
fenmu/=mod;
fenzi/=mod;
cout<<fenzi<<"/"<<fenmu<<endl;
}
7-11 7K. 修炼
有一款双人小游戏，两个玩家分别控制两个人物，这两个人物的能力可以用v1,v2来表示，初始两人的能力都为0。
游戏进行的单位是天，每一天这两个人都会分别提升a1,a2的能力值，此外，每天可以获得一个能力点，可以让a1+=1或者a2+=1。
等到两人修炼足够长的时间，就可以去打boss通关了。
小沃沃通过查攻略，发现最后两人的能力值组合只要满足v1≥b1且v2≥b2，就可以过关。
由于通关方式有很多种，可能有很多组b1,b2的组合，只要满足其中任意一组就可以通关。
现在小沃沃想知道最短几天能够通关。
输入格式
第一行2个数，表示a1,a2 (0≤a1,a2<100000)。
接下来一行输入一个数 n (1≤n≤1000)。
下面n行，每行2个数，表示一组可以通关的b1,b2 (0<b1,b2<10
9
)。
输出格式
一个数表示最短通关天数。
输入样例
0 0
1
1 2
1 1
2
5 7
6 6
输出样例
2
3
思路
看代码
#include<iostream>
using namespace std;
struct all
{
long long b1,b2;
};
all a[1005],b[1005];
long long chu(long long aa,long long bb)
{
if(aa<=0) return 0;
else
{
if(bb==0) return aa+1000000000;
else
{
if(aa%bb==0) return aa/bb;
else return aa/bb+1;
}
}
}
int main()
{
long long a1,a2,v1=0,v2=0;
cin>>a1>>a2;
long long n;
cin>>n;
long long minx=1000000000009;
for(int i=1; i<=n; i++)
{
cin>>a[i].b1>>a[i].b2;
}
long long minas=1000000000009;
long long we=a1,qe=a2;
for(long long j=1; j<=n; j++)
{
v1=0;v2=0;
a1=we;
a2=qe;
for(long long i=1;;i++)
{
if(chu(a[j].b2-v2,a2)>=chu(a[j].b1-v1,a1))
{
a2++;
}
else a1++;
v1+=a1;
v2+=a2;
if(v1>=a[j].b1&&v2>=a[j].b2)
{
minas=min(i,minas);
break;
}
}
}
cout<<minas<<endl;
return 0;
}
终于结束了……下班下班……
开心