POJ 3015 Expected Difference

卡(int64)超久＝＝ 一卡卡兩小時＝＝

#include<cstdio>
#include<cstdlib>

long double arr[50001];
long double sig[50001];

int main(){
    int n, m;
    for(;;){
        scanf("%d %d", &n, &m);
        if(n + m == 0)
            break;

        arr[n] = m*(m-1)/(long double)((n-m+2)*(n-m+1));
        for(int lx = n-1;lx >= 0;lx--)
            arr[lx] = arr[lx+1]*(((lx+1)-(m-2))/((long double)(lx+1)));

        sig[0] = arr[0];
        for(int lx= 1;lx <= n;lx++)
            sig[lx] = sig[lx-1] + arr[lx];

        int val;
        long double ans= 0;
        for(int lx = 0;lx < n;lx++){
            scanf("%d", &val);
            long double gv = (long double) val;
            if(lx == 0)
                ans -= gv*sig[n-2];
            else
                ans -= gv*(sig[n-2-lx] - sig[lx-1]);
        }
        printf("%.3LF\n", ans);
    }
    return 0;
}

Testing Round #11, problem: (B) New York Hotel

最近都沒在寫QQ

分出
x+y, -x+y, x-y, -x-y 後greedy

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define INF 2000000001
using namespace std;
int main(){
    int n, m;scanf("%d %d", &n, &m);
    int C, H;
    int p[4], x, y;
    scanf("%d", &C);
    for(int lx = 0;lx < 4;lx++)
        p[lx] = INF;
    for(int lx = 0;lx < C;lx++){
        scanf("%d %d", &x, &y);
        p[0] = min(p[0], x+y);
        p[1] = min(p[1], -x+y);
        p[2] = min(p[2], x-y);
        p[3] = min(p[3], -x-y);
    }
    scanf("%d", &H);
    int d = INF, ih;
    for(int lx = 0;lx < H;lx++){
        scanf("%d %d", &x, &y);
        int cal = max(max(x+y - p[0], -x+y - p[1]), max(x-y - p[2], -x-y-p[3]));
        if(cal < d)
            d = cal, ih = lx+1;
    }
    printf("%d\n%d\n", d, ih);
    return 0;
}

TIOJ 1214 樹論 之 樹同構測試

Tree Hash

#include<cstdio>
#include<cstdlib>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int int64;

const int64 P = 100000000007LL;
const int64 X = 107;
vector<int> tree[2][101];

int64 hasht(int fat, int rt, int index){
    vector<int64> ht;
    for(int lx = 0;lx < tree[index][rt].size();lx++){
        int ind = tree[index][rt][lx];
        if(ind == fat) continue;
        ht.push_back(hasht(rt, ind, index));
    }
    sort(ht.begin(), ht.end());
    int64 XN = 1;
    int64 ret = 23;
    for(int lx = 0;lx < ht.size();lx++){
        ret += ht[lx]*XN;
        ret %= P;
        XN *= X;
        XN %= P;
    }
    return ret^34567;
}
int main()
{
    int n, a, b;
    for(;;){
        scanf("%d", &n);
        if(n == 0) break;
        for(int lx = 0;lx < n;lx++)
            tree[0][lx].clear(), tree[1][lx].clear();
        for(int lx = 0;lx < n-1;lx++){
            scanf("%d %d", &a, &b); a--, b--;
            tree[0][a].push_back(b);
            tree[0][b].push_back(a);
        }
        for(int lx = 0;lx < n-1;lx++){
            scanf("%d %d", &a, &b); a--, b--;
            tree[1][a].push_back(b);
            tree[1][b].push_back(a);
        }
        set<int64> hashv[2];
        for(int li = 0;li < 2;li++)
            for(int lx = 0;lx < n;lx++)
                hashv[li].insert(hasht(-1, lx, li));
        bool same = false;
        for(set<int64>::iterator it = hashv[0].begin(); it != hashv[0].end(); it++)
            if(hashv[1].count(*it))
                same = true;
        puts(same?"Same":"Different");
    }
    return 0;
}

Codeforces Round #280 (Div. 2), problem: (E) Vanya and Field

還是寫的有點慢

#include<cstdio>
#include<cstdlib>
typedef long long int int64;
int arr[1000000] = {0};
bool seive[1000001] = {0};
int64 phi[1000001];
int64 _pow(int64 a, int n, int64 m){
    a%=m;
    if(n == 0) return 1;
    if(n == 1) return a;
    int64 half = _pow(a, n/2, m);
    half = (half*half)%m;
    if(n&1) return (half*a)%m;
    return half;
}
int main()
{
    for(int lx = 1;lx <= 1000000;lx++)
        phi[lx] = lx;
    for(int lx = 2;lx <= 1000000;lx++)
        if(seive[lx] == 0)
            for(int ly = 1;ly*lx <= 1000000;ly++)
                seive[ly*lx] = 1, phi[ly*lx] = phi[ly*lx]/lx*(lx-1);
    int64 n, m, dx, dy;;
    scanf("%I64d %I64d %I64d %I64d", &n, &m, &dx, &dy);
    for(int lx = 0;lx < m;lx++){
        int64 a, b;scanf("%I64d %I64d", &a, &b);
        int64 nn = (b*_pow(dy, phi[n]-1, n))%n;
        int64 p = ((a - dx*nn)%n + n)%n;
//        printf("step = %I64d, add on %I64d\n", nn, p);
        arr[p]++;
    }
    int maxpos = 0;
    for(int lx = 1;lx < n;lx++)
        if(arr[lx] > arr[maxpos])
            maxpos = lx;
    printf("%d 0\n", maxpos);
//    while(1);
    return 0;
}