题目链接
B
按照monster的攻击力排序
由于存在同归于尽也算成功 所以我们需要讲攻击力最大的monster放在最后 保证同归于尽的这一次效率最大
CODE:
#include<bits/stdc++.h>
#define M 1008611
using namespace std;
int T,n;
long long A,B;
bool flag;
struct Node
{
long long ai,bi,val;
friend bool operator <(const Node &a,const Node &b)
{return a.ai<b.ai;}
}e[M];
long long check(long long x,long long y)
{return (x%y) ? (x/y)+1:(x/y);}//由于存在同归于尽 所以致死时的那一次攻击也要算上
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld%d",&A,&B,&n);flag=1;
for(int i=1;i<=n;++i) scanf("%lld",&e[i].ai);
for(int i=1;i<=n;++i) scanf("%lld",&e[i].bi);
sort(e+1,e+n+1);
for(int i=1;i<=n;++i)
{
long long nowx=check(e[i].bi,A)*e[i].ai,nowy=check(B,e[i].ai)*A;
if(e[i].bi<=nowy)
{
if(B<=nowx&&i<n) {flag=0;break;}
else B-=nowx;
}
else {flag=0;break;}
}
puts(flag ? "YES":"NO");
}
return 0;
}
C
按照分布的话 可以看作一个波形图 让你寻找一个波谷
通过排列以及查询次数的范围可以猜出 可以使用二分求解
CODE:
#include<bits/stdc++.h>
#define M 1008611
using namespace std;
int n;
int num[M];
int main()
{
scanf("%d",&n);
num[0]=num[n+1]=1008611;
int le=1,ri=n;
while(le<ri)
{
int mid=(le+ri)>>1;
printf("? %d\n",mid);fflush(stdout);scanf("%d",&num[mid]);
printf("? %d\n",mid+1);fflush(stdout);scanf("%d",&num[mid+1]);
if(num[mid]<num[mid+1]) ri=mid;
else le=mid+1;
}
printf("! %d\n",le);
return 0;
}
D1
一个贪心题
我们假设分别维护了两个序列
当前原序列到了x 将x同两个序列末尾比较
如果均相同的话 将x放在任一序列末尾均可
如果只有一个相同一个不同的话 将x放在不相同的序列末尾
如果均不相同的话 分别查询两个序列末尾的数字在原序列中 后面出现相同的数字哪个更靠前 将x放在这个序列的末尾 从而防止其线段相连
CODE:
#include<bits/stdc++.h>
#define M 1008611
using namespace std;
int n,ans;
int num[M],pos[M],fro[M];
int ed1,ed2;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&num[i]);
for(int i=0;i<=n;++i) pos[i]=n+1;
for(int i=1;i<=n;++i)
{
if(fro[num[i]]) pos[fro[num[i]]]=i;
fro[num[i]]=i;
}
for(int i=1;i<=n;++i)
{
if(num[i]!=num[ed1]&&num[i]==num[ed2]) {++ans;ed1=i;}
else if(num[i]==num[ed1]&&num[i]!=num[ed2]) {++ans;ed2=i;}
else if(num[i]!=num[ed1]&&num[i]!=num[ed2])
{
++ans;
if(pos[ed1]<pos[ed2]) ed1=i;
else ed2=i;
}
else if(num[i]==num[ed1]&&num[i]==num[ed2]) ed1=i;
}
printf("%d\n",ans);
return 0;
}
D2
一道贪心题 跟上面的做法很相似
如果均相同的话 将x放在任一序列末尾均可
如果只有一个相同一个不同的话 将x放在相同的序列末尾
如果均不相同的话 分别查询两个序列末尾的数字在原序列中 后面出现相同的数字哪个更靠后 将x放在这个序列的末尾 从而保证其线段相连
CODE:
#include<bits/stdc++.h>
#define M 1008611
using namespace std;
int n,ans;
int num[M],pos[M],fro[M];
int ed1,ed2;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&num[i]);
for(int i=0;i<=n;++i) pos[i]=n+1;
for(int i=1;i<=n;++i)
{
if(fro[num[i]]) pos[fro[num[i]]]=i;
fro[num[i]]=i;
}
// for(int i=1;i<=n;++i) printf("%d%c",pos[i],(i==n ? '\n':' '));
for(int i=1;i<=n;++i)
{
if(num[i]!=num[ed1]&&num[i]==num[ed2]) ed2=i;
else if(num[i]==num[ed1]&&num[i]!=num[ed2]) ed1=i;
else if(num[i]!=num[ed1]&&num[i]!=num[ed2])
{
++ans;
if(pos[ed1]>pos[ed2]) ed1=i;
else ed2=i;
}
else if(num[i]==num[ed1]&&num[i]==num[ed2]) ed1=i;
// printf("now is %d %d\n",ed1,ed2);
}
printf("%d\n",ans);
return 0;
}
E
极致构造题
首先 一看数据范围 L≤R≤\(10^6\) n≤32
然后这道题也是数的分解 容易让人想到二进制拆分
我们需要分情况讨论
1.L=1 R=\(2^k\)
我们构造k+2个点
每一个点i(2≤i≤k+2)满足\((1,2^{i-2})\)-continuous
如何构造？
我们构造到i的时候 首先建一条边(1-i)=1
然后对于j(2≤j≤i-1) 构造(j-i)=\(2^{j-2}\)
这样的话就成为了
(1,1)->(2,2) 2为中继
(1,2)->(3,4) 3为中继
(1,4)->(5,8) 4为中继
(1,8)->(9,16) 5为中继
...
(1,\(2^{i-3}\))->(\(2^{i-3}+1\),\(2^{i-2}\)) i-1为中继
2.L=1 R≠\(2^k\)
首先 二进制拆分 令
先按照上面的 对于\(2^k\)进行建图
一定要注意三件事 1.L≤d≤R对应的路径只能有一条 2.不可以存在边权为0的边 3.两点之间只能有一条边
我们建立第k+3个点 在使用类似于二进制拆分的方法
假设是R=14 我们先建立(1-k+3)=1
然后讨论[2,14] 使用二进制拆分
使用已经建好的图[2,k+2]中的点同k+3相连
3.L≠1
我们建一条边(1,2)=L-1 剩下的按照第2种情况做法就行了
CODE:
#include<bits/stdc++.h>
#define M 1008611
using namespace std;
int Le,Ri,cnt;
int ln[M];
struct Edge
{
int u,v,w;
}ans[M];
void Make_Ans(int now,int knd)
{
int k;
if((1<<ln[now])==now)
{
// printf("cdy\n");
k=ln[now]+2;
for(int i=2;i<=ln[now]+2;++i)
{
ans[++cnt]=(Edge){1+knd,i+knd,1};
for(int j=2;j<i;++j)
ans[++cnt]=(Edge){j+knd,i+knd,(1<<(j-2))};
}
}
else
{
// printf("wzy\n");
k=ln[now]+3;
for(int i=2;i<=ln[now]+2;++i)
{
ans[++cnt]=(Edge){1+knd,i+knd,1};
for(int j=2;j<i;++j)
ans[++cnt]=(Edge){j+knd,i+knd,(1<<(j-2))};
}
ans[++cnt]=(Edge){1+knd,k+knd,1};
int x=now-1;
while(x)
{
int tmp=x&(-x),tmpx=ln[x&(-x)];
ans[++cnt]=(Edge){tmpx+2+knd,k+knd,x-tmp+1};
x-=tmp;
}
}
printf("%d %d\n",k+knd,cnt);
for(int i=1;i<=cnt;++i)
printf("%d %d %d\n",ans[i].u,ans[i].v,ans[i].w);
}
int main()
{
scanf("%d%d",&Le,&Ri);
for(int i=1,t=0;i<=1000000;i<<=1,++t) ln[i]=t;
for(int i=1;i<=1000000;++i) if(!ln[i]) ln[i]=ln[i-1];
puts("YES");
if(Le==1) Make_Ans(Ri,0);
else
{
ans[++cnt]=(Edge){1,2,Le-1};
Make_Ans(Ri-Le+1,1);
}
return 0;
}