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 种走法：
- 自行车 \(d\)
- 自行车 \(\dfrac{d}{k} \times k\) ，走路 \(d - \dfrac{d}{k} \times k\)
- 自行车 \(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;
}