Educational Codeforces Round 15

题目链接在这里

A. Maximum Increase

最长上升子串

#include bits/stdc++.h

using namespace std;

int n;
int arr[100005];
int main() {
    cin  n;
    for (int i = 1; i = n; i++)
        cin  arr[i];
    int ans = 0;
    int mx = 0;
    for (int i = 1; i = n; i++) {
        if (arr[i]  arr[i - 1]) {
            ans++;
        } else {
            mx = max(ans, mx);
            ans = 1;
        }
    }
    mx = max(mx, ans);
    cout  mx  endl;
    return 0;
}
B. Powers of Two

n个数,问多少对 ai+aj=2x(ij)
map瞎搞。。

#include bits/stdc++.h

using namespace std;

int n;
int arr[100005];
mapint, int vis;

int main() {
    cin  n;
    for (int i = 1; i = n; i++) {
        cin  arr[i];
        if (!vis[arr[i]]) vis[arr[i]] = 1;
        else vis[arr[i]]++;
    }
    long long ans = 0;
    for (int num = 2; num = 1  30  num  0; num = 1) {
        for (int i = 1; i = n; i++) {
            int a = arr[i];
            if (!vis[num - a]) continue;
            int b = num - a;
            int t = vis[b];
            if (a == b) ans += (long long)(t - 1);
            else ans += t;
        }
    }
    cout  ans / 2  endl;
    return 0;
}
C. Cellular Network

直线上n个点,m座塔,每座塔都有相同的管辖范围r,问r最小是多少可以把n个点全部包含。

也就是说每个点左右距离r以内至少有一个灯塔,所以找到每个点距离最近的灯塔的距离,取最大值即可。

#include bits/stdc++.h

using namespace std;

int n, m;
long long arr[100005];
long long brr[100005];
int main() {
    cin  n  m;
    for (int i = 1; i = n; i++)
        cin  arr[i];
    long long a;
    for (int i = 1; i = m; i++) {
        cin  brr[i];
    }
    brr[0] = -10000000000000000;
    brr[m + 1] = 10000000000000000;
    int idx = 0;
    long long ans = 0;
    for (int i = 1; i = n; i++) {
        while (idx  m  brr[idx + 1]  arr[i]) idx++;
        ans = max(ans, min(arr[i] - brr[idx], brr[idx + 1] - arr[i]));
    }
    cout  ans  endl;
    return 0;
}
D. Road to Post Office

d 公里的距离要走,开车一公里a秒,但每开 k 公里要休息t秒,走路一公里 b (ab),你一开始开车,并随时可以选择下来走路,问最短时间。

没啥好说的。。

#include bits/stdc++.h

using namespace std;

long long d, k, a, b, t;
int main() {
    cin  d  k  a  b  t;
    long long x = d / k;
    long long y = d % k;
    long long ans = 0;
    if (!x) {
        ans = d * a;
    } else {
        ans += k * a;
        ans += min(t + y * a, y * b);
        ans += min(a * k + t, b * k) * (x - 1);
    }
    cout  ans  endl;
    return 0;
}
E. Analysis of Pathes in Functional Graph

一个图,每个点都有且仅有一条出边,这条边有一个权值。
问从每个点开始走k步所经过的路径上的权值和与最小值。

用倍增的思想。
to[i][j] 表示从 i 2j步到达的点,
sum[i][j] 表示从 i 2j步路径上的权值和,
mi[i][j] 表示从 i 2j步路径上的权值最小值。
所以
to[i][j+1]=to[to[i][j]][j],
sum[i][j+1]=sum[i][j]+sum[to[i][j]][j],
mi[i][j+1]=min(mi[i][j],mi[to[i][j]][j]) .

#include bits/stdc++.h

using namespace std;

const int MAXN = 100005;

int n;
long long k;
int to[MAXN][55];
long long val[MAXN][55];
long long mi[MAXN][55];
long long sum[MAXN], smi[MAXN];
int idx[MAXN];

int main() {
    cin  n  k;
    for (int i = 1; i = n; i++) {
        scanf("%d", to[i][0]);
        to[i][0]++;
        idx[i] = i;
    }
    for (int i = 1; i = n; i++) {
        scanf("%lld", val[i][0]);
        mi[i][0] = val[i][0];
    }
    memset(smi, 0x3f, sizeof(smi));
    int j = 0;
    long long t = k;
    while (k) {
        for (int i = 1; i = n; i++) {
            val[i][j + 1] = val[i][j] + val[to[i][j]][j];
            mi[i][j + 1] = min(mi[i][j], mi[to[i][j]][j]);
            to[i][j + 1] = to[to[i][j]][j];
        }
        j++;
        k = 1;
    }
    j--;
    k = t;

    while (k) {
        while ((1ll  j)  k) j--;
        for (int i = 1; i = n; i++) {
            sum[i] += val[idx[i]][j];
            smi[i] = min(smi[i], mi[idx[i]][j]);
            idx[i] = to[idx[i]][j];
        }
        k -= (1ll  j);
    }
    for (int i = 1; i = n; i++) {
        cout  sum[i]  ' '  smi[i]  endl;
    }
    return 0;
}
最新回复(0)
/jishuewQNDi4GmY1zZYJgpE9O7NOOsP_2Fq8VDwDcT9Y7xSjqU_3D4858344
8 简首页