直接从 D 开始了。
可可爱爱的二分捏。
check 就按照题目里写的就行了。
然后 \(l\) 的初值要注意一下，就是 \(\max^{i \le n}_{i=1}a_i\)。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 10;
int n,m;
int a[maxn];
int l,r = 1e18;
bool check(int x)
{
int now = a[1],cnt = 1;
for(int i = 2;i <= n;i++)
{
if(now + a[i] + 1 > x)
{
cnt++;
now = a[i];
}
else
{
now += a[i] + 1;
}
}
return cnt <= m;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
l = max(l,a[i]);
}
int ans = 0;
while(l <= r)
{
int mid = l + r >> 1;
if(check(mid))
{
r = mid - 1;
ans = mid;
}
else
{
l = mid + 1;
}
}
cout << ans;
return 0;
}
看到 \(q_i \le 10^9\)，不可以暴力直接做。
由于 \(1 \le P_i \le 8\)，于是我们想到每 \(LCM(1,2 \cdots ,8) = 840\)，所以只用记录 \(q_i\) 模 \(840\) 的结果就行了。
预处理前 \(840\) 秒数，然后计算答案即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 10;
int n,m,k,q,a[maxn],b[maxn],res[maxn];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m >> k;
for(int i = 1;i < n;i++)
{
cin >> a[i] >> b[i];
}
for(int i = 0;i < 840;i++)
{
int T = i + m;
res[i] = m;
for(int j = 1;j < n;j++)
{
while(T % a[j] != 0)
{
T++;
res[i]++;
}
T += b[j];
res[i] += b[j];
}
res[i] += k;
}
cin >> q;
while(q--)
{
int x;
cin >> x;
cout << x + res[x % 840] << '\n';
}
return 0;
}