天天看點
傳回

2014 BUPT 新生排位賽11

A 小妹妹的個數

連結：http://code.bupt.edu.cn/problem/p/488/

思路：亂搞法，平方分割加打表,還沒有寫出來。

B 田田背課文

連結：http://code.bupt.edu.cn/problem/p/480/

大緻題意：求一個字元串的最短不重複子串。

思路：其實就是上次的最長重疊子串+1，姿勢有很多種，直接暴力，hash+vector，字尾數組等等~

code：

#include <iostream>
#include <cstring>
#include <cstdlib>
#include<cstdio>
#include <algorithm>
#include <vector>
#include <set>
#define INF 1000000000
#define eps 1e-9
using namespace std;
const int MAX_E=1;
const int MAX_N=1000005;
const int MAX_M=10007;
typedef unsigned long long ull;
const ull B=9937;
char st[MAX_N];
vector<ull>vv[MAX_M];
void solve()
{
    for(int i=0;i<MAX_M;i++) vv[i].clear();
    int l=strlen(st);
    ull kk;
    ull tt;
    int dd;
    bool flag;
    for(int i=1;i<=l;i++){
        kk=0;
        tt=1;
        flag=1;
        for(int j=0;j<i;j++){
            kk=kk*B+st[j];
            tt*=B;
        }
        dd=kk%MAX_M;
        vv[dd].push_back(kk);
        for(int j=1;j+i-1<l;j++){
            kk=kk*B+st[j+i-1]-st[j-1]*tt;
            dd=kk%MAX_M;
            for(int i=0;i<vv[dd].size();i++){
                if(vv[dd][i]==kk){
                    flag=0;
                    break;
                }
            }
            if(flag==0) break;
            vv[dd].push_back(kk);
        }
        if(flag==1){
            printf("%d\n",i);
            return ;
        }
    }
}
 
int main()
{
    while(scanf("%s",st)!=EOF){
        solve();
    }
}

C 小妹妹采蘑菇

連結：http://code.bupt.edu.cn/problem/p/478/

思路：其實我一開始想的是dp的方法，後來zy給我說是找規律，我就一直開始找規律，最後就是一個幾何概型（其實感覺直接想就可以）。對于采n種不同的蘑菇，我們可以這樣想，一開始取任意一種不重複的蘑菇的機率是1，第二次取一種不跟剛才情況重複的蘑菇的機率是(n-1)/n，第三次的機率是(n-2)/n........... 是以我們就能得到每一步的最小步數的期望就是機率的倒數，第一次是1，第二次是(n-1)/(n),第三次是(n-2)/n..........這樣将每一種情況加起來就能得到總的最小步數期望。

code：

#include <iostream>
#include <cstring>
#include <cstdlib>
#include<cstdio>
#include <algorithm>
#include <vector>
#include <set>
#define INF 1000000000
#define eps 1e-9
using namespace std;
const int MAX_E=1;
const int MAX_N=1000005;
const int MAX_M=10007;
int main()
{
    double a[110];
    a[1]=1;
    for(int i=2;i<=100;i++){
        double mid=1;
        for(int j=i-1;j>=1;j--) mid+=(double)i/j;
        a[i]=mid;
    }
    int n;
    while(scanf("%d",&n)!=EOF){
        printf("%.6f\n",a[n]);
    }
}

我感覺很有必要用機率dp的方法再寫一次，待更新~~~~

~動态規劃的方法~：：dp[i][j]表示用j步取i個不同的蘑菇的機率，n表示蘑菇的種樹，

狀态轉移方程是 dp[i][j]=dp[i-1][j-1]*(n-i+1)/n+dp[i][j-1]*(i)/n;   (i<n)

dp[i][j]=dp[i-1][j-1]*(n-i+1)/n; (i==n)   因為取到n個的時候就結束了，是以不可能由第二種方案再轉移過來

dp的邊界條件 (1)dp[1][1]=1   (2) for(int i=2;i<=MAX_N;i++)  dp[1][i]=dp[1][i-1]*(1/n);  其中MAX_N是我設定的最大步數，此題我設定了3000就可以過了

code:

#include <iostream>
#include <cstring>
#include <cstdlib>
#include<cstdio>
#include <algorithm>
#include <vector>
#include <set>
#define INF 1000000000
#define eps 1e-9
using namespace std;
const int MAX_E=1;
const int MAX_N=3005;
const int MAX_M=110;

