2019.7.30_牛客博客

Paint Tree

https://cn.vjudge.net/problem/CodeForces-197E

看似计算几何，实际是一道巧妙的思维题

思路来自https://www.cnblogs.com/whc200305/p/7214453.html

代码实现参考https://blog.csdn.net/qq_43900769/article/details/87193825

核心思想：

所有点中，找到左下角的点，看作根

除了根的点之外，其它点按极角（斜率）由小到大排序，这样必然保证其它点和根的连线不相交。如果共线，那么选取离根较近的点作为儿子

注意：斜率排序的时候要用到全局变量

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define max1 (500+10)
#define max2 (1000+10)
#define maxn (1500+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL cout<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n;
int head[maxn],pre[maxn<<1],to[maxn<<1],tot,sz[maxn];
void adde(int u,int v)
{  to[++tot]=v,pre[tot]=head[u],head[u]=tot;
}
struct node
{  int x,y,id;
}p[maxn];
int rt;
int ans[maxn];
bool cmp(node a,node b)
{  //see(a.x),see(a.y),see(b.x),see(b.y),NL;  int x1=a.x-p[rt].x,  y1=a.y-p[rt].y,  x2=b.x-p[rt].x,  y2=b.y-p[rt].y;  if(1LL*y1*x2!=1LL*y2*x1) return 1LL*y1*x2<1LL*y2*x1;  else return abs(x1)<abs(x2);
}
void dfs1(int u,int f)
{  sz[u]=1;  for(int i=head[u];i;i=pre[i])  {  int v=to[i];if(v==f)continue;  dfs1(v,u);sz[u]+=sz[v];  }
}
void dfs(int l,int r,int u,int f)
{  //see(l),see(r),see(u),see(f),NL;  rt=l;  for(int i=l+1;i<=r;i++)  if(p[i].x<p[rt].x||p[i].x==p[rt].x&&p[i].y<p[rt].y)rt=i;  swap(p[rt],p[l]);  ans[p[l].id]=u;  //see(p[l].id),see(u),NL;  rt=l;  sort(p+l+1,p+r+1,cmp);  int pos=l;  for(int i=head[u];i;i=pre[i])  {  int v=to[i];if(v==f)continue;  dfs(pos+1,pos+sz[v],v,u);  pos+=sz[v];  }
}
int main()
{  RD1(n);  for(int i=1;i<n;i++){int u,v;RD2(u,v);adde(u,v),adde(v,u);}  for(int i=1;i<=n;i++){RD2(p[i].x,p[i].y);p[i].id=i;}  dfs1(1,0);  dfs(1,n,1,0);  for(int i=1;i<=n;i++)printf("%d ",ans[i]);  return 0;
}

Sad powers

https://cn.vjudge.net/problem/CodeForces-955C

有思维的暴力题

思路参考https://blog.csdn.net/computer_user/article/details/79715417

