首页 > 其他分享 >C141 线段树分治+线性基 P3733 [HAOI2017] 八纵八横

C141 线段树分治+线性基 P3733 [HAOI2017] 八纵八横

时间:2024-07-27 19:17:58浏览次数:14  
标签:C141 int 八横 sum P3733 -- bit include any

视频链接:C141 线段树分治+线性基 P3733 [HAOI2017] 八纵八横_哔哩哔哩_bilibili

 

 

 

P3733 [HAOI2017] 八纵八横 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// 线段树分治+线性基 O(q*logq*logL*logL)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <vector>
using namespace std;

#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)
const int N=1005;
typedef bitset<N> bit;
vector<bit> tr[N<<2]; //节点
bit sum[N],val[N];
int n,m,q,x,y,k;
char s[N],z[N];
int vis[N],tim[N],cnt;
int head[N],idx;
struct edge{
  int to,ne; bit w;
}e[N<<1]; //原边
struct edge2{
  int x,y;
}a[N<<1]; //新边
bit p[N]; //初始的线性基

void add(int x,int y,bit w){
  e[++idx].to=y;
  e[idx].ne=head[x];
  e[idx].w=w;
  head[x]=idx;
}
void print(bit a[]){
  int i,j; bit c;
  for(i=1000;i>=0&&!a[i].any();i--)
  if(i<0){puts("0");return;}
  
  for(j=i;j>=0;j--)
    if(a[j].any()&&!c[j]) c^=a[j];
  for(j=i;j>=0;j--) putchar('0'+c[j]);
  puts("");
}
void insert(bit a[],bit x){ //插入线性基
  if(!x.any()) return;
  for(int i=1000;i>=0;i--){
    if(x[i]){
      if(!a[i].any()){
        a[i]=x;
        break;
      }
      x^=a[i];
    }
  }
}
void dfs(int x){
  vis[x]=1;
  for(int i=head[x];i;i=e[i].ne){
    int y=e[i].to;
    if(!vis[y]) sum[y]=sum[x]^e[i].w,dfs(y);
    else insert(p,sum[x]^e[i].w^sum[y]);
  }
}
void ins(int u,int l,int r,int L,int R,bit x){
  if(l>R||r<L) return;
  if(L<=l&&r<=R){
    tr[u].push_back(x);
    return;
  }
  ins(ls,l,mid,L,R,x);
  ins(rs,mid+1,r,L,R,x);
}
void solve(int u,int l,int r,bit a[]){
  bit b[N];
  for(int i=1000;i>=0;i--) b[i]=a[i];
  for(auto i:tr[u]) insert(b,i); //插入基
  
  if(l==r){
    print(b); return;
  }
  solve(ls,l,mid,b);
  solve(rs,mid+1,r,b);
}
int main(){
  scanf("%d%d%d",&n,&m,&q);
  for(int i=1;i<=m;i++){
    scanf("%d%d%s",&x,&y,z);
    bit w(z);
    add(x,y,w); add(y,x,w);
  }
  dfs(1);
  print(p);
  
  for(int i=1;i<=q;i++){
    scanf("%s",s);
    if(s[1]=='d'){ //Add
      scanf("%d%d%s",&x,&y,z);
      tim[++cnt]=i; //第k号边的出现时刻
      bit w(z);
      a[cnt]={x,y};
      val[cnt]=sum[x]^sum[y]^w; //环值
    }
    else if(s[1]=='h'){ //Change
      scanf("%d%s",&k,z);
      ins(1,1,q,tim[k],i-1,val[k]); //插入树
      tim[k]=i; //第k号边的出现时刻
      bit w(z);
      val[k]=sum[a[k].x]^sum[a[k].y]^w; //环值
    }
    else{ //Cancel
      scanf("%d",&k);
      ins(1,1,q,tim[k],i-1,val[k]); //插入树
      tim[k]=q+1; //第k号边消失
    }
  }
  for(int i=1;i<=cnt;i++)
    ins(1,1,q,tim[i],q,val[i]); //插入树
  if(q) solve(1,1,q,p); //分治
}

 

