$JOI2022$
$T1$
二分+贪心显然,由于是$subtask$然后竟然连$long\ long$也爆掉了,所以每个$subtask$都错了一个点...$100pts->9pts$,枯了
#include<bits/stdc++.h>
#define int long long
#define MAXN 300005
#define INF 1e18
using namespace std;
int A[MAXN],B[MAXN],N,M;
bool check(int Now)
{
int ls=0;
for(int i=1;i<=N;i++)
{
if(A[i]>B[i])
{
if(Now/A[i]+(Now%A[i]==0?0:1)>M) continue;
ls+=(M-(Now/A[i]+(Now%A[i]==0?0:1)));
}
else
{
ls+=M;
}
}
for(int i=1;i<=N;i++)
{
if(A[i]<=B[i])
{
ls-=Now/B[i]+((Now%B[i]==0?0:1));
}
else if(Now/A[i]+(Now%A[i]==0?0:1)>M)
{
ls-=(Now-M*A[i])/B[i]+((Now-M*A[i])%B[i]==0?0:1);
}
if(ls<0) return false;
}
return ls>=0;
}
signed main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%lld%lld",&N,&M);
for(int i=1;i<=N;i++)
{
scanf("%lld",&A[i]);
}
for(int i=1;i<=N;i++)
{
scanf("%lld",&B[i]);
}
// check(41397427274960);
int l=0,r=INF,mid,ans;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid))
{
ans=mid;
l=mid+1;
}
else
{
r=mid-1;
}
}
cout<<ans<<endl;
}
/*
3 3
19 4 5
2 6 2
2 1
9 7
2 6
41397427274960
27823531422776
4 25
1 2 3 4
1 2 3 4
*/
$T2$
预处理+二分
#include<bits/stdc++.h>
#define int long long
#define MAXN 200005
using namespace std;
int Fin[MAXN],res[MAXN],Num,n,q,y;
void sol(int id,int x)
{
int now=1;
while(x%2==0)
{
now*=2;
x/=2;
}
Fin[id]=x;
res[id]=now;
}
void Mid_search(int id)
{
int now=lower_bound(res+1,res+1+n,id)-res;
printf("%lld\n",Fin[now]);
}
signed main()
{
// freopen("b.in","r",stdin);
// freopen("b.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&Num);
sol(i,Num);
res[i]+=res[i-1];
}
scanf("%lld",&q);
for(int i=1;i<=q;i++)
{
scanf("%lld",&y);
Mid_search(y);
}
}
$T3$
考虑维护两次倍增数组
考虑一个点能到达的区间是连续的一段,如果到了一个点,那么中间的点必然也可以到达
考虑一条线路,那么这个起点可以到所有在起点和终点之间的点
那么只需要维护每个点向左和向右能到达的最远点就好了
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,k,x,y,m,lg[maxn],q[maxn],id[maxn],lp[maxn],rp[maxn];
int l[18][maxn],ls[18][18][maxn],r[18][maxn],rs[18][18][maxn];
int getl(int t,int l,int r) {
int k=lg[r-l+1];
//传参,跳的步数,左端点,右端点
//至于为什么维护一个区间,大概理解了,也就是说
//你这几步能到的左右端点之间都能到达,然后一点一点扩大范围罢了
return min(ls[t][k][l],ls[t][k][r-(1<<k)+1]);
}
int getr(int t,int l,int r) {
int k=lg[r-l+1];
return max(rs[t][k][l],rs[t][k][r-(1<<k)+1]);
}
void prep(){
lg[0]=-1;
for(int i=1; i<=n; i++)
lg[i]=lg[i>>1]+1,lp[i]=rp[i]=i;
}
int main() {
scanf("%d%d%d",&n,&k,&m);
prep();
while(m--){
scanf("%d%d",&x,&y);
if(x>y)lp[x]=min(lp[x],y);
else rp[x]=max(rp[x],y);
//预处理每个点到左右最远的点
}
for(int i=n,l=1,r=0; i>=1; i--) {
//单调队列更新每个点的值
while(l<=r&&q[r]>lp[i])r--;
while(l<=r&&id[l]>=i+k)l++;
q[++r]=lp[i];
id[r]=i;
lp[i]=min(q[l],i);
}
for(int i=1,l=1,r=0; i<=n; i++) {
//单调队列更新每个点的值
while(l<=r&&q[r]<rp[i])r--;
while(l<=r&&id[l]<=i-k)l++;
q[++r]=rp[i];
id[r]=i;
rp[i]=max(q[l],i);
}
for(int t=0; t<18; t++) {
//三维
//一维维护区间,一维维护步数
for(int i=1; i<=n; i++) {
ls[t][0][i]=l[t][i]=t?getl(t-1,l[t-1][i],r[t-1][i]):lp[i];
rs[t][0][i]=r[t][i]=t?getr(t-1,l[t-1][i],r[t-1][i]):rp[i];
//目前就是长度是1的区间,跳
}
for(int k=1; k<18; k++)
for(int i=1; i+(1<<k)-1<=n; i++){
ls[t][k][i]=min(ls[t][k-1][i],ls[t][k-1][i+(1<<(k-1))]);
rs[t][k][i]=max(rs[t][k-1][i],rs[t][k-1][i+(1<<(k-1))]);
}
}
int Q;
scanf("%d",&Q);
while(Q--){
int x,y; scanf("%d%d",&x,&y);
int l=x,r=x,ans=0;
for(int i=17; i>=0; i--) {
int tl=getl(i,l,r),tr=getr(i,l,r);
if(y<tl||tr<y)l=tl,r=tr,ans|=1<<i;
}
printf("%d\n",ans>n?-1:ans+1);
//发现一直到不了就寄了
}
return 0;
}
$T4$
考场上写了个暴力,显然判定比较好想,而且如果不存在全部相等的话,那么路径是唯一的
那么这个子矩阵必然是一条链,那么只需要判断相邻数字是否连着就好了