牛客练习赛3
A.反蝴蝶效应
水题，ans=max(ans,x+i-1);
时间复杂度O(n)
#include<bits/stdc++.h>
using namespace std;
int n,x,ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
ans=max(ans,x+i-1);
}
cout<<ans;
return 0;
}
B. 贝伦卡斯泰露
好题。
方法一：折半搜索。
方法二：状压dp。
方法三：用两个队列，正反扫一边这n个数，如何可以抵消，就弹出队首，否则就进队
时间复杂度O(n)
#include<bits/stdc++.h>
using namespace std;
int T,n,a[100005];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
queueq,p;
for(int i=1;i<=n;i++)
{
if(q.empty())q.push(a[i]);
else if(q.front()!=a[i])q.push(a[i]);
else q.pop();
}
for(int i=n;i>0;i--)
{
if(p.empty())p.push(a[i]);
else if(p.front()!=a[i])p.push(a[i]);
else p.pop();
}
if(q.empty()||p.empty())puts("Frederica Bernkastel");
else puts("Furude Rika");
}
return 0;
}
D.生物课程
一眼看有点难(我在考虑形状，发现做不出来)。
这时我们换个方向，换个思路，就觉得不难了。
考虑每个点的度数，我们用点的度数来判断形状。
如果有1个点度为4，4个点度为1，其余点度为2，这是X
如果有1个点度为3，3个点度为1，其余点度为2，这是Y
如果有2个点度为1，其余点度为2，这是Z
时间复杂度O(n)
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,ru[505],a[505];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
ru[x]++;ru[y]++;
}
for(int i=1;i<=n;i++)a[ru[i]]++;
if(a[4]==1&&a[1]==4&&a[2]==n-5){puts("X");return 0;}
if(a[3]==1&&a[1]==3&&a[2]==n-4){puts("Y");return 0;}
if(a[1]==2&&a[2]==n-2){puts("I");return 0;}
puts("NotValid");
return 0;
}
E.绝对半径2051
noip提高组t2难度吧，有点思维含量。
我是先离散化，再把每种型号的子弹用vactor存下来。
然后对于每一种型号的子弹做一边区间伸缩（明显有单调性）。
有些同学可能不知道什么是区间伸缩，其实就是尺取法。
就是对于逐渐增大的左端点，右端点也会逐渐增大
时间复杂度O(n)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,k,len,ans,l,r,a[N],b[N];
vectorv[N];
char buf[1<<21],*p1=buf,*p2=buf;
/*inline int gc()
{
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1=p2)?EOF:*p1++;
}*/
#define gc getchar
inline int read()
{
int res=0,f=0;
char c;
c=gc();
while(!isdigit(c))
{
if(c=='-')f=1;
c=gc();
}
while(isdigit(c))
{
res=res*10+c-48;
c=gc();
}
if(f)return -res;
return res;
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
b[i]=a[i];
}
sort(b+1,b+n+1);
len=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++)
{
a[i]=lower_bound(b+1,b+len+1,a[i])-b;
v[a[i]].push_back(i);
}
ans=1;
for(int i=1;i<=len;i++)
{
k=m;
l=0;r=0;
while(l<=r&&r<v[i].size()-1)
{
if(k>=v[i][r+1]-v[i][r]-1)
{
k-=v[i][r+1]-v[i][r]-1;
r++;
}
else{
l++;
k+=v[i][l]-v[i][l-1]-1;
}
ans=max(ans,r-l+1);
}
}
cout<<ans;
return 0;
}
F.监视任务
一眼看，发现是道差分约束的裸题。设点i的值为sum[i]，如果l-r中至少有x个，就是sum[r]-sum[l-1]>=x。
就l-1向r建一条值为x的边，注意要建超级源点，但是会超时。
我们换一种方法，我们贪心+线段树。
我们把区间根据右端点大小排序。
对于每一个区间，若这个区间满足条件就continue，如果不满足就尽量填在右边。
时间复杂度O(nlog(n))
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int n,m,l,r,L,R,mid,ans,tree[N*2],tag[N*2];
struct node{
int x,y,z;
}q[N];
bool cmp(node a,node b)
{
return a.y<b.y;
}
void pushdown(int nod,int l,int r)
{
int mid=(l+r)/2;
if(tag[nod])
{
tree[nod*2]=(mid-l+1);
tree[nod*2+1]=r-mid;
tag[nod*2]=tag[nod*2+1]=1;
tag[nod]=0;
}
}
void change(int nod,int l,int r,int L,int R)
{
if(l==L&&r==R)
{
tree[nod]=(r-l+1);
tag[nod]=1;
return;
}
pushdown(nod,l,r);
int mid=(l+r)/2;
if(R<=mid)change(nod*2,l,mid,L,R);
else if(L>mid)change(nod*2+1,mid+1,r,L,R);
else{
change(nod*2,l,mid,L,mid);
change(nod*2+1,mid+1,r,mid+1,R);
}
tree[nod]=tree[nod*2]+tree[nod*2+1];
}
int find(int nod,int l,int r,int L,int R)
{
if(l==L&&r==R)return tree[nod];
pushdown(nod,l,r);
int mid=(l+r)/2;
if(R<=mid)return find(nod*2,l,mid,L,R);
else if(L>mid)return find(nod*2+1,mid+1,r,L,R);
else return(find(nod*2,l,mid,L,mid)+find(nod*2+1,mid+1,r,mid+1,R));
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].z);
sort(q+1,q+m+1,cmp);
for(int i=1;i<=m;i++)
{
l=q[i].x;r=q[i].y;
int k=find(1,1,n,l,r);
k=q[i].z-k;
if(k<=0)continue;
L=l;R=r;ans=l;
while(L<=R)
{
mid=(L+R)/2;
int p=find(1,1,n,mid,r);
if(r-mid+1-p>=k)
{
ans=mid;
L=mid+1;
}
else R=mid-1;
}
change(1,1,n,ans,r);
}
printf("%d\n",find(1,1,n,1,n));
return 0;
}