比赛概况

solve: ACDHKLM
rank: 374/3835
dirt:630

补题情况

EFG

题解

E:鸡算几何

题目链接：https://ac.nowcoder.com/acm/contest/46800/E

思路：简单的计算几何叉积运算。我们容易发现：如果我们要判断有没有进行过操作三，就是判断会不会出现，E和B点重合的时候，通过旋转两个L形铁丝无法正常重叠。显然：当原铁丝两边长一样时，我们是无论如何都无法判断的，因此先判断两边长情况，相同则直接输出“NO\n”并返回；否则，我们用向量的叉积来判断长边和短边的位置关系，我们先将AB与DE对正，即加入AB是短边，DE是长边，那么我们交换D,F点使得长边对长边（即EF对BC），短边对短边。然后分别计算向量BA叉乘向量BC,向量ED叉乘向量EF，判断两个叉积符号是否一致，如果一致，则输出"NO\n",反之输出“YES\n”

AC代码：

#include<bits/stdc++.h>
#define i64 long long

using namespace std;
const int maxn=1e6+10;
const int inf = 0x3f3f3f3f;
const double eps=1e-9;
const double pi = acos(-1.0);

int sgn(double x){//判断误差之内是否是0
  if(fabs(x) < eps) return 0;
  return 1;
}

struct point{//定义二维平面上的点
  double x,y;
}a[10];

double o_dis_pow(point x,point y){//两点之间欧几里得距离的平方
  return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);
}

double cross(point o,point a,point b){//计算向量oa,ob的叉积
  return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);//>0,b在a的逆时针方向上；<0,b在a的顺时针方向上；=0,o,a,b三点共线
}

