報(bào)同步賽的時(shí)候出了些意外。于是僅僅能做一做“滯后賽”了2333
DAY1
T1離線+離散化搞，對于相等的部分直接并查集，不等部分查看是否在同一并查集中就可以，code：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int t,n; int father[200001]; struct hp{int kind,x,y;bool operator < (const hp &a) const{return kind>a.kind;} }qst[200001]; int b[400001]; int find(int x) {if (x!=father[x])father[x]=find(father[x]);return father[x]; } int main() {int i,st,r1,r2,size;bool f;freopen("prog.in","r",stdin);freopen("prog.out","w",stdout); scanf("%d",&t);while (t--){scanf("%d",&n);for (i=1;i<=n;++i){scanf("%d%d%d",&qst[i].x,&qst[i].y,&qst[i].kind);b[i*2-1]=qst[i].x; b[i*2]=qst[i].y; }sort(b+1,b+2*n+1);size=unique(b+1,b+2*n+1)-b-1;for (i=1;i<=n;++i){qst[i].x=upper_bound(b+1,b+size+1,qst[i].x)-b-1;qst[i].y=upper_bound(b+1,b+size+1,qst[i].y)-b-1;}sort(qst+1,qst+n+1);for (i=1;i<=size;++i)father[i]=i;st=n+1; for (i=1;i<=n;++i){if (qst[i].kind==0) {st=i; break;}r1=find(qst[i].x);r2=find(qst[i].y);if (r1!=r2) father[r1]=r2; }f=false;for (i=st;i<=n;++i){r1=find(qst[i].x);r2=find(qst[i].y);if (r1==r2) {f=true; break;}}if (f) printf("NO\n");else printf("YES\n"); } }

T2裸鏈剖啊。同【HAOI 2015】T2，對于子樹問題能夠在建樹的時(shí)候記錄一下子樹的左右邊界。（據(jù)說這題現(xiàn)場200+人AC，大天朝的數(shù)據(jù)結(jié)構(gòu)啊） code：

#include<iostream> #include<cstdio> #include<cstring> #define mid (l+r)/2 #define lch i<<1,l,mid #define rch i<<1|1,mid+1,r using namespace std; struct hp{int size,top,wson,dep,fat; }tree[100001]; int plc[100001],ls[100001],rs[100001]; int seg[400001],delta[400001]; int totw,e,n,m,ans; struct hq{int u,v; }a[200001]; int point[100001],next[200001]; void add(int u,int v) {e++; a[e].u=u; a[e].v=v; next[e]=point[u]; point[u]=e; } void build_tree(int now,int last,int depth) {int i;tree[now].dep=depth;tree[now].size=1;tree[now].wson=0;tree[now].fat=last;for (i=point[now];i;i=next[i])if (a[i].v!=last){build_tree(a[i].v,now,depth+1);tree[now].size+=tree[a[i].v].size;if (tree[tree[now].wson].size<tree[a[i].v].size)tree[now].wson=a[i].v;} } void build_seg(int now,int tp) {int i;tree[now].top=tp; plc[now]=++totw;ls[now]=totw;if (tree[now].wson!=0)build_seg(tree[now].wson,tp);for (i=point[now];i;i=next[i])if (a[i].v!=tree[now].fat&&a[i].v!=tree[now].wson)build_seg(a[i].v,a[i].v);rs[now]=totw; } void updata(int i) {seg[i]=seg[i<<1]+seg[i<<1|1]; } void paint(int i,int l,int r,int a) {seg[i]=a*(r-l+1);delta[i]=a; } void pushdown(int i,int l,int r) {paint(lch,delta[i]);paint(rch,delta[i]);delta[i]=-1; } void insert(int i,int l,int r,int x,int y,int a) {if (x<=l&&y>=r){paint(i,l,r,a);return;}if (delta[i]!=-1)pushdown(i,l,r);if (x<=mid) insert(lch,x,y,a);if (y>mid) insert(rch,x,y,a);updata(i); } void query(int i,int l,int r,int x,int y,int a) {if (x<=l&&y>=r){if (a==1) ans=ans+seg[i];if (a==0) ans=ans+r-l+1-seg[i];return;}if (delta[i]!=-1)pushdown(i,l,r);if (x<=mid) query(lch,x,y,a);if (y>mid) query(rch,x,y,a); } void work(int x,int y) {int f1=tree[x].top,f2=tree[y].top;ans=0;while (f1!=f2){if (tree[f1].dep<tree[f2].dep) {swap(x,y); swap(f1,f2);}query(1,1,n,plc[f1],plc[x],0);insert(1,1,n,plc[f1],plc[x],1);x=tree[f1].fat; f1=tree[x].top;}if (tree[x].dep>tree[y].dep) swap(x,y); query(1,1,n,plc[x],plc[y],0);insert(1,1,n,plc[x],plc[y],1);printf("%d\n",ans); } void build(int i,int l,int r) {delta[i]=-1;if (l==r){seg[i]=0;return;}build(lch); build(rch);updata(i); } int main() {int i,x;char s[20];scanf("%d",&n);for (i=1;i<=n-1;++i){scanf("%d",&x);x++; add(x,i+1); }build_tree(1,0,0);build_seg(1,1);build(1,1,n);scanf("%d",&m);for (i=1;i<=m;++i){scanf("%s",&s);while (s[0]!='u'&&s[0]!='i') scanf("%s",&s);if (s[0]=='i'){scanf("%d",&x);x++;work(1,x);} if (s[0]=='u'){scanf("%d",&x);x++; ans=0;query(1,1,n,ls[x],rs[x],1);insert(1,1,n,ls[x],rs[x],0);printf("%d\n",ans);}} }

