[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[200], y[200];

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 = 0; i < n; i++) scanf("%lf%lf", &x[i], &y[i]);
double l = 0;
for (int i = 1; i < n; i++) l += sqrt((x[i] - x[i - 1]) * (x[i] - x[i - 1]) + (y[i] - y[i - 1]) * (y[i] - y[i - 1]));
    l /= 2.0;
for (int i = 1; i < n; i++) {
double tmp = sqrt((x[i] - x[i - 1]) * (x[i] - x[i - 1]) + (y[i] - y[i - 1]) * (y[i] - y[i - 1]));
if (l > tmp) l -= tmp;
else {
            printf("%.1lf %.1lf\n", x[i - 1] + (l / tmp) * (x[i] - x[i - 1]), y[i - 1] + (l / tmp) * (y[i] - y[i - 1]));
break;
        }
    }
return 0;
}

 

最小先序遍历

#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[200];
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 - 1);
    solve(x + 1, r);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
//makedata();
    std::ios::sync_with_stdio(0), cin.tie(0);
int n;
    cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
    solve(1, n);
return 0;
}

 

假期计划

#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[0] = fac[1] = inv[0] = inv[1] = f[0] = f[1] = 1;
for (int i = 2; i < n; i++) {
            fac[i] = fac[i - 1] * i % mod;
            f[i] = (mod - mod / i) * f[mod % i] % mod;
            inv[i] = inv[i - 1] * 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 = 1000000009;
AandC ac(mod,110000);

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
//makedata();
    std::ios::sync_with_stdio(0), cin.tie(0);
int n, a, b;
    cin >> n >> a >> b;
    lint ans = 0;
for (int i = 1; i < n; i++) {
if (i > b || n - i > a || n - i < 2) continue;
        ans += (n - i - 1) * ac.C(b - 1, i - 1) % mod * ac.C(a - 1, n - i - 1) % mod * ac.A(a, a) % mod * ac.A(b, b) % mod;
        ans %= mod;
    }
    cout << ans << endl;
return 0;
}

 

矩阵深度