实现起来坑比较多

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define max1 (500+10)
#define max2 (1000+10)
#define maxn (1000000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL cout<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll rt2(ll x)//二分，返回平方小于等于x的正整数个数
{  ll l=1,r=1e9;    //r不知道为什么要取1e9，原来取的r=(x<<1)+1, WA了  while(l<=r)  {  ll mid=(l+r)>>1;  if(mid*mid<=x)l=mid+1;  else r=mid-1;  }return r;
}
vector<ll>g;
bool chk(ll x)//判断平方数
{  if(rt2(x)*rt2(x)==x)return 1;return 0;
}
void init()
{  for(ll i=2;i<=1e6;i++)  {  if(chk(i))continue;  ll tmp=i*i*i;  double tmp1=1.0*i*i*i;  while(1e18-tmp1>1e-16)//坑！！！！！！！浮点比较不能直接==,<=>=  {  if(chk(tmp))continue;  g.push_back(tmp);  tmp*=i*i;  tmp1*=1.0*i*i;  }  }  sort(g.begin(),g.end());  g.erase(unique(g.begin(),g.end()),g.end());//坑！！！！！！！unique之后要erase
}
int main()
{  init();  int q;RD1(q);while(q--)  {  ll l,r,ans=0;scanf("%I64d %I64d",&l,&r);  ans+=rt2(r)-rt2(l-1);  ans+=upper_bound(g.begin(),g.end(),r)-lower_bound(g.begin(),g.end(),l);  printf("%I64d\n",ans);  }  return 0;
}

Culture Code

https://cn.vjudge.net/problem/CodeForces-1197E

比较麻烦的题，思维量较大，基本想不到这么做，过些时候填坑

比较好的思路及代码实现：https://blog.csdn.net/u013534123/article/details/96983956

Ball

https://cn.vjudge.net/problem/CodeForces-12D

线段树的巧妙运用。

首先任选一维，结构体降序排列。

其次对再选一维，单独保存于一个数组，sort+unique去重（即离散化），离散化后，数组每个值的下标成了这个值的相对大小，排第一的最小，排第二的第二小......

离散化保持了相对大小，同时缩小了数据的取值范围。之后每次要某个值的‘相对大小’时，只需要二分。

在离散化的数组上构建线段树，元素个数即离散化数组的长度。

在这里第二维数据的大小关系构成了线段树区间，线段树插入的是第三维数据，维护的是第三维数据区间最大值。

核心步骤：按x降序遍历，同时插入新的y点值，并且查询大于当前y的区间里是否有比当前z更大的。如果有，ans++

代码的实现也比较巧妙，参考https://blog.csdn.net/Amovement/article/details/86568141

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define max1 (500+10)
#define max2 (1000+10)
#define maxn (500000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL cout<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct tri
{  int x,y,z;
}p[maxn];
int n;
int h[maxn];
int Max[maxn<<2];
int ans=0;
bool cmp(tri a,tri b)
{  if(a.x!=b.x)return a.x>b.x;  else if(a.y!=b.y)return a.y>b.y;  else return a.z>b.z;
}
void udp(int pos,int v,int rt,int l,int r)
{  //see(pos),see(v),see(rt),see(l),see(r),NL;  if(l==r)  {  Max[rt]=max(Max[rt],v);return;  }  //Max[lson]=max(Max[lson],Max[rt]),  //Max[rson]=max(Max[rson],Max[rt]);  int mid=(l+r)>>1;  if(pos<=mid)udp(pos,v,lson,l,mid);  else udp(pos,v,rson,mid+1,r);  Max[rt]=max(Max[lson],Max[rson]);
}
int query(int L,int R,int rt,int l,int r)
{  //see(L),see(R),see(rt),see(l),see(r),NL;  if(L>R)return 0;  if(L<=l&&r<=R)return Max[rt];  //Max[lson]=max(Max[lson],Max[rt]),  //Max[rson]=max(Max[rson],Max[rt]);  int mid=(l+r)>>1;  int ans1=-1,ans2=-1;  if(L<=mid)ans1=query(L,R,lson,l,mid);  if(mid<R)ans2=query(L,R,rson,mid+1,r);  return max(ans1,ans2);
}
int main()
{  RD1(n);  for(int i=1;i<=n;i++)RD1(p[i].x);  for(int i=1;i<=n;i++){RD1(p[i].y);h[i]=p[i].y;}  for(int i=1;i<=n;i++)RD1(p[i].z);  sort(h+1,h+1+n);  int sz=unique(h+1,h+1+n)-h-1;  //for(int i=1;i<=sz;i++)see(i),see(h[i]),NL;  sort(p+1,p+1+n,cmp);  for(int i=1,pre=1;i<=n;)  {  //see(i),see(p[i].x),see(p[i].y),see(p[i].z),NL;  //see(res),see(p[i].z),NL;  while(p[i].x==p[pre].x&&i<=n)  {  int pos=lower_bound(h+1,h+1+sz,p[i].y)-h;  p[i].y=pos;  int res=query(pos+1,sz,1,1,sz);  if(res>p[i].z)ans++;  i++;  }  while(pre<i)  {  udp(p[pre].y,p[pre].z,1,1,sz);  pre++;  }  }printf("%d",ans);  return 0;
}