nbhkdz.com冰点文库

NOIP2015提高组解题报告


NOIP2015 提高组解题报告
T1 神奇的幻方
【题目大意】 告诉你幻方的构造方法,给出 N*N 幻方的方案。N≤39 且为奇数。 【解题说明】 直接模拟即可 【代码】 #include<cstdio> int n,m,i,j,x,y,a[55][55]; int main(){ scanf("%d",&n);m=n

*n;x=1;y=(n+1)/2;a[x][y]=1; for(i=2;i<=m;a[x][y]=i++) if(x==1&&y!=n)x=n,y++;else if(x!=1&&y==n)y=1,x--; else if(x==1&&y==n)x++,a[x][y]=i;else if(!a[x-1][y+1])x--,y++;else x++; for(i=1;i<=n;i++) for(j=1;j<=n;j++){ printf("%d",a[i][j]); if(j<n)printf(" ");else puts(""); } } 【时间复杂度】 O(n^2) 【空间复杂度】 O(n^2) 【思想难度】 6 【编程难度】 8 【总用时】5 min

T2 信息传递
【题目大意】 在若干颗基环+内向树中找到一个最小的环。N≤200000,无自环。 【解题说明】 30 分做法:Floyd 找最小环 60 分做法:每个点 BFS 一遍就可以了 100 分做法: ① 基环+内向树的找环 直接套模板即可 ② Tarjan 找到一个最小的 size 不为 1 的强连通分量即可 ③ BFS/DFS 在暴力的基础上多加一个标记即可 ④ 并查集 据说这也能做 【代码】 #include<cstdio> #include<algorithm> #define N 222222 using namespace std; int n,i,tm,tp,now,ans,sz,to[N],dfn[N],low[N],st[N];bool is[N]; void dfs(int x){ dfn[x]=low[x]=++tm;st[++tp]=x;is[x]=1; int y=to[x]; if(!dfn[y])dfs(y),low[x]=min(low[x],low[y]);

else if(is[y])low[x]=min(low[x],dfn[y]); if(low[x]==dfn[x]){ for(sz=now=0;now!=x;)now=st[tp--],sz++; if(sz>1)ans=min(ans,sz); } } int main(){ for(ans=1e9,scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&to[i]); for(i=1;i<=n;i++)if(!dfn[i])dfs(i); printf("%d",ans); } 【时间复杂度】 O(n) 【空间复杂度】 O(n) 【思想难度】 25 【编程难度】 25 【总用时】15 min

