daily 2

CF 768C

打表的题,循环节是4

void solve(){
  int n,k,x;
  cin>>n>>k>>x;
  vector<int>maxx(k+1),minx(k+1);
  maxx[0]=-INF,minx[0]=INF;
  vector<int>a(n+1);
  for(int i=1;i<=n;++i){
    cin>>a[i];
    maxx[0]=max(maxx[0],a[i]);
    minx[0]=min(minx[0],a[i]);
  }
  auto check=[&](vector<int>&arr,int cur){
    return arr[cur]==arr[cur-1]&&arr[cur]==arr[cur-2]&&arr[cur]==arr[cur-3]&&arr[cur]==arr[cur-4];
  };
  for(int i=1;i<=k;++i){
    sort(a.begin()+1,a.end());
    maxx[i]=-INF;
    minx[i]=INF;
    for(int j=1;j<=n;++j){
        if(j&1){
            a[j]^=x;
        }
        maxx[i]=max(a[j],maxx[i]);
        minx[i]=min(a[j],minx[i]);
    }
    if(i>4&&check(maxx,i)&&check(minx,i)){
        cout<<maxx[i]<<' '<<minx[i]<<'\n';
        return;
    }
  }
  cout<<maxx.back()<<' '<<minx.back()<<'\n';
  return;
}

CF 766D
扩展并查集的板子题，有点像那个囚犯的题,有点水s

void solve(){
  int n,m,q;
  cin>>n>>m>>q;
  vector<string>sets(n+1);
  unordered_map<string,int>mp;
  vector<int>fa(2*n+1);
  for(int i=1;i<=n;++i){
    cin>>sets[i];
    mp[sets[i]]=i;
    fa[i]=i;
    fa[i+n]=i+n;
  }
  function<int(int)>find=[&](int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
  };
  for(int i=1;i<=m;++i){
    int t;
    string s1,s2;
    cin>>t>>s1>>s2;
    int u=mp[s1],v=mp[s2];
    switch (t)
    {
        case 1:{//same
            if(find(u)==find(v+n)){
                cout<<"NO\n";
            }else{
                cout<<"YES\n";
                fa[find(v)]=find(u);
                fa[find(v+n)]=find(u+n);
            }
            break;
        }
        case 2:{//diff
            if(find(v)==find(u)){
                cout<<"NO\n";
            }else{
                cout<<"YES\n";
                fa[find(v)]=find(u+n);
                fa[find(v+n)]=find(u);
            }
            break;
        }
        default:
            break;
    }
  }
  while(q--){
    string s1,s2;
    cin>>s1>>s2;
    int u=mp[s1],v=mp[s2];
    if(find(u)==find(v)){
        cout<<1<<'\n';
    }else if(find(u)==find(v+n)||find(v)==find(u+n)){
        cout<<2<<'\n';
    }else{
        cout<<3<<'\n';
    }
  }
  return;
}