Educational Codeforces Round 15

https://codeforces.com/contest/702
3/6:ABC 不会小学数学，基础差前面写的慢

A. Maximum Increase

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int a[N], n, ans, len = 1;

int main () {
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    for (int i = 2; i <= n; i++) {
        if (a[i] > a[i-1])  len ++;
        else {
            ans = max (ans, len);
            len = 1;
        }
    }
    ans = max (ans, len);
    cout << ans;
}

B. Powers of Two

#include <bits/stdc++.h>
#define int long long

using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 5;
int a[N], n, ans;
int pw2[] = {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648};

signed main () {
    map<int, int> mp;
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i], mp[a[i]] ++;
    sort (a + 1, a + n + 1);
    //for (int i = 1; i <= n; i++)    cout << a[i] << ' ';    cout << endl;
    
    // int x = 1;
    // while (x <= 2e9) {
    //     x *= 2;
    //     cout << x << ", ";
    // }

    for (int i = 1; i < n; i++) {
        mp[a[i]] --;
        //可以取到的范围: [a[i]+a[i+1], a[i]+a[n]]
        int l = a[i] + a[i+1], r = a[i] + a[n];
        int ed = *lower_bound (pw2, pw2 + 31, r);
        int st = *lower_bound (pw2, pw2 + 31, l); //[st, ed)
        //cout << st << ' ' << ed << endl;
        for (int j = st; j <= ed; j *= 2) {
            int find = j - a[i]; //找有多少个
            ans += mp[find];
        }
    }
    cout << ans << endl;
}

C. Cellular Network

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1e5 + 5, inf = 1e9 + 5;
int a[N], n, m, x, ans, dist;

signed main () {
    vector <int> b;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    for (int i = 1; i <= m; i++)    cin >> x, b.push_back (x);
    sort (b.begin (), b.end ());
    //for (int i = 1; i <= m; i++)    cout << b[i] << ' ';    cout << endl;

    for (int i = 1; i <= n; i++) {
        //二分最近的左右点
        auto it = lower_bound (b.begin (), b.end (), a[i]);
        if (it == b.end ())     dist = a[i] - *prev(it);
        else if (it == b.begin ())  dist = *it - a[i];
        else    dist = min (*it - a[i], a[i] - *prev(it));
        //cout << *l << ' ' << *r << ' ' << dist << endl;
        ans = max (ans, dist);
    }
    cout << ans << endl;
}

//sort b, 二分
//计算每个cly到最近站的距离, 取max

D. Road to Post Office

#include <bits/stdc++.h>
#define int long long

using namespace std;
int d, k, a, b, t, ans; // a车b人

signed main() {
    cin >> d >> k >> a >> b >> t;
    if (k > d)    ans = a * d; //直接开车到了
    else {
        ans = min(k * a + b * (d - k), d * a + t * (d / k)); //开车k公里, 再走路; 全部开车
        ans = min(ans, (d % k) * b + t * (d / k - 1) + a * (d - d % k)); //在最后一次要修车的时候，开始走路
    }
    cout << ans << endl;
}

//烦人的小学数学题
//坑点：到站了也要修

E. Analysis of Pathes in Functional Graph

F. T-Shirts