T3 斗地主
【题目大意】 给你一副斗地主手牌,问你最快几次出完,数据随机,牌数不超过 23。 【解题说明】 30 分做法:N≤4,没有顺子,直接贪心即可。 60~70 分做法: ① 写一个非常暴力的暴力。 ② 写一个非常暴力的状压 DP。 90 分做法:状压 DP 再小小地优化一下,由于每种牌在读入数据出来后上限已经固定了,最 差情况下是每种牌平均分布,状态表示需要 3^9*2^5=629856,转移再加一些优化,理论上 能过,但 CCF 的机子太慢了会被卡 10 分 100 分做法: ① 还是暴力,单牌和对牌最后处理就可以了,剩下的各种情况讨论,随机数据轻松跑出。 ② 暴力+贪心,暴力枚顺子,剩下的牌肯定是可以贪心的,随便搞一搞就可以了 【代码】 #include<cstdio> #include<algorithm> #include<cstring> #define mxh 1000000007 using namespace std; int ans,T,n,i,x,y,pai[6],cnt[15]; void find(int step){ int i,j,k,w; if(step>=ans)return; ans=min(ans,step+pai[1]+pai[2]+pai[3]+pai[4]); if(pai[4])for(i=2;i<=14;i++)if(cnt[i]==4){ pai[4]--;cnt[i]-=4; if(!pai[3]&&!pai[4]&&!pai[1]&&pai[2]<=1){ ans=min(ans,step+1); pai[4]++;cnt[i]+=4; return;

} for(j=1;j<=14;j++)if(cnt[j]){ pai[cnt[j]]--;cnt[j]--;pai[cnt[j]]++; for(k=j;k<=14;k++)if(cnt[k]){ pai[cnt[k]]--;cnt[k]--;pai[cnt[k]]++; find(step+1); pai[cnt[k]]--;cnt[k]++;pai[cnt[k]]++; } pai[cnt[j]]--;cnt[j]++;pai[cnt[j]]++; } if(pai[2]||pai[3]||pai[4])for(j=2;j<=14;j++)if(cnt[j]>1){ pai[cnt[j]]--;cnt[j]-=2;pai[cnt[j]]++; for(k=j;k<=14;k++)if(cnt[k]>1){ pai[cnt[k]]--;cnt[k]-=2;pai[cnt[k]]++; find(step+1); pai[cnt[k]]--;cnt[k]+=2;pai[cnt[k]]++; } pai[cnt[j]]--;cnt[j]+=2;pai[cnt[j]]++; } pai[4]++;cnt[i]+=4; } if(pai[3])for(i=2;i<=14;i++)if(cnt[i]>=3){ pai[cnt[i]]--;cnt[i]-=3;pai[cnt[i]]++; find(step+1); for(j=1;j<=14;j++)if(cnt[j]){ pai[cnt[j]]--;cnt[j]--;pai[cnt[j]]++; find(step+1); pai[cnt[j]]--;cnt[j]++;pai[cnt[j]]++; } if(pai[2]||pai[3]||pai[4])for(j=2;j<=14;j++)if(cnt[j]>1){ pai[cnt[j]]--;cnt[j]-=2;pai[cnt[j]]++; find(step+1); pai[cnt[j]]--;cnt[j]+=2;pai[cnt[j]]++; } pai[cnt[i]]--;cnt[i]+=3;pai[cnt[i]]++; } if(pai[3]+pai[4]>=2)for(i=3;i<14;i++)if(cnt[i]>=3&&cnt[i+1]>=3){ pai[cnt[i]]--;cnt[i]-=3;pai[cnt[i]]++;w=i; for(j=i+1;cnt[j]>=3&&j<=14;j++){ pai[cnt[j]]--;cnt[j]-=3;pai[cnt[j]]++; find(step+1);w=j; } for(j=i;j<=w;j++){ pai[cnt[j]]--;cnt[j]+=3;pai[cnt[j]]++;

} } if(pai[2]+pai[3]+pai[4]>=3)for(i=3;i<13;i++)if(cnt[i]>=2&&cnt[i+1]>=2&&cnt[i+2]>=2){ pai[cnt[i]]--;cnt[i]-=2;pai[cnt[i]]++; pai[cnt[i+1]]--;cnt[i+1]-=2;pai[cnt[i+1]]++;w=i+1; for(j=i+2;cnt[j]>=2&&j<=14;j++){ pai[cnt[j]]--;cnt[j]-=2;pai[cnt[j]]++; find(step+1);w=j; } for(j=i;j<=w;j++){ pai[cnt[j]]--;cnt[j]+=2;pai[cnt[j]]++; } } if(pai[1]+pai[2]+pai[3]+pai[4]>=5)for(i=3;i<11;i++)if(cnt[i]&&cnt[i+1]&&cnt[i+2]&&cnt[i +3]&&cnt[i+4]){ pai[cnt[i]]--;cnt[i]--;pai[cnt[i]]++; pai[cnt[i+1]]--;cnt[i+1]--;pai[cnt[i+1]]++; pai[cnt[i+2]]--;cnt[i+2]--;pai[cnt[i+2]]++; pai[cnt[i+3]]--;cnt[i+3]--;pai[cnt[i+3]]++;w=i+3; for(j=i+4;cnt[j]&&j<=14;j++){ pai[cnt[j]]--;cnt[j]--;pai[cnt[j]]++; find(step+1);w=j; } for(j=i;j<=w;j++){ pai[cnt[j]]--;cnt[j]++;pai[cnt[j]]++; } } } int main(){ for(scanf("%d%d",&T,&n);T--;){ ans=12; memset(cnt,0,sizeof(cnt)); memset(pai,0,sizeof(pai)); for(i=1;i<=n;i++){ scanf("%d%d",&x,&y); if(x==1)x=14; if(x==0)x=1; cnt[x]++; } for(i=1;i<=14;i++)pai[cnt[i]]++; find(0); printf("%d\n",ans); } }

【时间复杂度】 O(?) 【空间复杂度】 O(?) 【思想难度】 27 【编程难度】 51 【总用时】45 min

