学步园

1006 概率

P[find(i)] = 1/6(P[i-1]+P[i-2]+P[i-3]+P[i-4]+P[i-5]+P[i-6]); //概率

E[find(i)] = 1/6(sum(P[i-6, i-1])+sum(E[i-6, i-1])); //期望

ans = sum(E[n, n+5]);

double P[N];
double E[N];
int fa[N];

void init(int n)
{
    for(int i=0; i<=n; i++)
    {
        P[i] = 0;
        E[i] = 0;
        fa[i] = i;
    }
    P[0] = 1;
}

int find(int x)
{
    if(x==fa[x]) return x;
    return fa[x] = find(fa[x]);
}

int main()
{
    int n, m, x, y;
    while(scanf("%d%d", &n, &m), n+m)
    {
        init(n+7);
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d", &x, &y);
            fa[x] = y;
        }
        for(int i=0; i<n; i++)
        {
            for(int j=1; j<=6; j++)
            {
                int tmp = find(i+j);
                P[tmp] += P[i]/6.0;
                E[tmp] += (E[i]+P[i])/6.0;
            }
        }
        double ans = 0;
        for(int i=0; i<6; i++)
            ans += E[n+i];
        printf("%.4f\n", ans);
    }
	return 0;
}

1001 乱搞

对X离线排序，对于每个X开一个set放Y。对于每个炸弹，二分X的区间，在区间内二分Y。 BFS

1004 暴力

我的算法是——枚举符号放的位置dfs ， 然后枚举等号位置，Check。

string str;
int lis[20] , ans , n;
LL dp[20][20];
void check(int m){

    for (int i = 1 ; i <= m ; ++i){
        LL sumpre = 0 , sumnex = 0;
        bool pre = true;
        for (int j = 1 ; j <= m ; ++j){

            if (pre) sumpre += dp[lis[j - 1] + 1 ][lis[j]];
            else sumnex += dp[lis[j -1] + 1] [lis[j]];
            if (i == j) pre= false;
        }
        if (pre) return;
        sumnex += dp[lis[m] + 1 ][n];/*
        if(sumpre == sumnex) {
            printf("%I64d %I64d   %d\n",sumpre , sumnex , i);
            for (int k = 1 ; k <= m ; ++k){
                printf("%d ",lis[k]);
            }
            printf("\n");
        }*/
        if (sumnex == sumpre && sumpre) ++ans;
    }
}
void dfs(int x){
    for (lis[x] = lis[x - 1 ] + 1 ; lis[x] < n ; ++lis[x]){
        check(x);
        dfs(x + 1);
    }
    return;
}

void init(){
    for (int i = 1 ; i <= n ; ++i)
        for (int j = i ; j <= n ; ++j){
            dp[i][j] = 0;
            for (int k = i ; k <= j ; ++k)
                dp[i][j] = dp[i][j] * 10 + str[k - 1] - '0';
        }
}
void solve(){
    n = str.length();
    init();
    ans = 0;
    lis[0] = 0;
    dfs(1);
    printf("%d\n",ans);
}
int main(){
    while (cin >> str , str != "END") solve();
}

1005 模板题

1007 费用流