[hihocoder][Offer收割]编程练习赛48

折线中点

#pragma comment(linker, "/STACK:102400000,102400000")

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<functional>

#include<math.h>

//#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef queue<int> QI;

void makedata() {

    freopen("input.txt", "w", stdout);

    fclose(stdout);

}

double x[], y[];

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    //makedata();

    //std::ios::sync_with_stdio(0), cin.tie(0);

    int n;

    scanf("%d", &n);

    for (int i = ; i < n; i++) scanf("%lf%lf", &x[i], &y[i]);

    double l = ;

    for (int i = ; i < n; i++) l += sqrt((x[i] - x[i - ]) * (x[i] - x[i - ]) + (y[i] - y[i - ]) * (y[i] - y[i - ]));

    l /= 2.0;

    for (int i = ; i < n; i++) {

        double tmp = sqrt((x[i] - x[i - ]) * (x[i] - x[i - ]) + (y[i] - y[i - ]) * (y[i] - y[i - ]));

        if (l > tmp) l -= tmp;

        else {

            printf("%.1lf %.1lf\n", x[i - ] + (l / tmp) * (x[i] - x[i - ]), y[i - ] + (l / tmp) * (y[i] - y[i - ]));

            break;

        }

    }

    return ;

}

最小先序遍历

#pragma comment(linker, "/STACK:102400000,102400000")

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<functional>

#include<math.h>

//#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef queue<int> QI;

void makedata() {

    freopen("input.txt", "w", stdout);

    fclose(stdout);

}

int a[];

void solve(int l, int r) {

    if (l > r) return;

    int x = l;

    for (int i = l; i <= r; i++) {

        if (a[i] < a[x]) x = i;

    }

    cout << a[x] << endl;

    solve(l, x - );

    solve(x + , r);

}

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    //makedata();

    std::ios::sync_with_stdio(), cin.tie();

    int n;

    cin >> n;

    for (int i = ; i <= n; i++) cin >> a[i];

    solve(, n);

    return ;

}

假期计划

#pragma comment(linker, "/STACK:102400000,102400000")

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<functional>

#include<math.h>

//#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef queue<int> QI;

void makedata() {

    freopen("input.txt", "w", stdout);

    fclose(stdout);

}

class AandC {

public:

    long long *fac, *inv, *f;

    long long mod;

    AandC(long long m, int n) {

        mod = m;

        fac=(long long *)malloc((n) * sizeof(long long));

        inv=(long long *)malloc((n) * sizeof(long long));

        f=(long long *)malloc((n) * sizeof(long long));

        fac[] = fac[] = inv[] = inv[] = f[] = f[] = ;

        for (int i = ; i < n; i++) {

            fac[i] = fac[i - ] * i % mod;

            f[i] = (mod - mod / i) * f[mod % i] % mod;

            inv[i] = inv[i - ] * f[i] % mod;

        }

    }

    //choose b from a

    long long A(int a, int b) {

        return fac[a] * inv[a - b] % mod;

    }

    long long C(int a, int b) {

        return fac[a] * inv[b] % mod * inv[a - b] % mod;

    }

};

const lint mod = ;

AandC ac(mod,);

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    //makedata();

    std::ios::sync_with_stdio(), cin.tie();

    int n, a, b;

    cin >> n >> a >> b;

    lint ans = ;

    for (int i = ; i < n; i++) {

        if (i > b || n - i > a || n - i < ) continue;

        ans += (n - i - ) * ac.C(b - , i - ) % mod * ac.C(a - , n - i - ) % mod * ac.A(a, a) % mod * ac.A(b, b) % mod;

        ans %= mod;

    }

    cout << ans << endl;

    return ;

}

矩阵深度