T4 跳石头
【题目大意】给你一排 N 块石头,你可以移走 M 块石头,使得最小的两块石头之间的距离 尽可能长,N,M≤50000。 【解题说明】 20 分做法:直接暴力即可 50 分做法:考虑 DP,f[i][j]表示在前 i 块石头移走 j 块石头的最短距离,转移即可 60 分做法:考虑贪心,每次删除间距最小的,用堆维护 100 分做法:考虑二分答案后贪心,先二分这个距离使其变为判断可行性问题,然后从前往 后扫,一旦这个石头到上一个选的石头的距离小于这个二分的答案就把这块石头移走 这样显然是正确的,很容易证明先移一定比后移好,所以这个算法是正确的 【代码】 #include<cstdio> int L,n,m,i,w,l,r,mid,pos,ans,a[55555]; bool ok(int x){ for(pos=w=0,i=1;i<=n;i++)if(a[i]-pos<x)w++;else pos=a[i]; return w<=m; } int main(){ for(scanf("%d%d%d",&L,&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]);a[++n]=L; for(l=1,r=L;l<=r;)if(ok(mid=l+r>>1))ans=mid,l=mid+1;else r=mid-1; printf("%d",ans); } 【时间复杂度】 O(nlgL) 【空间复杂度】 O(n) 【思想难度】 30 【编程难度】 23 【总用时】10 min

T5 子串
【题目大意】有两个字符串 A 和 B。现在要从字符串 A 中取出 k 个互不重叠的非空子串, 然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一个新的字符串,问 有多少种方案可以使得这个新串与字符串 B 相等?A 的长度≤1000,B 的长度≤200,k≤ 200。 【解题说明】 特殊的 10 分做法:k=1,所以直接扫一遍判断就可以了 特殊的 20 分做法:k=2,所以枚举分隔点再扫一遍判断就可以了 特殊的 20 分做法:k=m,所以从前往后扫一遍 DP 统计一下方案就可以了 70 分做法:考虑 dp,用 f[i][j][k]表示 A 串匹配到第 i 个字符,B 串匹配到第 j 个字符,已经 取了 k 个互不重叠的非空子串的方案数,那么 f[i][j][k]=Σ f[i-w-o][j-w][k-1](w=1-A[i]和 B[j] 的最大后缀匹配,i-w-o>=0),f[0][0][0]=1,这样直接转移的复杂度是 O(nm^3k)的,把 o 这 一维前缀和转移一下,就是 O(nm^2k)的,可以通过 70 分的数据。 90 分做法:再把 w 也前缀和转移掉,就可以通过 90 分的数据。 100 分做法:加一个滚动数组,然后再卡一卡常,就可以通过 100 分的数据。 【代码】 (90)

#include<cstdio> #define mxh 1000000007 int i,j,w,n,m,k,h,ans,pre[1111][222],f[2][1111][222];char a[1111],b[1111]; int main(){ scanf("%d%d%d%s%s",&n,&m,&k,a+1,b+1); for(i=1;i<=n;i++) for(j=1;j<=m;j++){ for(w=j;w&&i-(j-w)&&a[i-(j-w)]==b[w];w--); pre[i][j]=j-w; } f[1][0][0]=1; for(j=0;j<=n;j++)for(w=0;w<=m;w++)f[1][j][w]=(f[1][j][w]+(j?f[1][j-1][w]:0))%mxh; for(j=0;j<=n;j++)for(w=0;w<=m;w++)f[1][j][w]=(f[1][j][w]+((j&&w)?f[1][j-1][w-1]:0))%m xh; for(i=1;i<=k;h^=1,i++){ for(j=0;j<=n;j++)for(w=0;w<=m;w++) f[h][j][w]=(((j&&w)?f[h^1][j-1][w-1]:0)-(((j-pre[j][w])&&(w-pre[j][w]))?f[h^1][j-pre[j][w]1][w-pre[j][w]-1]:0)+mxh)%mxh; if(i!=k){ for(j=1;j<=n;j++)for(w=1;w<=m;w++) f[h][j][w]=(f[h][j][w]+f[h][j-1][w])%mxh; for(j=1;j<=n;j++)for(w=1;w<=m;w++) f[h][j][w]=(f[h][j][w]+f[h][j-1][w-1])%mxh; } } for(i=1;i<=n;i++)ans=(ans+f[h^1][i][m])%mxh; printf("%d",ans); } 【时间复杂度】 O(nmk) 【空间复杂度】 O(nm) 【思想难度】 39 【编程难度】 30 【总用时】45 min