double dp[MAX_M][MAX_N];
double ans[MAX_M];
void Dp()
{
    memset(dp,0,sizeof(dp));
    memset(ans,0,sizeof(ans));
    for(int n=1;n<=100;n++){
        dp[1][1]=1.00;
        for(int i=2;i<=MAX_N;i++) dp[1][i]=dp[1][i-1]*((double)1/n);
        for(int i=2;i<=n;i++){
            for(int j=i;j<=MAX_N;j++){
                if(i==n) dp[i][j]=dp[i-1][j-1]*((double)(n-i+1)/n);
                else dp[i][j]=dp[i-1][j-1]*((double)(n-i+1)/n)+dp[i][j-1]*((double)i/n);
            }
        }
        for(int k=n;k<=MAX_N;k++) ans[n]+=(double)k*dp[n][k];
    }
    ans[1]=1.00;
}
int main()
{
    int n;
    Dp();
    while(scanf("%d",&n)!=EOF){
        printf("%.6f\n",ans[n]);
    }
    return 0;
}

還有一個亂搞版的，當時什麼思考的都不清晰，就寫了一個版本還過了，寫題解的時候才發現有這麼多的問題，求指點為什麼能過。。

code:

#include <iostream>
#include <cstring>
#include <cstdlib>
#include<cstdio>
#include <algorithm>
#include <vector>
#include <set>
#define INF 1000000000
#define eps 1e-9
using namespace std;
const int MAX_E=1;
const int MAX_N=3005;
const int MAX_M=110;
 
double dp[MAX_M][MAX_N];
double ans[MAX_M];
void Dp()
{
    memset(dp,0,sizeof(dp));
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=100;i++){
        dp[1][1]=1.00;
        for(int j=2;j<=i;j++){
            for(int k=j;k<=MAX_N;k++){
                dp[j][k]=dp[j-1][k-1]*((double)(i-j+1)/i)+dp[j][k-1]*((double)(j-1)/i);
            }
        }
        for(int k=i;k<=MAX_N;k++) ans[i]+=(double)k*dp[i][k];
    }
}
int main()
{
    int n;
    Dp();
    while(scanf("%d",&n)!=EOF){
        printf("%.6f\n",ans[n]);
    }
    return 0;
}

D 焦級長的雷射炮

連結：http://code.bupt.edu.cn/problem/p/482/

大緻題意：

思路：

code：

E 小妹妹去劃船

連結：http://code.bupt.edu.cn/problem/p/489/

思路：純模拟，因為可以放錨是以一定不會向偏離目的地的方向前進的，是以就計算出來兩點之間的坐标差，分成四個方向，掃一遍字元串就行了，要注意區間的開閉以及一些特殊的情況。

code：

#include <iostream>
#include <cstring>
#include <cstdlib>
#include<cstdio>
#include <algorithm>
#include <vector>
#include <set>
#define INF 1000000000
#define eps 1e-9
using namespace std;
const int MAX_E=1;
const int MAX_N=100010;
const int MAX_M=10007;
 
int main()
{
    int sx,sy,ex,ey,t;
    char st[MAX_N];
    int mx,my,l;
    bool flag;
    while(scanf("%d%d%d%d%d",&t,&sx,&sy,&ex,&ey)!=EOF){
        scanf("%s",st);
        mx=ex-sx;
        my=ey-sy;
        l=strlen(st);
        flag=1;
        if(mx>0&&my>=0){
            for(int i=0;i<l;i++){
                if(st[i]=='N'&&my>0) my--;
                if(st[i]=='E'&&mx>0) mx--;
                if(my==0&&mx==0){
                    flag=0;
                    printf("%d\n",i+1);break;
                }
            }
        }
        else if(mx<=0&&my>0){
            mx=-mx;
            for(int i=0;i<l;i++){
                if(st[i]=='N'&&my>0) my--;
                if(st[i]=='W'&&mx>0) mx--;
                if(my==0&&mx==0){
                    flag=0;
                    printf("%d\n",i+1);break;
                }
            }
        }
        else if(mx<0&&my<=0){
            mx=-mx;
            my=-my;
            for(int i=0;i<l;i++){
                if(st[i]=='S'&&my>0) my--;
                if(st[i]=='W'&&mx>0) mx--;
                if(my==0&&mx==0){
                    flag=0;
                    printf("%d\n",i+1);break;
                }
            }
        }
        else if(mx>=0&&my<0){
            my=-my;
            for(int i=0;i<l;i++){
                if(st[i]=='S'&&my>0) my--;
                if(st[i]=='W'&&mx>0) mx--;
                if(my==0&&mx==0){
                    flag=0;
                    printf("%d\n",i+1);break;
                }
            }
        }
        else if(mx==0&&my==0){
            flag=0;
            printf("0\n");
        }
        if(flag) printf("-1\n");
    }
}
排位賽
上一篇: 2014 BUPT 新生排位賽09
下一篇: 2014 BUPT 新生排位賽04

繼續閱讀