Codeforces Round #700 (Div. 2)
题目链接
B
按照monster的攻击力排序
由于存在同归于尽也算成功 所以我们需要讲攻击力最大的monster放在最后 保证同归于尽的这一次效率最大
CODE:
#include
#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 C
按照分布的话 可以看作一个波形图 让你寻找一个波谷
通过排列以及查询次数的范围可以猜出 可以使用二分求解
CODE:
#include
#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>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] D1
一个贪心题
我们假设分别维护了两个序列
当前原序列到了x 将x同两个序列末尾比较
如果均相同的话 将x放在任一序列末尾均可
如果只有一个相同一个不同的话 将x放在不相同的序列末尾
如果均不相同的话 分别查询两个序列末尾的数字在原序列中 后面出现相同的数字哪个更靠前 将x放在这个序列的末尾 从而防止其线段相连
CODE:
#include
#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] D2
一道贪心题 跟上面的做法很相似
如果均相同的话 将x放在任一序列末尾均可
如果只有一个相同一个不同的话 将x放在相同的序列末尾
如果均不相同的话 分别查询两个序列末尾的数字在原序列中 后面出现相同的数字哪个更靠后 将x放在这个序列的末尾 从而保证其线段相连
CODE:
#include
#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\)
首先 二进制拆分 令
\[R=\sum_{i=0}^k(p_i2^i)(p_i=0,1) \]先按照上面的 对于\(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
#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<