T6 运输计划
【题目大意】 给你一颗带权树和若干条航线,你可以使一条边的权值变为 0,然后使得最 长航线最短,N≤300000。 【解题说明】 ①20 分做法:m=1,直接找到这条路然后删掉这条路上的最长边就可以了 ②50~60 分做法:枚举删除哪条边,然后用倍增的方法暴力求出每条航线的代价就可以了, 复杂度 O(nlgn+nmlgn) ③ 特殊的 40 分做法:为一条链,可以线段树随便维护一下,结合算法②可以获得 80 分。 ④ 45~60 分做法:考虑把初始航线长度从小到大排序,二分这个答案,然后用数据结构判 断一下可行性就可以了,简单的方法是树链剖分,这样的时间复杂度是 O(mlg^3n)的, 理论上可以通过 95 分的数据,但由于 CCF 的评测机很慢,只能通过 45~60 分的数据。 ⑤ 95 分做法:把航线从大到小排序,我们要求的就是当前航线的交中的最大值,这个可以

用树链剖分维护然后分类讨论一下是选择新的交的最大值好还是旧的交的最大值和新 航线的长度好,如果新航线单独算一条更好,那么就退出并得到了答案,时间复杂度 O(nlgn+mlg^2n)。 ⑥ 95 分做法:同样把航线从大到小排序,仍然要求交,可以用 LCA 大力分类讨论一下得 到航线的交,这样时间复杂度是 O(nlgn+mlgn)的,但由于常数比较大,还是不能通过全 部的数据。 ⑦ 100 分做法:据说可以用直接线段树维护,由于线段树很快,就可以艹过全部数据啦。 【代码】 (95) #include<cstdio> #include<algorithm> #include<cstring> #define N 300300 using namespace std; int n,m,i,j,x,y,z,tp,pt,ww,tot,sum,ans,bl[N],sz[N],h[N],pos[N],to[N],fa[N][19],g[N][19],fir[N],va[N<< 1],ne[N<<1],la[N<<1],val[N<<2];bool lz[N<<2]; struct P{int x,y,z;}p[N];struct Q{int l,r;}q[N];char ch; void read(int &x){ for(ch=getchar();ch<'0'||ch>'9';ch=getchar()); for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0'; } bool cmp(P a,P b){return a.z>b.z;}bool cmp2(Q a,Q b){return a.l<b.l;} void ins(int x,int y,int z){la[++tot]=y;ne[tot]=fir[x];va[tot]=z;fir[x]=tot;} void dfs(int x){ sz[x]=1; for(int i=1;i<=18;i++)fa[x][i]=fa[fa[x][i-1]][i-1],g[x][i]=g[x][i-1]+g[fa[x][i-1]][i-1]; for(int i=fir[x];i;i=ne[i])if(fa[x][0]!=la[i]){ fa[la[i]][0]=x;g[la[i]][0]=va[i];h[la[i]]=h[x]+1; dfs(la[i]); sz[x]+=sz[la[i]]; } } void dfs2(int x,int f){ pos[x]=++tp;to[tp]=x;bl[x]=f; int i,now=0; for(i=fir[x];i;i=ne[i])if(fa[x][0]!=la[i]&&sz[la[i]]>sz[now])now=la[i]; if(!now)return; dfs2(now,f); for(i=fir[x];i;i=ne[i])if(fa[x][0]!=la[i]&&now!=la[i])dfs2(la[i],la[i]); } int lca(int x,int y){ sum=0; if(h[x]<h[y])swap(x,y);int i,t=h[x]-h[y]; for(i=0;i<=18;i++)if(t&(1<<i))sum+=g[x][i],x=fa[x][i];

