Yandex.Algorithm Online Round 3 Sunday, June 15, 2014

Problem A. Distance 求樹中距離恰好為2的結點對的個數

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int edge[100007];

int main(){
    int t;
    while(scanf("%d",&t)!=EOF){
        for(int i = 1;i <= t; i++)
            edge[i] = 0;
        int u,v;
        for(int i =1 ;i < t; i++){
            scanf("%d%d",&v,&u);
            edge[u]++;
            edge[v]++;
        }
        long long ans = 0;
        for(int i = 1;i <= t; i++){
            ans += (1ll*edge[i]*edge[i]-edge[i])/2;
        }
        cout<<ans<<endl;
    }
    return 0;
}
           

Problem B. Science

求長度為n隻有01的字元串，包含01{k}0子串個數的期望 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

struct Node{
    double max[107][107];
};
int k;
Node operator *(Node a,Node b){
    Node c;
    memset(c.max,0,sizeof(c.max));
    for(int i = 0;i <= k + 2; i++){
        for(int j = 0;j <= k+2; j++){
            for(int l = 0;l <= k+2; l++){
                c.max[i][j] += a.max[i][l]*b.max[l][j];
            }
        }
    }
    return c;
}
Node x,y,z;
int main(){
    long long n;
    while(cin>>n>>k){
        memset(x.max,0,sizeof(x.max));
        for(int i = 0;i <= k+2 ;i++)
            x.max[i][i] = 1.0;
        memset(y.max,0,sizeof(y.max));
        for(int i = 0;i <= k; i++)
            y.max[0][i] = 0.5;
        for(int i = 1;i <= k+1; i++)
            y.max[i][i-1] = 0.5;
        y.max[0][k+1] = 0.5;
        y.max[k+1][k+1] = 0.5;
        y.max[k+2][k] = 0.5;
        y.max[k+2][k+2] = 1.0;
        n--;
        while(n){
            if(n&1) x = x*y;
            y = y * y;
            n /= 2;
        }
        double ans = x.max[k+2][0]*0.5 + x.max[k+2][k+1]*0.5;
        printf("%0.16f\n",ans);
    }
    return 0;
}













           

Problem C. Intervals

求有幾個區間，在這個區間中存在兩個數，內插補點為d

#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<cstdio>
#define ll long long
using namespace std;
map<ll,int> haha;
int main(){
    int n,d;
    while(scanf("%d%d",&n,&d)!=EOF){
        haha.clear();
        int be = 0;
        haha[0] = 0;
        ll sum = 0,u;
        ll ans = 0;
        for(int i = 1;i <= n; i++){
            scanf("%I64d",&u);
            if(haha.find(u-d)!= haha.end())
                be = max(be,haha[u-d]);
            if(haha.find(u+d) != haha.end())
                be = max(be,haha[u+d]);
            ans += be;
            haha[u] = i;
        }
        cout<<ans<<endl;
    }
    return 0;
}
           

F. Weird Game

對于長度為N的一維格子，每次可以從中選出恰好長度為L，且不包含被染色位置的格子。

如果找不到可以染色的區間了。算輸。

sg函數 對于可以選擇長度為L進行染色，算出 格子長度為1-7000的sg函數。

由于對于一個N，要枚舉分出的兩個線段長度，需要N的轉移，是以是N*N的複雜度，會逾時。

打表找規律，發現大于8的L的必敗态有固定的增長速度。于是，打表。

小于8的就直接sg函數做了就行。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<iostream>
#include<set>
using namespace std;

int check[7000];
int sg[7000];
set<int> haha[70001];

int change[14][2]={
2,0,
2,0,
4,-2,
4,-2,
4,0,
4,-2,
8,-2,
4,-2,
8,0,
8,-2,
16,-6,
4,0
};

int main(){
    int cnt = 1;
    for(int i = 2;i <= 7;i++){
        memset(sg,0,sizeof(sg));
        for(int j = i; j <= 7000; j++){
            int u = j - i;
            for(int k = 0;k + k <= u; k++){
                check[sg[k]^sg[u-k]] = cnt;
            }
            for(int k = 0;;k++){
                if(check[k] != cnt){
                    sg[j] = k;
                    break;
                }
            }
            cnt++;
        }
        int f = 0;
        for(int j = i;j <= 7000; j++){
           if(sg[j] == 0){
               haha[i].insert(j);
           }
        }
    }

    for(int i = 8; i<=7000;i++){
        int j = i -1;
        for(int l = 0;l < 12; l++){
            j = j + change[l][0]*i+change[l][1];
            if(j > 7000) break;
            haha[i].insert(j);
        }
    }


    int n;
    while(scanf("%d",&n)!=EOF){
        if(n % 2 == 0) printf("S");
        else printf("F");
        for(int i = 2;i <= n; i++){
            if(haha[i].find(n) != haha[i].end()) printf("S");
            else printf("F");
        }
        printf("\n");
    }
    return 0;
}