T3。考試沒想出來，交的30分還打的表，最后10分鐘跑出來n=30的數(shù)據(jù)，嚇尿了= =；
UPD:這題事實(shí)上就是一個(gè)狀壓DP，考慮每一個(gè)數(shù)加到一個(gè)集合中，相當(dāng)于增加一個(gè)其質(zhì)因數(shù)，而考慮每一個(gè)數(shù)n至多一個(gè)大于其n√的因子。于是我們能夠僅僅考慮小質(zhì)因子的情況，最后再減去同樣大質(zhì)因子。詳見PoPoQQQ神犇的題解 code：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n; long long f[301][301],p[3][301][301]; int pri[9]={0,2,3,5,7,11,13,17,19}; struct hp{int prime;int set;bool operator < (const hp &a) const{return ((prime<a.prime)||(prime==a.prime&&set<a.set));} }num[501]; long long P; int main() {int i,j,k,t;long long ans;freopen("dinner.in","r",stdin);freopen("dinner.out","w",stdout);scanf("%d%I64d",&n,&P);for (i=1;i<=n;++i){num[i].set=0; t=i;for (j=1;j<=8;++j)if (t%pri[j]==0){num[i].set=num[i].set+(1<<(j-1)); while (t%pri[j]==0)t/=pri[j];}num[i].prime=t;}sort(num+2,num+n+1);f[0][0]=1;for (i=2;i<=n;++i){if (i==2||num[i].prime==1||num[i].prime!=num[i-1].prime){memcpy(p[1],f,sizeof(f));memcpy(p[2],f,sizeof(f));}for (j=255;j>=0;--j)for (k=255;k>=0;--k)if ((j&k)==0){if ((k&num[i].set)==0) p[1][j|num[i].set][k]=(p[1][j|num[i].set][k]+p[1][j][k])%P;if ((j&num[i].set)==0) p[2][j][k|num[i].set]=(p[2][j][k|num[i].set]+p[2][j][k])%P;}if (i==n||num[i].prime==1||num[i].prime!=num[i+1].prime){for (j=0;j<=255;++j)for (k=0;k<=255;++k)if ((j&k)==0){f[j][k]=((p[1][j][k]+p[2][j][k]-f[j][k])%P+P)%P;}}}ans=0;for (i=0;i<=255;++i)for (j=0;j<=255;++j)if ((i&j)==0)ans=(ans+f[i][j])%P;printf("%I64d\n",ans); }

DAY2：
T1，考慮兩個(gè)數(shù)的編碼不存在一個(gè)是還有一個(gè)前綴的，在樹上就相當(dāng)于不存在兩個(gè)點(diǎn)之間有父子關(guān)系。

而長度最短就相當(dāng)于讓權(quán)值與到根路徑的乘積和最短。

這不就是k叉哈夫曼樹么，對于不夠k的能夠先補(bǔ)零，然后同合并果子code：

#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; struct hp{long long num;int dep;bool operator < (const hp &a) const{return (num>a.num)||(num==a.num&&dep>a.dep);} }; int n,k; priority_queue<hp> q; int main() {long long a,x,ans=0;int i,depth;freopen("epic.in","r",stdin);freopen("epic.out","w",stdout);hp minn;scanf("%d%d",&n,&k);for (i=1;i<=n;++i){scanf("%lld",&a);q.push((hp){a,0});}if (k!=2){while (n%(k-1)!=1){n++;q.push((hp){0,0});}}while (n!=1){x=0; depth=0;for (i=1;i<=k;++i){minn=q.top();x=x+minn.num;depth=max(depth,minn.dep);q.pop();}n=n-k+1;ans+=x;q.push((hp){x,depth+1});}minn=q.top();printf("%lld\n%d\n",ans,minn.dep); }

T2：學(xué)后綴數(shù)組在BZOJ上就做了兩道題，【AHOI 2013】差異和【JSOI 2007】字符加密。后者是裸題，而前者差點(diǎn)兒與此題一模一樣，都能夠分治的做。做法似乎被卡了常數(shù)，按點(diǎn)時(shí)限可能會(huì)T一到兩個(gè)點(diǎn)。總時(shí)限的話沒有問題。