for(i=18;i>=0;i--)if(fa[x][i]!=fa[y][i])sum+=g[x][i]+g[y][i],x=fa[x][i],y=fa[y][i]; if(x==y)return sum;else{ sum+=g[x][0]+g[y][0]; return sum; } } void bt(int k,int l,int r){ if(l==r){val[k]=g[to[l]][0];return;} int mid=l+r>>1; bt(k<<1,l,mid);bt(k<<1|1,mid+1,r); val[k]=max(val[k<<1],val[k<<1|1]); } void add(int k,int l,int r,int x,int y){ if(x>y||x==0)return; if(x<=l&&r<=y){ val[k]=0;lz[k]=1; return; } if(lz[k]){val[k<<1]=val[k<<1|1]=0;lz[k<<1]=lz[k<<1|1]=1;} int mid=l+r>>1; if(x<=mid)add(k<<1,l,mid,x,y); if(y>mid)add(k<<1|1,mid+1,r,x,y); val[k]=max(val[k<<1],val[k<<1|1]); } int main(){ for(read(n),read(m),i=1;i<n;i++)read(x),read(y),read(z),ins(x,y,z),ins(y,x,z); dfs(1);dfs2(1,1); for(i=1;i<=m;i++)read(p[i].x),read(p[i].y),p[i].z=lca(p[i].x,p[i].y); bt(1,1,n);sort(p+1,p+m+1,cmp); for(i=1;i<=m;i++)if(p[i].z>ans){ ww=val[1];pt=0;x=p[i].x;y=p[i].y; for(;bl[x]!=bl[y];x=fa[bl[x]][0]){ if(h[bl[x]]<h[bl[y]])swap(x,y); q[++pt].l=pos[bl[x]];q[pt].r=pos[x]; } if(pos[x]>pos[y])swap(x,y); if(pos[x]!=pos[y])q[++pt].l=pos[x]+1,q[pt].r=pos[y]; sort(q+1,q+pt+1,cmp2); for(j=1;j<=pt;j++)add(1,1,n,q[j-1].r+1,q[j].l-1); add(1,1,n,q[pt].r+1,n); if(max(p[1].z-ww,p[i].z)<=p[1].z-val[1]){ ans=max(ans,max(p[1].z-ww,p[i].z)); break; }else ans=max(ans,p[1].z-val[1]);

} printf("%d",ans); }【时间复杂度】 O(nlgn+mlgn) 【空间复杂度】 O(n) 【思想难度】 35 【编程难度】 52 【总用时】75 min ——By lbn187


NOIP2015提高组解题报告

NOIP2015提高组解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组的解题报告,有详细的算法和代码 NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意】 告诉你...

NOIP2015提高组day1第二题解题报告

NOIP2015提高组day1第二题解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组day1第二题的解题报告因为太简单所以写出来(误作者:蒟蒻zrw ...

NOIP2015提高组一等奖

NOIP2015提高组一等奖_计算机软件及应用_IT/计算机_专业资料。NOIP2015提高组复赛一等奖名单 CCF NOIP2015 复赛提高组一等奖获奖名单证书编号 CCF-NOIP2015-0001 CCF-...

noip2015普及组解题报告

noip2015普及组解题报告_学科竞赛_初中教育_教育专区。noip2015普及组解题报告 NOIP2015 普及组(Junior) 解题报告 1. 金币 (coin.cpp/c/pas) 国王将金币作为工资...

NOIP2015普及组解题报告

NOIP2015普及组解题报告_学科竞赛_初中教育_教育专区。NOIP2015解题报告,by贴吧id u007zzt 的某蒟蒻 NOIP2015 普及组解题报告 From 贴吧 id u007zzt 金币 国王将...

NOIP2015普及组复赛试题解题报告word版第一二题满分程序

全国信息学奥林匹克联赛(NOIP2015)复赛 普及组 NOIP2015 普及组复赛试题解题报告 word 版 第一二题满分程序 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 普及组一...

NOIP2015提高组Pascal试题及参考答案

NOIP2015提高组Pascal试题及参考答案_其它考试_资格考试/认证_教育专区。第二十...2015 年 10 月 11 日 14:30~16:30 选手注意: 试题纸共有 9 页,答题纸...

noip 2012 提高组 解题报告

noip 2012 提高组 解题报告_学科竞赛_高中教育_教育专区。noip 2012 提高组 ...©2015 Baidu 使用百度前必读 | 文库协议 | 网站地图 关闭 ...

NOIP2015普及组复赛解题报告

NOIP2015普及组复赛解题报告_学科竞赛_初中教育_教育专区。NOIP2015普及组复赛解题报告 NOIP2015 普及组解题报告南京师范大学附属中学树人学校 CT 1. 金币(coin.cpp/...