// 线段树分治+线性基 O(q*logq*logL*logL)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <vector>
using namespace std;

#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)
const int N=1005;
typedef bitset<N> bit;
vector<bit> tr[N<<2]; //节点
bit sum[N],val[N];
int n,m,q,x,y,k;
char s[N],z[N];
int vis[N],tim[N],cnt;
int head[N],idx;
struct edge{
  int to,ne; bit w;
}e[N<<1]; //原边
struct edge2{
  int x,y;
}a[N<<1]; //新边
struct bs{
  bit b[N];
}p; //初始的线性基

void add(int x,int y,bit w){
  e[++idx].to=y;
  e[idx].w=w;
  e[idx].ne=head[x];
  head[x]=idx;
}
void print(bs &a){
  int i,j; bit c;
  for(i=1000;i>=0&&!a.b[i].any();i--)
  if(i<0){puts("0");return;}
  
  for(j=i;j>=0;j--)
    if(a.b[j].any()&&!c[j]) c^=a.b[j];
  for(j=i;j>=0;j--) putchar('0'+c[j]);
  puts("");
}
void insert(bs &a,bit x){ //注意bs传地址
  if(!x.any()) return;
  for(int i=1000;i>=0;i--){
    if(x[i]){
      if(!a.b[i].any()){
        a.b[i]=x;
        break;
      }
      x^=a.b[i];
    }
  }
}
void dfs(int x){
  vis[x]=1;
  for(int i=head[x];i;i=e[i].ne){
    int y=e[i].to;
    if(!vis[y]) sum[y]=sum[x]^e[i].w,dfs(y);
    else insert(p,sum[x]^e[i].w^sum[y]);
  }
}
void ins(int u,int l,int r,int L,int R,bit x){
  if(l>R||r<L) return;
  if(L<=l&&r<=R){
    tr[u].push_back(x);
    return;
  }
  ins(ls,l,mid,L,R,x);
  ins(rs,mid+1,r,L,R,x);
}
void solve(int u,int l,int r,bs a){ //注意bs传值
  for(auto i:tr[u]) insert(a,i); //插入基
  
  if(l==r){
    print(a); //输出
    return;
  }
  solve(ls,l,mid,a);
  solve(rs,mid+1,r,a);
}
int main(){
  scanf("%d%d%d",&n,&m,&q);
  for(int i=1;i<=m;i++){
    scanf("%d%d%s",&x,&y,z);
    bit w(z);
    add(x,y,w); add(y,x,w);
  }
  dfs(1);
  print(p);
  
  for(int i=1;i<=q;i++){
    scanf("%s",s);
    if(s[1]=='d'){ //Add
      scanf("%d%d%s",&x,&y,z);
      tim[++cnt]=i; //第k号边的出现时刻
      bit w(z);
      a[cnt]={x,y};
      val[cnt]=sum[x]^sum[y]^w; //环值
    }
    else if(s[1]=='h'){ //Change
      scanf("%d%s",&k,z);
      ins(1,1,q,tim[k],i-1,val[k]); //插入树
      tim[k]=i; //第k号边的出现时刻
      bit w(z);
      val[k]=sum[a[k].x]^sum[a[k].y]^w; //环值
    }
    else{ //Cancel
      scanf("%d",&k);
      ins(1,1,q,tim[k],i-1,val[k]); //插入树
      tim[k]=q+1; //第k号边消失
    }
  }
  for(int i=1;i<=cnt;i++)
    ins(1,1,q,tim[i],q,val[i]); //插入树
  if(q) solve(1,1,q,p); //分治
}

 

标签:C141,int,八横,sum,P3733,--,bit,include,any
From: https://www.cnblogs.com/dx123/p/18248613