code：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define mid (l+r)/2 #define lch i<<1,l,mid #define rch i<<1|1,mid+1,r #define inf 2100000000LL using namespace std; char s[300001]; int n,maxm; int sa[300001],rank[300001],height[300001]; int c[300001],x[300001],y[300001]; long long val[300001]; int t,ti; long long txl,txr,tnl,tnr; struct hq{long long tot,maxn; }ans[300001]; struct hp{int sim,mini;long long minn,maxn; }seg[1200001]; bool cmp(int *y,int i,int j,int k) { int a,b,c,d; a=y[i]; b=y[j]; c=i+k>=n?-1:y[i+k]; d=j+k>=n?

-1:y[j+k]; return a==b&&c==d; } void build_sa() { int i,j,k; for (i=0;i<maxm;++i) c[i]=0; for (i=0;i<n;++i) c[x[i]=s[i]]++; for (i=1;i<maxm;++i) c[i]+=c[i-1]; for (i=n-1;i>=0;--i) sa[--c[x[i]]]=i; for (k=1;k<=n;k<<=1) { int p=0; for (i=n-k;i<n;++i) y[p++]=i; for (i=0;i<n;++i) if (sa[i]>=k) y[p++]=sa[i]-k; for (i=0;i<maxm;++i) c[i]=0; for (i=0;i<n;++i) c[x[y[i]]]++; for (i=1;i<maxm;++i) c[i]+=c[i-1]; for (i=n-1;i>=0;--i) sa[--c[x[y[i]]]]=y[i]; swap(x,y); p=1; x[sa[0]]=0; for (i=1;i<n;++i) x[sa[i]]=cmp(y,sa[i],sa[i-1],k)?p-1:p++; if (p>=n) break; maxm=p; } for (i=0;i<n;++i) rank[sa[i]]=i; k=0; for (i=0;i<n;++i) { if (!rank[i]) continue; if (k) k--; j=sa[rank[i]-1]; while (s[i+k]==s[j+k]) k++; height[rank[i]]=k; } } void updata(int i) { seg[i].sim=min(seg[i<<1].sim,seg[i<<1|1].sim); if (seg[i<<1].sim<=seg[i<<1|1].sim) seg[i].mini=seg[i<<1].mini; else seg[i].mini=seg[i<<1|1].mini; seg[i].minn=min(seg[i<<1].minn,seg[i<<1|1].minn); seg[i].maxn=max(seg[i<<1].maxn,seg[i<<1|1].maxn); } void build(int i,int l,int r) { if (l==r) { seg[i].sim=height[l]; seg[i].mini=l; seg[i].minn=seg[i].maxn=val[l]; return; } build(lch); build(rch); updata(i); } void query(int i,int l,int r,int x,int y,int kind) { if (x<=l&&y>=r) { if (kind==0) if (seg[i].sim<t) {t=seg[i].sim; ti=seg[i].mini;} if (kind==1) {txl=max(txl,seg[i].maxn); tnl=min(tnl,seg[i].minn);} if (kind==2) {txr=max(txr,seg[i].maxn); tnr=min(tnr,seg[i].minn);} return; } if (x<=mid) query(lch,x,y,kind); if (y>mid) query(rch,x,y,kind); } void work(int l,int r) { int tti; if (l==r) return; t=n+1; ti=-1; query(1,0,n-1,l+1,r,0); tti=ti; ans[t+1].tot=ans[t+1].tot+(long long)((long long)(r-ti+1)*(long long)(ti-l)); txl=-inf; tnl=inf; query(1,0,n-1,l,ti-1,1); txr=-inf; tnr=inf; query(1,0,n-1,ti,r,2); ans[t+1].maxn=max(ans[t+1].maxn,max(txl*txr,tnl*tnr)); work(l,tti-1); work(tti,r); } int main() { int i; int a; freopen("savour.in","r",stdin); freopen("savour.out","w",stdout); scanf("%d",&n); scanf("%s",&s); while (s[0]<'a'||s[0]>'z') scanf("%s",&s); for (i=0;i<n;++i) maxm=max(maxm,(int)(s[i])); maxm++; build_sa(); for (i=0;i<n;++i) { scanf("%d",&a); val[rank[i]]=(long long)a; ans[i+1].tot=0; ans[i+1].maxn=-1000000000000000000LL; } build(1,0,n-1); work(0,n-1); for (i=n-1;i>=1;--i) {ans[i].tot=ans[i].tot+ans[i+1].tot; ans[i].maxn=max(ans[i].maxn,ans[i+1].maxn);} for (i=1;i<=n;++i) { if (ans[i].tot==0) ans[i].maxn=0; printf("%lld %lld\n",ans[i].tot,ans[i].maxn); } }

T3并沒有看懂題解，（我會(huì)說我連題目都看得迷迷糊糊的么= =）
以后再研究吧= =

總結(jié)

以上是生活随笔為你收集整理的NOI 2015 滞后赛解题报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。