Codeforces 8VC Venture Cup 2016 - Elimination Round
A:
求有多少子串能走回起点 n<=200
n^3暴力
B:
你可以将RR-->R(GG-->G BB-->B)
或者RG-->B(RB-->G BG-->R)
给你n个,求最后能变成啥,字典序输出
n<=200
结论题:
如果没有R,没有G,那么答案一定是B
如果没有R,有G和B,那么:
G>=2 可能有B
B>=2 可能有G
无论如何,都可以出R
C:
求(从1开始)最少多少个数,能分成两个集合
一个集合中包含至少n个2的倍数,另一个集合中包含至少m个3的倍数
n,m<=1e6
直接从1开始暴力答案,数学计算下即可
D:
有两个人摸球
第一次A>B 第二次A>B 第三次A<B
求三次A之和<B之和的概率
球数n<=2000,球上数字<=5000
每次一实际上是赚一个差值
那么暴力把差值算出来,每次随机取一个
变成了在n个差值里,找有多少组A+B<C
因为数字就5000,部分和什么的乱搞下即可....
E:
构造一个数列,使得平均数和中位数差最大
现场没做出来
F:
把n个人分成若干组,每个人有个特征值
每一组的差异值为最大特征值-最小特征值
求差异值之和<=k的方案数
n<=200,k<=1000,特征值<=500
可以写dp.....
先排序
dp(i,j,k):到第i个人为止,你目前有j组是还没找到末尾的,目前差异值为k
转移:
考虑,如果某一组还没有结尾,那么它将来的最大值a(i)-最小值a(j)可以拆分成
a(i)-a(i-1)+a(i-1)-a(i-2)....+a(j+1)-a(j)
如此拆分后,可以发现,每一组没有末尾的都会消耗一份a(i)-a(i-1)
就按照这思路下去即可
代码如下:
A:
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char a[205];
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
scanf("%d",&n);
scanf("%s",a);
int i,j;
int sum=0;
for (i=0;a[i]!='\0';i++)
{
for (j=i;a[j]!='\0';j++)
{
int x=0,y=0;
int k;
for (k=i;k<=j;k++)
{
if (a[k]=='L') x++;
if (a[k]=='R') x--;
if (a[k]=='U') y++;
if (a[k]=='D') y--;
}
if ((x==0)&&(y==0)) sum++;
}
}
printf("%d\n",sum);
return 0;
}
B:
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char a[205];
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
scanf("%d",&n);
scanf("%s",a);
int i;
int r=0,g=0,b=0;
for (i=0;i<n;i++)
{
if (a[i]=='R') r++;
if (a[i]=='G') g++;
if (a[i]=='B') b++;
}
if ((r==0)+(g==0)+(b==0)==2)
{
if (r!=0) putchar('R');
if (g!=0) putchar('G');
if (b!=0) putchar('B');
return 0;
}
else if ((r==0)+(g==0)+(b==0)==1)
{
if (r==0)
{
if (g>1) putchar('B');
if (b>1) putchar('G');
putchar('R');
}
if (g==0)
{
if (r>1) putchar('B');
putchar('G');
if (b>1) putchar('R');
}
if (b==0)
{
putchar('B');
if (r>1) putchar('G');
if (g>1) putchar('R');
}
}
else
{
puts("BGR");
}
return 0;
}
C:
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n,m;
scanf("%d%d",&n,&m);
int i;
for (i=1;;i++)
{
int x1=i/2;
int x2=i/3;
int x3=i/6;
x1-=x3;
x2-=x3;
x1=min(x1,n);
x2=min(x2,m);
if (x1+x2+x3>=n+m)
{
printf("%d\n",i);
return 0;
}
}
return 0;
}
D:
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int a[2005];
int sum[10005];
int tot[10005];
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
scanf("%d",&n);
int i;
for (i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
int j;
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
if (a[i]<=a[j]) continue;
sum[a[i]-a[j]]++;
}
}
tot[0]=0;
for (i=1;i<=10000;i++)
{
tot[i]=tot[i-1]+sum[i];
}
long long ans=0;
for (i=1;i<=5000;i++)
{
int j;
for (j=1;j<=5000;j++)
{
ans+=(long long)sum[i]*sum[j]*tot[i+j];
}
}
printf("%.12lf\n",((long long)tot[5000]*tot[5000]*tot[5000]-ans)*1.0/tot[5000]/tot[5000]/tot[5000]);
return 0;
}
F:
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int dp[205][205][1505];
int a[205];
const int modo=1000000007;
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n,k;
scanf("%d%d",&n,&k);
int i;
for (i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
dp[0][0][0]=1;
for (i=0;i<n-1;i++)
{
int j;
for (j=0;j<n;j++)
{
int l;
for (l=0;l<=k;l++)
{
if (l+j*(a[i+1]-a[i])<=k)
{
dp[i+1][j][l+j*(a[i+1]-a[i])]+=dp[i][j][l];
dp[i+1][j][l+j*(a[i+1]-a[i])]%=modo;
}
if (l+(j+1)*(a[i+1]-a[i])<=k)
{
dp[i+1][j+1][l+(j+1)*(a[i+1]-a[i])]+=dp[i][j][l];
dp[i+1][j+1][l+(j+1)*(a[i+1]-a[i])]%=modo;
}
if (l+j*(a[i+1]-a[i])<=k)
{
dp[i+1][j][l+j*(a[i+1]-a[i])]+=(long long)dp[i][j][l]*j%modo;
dp[i+1][j][l+j*(a[i+1]-a[i])]%=modo;
}
if (j==0) continue;
if (l+(j-1)*(a[i+1]-a[i])<=k)
{
dp[i+1][j-1][l+(j-1)*(a[i+1]-a[i])]+=(long long)dp[i][j][l]*j%modo;
dp[i+1][j-1][l+(j-1)*(a[i+1]-a[i])]%=modo;
}
}
}
}
int sum=0;
int l;
for (l=0;l<=k;l++)
{
sum+=dp[n-1][0][l];
sum%=modo;
sum+=dp[n-1][1][l];
sum%=modo;
}
printf("%d\n",sum);
return 0;
}
评论 (0)