Codeforces 8VC Venture Cup 2016

本文主要是介绍Codeforces 8VC Venture Cup 2016 - Elimination Round，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

C. Block Towers

贪心，先分别尽量用低的高度，标记哪些高度用过了。对于那些冲突的，选一个尽可能低的来用。二分答案也可以，并且还有用公式 $O(1)$ 的解法。

#include <bits/stdc++.h>using namespace std;#define ll long long bool vis[5000010];int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){vis[i*2]=1;}for(int i=1;i<=m;i++){vis[i*3]=1;}int top_2 = n*2;int top_3 = m*3;int MAX = min(top_2,top_3);for(int i=6;i<=MAX;i+=6){int go2=top_2+2;while(vis[go2]){go2+=2;}int go3=top_3+3;while(vis[go3]){go3+=3;}if(go2<=go3){top_2=go2;vis[go2]=1;}else{top_3=go3;vis[go3]=1;}}cout<<max(top_2,top_3)<<endl;return 0;
}

D. Jerry’s Protest

基础的概率题。可以先算第一局分差为 $i$ 的概率 $p_1(i)$ ，然后算前两局合起来分差为 $i$ 的概率 $p_2(i)$ ，最后枚举第三局分差，乘上 $p_2$ 的前缀和。

#include <bits/stdc++.h>using namespace std;#define ll long long int a[2010];double p[10010];
double p2[10010];
double sum[10010];int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);double pro = 1.0/(n*(n-1)/2);for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){p[a[j]-a[i]] += pro;}}for(int i=1;i<=5000;i++){for(int j=1;j<=5000;j++){p2[i+j]+=p[i]*p[j];}}for(int i=1;i<=10000;i++){sum[i]=sum[i-1]+p2[i];}double ans = 0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){int delta = a[j]-a[i];ans += pro*sum[delta-1];}}printf("%.10f",ans);return 0;
}

E. Simple Skewness

大多数人应该都是用二分/三分来做的。这里有个 $O(n)$ 的解法。。首先可以证明，最优解总可以只包含奇数个元素，也就是只有一个中位数。排序后，对于给定的中位数 $x(i)$ 和给定的集合大小 $2*len+1$ ，集合肯定由 $x(i-len)$ ~ $x(i)$ 和 $x(n+1-len)$ ~ $x(n)$ 组成。枚举中位数，然后动态维护集合，每次加入 $x(i)$ 和 $x(n-len+1)$ ，然后不断删除 $x(i-len)$ 和 $x(n-len+1)$ ，直到这两个数的均值小于整个集合的均值。因为这样做中位数不会动而平均数会不断变大。

#include <bits/stdc++.h>using namespace std;int n;
int x[200010];
int a[1000010]; int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d",&x[i]);a[x[i]]++;}//sort(x+1,x+n+1);int k=1;for(int i=0;i<=1000000;i++){while(a[i]--){x[k++]=i;}}if(n<=2){cout<<1<<endl;cout<<x[1]<<endl;}else{int seglen=0;int median=1;double MAX=0;int cnt=1;double sum = x[1];int len = 0;for(int i=2;i<n;i++){len++;cnt+=2;sum+=x[i];sum+=x[n+1-len];while( (x[i-len]+x[n+1-len])/2.0 <= sum/cnt && len>1){sum-=x[i-len];sum-=x[n+1-len];len--;cnt-=2;}if((sum/cnt-x[i])>MAX){MAX = (sum/cnt-x[i]);seglen=len;median=i;}}cout<<seglen*2+1<<endl;for(int i=median-seglen;i<=median;i++){printf("%d ",x[i]);}for(int i=n-seglen+1;i<=n;i++){printf("%d ",x[i]);}}return 0;
}

F. Group Projects

明知道这题是DP，还是想不出来，太弱了。。（先排序）状态为 $dp(i,j,k)$ ，指的是当前考察到了第 $i$ 个元素，有 $j$ 个组还可以加入后面的元素，当前总的不平衡为 k <script type="math/tex" id="MathJax-Element-1167">k</script>。每次考察到新的元素，可以加入到之前的某个组，可以单独成组并不允许继续加入或允许继续加入，状态转移见代码。

#include <bits/stdc++.h>using namespace std;#define ll long longconst int mod = 1e9+7;int a[210];ll dp[2][210][1010];int main(){int n,K;cin>>n>>K;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int cur=0;int pre=1;dp[cur][0][0]=1;a[0]=a[1];for(int i=1;i<=n;i++){swap(cur,pre);memset(dp[cur],0,sizeof(dp[cur]));for(int k=0;k<=K;k++){dp[cur][0][k] += dp[pre][0][k]; dp[cur][1][k] += dp[pre][0][k];dp[cur][0][k] %= mod;dp[cur][1][k] %= mod;}for(int j=1;j<i;j++){for(int k=0;k<=K;k++){if(k-j*(a[i]-a[i-1])<0)continue; dp[cur][j-1][k] += j*dp[pre][j][k-j*(a[i]-a[i-1])];dp[cur][j][k] += (j+1)*dp[pre][j][k-j*(a[i]-a[i-1])];   dp[cur][j+1][k] += dp[pre][j][k-j*(a[i]-a[i-1])];dp[cur][j-1][k] %= mod;dp[cur][j][k] %= mod;dp[cur][j+1][k] %= mod;}}}int ans = 0;for(int k=0;k<=K;k++){ans+=dp[cur][0][k];ans%=mod;}cout<<ans<<endl;return 0;
}