absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
Topcoder 681 Div.1 (Unrated)
Codeforces Round #343 (Div. 2 Only)

Codeforces 8VC Venture Cup 2016 - Elimination Round

absi2011 posted @ Feb 14, 2016 05:00:48 PM in 网上比赛 with tags CF Div.1 Div.2 , 349 阅读

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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter