2016ACM ECfinal补题题解

本文主要是介绍2016ACM ECfinal补题题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem E. Bet

题意：赌钱，每个队都有对应的赔率，求最多能对多少个队下注，使得只要有一个队赢了就可以保证总是赚钱的。

思路：这个题目中钱是未知的，所以设变量不能用钱，因为最后消不掉，设我对第$i$队下注了一份钱，占下注总额的比例为$p_i$,只有该队胜利，有$1+\frac{B_i}{A_i}\ast 1>\frac{1}{p_i}$，最后推出$\frac{A_i}{A_i+B_i}>p_i$，又因为${\sum }_{i=1}^{i=n}{p}_i=1$，于是有${\sum }_{i=1}^{i=n-1}\frac{A_i}{A_i+B_i}>{\sum }_{i=1}^{i=n-1}{p}_i<1$。

但是这个题目double会爆精度，因为double只有16位，用long double。注意这个题目不能交c++11。

代码：

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
const int maxn=10005;
using namespace std;
typedef long long ll;
long double A[maxn];int main ()
{//freopen("D:\\input.txt", "r", stdin);//freopen("D:\\output.txt", "w", stdout);int t,n;cin>>t;for(int cas = 1; cas <= t;cas++){cin>>n;long double x,y;char s;for(int i =1;i <= n;i++){cin>>x>>s>>y;A[i] = x / (x + y);}// sort(g+1,g+1+n,cmp);sort(A+1,A+1+n);long double sum1 = 0.0;int cnt = 0;for(int i = 1;i <= n;i++){sum1 += A[i];if(sum1 < 1.0)cnt++;else break;}cout<<"Case #"<<cas <<": "<< cnt << endl;}return 0;
}

Problem H. Great Cells

思路：
学长说是容斥原理，不过是想复杂了。一个思维+数学题。

对于这个式子先拆开为${\sum }_{g=0}^{NM}(g+1)\ast A_g={\sum }_{g=0}^{NM}g\ast A_g+{\sum }_{g=0}^{NM}{A}_g$
对于后者${\sum }_{g=0}^{NM}{A}_g$，从0到n*m所有的染色方案就是对所有的格子用k种颜色的染色方案$K^{NM}$.

对于前者，（我想不通），可能就是${\sum }_{g=0}^{NM}g\ast A_g$，不同数量的方案数都是染g个good点，每个good点都有贡献1，那么就是任意染，所有有good点的染色方案总数。每次可能只用$i$种颜色，good点占了一种，对于它的同行同列只有$i-1$种可以选择，非同行同列仍有K种可以选择，即
${\sum }_{i=1}^K(i-1{)}^{M-1+N-1}{K}^{(N-1)(M-1)}$，共有$NM$个点。

答案就是$NM{\sum }_{i=1}^K(i-1{)}^{M-1+N-1}{K}^{(N-1)(M-1)}+K^{NM}$

代码：

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
const int maxn=10005;
const int mod = 1e9+7;
using namespace std;
typedef long long ll;
long double A[maxn];ll ksm (ll a,ll b ,ll m){ll ans = 1;while(b){if(b&1) ans = (ans * a) % m;b >>= 1;a = (a * a) % m;}return ans; 
}int main ()
{//freopen("D:\\input.txt", "r", stdin);//freopen("D:\\output.txt", "w", stdout);int t,n,m,k;cin>>t;for(int cas = 1; cas <= t;cas++){cin>>n>>m>>k;ll ans = 0;for(int i = 2;i <= k ;i++)ans = (ans + ksm(i-1,m+n-2,mod)) % mod;ans = ans * m % mod * n % mod;ans = ans * ksm(k,(n-1)*(m-1),mod) % mod;ans = (ans + ksm(k,n*m,mod)) % mod;cout<<"Case #"<<cas <<": "<< ans << endl;}return 0;
}

这篇关于2016ACM ECfinal补题题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---