相关文章

  • G71 可删除线性基+离线处理 P3733 [HAOI2017] 八纵八横
    视频链接:G71可删除线性基+离线处理P3733[HAOI2017]八纵八横_哔哩哔哩_bilibili   G67线性基+贪心法P4151[WC2011]最大XOR和路径-董晓-博客园(cnblogs.com) P3733[HAOI2017]八纵八横-洛谷|计算机科学教育新生态(luogu.com.cn)//可删除线性基+离......
  • ABC141F
    偶然找到的线性基好题。考虑\(s=\bigoplusx_i\),则此时\(b=s\oplusa\),问题变为\(\max(a+(s\oplusa))\)。然后观察\(s\),有一个很典的想法是,\(s\)为\(0\)的位上,\(a\)如果是\(0\)则会产生\(0\)的贡献,否则产生\(2\),\(s\)为\(1\)的位则稳定产生\(1\)的贡献,结合异......
  • [ARC141C] Bracket and Permutation
    考虑假设已知括号序列\(s\),如何求出\(p,q\)。对于求\(p\),考虑从\(s_1\)到\(s_n\)逐个往里放,如果能放就直接放,肯定不劣,否则就从后面抽最近的左括号放过来,然后继续放。不难证明不存在更优方案,对于\(q\)同理。接下来我们发现,如果\(p\)中存在\(p_i<p_{i-1}\),\(s_{p_{i......
  • [ARC141D] Non-divisible Set 题解
    题目链接点击打开链接题目解法很思维的题,需要用好所有的特殊性质暴力的做法是建出图,然后求包含点\(i\)的最长反链,但这明显过不了上面的做法没用到\(a_i<2m\)的性质如何用?把\(a_i\)拆分成\(q\times2^k\;(k\)为奇数\()\)的形式,那么对于同一个\(q\),只能在其中选一个......
  • [ARC141E] Sliding Edge on Torus 题解
    题目链接点击打开链接题目解法比较套路的题首先画个图,然后把\(y-x\)相同的变成一个点(使\(y>x\))然后再两个点之间连有权边那么问题就变成求新图的每个连通块中形成的原图的连通块数量手玩几个数据发现,原图的连通块数量即为新图的所有环长的\(\gcd\),再和\(n\)的\(\gcd......
  • 题解 ARC141D【Non-divisible Set】
    这个题不是网络流。problem我们说一个集合\(D\)是一个好的集合,当不存在集合中的两个不同元素\(a,b\)使得\(a\)是\(b\)的约数。给定\(N\)个整数的一个集合\(S\),值域均落在\([1,2*M]\)内。对\(S\)中的每个元素\(A_i\)询问:是否存在一个恰好包含\(A_i\)的\(......
  • 设计原理图:FMC141-四路 250Msps 16bits AD FMC子卡
     一、产品概述:   本板卡基于 FMC 标准板卡,实现 4 路 16-bit/250Msps ADC 功能。遵循 VITA 57 标准,板卡可以直接与xilinx公司或者本公司 FPGA 载板连接使用。板卡 ADC 器件采用 ADI 公司 AD9467 芯片,用户可以通过 FMC 接口配置芯片工作状......
  • arc139,arc140,arc141题解
    ARC139A-DATrailingZeros憨的。BMakeN感觉没有那么naive。首先用\(1\)去更新一下后面两个决策的价值。然后有一个较为显然的东西是说\(\text{lcm}\)为周期,周期内应该贪心取最大的。周期外由于范围很小,可以直接枚举一种决策的次数,取最小值即可。复杂度是正确的。CO......
  • ARC141
    ARC141B关注\(a\)递增和\(b\)递增,关注特殊,即最高位。发现最高位必然递增,DP即可。C关注\(P\)的形成过程。必然是先一段合法括号序列,再是若干\(a_i,a_{i+1}\),其中\(a_i>a_{i+1}\)且\(S_{a_{i}}=(\;,S_{a_{i+1}}=)\),如此往复。\(Q\)也是如此,如果出现冲突,考虑如果出......
  • [ABC141E] Who Says a Pun?
    WhoSaysaPunの传送门看到两个完全相同的子串,考虑dp。设\(f_{i,j}\)为从第\(i\)项和第\(j\)项开始的最长相同子串,则有\(s_i=s_j\)时,\(f_{i,j}=\max({f_{i-1,j-1}+1},f_{i,j})\)。注意,因为两个子串互不重叠,所以\(f_{i-1,j-1}<j-i\)时才可以转移状态。#include......