今天被这道题困住了一个晚上。
先看CF2018B
https://codeforces.com/problemset/problem/2018/B
题意：
这道题我一开始就行首先答案肯定是在所有区间[i-a[i]+1,i+a[i]-1]的交集里，但我没想到这就是答案了。
观察几个样例后，首先猜测答案肯定是在一个区间内。
证明：假设 x<y<z 且 x,z 满足条件而 y 不满足条件。不妨设 u 是那个 y 走不到的点。若 u<y 则等到 z 扩展到 y 的时候显然走不到 u 了，否则 x 走不到 u。
对于这道题还有一个贪心的性质：对于从一个点开始，肯定优先走到a[i]小的点，如果走到a[i]比较大的点反而不优。通过这个性质就可以二分了。
既然猜测到是一个区间之后，那么有一个思路就是从a[i]最小的点开始左右二分边界，通过写一个check函数判断这个点是否满足所有限制。
check函数该怎么写了，就可以写从这个点开始找一个距离他最近的最小的点走过去，并且时刻记录当前的时间，如果时间超过了a[i]就return FALSE。能遍历完整个数组就是return 1;
代码如下：
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
const int N=2e5+7;
int a[N];
int pre[N];
int suff[N];
int n;
bool check(int pos){
//找到距离这个点最近的 且最小的点 暴力走过去 判断时间是不是超过了a[i]
int cur=1;
int l=pos,r=pos;
while(r-l+1!=n){
if(a[pre[l-1]]>a[suff[r+1]]){
//先走右边
for(int i=r+1;i<=suff[r+1];i++){
cur++;
if(cur>a[i])return 0;
}
r=suff[r+1];
}else{
//先走左边
for(int i=l-1;i>=pre[l-1];i--){
cur++;
if(cur>a[i])return 0;
}
l=pre[l-1];
}
}
return 1;
}
void solved(){
cin>>n;
int mn=1e9;
int pos=1;
for (int i = 1; i <= n; i++){
cin>>a[i];
if(a[i]<mn)mn=a[i],pos=i;
}
a[0]=1e9,a[n+1]=1e9,suff[n+1]=0;
for(int i=1;i<=n;i++){
pre[i]=pre[i-1];
if(pre[i]==0 or a[i]<a[pre[i]])pre[i]=i;
}
for(int i=n;i>=1;i--){
suff[i]=suff[i+1];
if(a[i]<a[suff[i]] or suff[i]==0)suff[i]=i;
}
if(check(pos)==0){
cout<<0<<'\n';
return;
}
int ans=0;
int l=0,r=pos+1;
while(l+1!=r){
int mid=l+r>>1;
if(check(mid))r=mid;
else l=mid;
}
ans+=pos-r+1;
l=pos-1,r=n+1;
while(l+1!=r){
int mid=l+r>>1;
if(check(mid))l=mid;
else r=mid;
}
ans+=l-pos;
cout<<ans<<'\n';
}
signed main(){
auto begin = std::chrono::high_resolution_clock::now();
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _=1;
cin>>_;
while(_--)solved();
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
//cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.";
return 0;
}
https://www.luogu.com.cn/problem/P9755
对于种树这道题，先判断每棵树从从种下到生长到指定高度所需要的最短时间，进行排个序，那么肯定先到达所需要时间最长的点，这样的贪心策略肯定是最优的。
二分时间
要先把要遍历的路径预处理出来 根据贪心的性质 肯定从1号点开始一直找需要生长时间最长的点 然后遍历过去
对于每个点 求出生长到a[i] 最晚开始的时间 O(n)遍历过去判断当前时间是否超过了该树最晚开始的时间
#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
typedef double db;
const ll N=100100,INF=1e10;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
struct Node{
ll x,y;
bool operator<(const Node&rhs)const{
return x<rhs.x;
}
}k[N];
ll n;
ll a[N],b[N],c[N],h[N],p[N],fa[N];
vector<ll> E[N];
bool f[N];
void add(ll u,ll v){
E[u].push_back(v);
E[v].push_back(u);
}
void dfs(ll u,ll f){
for(auto v:E[u]){
if(v==f)
continue;
fa[v]=u;
dfs(v,u);
}
}
ll F(ll i,ll l,ll r){
ll t=(r-l+1);
if(h[i]<l)
return t;
if(h[i]>r)
return t*b[i]+(((l+r)*t)/2)*c[i];
return (r-h[i])+(h[i]-l+1)*b[i]+(((l+h[i])*(h[i]-l+1))/2)*c[i];
}
bool check(ll x){
for(int i=1;i<=n;i++){
if(F(i,1,x)<a[i])
return 0;
ll l=1,r=n;
while(l<r){
ll mid=(l+r+1)>>1;
if(F(i,mid,x)>=a[i])
l=mid;
else
r=mid-1;
}
k[i]={l,i};
p[i]=k[i].x;
}
memset(f,0,sizeof(f));
sort(k+1,k+n+1);
f[0]=1;
ll h=0;
for(int i=1;i<=n;i++){
stack<ll> d;
ll t=k[i].y;
while(!f[t]){
d.push(t);
f[d.top()]=1;
t=fa[t];
}
while(!d.empty()){
++h;
if(p[d.top()]<h)
return 0;
d.pop();
}
}
return 1;
}
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
b[i]=read();
c[i]=read();
}
for(int u,v,i=1;i<n;i++){
u=read(),v=read();
add(u,v);
}
for(int i=1;i<=n;i++){
if(c[i]>=0)
h[i]=INF;
else
h[i]=(1-b[i])/c[i];
}
dfs(1,1);
ll l=n,r=1e9;
while(l<r){
ll mid=(l+r)>>1;
if(check(mid))
r=mid;
else
l=mid+1;
}
write(l);
return 0;
}
Comments NOTHING