Atcoder ABC 177 题解

ABC就不多说了。。。

D

显然可以一个带权值的并查集就可以维护了

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double dd;
const int N = 3e5+5;
const dd eps = 1e-8;
const int mod = 1e9+7;
int fa[N],siz[N];
int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
void merge(int u,int v){
  int x = find(u),y = find(v);
  if(x != y){
    fa[x] = y;
    siz[y] += siz[x];
  }
}
int n,m,a,b;
int main(){
  // freopen("input.txt","r",stdin);
  cin>>n>>m;
  for(int i = 1;i <= n;i++) fa[i] = i,siz[i] = 1;
  for(int i = 1;i <= m;i++){
    cin>>a>>b;
    merge(a,b);
  }
  int ans = 0;
  for(int i = 1;i <= n;i++){
    ans = max(ans,siz[find(i)]);
  }
  cout<<ans<<endl;
  return 0;
}

E

用类似筛法和多数gcd处理一下就好了

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double dd;
const int N = 2e6+5;
const dd eps = 1e-8;
const int mod = 1e9+7;
int n,vis[N],vis2[N];
ll gcd(ll a,ll b){
  if(b==0) return a;
  else return gcd(b,a%b);
}
ll a[N];
int main(){
  ios::sync_with_stdio(false);
  // freopen("input.txt","r",stdin);
  ll now = 0;
  cin>>n;
  bool paok = true;
  bool seok = true;
  bool have1 = false;
  for(int i = 1;i <= n;i++) {cin>>a[i];}
  for(int i = 1;i <= n;i++){
    now = gcd(now,a[i]);
    vis[a[i]]++;
  }
  for(int i = 2;i <= 1e6+100;i++){
    for(int j = i;j <= 1e6+100;j+=i){
      if(vis[j]) vis2[i]+=vis[j];
    }
  }
  for(int i = 2;i <= 1e6+100;i++){
    if(vis2[i] > 1) {paok = false;break;}
  }
  if(have1) paok = false;
  if(now != 1) seok = false;
  if(paok) cout<<"pairwise coprime"<<endl;
  else if(seok or have1) cout<<"setwise coprime"<<endl;
  else cout<<"not coprime"<<endl;
  return 0;
}

F

这题的话。。。如果范围是1e3左右的话就是个很裸的DP了，可是对于2e5这种级别的数据，只能考虑去用数据结构维护了。

于是我们可以维护一个线段树，维护每一层的 $[1,W]$ 的区间，对于给定的A和B，我们可以对 $[1,A)$ 和 $(B,W]$ 这个区间直接+1，而对其中的数暴力转移，对于一个为 $[l,r]$ 的区间，可以用 $f[i] = f[l-1] + i-l+1$ 来转移，同时还要询问的时候维护最小值就好了

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double dd;
const int N = 2e5+5;
const dd eps = 1e-8;
const int mod = 1e9+7;
ll ans[N],h,w,a,b;
inline int lc(int x){return x<<1;}
inline int rc(int x){return x<<1|1;}

struct node{
  int l,r;
  ll segl = 0,segmin = 0,lazy = 0;
  bool flag = false;
}t[N<<2];

void build(int p,int l,int r){
  t[p].l = l;t[p].r = r;
  if(l == r) return;
  int mid = (l+r)>>1;
  build(lc(p),l,mid);build(rc(p),mid+1,r);
}

void push_down(int p){
  if(t[p].flag){
    for(int i = lc(p);i <= rc(p);i++){
      t[i].segl = t[i].segmin = t[p].segl + t[i].l - t[p].l;
      t[i].lazy = 0;t[i].flag = true;
    }
  }
  else if(t[p].lazy){
    for(int i = lc(p);i <= rc(p);i++){
      t[i].segl += t[p].lazy;
      t[i].segmin += t[p].lazy;
      t[i].lazy += t[p].lazy;
    }
  }
  t[p].flag = false;t[p].lazy = 0;
}

void update(int p,int l,int r,ll val){
  if(t[p].l >= l and t[p].r <= r){
    t[p].segl = t[p].segmin = val + t[p].l - l + 1;
    t[p].flag = true;t[p].lazy = 0;return;
  }
  push_down(p);
  int mid = (t[p].l + t[p].r)>>1;
  if(l <= mid) update(lc(p),l,r,val);
  if(mid + 1 <= r) update(rc(p),l,r,val);
  t[p].segl = t[lc(p)].segl;
  t[p].segmin = min(t[lc(p)].segmin,t[rc(p)].segmin);
}

void add(int p,int l,int r){
  if(t[p].l >= l and t[p].r <= r){
    t[p].lazy++;t[p].segl++;t[p].segmin++;return;
  }
  push_down(p);
  int mid = (t[p].l + t[p].r)>>1;
  if(l <= mid) add(lc(p),l,r);
  if(mid+1 <= r) add(rc(p),l,r);
  t[p].segl = t[lc(p)].segl;
  t[p].segmin = min(t[lc(p)].segmin,t[rc(p)].segmin);
}

ll query(int p,int l,int r){
  if(r < 1 or l > w) return inf;
  if(t[p].l >= l and t[p].r <= r) return t[p].segmin;
  push_down(p);
  ll ans = inf;
  int mid = (t[p].l + t[p].r)>>1;
  if(l <= mid) ans = min(ans,query(lc(p),l,r));
  if(mid+1 <= r) ans = min(ans,query(rc(p),l,r));
  return ans;
}
int main(){
  ios::sync_with_stdio(false);
  // freopen("input.txt","r",stdin);
  cin>>h>>w;
  build(1,1,w);
  memset(ans,inf,sizeof(ans));
  for(int i = 1;i <= h;i++){
    cin>>a>>b;
    if(a > 1) add(1,1,a-1);
    if(b < w) add(1,b+1,w);
    ll L = query(1,a-1,a-1);
    update(1,a,b,L);
    ans[i] = min(ans[i],query(1,1,w));
    if(ans[i] > h+w) ans[i] = -1;
  }
  for(int i = 1;i <= h;i++){
    cout<<ans[i]<<endl;
  }
  return 0;
}

init0xyz的自留地

D

E

F

写题记录2