A - Two Rival Students
贪心一下就可以了......
#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int main()
{
int T;cin>>T;
while(T--)
{
int x,y;
cin>>x>>y;
if(y<=x){puts("yes");continue;}
if(x==1)
{
if(y==1)puts("yes");
else puts("no");
}
else if(x<=3)
{
if(y<=3)puts("yes");
else puts("no");
}
else puts("yes");
}
return 0;
}
B - Magic Stick
不难发现，当$x$大于等于$4$的时候，不论多大的数我们都可以得到。
所以判断一下$x$小于等于$3$的情况就可以了。
#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int main()
{
int T;cin>>T;
while(T--)
{
int x,y;
cin>>x>>y;
if(y<=x){puts("yes");continue;}
if(x==1)
{
if(y==1)puts("yes");
else puts("no");
}
else if(x<=3)
{
if(y<=3)puts("yes");
else puts("no");
}
else puts("yes");
}
return 0;
}
C - Dominated Subarray
这题没怎么看......
#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=200050;
vector <int> vec[N];
int n,ans;
int main()
{
int Test;cin>>Test;
while(Test--)
{
scanf(
for(int i=0;i<=n;++i)vec[i].clear();
for(int i=1;i<=n;++i)
{
int num;
scanf(
vec[num].push_back(i);
}
ans=INT_MAX;
for(int i=0;i<=n;++i)
{
int sz=vec[i].size()-1;
for(int j=0;j<sz;++j)
{
ans=min(ans,vec[i][j+1]-vec[i][j]);
}
}
if(ans==INT_MAX)puts("-1");
else printf(
}
return 0;
}
D - Yet Another Monster Killing Problem
qnm的边界啊啊啊啊啊
每一天怪物能杀就杀，杀得越多越好，所以我们需要二分。
怎么二分呢？先用线段树或者st表维护怪物的区间最大值，勇者按$s$为第一关键字从大到小排序，再维护一个$p$的前缀最大值就可以check了。
（这题因为多组数据+边界清空卡了半天......）
#include <bits/stdc++.h>
#define ll long long
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=200500;
int n,m;
int mxkill[N];
int vec[N],cnt;
struct node
{
int p;
int s;
}c[N];
int a[N];
struct segtree
{
int mx;
}t[N<<3];
void build(int l,int r,int id)
{
if(l==r)
{
t[id].mx=a[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,ls);
build(mid+1,r,rs);
t[id].mx=max(t[ls].mx,t[rs].mx);
}
int query(int l,int r,int id,int L,int R)
{
if(l>=L&&R>=r)
{
return t[id].mx;
}
int mid=(l+r)>>1;
if(R<=mid)return query(l,mid,ls,L,R);
else if(L>mid)return query(mid+1,r,rs,L,R);
else return max(query(l,mid,ls,L,mid),query(mid+1,r,rs,mid+1,R));
}
inline bool cmp(const node &x,const node &y)
{
return x.s>y.s;
}
inline bool check(int pos,int x)
{
int nowR=pos+x-1;
int nowmx=query(1,n,1,pos,nowR);
int xx=lower_bound(vec+1,vec+cnt+1,x)-vec;
if(mxkill[vec[xx]]>=nowmx)return true;
else return false;
}
int main()
{
int T;cin>>T;
while(T--)
{
cnt=0;
memset(t,0,((n+5)<<2)*sizeof(int));
scanf(
for(int i=0;i<=n+50;++i)mxkill[i]=0;
for(int i=1;i<=n;++i)
{
scanf(
}
scanf(
for(int i=1;i<=m;++i)
{
scanf(
}
sort(c+1,c+m+1,cmp);
for(int i=1;i<=m;++i)
{
vec[++cnt]=c[i].s;
mxkill[c[i].s]=max(mxkill[c[i].s],c[i].p);
}
vec[cnt+1]=0;
sort(vec+1,vec+cnt+1);
for(int i=1;i<=m;++i)
{
mxkill[c[i].s]=max(mxkill[c[i-1].s],mxkill[c[i].s]);
}
build(1,n,1);
int ans=0,monster=1;
while(monster<=n)
{
int L=1,R=n-monster+1,tmp=-1;
while(L<=R)
{
int mid=(L+R)>>1;
if(check(monster,mid))tmp=mid,L=mid+1;
else R=mid-1;
}
if(tmp==-1){ans=-1;break;}
monster+=tmp;
ans++;
}
printf(
}
return 0;
}
EFG暂补
Comments NOTHING