void slv(){
  for(int i=1;i<=6;i++) cin>>a[i].x>>a[i].y;
  if(!sgn(o_dis_pow(a[1],a[2])-o_dis_pow(a[2],a[3]))){
      cout<<"NO\n";
      return;
  }
  if(sgn(o_dis_pow(a[1],a[2])-o_dis_pow(a[4],a[5]))){
      //交换4,6
      point t=a[4];
      a[4]=a[5];
      a[5]=t;
  }
  int a1=cross(a[2],a[1],a[3]),a2=cross(a[5],a[4],a[6]);
  if(a1*a2<0){
      cout<<"YES\n";
  }else{
      cout<<"NO\n";
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int _=1;
  cin>>_;
  while(_--) slv();
}

F:鸡玩炸蛋人

题目链接：https://ac.nowcoder.com/acm/contest/46800/F

思路：因为原来的图不一定是联通的，我们可以意识到什么情况下是无解的，即：有两个及两个以上的独立连通块中最后含有炸弹。因此我们可以先用并查集维护一下各个节点属于哪个连通块，然后O(n)遍历所有点，判断该有多少个连通块中最后有炸弹。设有x个连通块最后有炸弹，当x >=2 时，直接输出0；当x == 1时，我们会发现，在最后有炸弹的那个连通块中，我们可以选择从任一点出发,用一种类似于dfs的方法，先走到所有有炸弹的最“远”端，然后逐步回溯，在回溯的路上放下若干个数的炸弹，所以答案就是该连通块的大小的平方；当x == 0时，答案就是所有连通块的sz平方和，容易发现这是对的。

AC代码：

#include<bits/stdc++.h>
#define i64 long long

using namespace std;
const int maxn=1e6+10;
const int inf = 0x3f3f3f3f;

int fa[maxn],sz[maxn];
int a[maxn];
int f[maxn];

int find(int x){
  return x==fa[x]?x:fa[x]=find(fa[x]);
}

void merge(int x,int y){
  x=find(x);
  y=find(y);
  if(x==y) return;//切记
  if(sz[x]>sz[y]) swap(x,y);//启发式合并
  fa[x]=y;
  sz[y]+=sz[x];
  sz[x]=0;
}

void slv(){
  int n,m;
  cin>>n>>m;
  int u,v;
  for(int i=1;i<=n;i++){
      sz[i]=1;
      fa[i]=i;
  }
  for(int i=1;i<=m;i++){
      cin>>u>>v;
      if(u==v) continue;
      merge(u,v);
  }
  for(int i=1;i<=n;i++) cin>>a[i];
  set<int> st;//存储存在1的连通块代表
  for(int i=1;i<=n;i++){
      int x=find(i);
      if(a[i]){
          st.insert(x);
      }
  }
  if(st.size()>1){
      cout<<0<<'\n';
  }else if(st.size()==1){
      cout<<(i64)sz[*st.begin()]*sz[*st.begin()]<<'\n';
  }else{
      i64 tt=0;
      for(int i=1;i<=n;i++){
          int x=find(i);
          if(!f[x])tt+=(i64)sz[x]*sz[x];
          f[x]=1;
      }
      cout<<tt<<'\n';
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int _=1;
  // cin>>_;
  while(_--) slv();
}

G:鸡格线

题目链接：https://ac.nowcoder.com/acm/contest/46800/G

思路：可以发现，f(x)=round(10sqrt(x))收敛的很快，随便打个表可以发现1e9的数据都可以在11次只能收敛到100在打表的过程中，我们会发现：0只能收敛到0,小于100的数会收敛到99，最多需要9次；大于等于100的数都会收敛到100，且最多11次
我们可以发现收敛速度很快导致其实很多的k是无用功，也就是说我们可以暴力地处理还没有收敛好的数让它在11次之内收敛完全。接下来：我们需要去找到，第一种操作什么时候是在做无用功，即：第一次操作中有没有区间是已经全部收敛了。当然可以，我们只需要建立一个线段树，每个节点上维护总和，区间最大值，区间最小值即可。modify操作中，假如当前节点最小值大于等于99，最大值小于等于100，那么直接return无需进行修改，因为已经完全收敛了，然后就是基本的线段树格式，两种操作。需要注意的是，我们在建树时要注意0的情况，假如叶子节点数值为0，我们给这个叶子节点分配的sum依然是0，不过_max和_min应该设置为99或者100，这样可以方便modify操作，同时，如果不进行这个操作，其实下面这组生成数据就可以卡成TLE:

数据生成：

void slv(){
    for(int i=1;i<=50000;i++){
        cout<<1000000000<<' '<<0<<' ';
    }
}

原因就是：0不在优化范围内，每次modify还是要遍历到叶子结点，这样均摊复杂度就是o(n)的，会超时

AC代码：

#include<bits/stdc++.h>
#define i64 long long

using namespace std;
const int maxn=1e5+10;
const int inf = 0x3f3f3f3f;

// pair<int,int> get(int x){
//     set<int> st;
//     int tt=0;
//     st.insert(x);
//     while(1){
//         x=round(10*sqrt(x));
//         if(st.find(x)==st.end()){
//             st.insert(x);
//         }else{
//             break;
//         }
//         ++tt;
//     }
//     return {x,tt};
// }

int n,m;
int a[maxn];

struct sgt{
    int l,r;
    i64 _max,_min;
    i64 sum=0;
}tr[4*maxn];

void pushup(int p){
    tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
    tr[p]._min=min(tr[p<<1]._min,tr[p<<1|1]._min);
    tr[p]._max=max(tr[p<<1]._max,tr[p<<1|1]._max);
}

void build(int p,int l,int r){
    tr[p].l=l;
    tr[p].r=r;
    if(l==r){
        tr[p].sum=tr[p]._max=tr[p]._min=a[l];
        if(a[l]==0) tr[p]._min=tr[p]._max=100;
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
}

void modify(int p,int l,int r,int k){
    if(l<=tr[p].l&&tr[p].r<=r&&(tr[p]._min>=99&&tr[p]._max<=100)){
        return;
    }
    if(tr[p].l==tr[p].r){
        int las=k;
        while(las){
            tr[p].sum=round(10*sqrt(tr[p].sum));
            --las;
            if(tr[p].sum==100||tr[p].sum==99)break;
        }
        tr[p]._min=tr[p]._max=tr[p].sum;
        return;
    }
    int mid=(tr[p].l+tr[p].r)>>1;
    if(l<=mid) modify(p<<1,l,r,k);
    if(mid<r) modify(p<<1|1,l,r,k);
    pushup(p);
}

// i64 query(int p,int l,int r){
//     if(l<=tr[p].l&&tr[p].r<=r){
//         return tr[p].sum;
//     }
//     i64 ans=0;
//     int mid=(tr[p].l+tr[p].r)>>1;
//     if(l<=mid)ans+=query(p<<1,l,r);
//     if(mid<r) ans+=query(p<<1|1,l,r);
//     return ans;
// }

void slv(){
    //最后只有 0,99 100
    //打表发现收敛次数最多不超过11次
    //也就是如果一段区间min<99||max>100才有处理的必要,或者是0
    //随便乱搞一下线段树
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    int op,l,r,k;
    build(1,1,n);
    while(m--){
        cin>>op;
        if(op==1){
            cin>>l>>r>>k;
            modify(1,l,r,k);
        }else{
            cout<<tr[1].sum<<'\n';
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _=1;
    // cin>>_;
    while(_--) slv();
}