Educational Codeforces Round 15

A - Maximum Increase

一段上升子数组\([l, r]\)最大化 \(r - l + 1\)，我们对于每个 \(l\) 做一个双指针即可

int n, a[N];
void solve()
{       
    cin>>n;
    int res = 0;
    for(int i = 1; i <= n; i++) cin>>a[i];
    for(int i = 1; i <= n; i++)
    {
        int j = i;
        while(j + 1 <= n && a[j + 1] > a[j])
            j++;
        res = max(res, j - i + 1);
        i = j;
    }
    cout<<res<<'\n';
 
 
    return;
}

B - Powers of Two

用map记录下每个数字的出现次数，对于每个数字 \(x\) 枚举 \(z\)，即可求出 \(y = 2^z - x\) 出现的次数，注意特判 \(x = y\) 的情况

const int N = 2e5 + 10;
 
ll n, a[N];
map<ll, ll> mp;
void solve()
{       
    cin>>n;
    for(int i = 1; i <= n; i++) 
    {
        cin>>a[i];
        mp[a[i]]++;
    }
    ll res = 0;
    for(int i = 1; i <= n; i++)
    {
        ll base = 1;
        ll x = a[i];
        for(int i = 0; i <= 30; i++)
        {
            if(i != 0)  base *= 2;
            ll y = base - x;
            res += mp[y];
            if(x == y)
                res--;
        }
    }
    res /= 2;
    cout<<res<<'\n';
    return;
}

C - Cellular Network

将信号站和城市排序后，二分答案，二分过程做一个双指针操作即可

typedef long long ll;
 
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
 
ll n, m, a[N], b[N];
 
bool check(ll r)
{
    int i = 1;
    for(int j = 1; j <= m; j++)
        while(i <= n && abs(b[j] - a[i]) <= r)
            i++;
    if(i > n)   return true;
    return false;
}
 
void solve()
{       
 
    cin>>n>>m;
    for(int i = 1; i <= n; i++) 
    {
        cin>>a[i];
    }
    for(int i = 1; i <= m; i++) 
    {
        cin>>b[i];
    }
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + m);
    ll l = 0, r = 2e9;
    while(l < r)
    {
        ll mid = (l + r) >> 1;
        if(check(mid))  r = mid;
        else l = mid + 1;
    }
    cout<<l<<'\n';
    return;
}

D - Road to Post Office

已知\(a < b\) ，从路程上我们有 3 种走法：

1. 自行车 \(d\)
2. 自行车 \(\dfrac{d}{k} \times k\) ，走路 \(d - \dfrac{d}{k} \times k\)
3. 自行车 \(k\) ，走路 \(d - k\)

我们对这三种的修车次数分类讨论即可，具体见代码

ll d, k, a, b, t;
void solve()
{       
    cin>>d>>k>>a>>b>>t;
    ll res = d * b;
    
    ll c = d / k + (d % k != 0) - 1;
    // cout<<c<<"   "<<r<<'\n';+
    res = min({d * a + c * t, res});
    // 情况1

    if(d % k != 0)  c--;
    res = min({max(0ll, c) * t + (d % k) * b + (max(0ll, c) + 1) * k * a, res});
    // 情况2
    
    res = min(a * min(k, d) + (d - min(k, d)) * b, res);
	// 情况3
    cout<<res<<'\n';
    return;
}

E. Analysis of Pathes in Functional Graph

倍增 LCA

2023杭电多校第六场Calculate和这道题很像

倍增预处理即可

//  AC one more times

#include <bits/stdc++.h>
#define int long long 
using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;
const int N = 1e5 + 10;
const int LOGN = 33;

ll n, k;
ll e[N], w[N], fa[N][LOGN + 2], f[N][LOGN + 2], g[N][LOGN + 2];
void init()
{
    for(int j = 1; j <= LOGN; j++)
        for(int i = 1; i <= n; i++)
        {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
            f[i][j] = f[i][j - 1] + f[fa[i][j - 1]][j - 1];
            g[i][j] = min(g[i][j - 1], g[fa[i][j - 1]][j - 1]);
            //cout<<j<<" "<<fa[i][j - 1]<<"  "<<f[i][j - 1]<<"  "<<g[i][j - 1]<<'\n';
        }
}
void query(int u)
{
    ll res = 0;
    ll res2 = 1e9;
    //cout<<k<<'\n';
    for(ll i = LOGN; i >= 0; i--)
    {
        //cout<<i<<"   "<<((k >> i) & 1)<<'\n';
        if(k & (1ll << i))
        {
            //cout<<i<<" "<<fa[u][i]<<"  "<<"  "<<f[u][i]<<"  "<<g[u][i]<<" "<<res<<'\n';
            res = res + f[u][i];
            res2 = min(g[u][i], res2);
            u = fa[u][i];
        }
    }
    cout<<res<<" "<<res2<<"\n";
}
void solve()
{       
    cin>>n>>k;
    for(int i = 1; i <= n; i++)
    {
        cin>>e[i];  e[i]++;
        fa[i][0] = e[i];
    }
    for(int i = 1; i <= n; i++)
    {
        cin>>w[i];
        f[i][0] = w[i];
        g[i][0] = w[i];
    }
    init();
    for(int i = 1; i <= n; i++)
    {
        query(i);
    }

    //cout<<e[1]<<" "<<w[1]<<'\n';
    return;
}


  
signed main()
{
    std::ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    
    int TC = 1;
    
    //cin >> TC;    
    for(int tc = 1; tc <= TC; tc++)
    {
        //cout << "Case #" << tc << ": ";         
        solve();
    }


    return 0;
}