CF每日5题（1300-1500）

思路很简单 d在$a_l$和$a_r$之间 $\frac{d-a_l}{t-b_l}=\frac{a_r-a_l}{b_r-b_l}$
lower_bound 找第一个大于等于d的$a_i$

void solve()
{int n,k,q;cin>>n>>k>>q;vector<int>a(k+1,0),b(k+1,0);vector<int>dis(k+1),t(k+1);forr(i,1,k){cin>>a[i];dis[i-1]=a[i]-a[i-1];}// for(auto i:a)cout<<i<<' ';cout<<endl;// forr(i,0,k)cout<<dis[i]<<' ';cout<<endl;forr(i,1,k){cin>>b[i];t[i-1]=b[i]-b[i-1];}while (q--){int d;cin>>d;int id=lower_bound(a.begin()+1,a.end(),d)-a.begin();// cout<<id<<endl;// cout<<id<<' '<<a[id]<<' '<<dis[id]<<endl;int ans=b[id-1]+(d-a[id-1])*t[id-1]/dis[id-1];cout<<ans<<' ';}cout<<endl;
}

（这是1500的题？

一开始还以为n-2个三元组里面有什么规律…看了题解恍然大悟，可以开桶计数，时间复杂度O(nlogn)，不会超时

• 统计13、23、12位置数字相同的三元组个数a、b、c，但是123位置都相同的也包含在a、b、c中，他们不是美丽的，要除去
• 统计123位置都相同的个数d
• 每个三元组贡献a+b+c-3*d

dalao的题解中用了三元组turple 二元组pair

struct gr1{int a,b;bool operator<(const gr1 &x)const{return (a==x.a?b<x.b:a<x.a);}
};
struct gr2{int a,b,c;bool operator<(const gr2 &x)const{return (a==x.a?(b==x.b?c<x.c:b<x.b):a<x.a);}
};
void solve()
{int n;cin>>n;vector<int>a(n+1,0);//b1:12相同 b2:23 b3:13map<gr1,int>b1,b2,b3;map<gr2,int>b4;forr(i,1,n)cin>>a[i];int ans=0;for(int i=1;i<=n-2;i++){// cout<<a[i]<<' '<<a[i+1]<<' '<<a[i+2]<<endl;ans+=b1[{a[i],a[i+1]}];ans+=b2[{a[i+1],a[i+2]}];ans+=b3[{a[i],a[i+2]}];ans-=b4[{a[i],a[i+1],a[i+2]}]*3;b1[{a[i],a[i+1]}]++;b2[{a[i+1],a[i+2]}]++;b3[{a[i],a[i+2]}]++;b4[{a[i],a[i+1],a[i+2]}]++;}cout<<ans<<endl;
}

一开始有找到递减位置进行处理的思路，但是不知道如果有多个位置怎么去判断。
参考dalao题解
a[1:n] 找出的gcd数组b[1:n-1]

• 从前后分别找出数组b一直递增的最大位置
• 如果没有递减的位置，l=n-1 r=1
• 如果递减的位置在边上，l=n-2或r=2
• 其他情况就枚举a中a[i]被删去，b中对应b[i]和b[i-1]也寄了，变成gcd(a[i-1],a[i+1])

const int N=1e18+10;//一开始无穷大开小了 一直wa
void solve()
{int n;cin>>n;vector<int>a(n+2),b(n+1);forr(i,1,n)cin>>a[i];a[n+1]=a[0]=0; forr(i,1,n-1)b[i]=__gcd(a[i],a[i+1]);b[n]=N;b[0]=0;int l=1,r=n;while (l<=n-2&&b[l]<=b[l+1])l++;//从前面开始记录降序的位置while (r>=2&&b[r-1]<=b[r])r--;// cout<<l<<' '<<r<<endl;if(l==n||r==0)return cout<<"yes"<<endl,void();if(l==n-2||r==2)return cout<<"yes"<<endl,void();//判断边上有没有递减的forr(i,1,n){//枚举每一个数被删去的情况int ng=__gcd(a[i-1],a[i+1]);if(ng>=b[max(i-2,0ll)]&&ng<=b[min(i+1,n)]&&l>=i-2&&r<=i+1){//看能不能和前后接上return cout<<"yes"<<endl,void();}}return cout<<"no"<<endl,void();}

参考dalao题解
三元组顺序不同属于不同答案，考虑枚举a,b
$c\le \frac{n-ab}{a+b},c\le x-a-b$

问题在于时间复杂度会不会超时
ab的要求是$a+b\le x,ab+(a+b)\le n(因为c\ge 1)$
那么$ab\le n,b\le \frac{n}{a}$
运行次数就是$n\sum _1^x\frac{1}{a}$ 调和级数求和是ln级别，不会超时

void solve()
{int n,x;cin>>n>>x;int ans=0;forr(a,1,x){forr(b,1,x){if(a*b+(a+b)>n)break;int c=max(0ll,min((n-a*b)/(a+b),x-(b+a)));ans+=c;}}cout<<ans<<endl;
}

dalao的神奇题解
题意：从左向右，在数组a中选取$a_j\le b_i$，如果不够可以使用一次机会在a中，添加一个数k能把b选满，求k最小值
分析：
选取的花有要求

• $a_j\le b_i$
• 下标递增

题解中题意转化成b的删数很神奇

来自dalao题解

• 每次贪心地选取，一遇到$a_j\le b_i$就记录a的下标
• 下标递增，从左向右和从右向左遍历+贪心都能形成，区别在于每次选取最靠左还是最靠右的数
  对某个$b_i$，$b_{i-1}$最靠左的数下标<$b_{i+1}$最靠右的数下标，那么在$b_i$两边能形成递增的下标，$k=b_i$可以添加在这之间

void solve()
{int n,m;cin>>n>>m;vector<int>a(n+1),b(m+1),pi(m+1,n+1),si(m+1,0);//从左向右找pi记录 从右向左siforr(i,1,n)cin>>a[i];forr(i,1,m)cin>>b[i];for(int bi=1,j=1;bi<=m&&j<=n;bi++,j++){while(j<=n&&b[bi]>a[j])j++;pi[bi]=j;//记录从左往右找的位置}if(pi[m]!=n+1)return cout<<0<<endl,void();for(int bi=m,j=n;bi>=1&&j>=1;bi--,j--){while(j>=1&&b[bi]>a[j])j--;si[bi]=j;}pi[0]=0,si[m+1]=n+1;int ans=1e9+10;forr(i,1,m){if(pi[i-1]<si[i+1])ans=min(ans,b[i]);}if(ans==1e9+10)return cout<<-1<<endl,void();else cout<<ans<<endl;
}