今天一起做NOI的题。
我只想说SunshinAK了好神啊。
T3数据好坑啊，打表居然被编译环境卡掉了。。。
T1:程序自动分析
(?id=4195) T1还是非常水的，就是一道离散+并查集。
T2:软件包管理器
(?id=4196) T2是一道裸的链剖，将安装的点设成1，没有的为0，查询的就只是根到这个节点的区间和，和以这个节点为根的子树的区间和。然后就没了。
T3:寿司晚宴
(?id=4197) T1，T2都这么水，T3肯定就比较神了。我们根据题意可以知道和谐的集合说明两个集合中的元素两两互质，也就是两个集合的所有元素所含的质因数没有交集。 我们可以对于每个数分解一下质因数，但是质因子可能做多有80多个，显然不行。那么我们就可以将这些质因数分成两种，一种是大于sqrt(n)的，另一种是小于的(只有8个)。对于包含第一种的数我们分成一类，其它的分成另一类，这样以后我们就可以状压了。。 我们有二进制的每一位表示一个质因子的有无。 f[i][j]就表示第一个集合中质因子情况为i，另一个集合中的质因子情况为j的方案数。 g[1][j][k]表示当选到第i个数的时候，第一个集合选或者不选的方案数。那么当(k&number[i].use)==0时(也就是第i个数与第二个集合没有相同的质因数)，就加上这个值。 g[1][j][k]表示当选到第i个数的时候，第二个集合选或者不选的方案数。转移同上。 然后每次用g再去更新f。但是还有一种情况需要减去，，就是在i的时候g[1]和g[2]都选择了i，这种情况是不合法的，我们需要减去这种情况。
T1code：
;const int N=100100;int n,T,c[N*2],tot=0,fa[N*2];struct S{int x,y,z;}a[N];int find(int x){if(fa[x]!=x) fa[x]=find(fa[x]);return fa[x];}int main(){scanf(“%d”,&T);while(T–){int i,size;bool f=true;scanf(“%d”,&n);tot=0; memset(c,0,sizeof(c));for(i=1;i<=2*n;++i) fa[i]=i;for(i=1;i<=n;++i){scanf(“%d%d%d”,&a[i].x,&a[i].y,&a[i].z);c[++tot]=a[i].x;c[++tot]=a[i].y;}sort(c+1,c+tot+1);size=unique(c+1,c+tot+1)-c-1;for(i=1;i<=n;++i){tot=a[i].x;a[i].x=upper_bound(c+1,c+size+1,a[i].x)-c-1;tot=a[i].y;a[i].y=upper_bound(c+1,c+size+1,a[i].y)-c-1;}for(i=1;i<=n;++i)if(a[i].z){int r1=find(a[i].x),r2=find(a[i].y);if(r1!=r2) fa[r1]=r2;}for(i=1;i<=n;++i)if(!a[i].z)if(find(a[i].x)==find(a[i].y)){f=false;break;}if(f) printf(“YES\n”);else printf(“NO\n”);}}
T2code：
using namespace std;const int N=100100;int n,q,tot=1,point[N],next[N*4],tr[N*4],num=0,siz[N];int deep[N],li[N],ri[N],belong[N],pos[N],fa[N],de[N*4];struct S{int st,en;}aa[N*4];char ch[20];void add(){tot+=1;next[tot]=point[x];point[x]=tot;aa[tot].st=x;aa[tot].en=y;tot+=1;next[tot]=point[y];point[y]=tot;aa[tot].st=y;aa[tot].en=x;}void dfs_1(){int i;siz[x]=1;fa[x]=last;for(i=point[x];i;i=next[i])if(aa[i].en!=last){deep[aa[i].en]=deep[x]+1;dfs_1(aa[i].en,x);siz[x]+=siz[aa[i].en];}}void dfs_2(){int i,k=0;num+=1;belong[x]=y;li[x]=ri[x]=pos[x]=num;for(i=point[x];i;i=next[i])if(deep[aa[i].en]>deep[x]&&siz[k]<siz[aa[i].en])k=aa[i].en;if(k==0) return ;dfs_2(k,y);li[x]=min(li[x],li[k]);ri[x]=max(ri[x],ri[k]);for(i=point[x];i;i=next[i])if(deep[aa[i].en]>deep[x]&&k!=aa[i].en){dfs_2(aa[i].en,aa[i].en);li[x]=min(li[x],li[aa[i].en]);ri[x]=max(ri[x],ri[aa[i].en]);}}void paint(int k,int l,int r,int z){if(z==0) tr[k]=0;if(z==1) tr[k]=r-l+1;de[k]=z;}void pushdown(int k,int l,int r){paint(k<<1,l,mid,de[k]);paint(k<<1|1,mid+1,r,de[k]);de[k]=-1;}void insert(,int z){if(x<=l&&y>=r){paint(k,l,r,z);return ;}if(de[k]>=0) pushdown(k,l,r);if(x<=mid) insert(L,x,y,z);if(y>mid) insert(R,x,y,z);tr[k]=tr[k<<1]+tr[k<<1|1];}){int sum=0;if(x<=l&&y>=r) return tr[k];if(de[k]>=0) pushdown(k,l,r);if(x<=mid) sum+=query(L,x,y);if(y>mid) sum+=query(R,x,y);return sum;}){int sum=0;while(belong[x]!=belong[y]){sum+=query(1,1,n,pos[belong[x]],pos[x]);insert(1,1,n,pos[belong[x]],pos[x],1);x=fa[belong[x]];}sum+=query(1,1,n,pos[y],pos[x]);insert(1,1,n,pos[y],pos[x],1);return sum;}int main(){int i,x;scanf(“%d”,&n);memset(de,128,sizeof(de));for(i=2;i<=n;++i){scanf(“%d”,&x);add(x+1,i);}dfs_1(1,0); dfs_2(1,1);scanf(“%d”,&q);while(q–){scanf(“%*c%s%d”,&ch,&x); x+=1;if(ch[0]==’i’) printf(“%d\n”,deep[x]+1-ask(x,1));if(ch[0]==’u’){printf(“%d\n”,query(1,1,n,li[x],ri[x]));insert(1,1,n,li[x],ri[x],0);}}}不义而富且贵，于我如浮云。
